作者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)