作者vvrr (vvrr)
站內Prob_Solve
標題[請益] 匈牙利演算法的其中一步
時間Mon Sep 17 18:49:18 2012
這幾天在研究匈牙利演算法，但是對其中的一個步驟沒有頭緒……
http://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation
其中的 Step 3:
Initially assign as many tasks as possible.
意思是「找最多的 0 使得每一行每一列最多只有一個 0」
又在 Step 3 的最後一段（Step 4的前面）：
is just one way to draw the minimum number of lines to cover all the 0's
意思是「找最少的直線能通過所有的零」
關於第一點，我有試著找過八皇后問題，看看有沒有「限定皇后出現格子」
的那種特別題目；第二點則是不太清楚關鍵字該怎麼下……
這兩個問題會這樣一句話帶過，應該是有什麼很有名的解法或是很有名的問題，
因此想請問比較有研究的版友們能否提示幾個關鍵字，謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.250.31.103
1F：→ stimim:二分圖 最大匹配 最小點覆蓋 09/17 20:50
2F：→ vvrr:呣，我知道匈牙利算法是要解上面的題目。但是是其中一個步驟 09/18 00:50
3F：→ vvrr:想問看看有沒有「不是用眼睛看」的方法 09/18 00:50
4F：推 DJWS:他是把原本的演算法過程 以矩陣形式呈現 09/18 11:10
5F：→ DJWS:所以你得看原本的演算法是怎麼處理的 09/18 11:11
6F：→ DJWS:位於上一段The algorithm in terms of bipartite graphs 09/18 11:12
7F：→ stimim:匈牙利整個要解的是有權重的匹配(最大化或最小化) 09/18 19:39
8F：→ stimim:你問的那一個步驟則是要解最大匹配，並找到一個最小點覆蓋 09/18 19:40
9F：→ stimim:二分圖的點就是原題目的點，但是只有在w_ij=0的時候i,j相連 09/18 19:42
10F：→ stimim:w_ij 是矩陣中 ij 那一格的值 09/18 19:42
11F：推 ariainaqua:OR裡面Hungarian是指派問題中的基礎解法，其原理是利用 09/22 01:15
12F：→ ariainaqua:原題與偶題的關係做變換，進一步求出最佳解~ 09/22 01:16