泽民博客 ☰ Menu

KM（Kuhn and Munkres）算法

Posted by 夏泽民 Jul 10, 2018

如果二分图的每条边都有一个权（可以是负数），要求一种完备匹配方案，使得所有匹配边的权和最大，记做最佳完美匹配。（特殊的，当所有边的权为1时，就是最大完备匹配问题） 我们使用KM算法解决该问题。

阅读全文

Hungarian_algorithm 匈牙利算法

Posted by 夏泽民 Jul 10, 2018

二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 和 ，使得每一条边都分别连接 中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。 最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。 完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替 增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。 增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。 我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（这是增广路定理）。匈牙利算法正是这么做的。在给出匈牙利算法 DFS 和 BFS 版本的代码之前，先讲一下匈牙利树。 匈牙利树一般由 BFS 构造（类似于 BFS 树）。从一个未匹配点出发运行 BFS（唯一的限制是，必须走交替路），直到不能再扩展为止。 // 由于时间紧凑，代码摘自http://dsqiu.iteye.com/blog/1689505 #define maxn 10//表示x集合和y集合中顶点的最大个数！
int nx,ny;//x集合和y集合中顶点的个数
int edge[maxn][maxn];//edge[i][j]为1表示ij可以匹配
int cx[maxn],cy[maxn];//用来记录x集合中匹配的y元素是哪个！
int visited[maxn];//用来记录该顶点是否被访问过！
int path(int u) {
int v;
for(v=0;v<ny;v++)
{
if(edge[u][v]&&!visited[v])
{
visited[v]=1;
if(cy[v]==-1||path(cy[v]))//如果y集合中的v元素没有匹配或者是v已经匹配，但是从cy[v]中能够找到一条增广路
{
cx[u]=v; //找到增广路，修改匹配M
cy[v]=u;
return 1;
}
}
}
return 0;
}
int maxmatch()
{
int res=0;
memset(cx,0xff,sizeof(cx));//初始值为-1表示两个集合中都没有匹配的元素！
memset(cy,0xff,sizeof(cy));
for(int i=0;i<=nx;i++)
{
if(cx[i]==-1) //还没被匹配，执行内部代码
{
memset(visited,0,sizeof(visitited)); //重置标记为为访问
res+=path(i); //以 i 为起点开始查找增广路，返回true ，匹配数+1
}
}
return res;
}

阅读全文

Edmond-Karp 算法 网络流 增广路

Posted by 夏泽民 Jul 10, 2018

基本的网络流模型，最基础的最大流求法，即bfs找增广路法，也就是EK法，全名是Edmond-Karp，其实我倒是觉得记一下算法的全名和来历可以不时的拿出来装一装。

阅读全文

git

Posted by 夏泽民 Jul 6, 2018

$ git clone git@git.xxxx.git Cloning into ‘intelligent-ranking’… fatal: cannot run ssh: No such file or directory fatal: unable to fork 查看用户主目录，确实没有对应的 .ssh 目录。 解决方案1:openssh 进行安装 解决方案2:没有装ssh命令，所以git地址得用http方式不能用git开头的。 $ git clone https://git.xxxxx git中ssh与https究竟有何不同 1.clone项目:使用ssh方式时，首先你必须是该项目的管理者或拥有者，并且需要配置个人的ssh key。而对于使用https方式来讲，就没有这些要求。 2.push:在使用ssh方式时，是不需要验证用户名和密码，如果你在配置ssh key时设置了密码，则需要验证密码。而对于使用https方式来讲，每次push都需要验证用户名和密码。

阅读全文

composer dump-atoload namespace dir

Posted by 夏泽民 Jul 6, 2018

参考：https://docs.phpcomposer.com/04-schema.html

阅读全文

Search

Blog Categories

jekyll (35)
web (334)
technology (2)
php (201)
linux (415)
spark (51)
deep_learning (2)
storage (290)
golang (1081)
cryptology (15)
lang (74)
docker (100)
zookeeper (11)
elasticsearch (86)
java (7)
algorithm (134)
hadoop (2)
slug (1)
architect (46)
k8s (107)
node (82)
python (18)
mysql (42)
rust (4)
elasticSearch (1)
arch (1)
Javascript (1)
kafka (2)
nginx (7)

Popular posts

Anything in here will be replaced on browsers that support the canvas element

Recent posts

Tags

This blog is maintained by 夏泽民

Get in touch with me at 465474307@qq.com

Subscribe to our mailing list

* indicates required