文档章节

匈牙利算法,KM算法详解及java实现

husthang
 husthang
发布于 2017/02/17 14:46
字数 1939
阅读 4465
收藏 138

匈牙利算法

基本概念

  • 二分图:二分图又称为二部图.简单来说,如果图中点可以被分为两组,并且使得所有边都跨越组的边界,则这就是一个二分图。准确地说:把一个图的顶点划分为两个不相交集 U 和V ,使得每一条边都分别连接U、V中的顶点。如果存在这样的划分,则此图为一个二分图。二分图的一个等价定义是:不含有"含奇数条边的环"的图。生成子图:子图包含原图的所有顶点
  • 匹配: 通俗的说:匹配(matching)是一个边的集合,其中任意两条边都没有公共顶点.定义:对给定二分图G,在G的子图M中,M的边集{E}中的任意两条边不依赖于同一个顶点,则称M为一个匹配
  • 最大匹配: 图的所有匹配中,含有边数最多的匹配称为最大匹配
  • 完备匹配: 如果图G的某个匹配M,使G的每个顶点都和匹配M中的某条边相关联,则称M为完全匹配(完备匹配); 完备匹配一定是最大匹配.
  • 如图: Fig.1为一个二分图,将其改为Fig.2的形式更为直观;Fig.3 红线部分,为一个匹配; Fig.4 为一个最大匹配,也是一个完备匹配

求图最大匹配的匈牙利算法

  • 求最大匹配最直接暴力的方法是: 找出全部匹配,然后保留边最多的. 这个方法的复杂度为边数目的指数级函数. 匈牙利算法是效率更高的方法.
  • 增广路径: 若P是图G一条连通两个未匹配点的路径,并且属于匹配M的边和不属于M的边(即已匹配边和未匹配边)在P上交替出现,则称P为相对于M的一条增广路径.
  • 如上图,Fig.5红色为匹配,Fig.6为相对于匹配的一条增广路径
  • 由增广路径的定义,可以推出三个结论:
    1. P的路径长度必定为奇数,第一条边和最后一条边都不属于M;
    2. P经过取反操作,可以得到一个更大的匹配M1;
    3. M为G的最大匹配当且仅当不存在相对于M的增广路径.
  • 匈牙利算法: 用增广路径求最大匹配(匈牙利科学家Edmonds于1965年提出); 其框架如下:
    1. 置M为空;
    2. 找出一条增广路径P,通过取反操作,得到更大的匹配M1;
    3. 重复步骤2,直到找不出增广路径为止.
  • 匈牙利算法实现(java)
    • 增广路径有两种寻径方法,一个是深搜(DFS),一个是宽搜(BFS)。如上图,蓝色线为第一次匹配子图,现在从x1寻找增广路径,如果是DFS深搜:首先:x1找到y0,发现y0已经被x0匹配,于是深入到x0,为x0找新的匹配点,发现x0可以匹配y2,让x0与y2匹配,然后让x1与y0匹配,得到第二次匹配子图(红色).现在,从x2出发,搜寻增广路径,x2找到y0匹配,但发现y0已经被x1匹配了,于是就深入到x1,去为x1找新的匹配节点,结果发现x1没有其他的匹配节点,于是匹配失败,x2接着找y1,发现y1可以匹配,于是就找到了新的增广路径,将x2-y1加入匹配中。
    • DFS实现代码见我的代码java实现|GitHub

KM算法

KM算法原理

  • 对于加权完全二分图,找出权和最大的匹配,叫做求最佳匹配; 直接穷举法:效率为n!;用KM算法.
  • 定理: 设M是一个带权完全二分图G的一个完备匹配,给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示,第j个y顶点的可行标用ly[j]表示),如果对所有的边(i,j) in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权),且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j]成立,则M是图G的一个最佳匹配。证明很容易。
  • 对任意的G和M,可行标都是存在的
  • 对二分图G和一组可行标,满足可行标边界条件(lx[i]+ly[j]=w[i,j])的所有边构成的生成子图(需要包含所有顶点),称为其等价子图(相等子图),在这个等价子图上,寻找其完备匹配,如果完备匹配存在,则这个完备匹配M就是图G的最大权匹配,最大权等于所有可行标的和; 如果完备匹配不存在,则修改可行标,用贪心的思想,将最优的边加入等价子图. KM算法就是一种逐次修改可行顶标的方法,使之对应的等价子图逐次增广(增加边),最后出现完备匹配.

KM算法流程及实例

  • Kuhn-Munkras算法流程
    1. 初始化可行顶标的值
    2. 用匈牙利算法在等价子图中寻找完备匹配
    3. 若未找到完备匹配则修改可行顶标的值
    4. 重复(2)(3)直到找到相等子图的完备匹配为止
  • 实例解释算法过程:
    • 带权二分图如下:
    • 从x0找增广路径,找到x0-y4;然后,从x1找不到增广路径,这时,需要修改顶标,加入一条最优的新边到等价子图中:此时搜索过的路径为x1-y4-x0(用匈牙利法DFS),在路径上的X顶点集为S(x0,x1),Y顶点集为T(y4),对所有在S中的点xi及不在T中的点yj,计算d=min{(L(xi)+L(yj)-weight(xiyj))},S中的点的顶标减去d,T中的点的顶标加上d,保持顶标依然为可行顶标.(这个d计算的意义是贪心思想,两种情况:此时让x0与其他点匹配,x1与y4匹配;x0依旧与y4匹配,x1找其他点匹配.d计算的是找到一条新加的边,让x0和x1都搭配后,与x0和x1都同y4搭配的非法搭配这种情况相比,损失的权重值最少).具体来说:此时算出来的最小d=L(X1)+L(Y0)-weight(X1Y0)=2,对顶标进行松弛后,得到的等价子图如上,加了一条边x1-y0,为x1重新找增广路径,找到x1-y0,此时匹配权值和为9+6=15;原来的非法匹配权值和为9+8=17,"损失"的权值最少为2(即加入一条其他的非x1-y0的边如x0-y2,损失的权值为3,比2大,即贪心思想,"损失最小").

    • KM算法原本的时间复杂度为O(n4),n个节点找n次增广路径,在某次找增光路径之中,顶标最多改变n次,修改顶标的松弛量需n2; 可改进为O(n3)时间复杂度:在寻找增广路径时顺便将slack值算出.

代码

  1. 我的代码|java实现

参考

  1. 图基本概念讲解blog
  2. 图论术语|wiki
  3. 带权的二分图的最优匹配KM算法|csdn-blog
  4. KM算法实例讲解blog
  5. 匈牙利算法wiki

© 著作权归作者所有

husthang
粉丝 14
博文 23
码字总数 17164
作品 0
武汉
程序员
私信 提问
加载中

评论(7)

宇林木风

引用来自“宇林木风”的评论

匈牙利算法实现那部分讲得不够形象,能用动图表示就最好了……

引用来自“husthang”的评论

😂 您说的有道理…… 求一个快捷做动图的软件or方法? 感觉做动图好麻烦……
这个,PPT就可以,做好了转gif……😄
husthang
husthang 博主

引用来自“554330833a”的评论

图的匹配算法?
差不多
554330833a
554330833a
图的匹配算法?
husthang
husthang 博主

引用来自“我的上铺叫路遥”的评论

深入浅出讲解算法的文章还是要手动点赞一下的👏
😊谢鼓励
husthang
husthang 博主

引用来自“宇林木风”的评论

匈牙利算法实现那部分讲得不够形象,能用动图表示就最好了……
😂 您说的有道理…… 求一个快捷做动图的软件or方法? 感觉做动图好麻烦……
我的上铺叫路遥
我的上铺叫路遥
深入浅出讲解算法的文章还是要手动点赞一下的👏
宇林木风
匈牙利算法实现那部分讲得不够形象,能用动图表示就最好了……
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
211
0
Java程序员进化为架构师需要掌握的知识

Java程序员进化为架构师掌握的知识: 一:Java知识 1、进制转换 2、Java基本数据类型 面向对象相关知识 3、类、接口、抽象类 this关键字、static关键字、final关键字 方法的参数传递机制 Ja...

andogo
2014/05/16
2.1K
3
收藏的技术博客链接(不断更新)

这里收藏了一些不错的的技术博客和文章的链接,供平时学习和参考,经常看看还是很有收获的。链接列表会不定时更新,列在这里就当是书的目录了。 (1)技术文章系列: 前端技术:http://www....

isam
2014/10/28
281
0
一张图看懂JVM之垃圾回收算法详解

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/t4i2b10X4c22nF6A/article/details/84143047 导读 在之前的内容中,我们通过一张图的方式(图),从总体上对J...

JAVA高级架构v
2018/11/16
0
0
95%的技术面试必考的JVM知识点都在这

jvm的知识点汇总共6个大方向:内存模型、类加载机制、GC垃圾回收是比较重点的内容。性能调优部分偏重实际应用,重点突出实践能力。编译器优化和执行模式部分偏重理论基础,主要掌握知识点。 ...

老道士
03/08
135
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux 运行shell文件,出现 $'\r': command not found

运行编写的shell脚本时,出现了 $'\\r': command not found 这样的错误提示。 报错的原因是我们在windows系统操作时,编辑器里的换行符是\r\n ,而Linux上为\n,两个系统之间有差异导致的。 ...

芥末无敌
今天
7
0
Java数据结构(上)

枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 1.Enumeration(枚举) boolean hasMoreElements( ):测试是否有更多的元素 Object nextElement( ):如果此枚举对象至少还...

Firefly-
昨天
12
0
vue 跨层组件通讯 provide inject

https://cn.vuejs.org/v2/api/#provide-inject 类型: provide:Object | () => Object inject:Array<string> | { [key: string]: string | Symbol | Object } 详细: provide 和 inject 主......

阿豪boy
昨天
8
0
黑马程序员面试宝典(Java)Beta6.0免费下载

场景 JavaSE基础 面向对象特征以及理解 访问权限修饰符区别 理解clone对象 JavaSE语法 java有没有goto语句 &和&&的区别 如何跳出当前的多重嵌套循环? 是否可以继承String? 重载与重写的区别...

badaoliumang
昨天
10
0
监控linux系统状态

查看系统负载: w/uptime 最后面三个数字表示1分钟,5分钟,15分钟平均有多少个进程占用CPU 占用CPU的进程可以是Running,也可以是Waiting 某一时刻1颗CPU只能有一个进程在使用其资源 #查看c...

asnfuy
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部