it技术匈牙利算法和km算法简介(编辑修改稿)内容摘要：
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的一个最佳匹配。 证明很容易。 KM算法 对于任意的 G和 M，可行顶标都是存在的： l(x) = maxw(x,y) l(y) = 0 欲求完全二分图的最佳匹配，只要用匈牙利算法求其相等子图的完备匹配；问题是当标号之后的 Gl无完备匹配时怎么办。 1957年（居然比匈牙利算法早。 ）， Kuhn和 Munkras给出了一个解决该问题的有效算法，用逐次修改可行顶标 l(v)的办法使对应的相等子图之最大匹配逐次增广，最后出现完备匹配。 KM算法 修改方法如下： 先将一个未被匹配的顶点 u(u in {x})做一次增广路，记下哪些结点被访问那些结点没有被访问。 求出d=min{lx[i]+ly[j]w[i,j]}其中 i结点被访问， j结点没有被访问。 然后调整 lx和 ly：对于访问过的 x顶点，将它的可行标减去 d，对于所有访问过的 y顶点，将它的可行标增加 d。 修改后的顶标仍是可行顶标，原来的匹配 M仍然存在，相等子图中至少出现了一条不属于 M的边，所以造成 M的逐渐增广。 KM算法 上述算法的证明也很容易 Kuhn－ Munkras算法流程： (1)初始化可行顶标的值 (2)用匈牙利算法寻找完备匹配 (3)若未找到完备匹配则修改可行顶标的值 (4)重复 (2)(3)直到找到相等子图的完备匹配为止 参考文献 王树禾 《 离散数学引论 》 吴文虎 王建德 《 图论算法与程序设计 》 刘汝佳 黄亮 《 算法艺术与信息学竞赛 》 20xx年冬令营论文－孙方成 《 偶图的算法及应用 》 20xx年冬令营论文－黄源河 《 浅谈图论模型的建立与应用 》 例题 1 Place the Robots（ ZOJ1654） 问题描述 有一个 N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。