二分图最大匹配问题匈牙利算法
icon2 Program Impossible | icon4 2005-09-27 12:50| icon39 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

    研究了几个小时，终于明白了。说穿了，就是你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。

Posted in Program Impossible
Tags: , , ,
Trackback: http://www.matrix67.com/blog/archives/39/trackback
我猜您可能还喜欢：

9 条回复

  • 楼层: 沙发 | 2007-04-15 19:51 | fearlessxjdx 说：

    大家弄个小数据模拟一下就能发现里面的奥秘了~
    真的很牛啊~

  • 楼层: 板凳 | 2007-04-15 19:55 | fearlessxjdx 说：

    不知道可不可以再扩展一个边(斜边)?
    那样是不是就变成N皇后问题了?

    回复：发错地方了？

  • 楼层: 地毯 | 2007-08-15 16:17 | kody_lau 说：

    说的还真是够白的，呵呵。

  • 楼层: 地板 | 2007-10-01 0:44 | 永恒的旋律 说：

    嗷~~~~~~~`
    为了研究这个匈牙利我n节课没好好听了！！
    结果还是没研究明白他工作原理~怒了  我要watch！！

  • 楼层: 地下室 | 2007-12-10 10:57 | dahe_1984 说：

    感谢matrix67,
    现在的教科书能不能写的简单直白点,
    别直接翻译老外的,写出来先自己看看能不能自己看明白,老子看了2天没看明白.

    再次感谢matrix67!!!

  • 楼层: 地基 | 2008-11-04 19:17 | memorygarden 说：

    赞一下，看了一下午没明白的地方，让您一点就明白了。谢谢您

  • 楼层: 地壳 | 2009-08-04 12:34 | Blue Gene 说：

    终于明白了……

  • 楼层: 地幔 | 2009-11-11 23:02 | dfx 说：

    简单的几句话 比别人几百句还清楚
    无比感激

  • 楼层: 地核 | 2010-02-01 13:09 | 小菜鸟 说：

    精简啊。。。现在我也明白了。。。orz

您也随便说几句吧：

您可以在 Gravatar 设置您的头像。