PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 匈牙利演算法

看板Prob_Solve (計算數學 Problem Solving)作者cyhe (好好活著最重要)時間16年前 (2009/01/30 04:28)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《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)