Ku二分图最大权匹配(KM算法)hn

学习二分图 最大权匹配 的 佳作

Kuhn-Munkres 算法 Maigo 的 KM 算法讲解(的确精彩) KM 算法是通过给每个顶点一个标号(叫做顶标)来把求最大权匹配的问题转 化为求完备匹配的问题的。设顶点 Xi 的顶标为 A[i], 顶点 Yi 的顶标为 B[i],顶点 Xi 与 Yj 之间的边权为 w[i,j]。在算法执行过程中 的任一时刻,对于任一条边(i,j), A[i]+B[j]>=w[i,j]始终成立。KM 算法的正确 性基于以下定理: * 若由二分图中所有满足 A[i]+B[j]=w[i,j]的边(i,j)构成的子图 (称做相等子 图)有完备匹配,那么这个完备匹配就是二分图的最大权匹配。 这个定理是显然的。因为对于二分图的任意一个匹配,如果它包含于相 等子图,那么它的边权和等于所有顶点的顶标和;如果它有的边不包含于相 等子图,那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配 一定是二分图的最大权匹配。 初始时为了使 A[i]+B[j]>=w[i,j]恒成立,令 A[i]为所有与顶点 Xi 关联的边 的最大权,B[j]=0。如果当前的相等子图没有完备匹配,就按下面的方法修改 顶标以使扩大相等子图,直到相等子

图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了,是因为对于某个 X 顶点,我们 找不到一条从它出发的交错路。这时我们获得了一棵交错树,它的叶子结点 全部是 X 顶点。现在我们把交错树中 X 顶点的顶标全都减小某个值 d,Y 顶 点的顶标全都增加同一个值 d,那么我们会发现:

Word文档免费下载Word文档免费下载:Ku二分图最大权匹配(KM算法)hn (共14页,当前第1页)

你可能喜欢

  • 最优匹配
  • 最小费用流
  • 匈牙利算法
  • 匹配算法
  • 算法竞赛
  • 分配问题
  • 动态规划
  • ACM课件

Ku二分图最大权匹配(KM算法)hn相关文档

最新文档

返回顶部