研究了几个小时,终于明白了。说穿了,就是你从二分图中找出一条路径来,让路径的起点和终点都是还没有匹配过的点,并且路径经过的连线是一条没被匹配、一条已经匹配过,再下一条又没匹配这样交替地出现。找到这样的路径后,显然路径里没被匹配的连线比已经匹配了的连线多一条,于是修改匹配图,把路径里所有匹配过的连线去掉匹配关系,把没有匹配的连线变成匹配的,这样匹配数就比原来多1个。不断执行上述操作,直到找不到这样的路径为止。
研究了几个小时,终于明白了。说穿了,就是你从二分图中找出一条路径来,让路径的起点和终点都是还没有匹配过的点,并且路径经过的连线是一条没被匹配、一条已经匹配过,再下一条又没匹配这样交替地出现。找到这样的路径后,显然路径里没被匹配的连线比已经匹配了的连线多一条,于是修改匹配图,把路径里所有匹配过的连线去掉匹配关系,把没有匹配的连线变成匹配的,这样匹配数就比原来多1个。不断执行上述操作,直到找不到这样的路径为止。
大家弄个小数据模拟一下就能发现里面的奥秘了~
真的很牛啊~
不知道可不可以再扩展一个边(斜边)?
那样是不是就变成N皇后问题了?
回复:发错地方了?
说的还真是够白的,呵呵。
嗷~~~~~~~`
为了研究这个匈牙利我n节课没好好听了!!
结果还是没研究明白他工作原理~怒了 我要watch!!
感谢matrix67,
现在的教科书能不能写的简单直白点,
别直接翻译老外的,写出来先自己看看能不能自己看明白,老子看了2天没看明白.
再次感谢matrix67!!!
赞一下,看了一下午没明白的地方,让您一点就明白了。谢谢您
终于明白了……
简单的几句话 比别人几百句还清楚
无比感激
精简啊。。。现在我也明白了。。。orz
很受用,谢谢!
强大的楼主!ORZ!!
强大的楼主!ORZ
恍然大悟,膜拜神牛
经典,膜拜
一下午PPT比不过这段话
哈哈
找了一个多小时的PPT……没有一个比得上这段话……
Orz神牛,看组合数学半天没懂,这下果然懂了…够精炼的…
精炼
非常感谢,也是看了半天,看了你的讲解很受益
跑一遍最大流好了
怎么证明贪心地找增广路是正确的呢?e.g. 在某种匹配的状态下找不到增广路了,为什么不存在另一种匹配,使得匹配的点更多?
http://liam0205.me/2016/04/03/Hungarian-algorithm-in-the-maximum-matching-problem-of-bigraph/
最后一段。
天龙sf架设|奇迹Musf架设|魔兽sf架设|魔域sf架设|墨香sf架设天堂2sf架设|传奇3sf架设|英雄王座sf架设|千年sf架设|征途sf架设新魔 http://www.64uv.com 界sf架设|骑士sf架设|烈焰sf架设|破天sf架设|决战sf架设美丽世界sf架设|乱勇OLsf架设|倚天2sf架设|完美世界sf架设|征服sf架设天堂sf架设 http://www.64uv.com |传世sf架设|真封神sf架设|劲舞团sf架设|天上碑sf架设永恒之塔sf架设|仙境ROsf架设|诛仙sf架设|神泣sf架设|石器sf架设冒险岛sf架设|惊天动地sf架设|热血江湖sf架设|问道sf架设|密传sf架设火线任务(Heat Project)sf架设|飞飞OLsf架设|洛汗s http://www.64uv.com f
天龙sf程序|奇迹Musf程序|魔兽sf程序|魔域sf程序|墨香sf程序天堂2sf程序|传奇3sf程序|英雄王座sf程序|千年sf程序|征途sf程序新 http://www.47ec.com47ec.com 魔界sf程序|骑士sf程序|烈焰sf程序|破天sf程序|决战sf程序美丽世界sf程序|乱勇 http://www.47ec.com OLsf程序|倚天2sf程序|完美世界sf程序|征服sf程序天堂sf程序|传世sf程序|真封神sf程序|劲舞团sf程序|天上碑sf程序永恒之塔sf程序|仙境ROsf程序|诛仙sf程序|神泣sf程序|石器sf程序冒险岛sf程序|惊天动地sf程序|热血江湖sf程序|问道sf程序|密传sf程序火线任务(Heat Project)sf程序|飞飞OLsf程序|洛汗s http://www.47ec.com f
今年省选你帮大忙了
蟹蟹