以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- 二分图匹配算法总结 (by phoenixinter, Aug 2006) (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=40964) |
-- 作者:Logician -- 发布时间:12/7/2006 7:35:00 PM -- 二分图匹配算法总结 (by phoenixinter, Aug 2006) 最近下决心要把二分图匹配部分的算法都搞搞清楚,努力了几天之后基本上搞定了,下面做一个这个专题的总结。 一、二分图最大匹配 二分图最大匹配的经典匈牙利算法是由Edmonds在1965年提出的,算法的核心就是根据一个初始匹配不停的找增广路,直到没有增广路为止。 二、Hopcroft-Karp算法 SRbGa很早就介绍过这个算法,它可以做到O(sqrt(n)*e)的时间复杂度,并且在实际使用中效果不错而且算法本身并不复杂。 三、二分图最优匹配 二分图最优匹配的经典算法是由Kuhn和Munkres独立提出的KM算法,值得一提的是最初的KM算法是在1955年和1957年提出的,因此当时的KM算法是以矩阵为基础的,随着匈牙利算法被Edmonds提出之后,现有的KM算法利用匈牙利树可以得到更漂亮的实现。 四、二分图的相关性质 本部分内容主要来自于SRbGa的黑书,因为比较简单,仅作提示性叙述。 五、稳定婚姻问题 稳定婚姻问题是一个很有意思的匹配问题,有n位男士和n位女士,每一个人都对每个异性有一个喜好度的排序,代表对他的喜爱程度,现在希望给每个男士找一个女士作配偶,使得每人恰好有一个异性配偶。如果男士u和女士v不是配偶但喜欢对方的程度都大于喜欢各自当前配偶的程度,则称他们为一个不稳定对。稳定婚姻问题就是希望找出一个不包含不稳定对的方案。 |
-- 作者:phoenixinter -- 发布时间:12/7/2006 8:50:00 PM -- 我上次胡扯什么算法学习……然后就被转载…… 这次正经的写了一篇技术帖。。就没人看-_- |
-- 作者:Logician -- 发布时间:12/8/2006 2:21:00 PM -- 哈哈。 技术帖看着费劲,很多人就懒得看了嘛…… :)
|
-- 作者:entrails -- 发布时间:9/7/2007 6:23:00 PM --
红线处说原属于(S,T)的边不会退出相等子图,这很好理解, 但是一些原相等子图的边是有可能退出相等子图的, 这不会影响算法的正确性? 谁能简单说下为什么
|
-- 作者:lovezqian -- 发布时间:9/11/2007 3:48:00 PM -- 实际上相等子图中的边是不会退出相等子图的: 两端都在交错树中的边(i,j),A[i]+B[j]的值没有变化。也就是说,它原来属于相等子图,现在仍属于相等子图。 两端都不在交错树中的边(i,j),A[i]和B[j]都没有变化。也就是说,它原来属于(或不属于)相等子图,现在仍属于(或不属于)相等子图。 X端不在交错树中,Y端在交错树中的边(i,j),它的A[i]+B[j]的值有所增大。它原来不属于相等子图,现在仍不属于相等子图。 X端在交错树中,Y端不在交错树中的边(i,j),它的A[i]+B[j]的值有所减小。也就说,它原来不属于相等子图,现在可能进入了相等子图,因而使相等子图得到了扩大。 |
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
62.500ms |