作者cyhe (好好活着最重要)
站内Prob_Solve
标题Re: [问题] 匈牙利演算法
时间Fri Jan 30 04:28:21 2009
※ 引述《DJWS (...)》之铭言：
: Assignment Problem and Hungarian Algorithm
: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
: 我想问的是O(n^4)演算法步骤二
: 为什麽可以这样调整权重?
理由如下
1. 同一个row的所有element, reduce相同的值
如果没有造成负数
不会影响哪个Matching会造成Minimum Cost
2. 同一个column的所有element, reduce相同的值
如果没有造成负数
不会影响哪个Matching会造成Minimum Cost
3. 把1. 2中的reduce改成increase
同样不会造成影响
4. X,Y是bipartite graph
利用cost=0的edge
产生M=maximum matching
然後利用M找出V=vertex cover
5. S = X intersects V
T = Y intersects V
如果一个y belongs to Y-T, then reduce the corresponding column
with a value(if you don't know what the value comes from, please
refer to the algorithm.)
如果一个x belongs to S, then add the corresponding row
with the same value
6. 第5点的column reduce会造成Matrix某些element<0,
但是row increase可以把这些element加回来
让Matrix中所有的element都不为负数
根据理由1~3, 第五点的动作不会影响哪个Matching造成Minimum Cost
7. 第5点的动作, 可以造成X-S以及Y-T之间
多产生至少一个cost=0的edge
让下次的Maximum Matching的个数至少加一
8. 根据理由7, 最後一定可以产生一个Perfect Matching
9. 把最後的Perfect Matching代入原本的Matrix 就可以得到最小的Cost
因为演算法所有的动作都没有影响哪个Matching会造成Minimum Cost
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.59.239.185
※ 编辑: cyhe 来自: 61.59.239.185 (01/30 04:39)
1F：推 DJWS:谢谢你 我理解了 :) 02/08 22:17
※ 编辑: cyhe 来自: 203.73.69.24 (02/14 04:37)