[請益] 匈牙利演算法的其中一步

[vvrr (vvrr)]

這幾天在研究匈牙利演算法，但是對其中的一個步驟沒有頭緒……

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
→ stimim:二分圖 最大匹配 最小點覆蓋
→ vvrr:呣，我知道匈牙利算法是要解上面的題目。但是是其中一個步驟
→ vvrr:想問看看有沒有「不是用眼睛看」的方法
推 DJWS:他是把原本的演算法過程  以矩陣形式呈現
→ DJWS:所以你得看原本的演算法是怎麼處理的
→ DJWS:位於上一段The algorithm in terms of bipartite graphs
→ stimim:匈牙利整個要解的是有權重的匹配(最大化或最小化)
→ stimim:你問的那一個步驟則是要解最大匹配，並找到一個最小點覆蓋
→ stimim:二分圖的點就是原題目的點，但是只有在w_ij=0的時候i,j相連
→ stimim:w_ij 是矩陣中 ij 那一格的值
推 ariainaqua:OR裡面Hungarian是指派問題中的基礎解法，其原理是利用
→ ariainaqua:原題與偶題的關係做變換，進一步求出最佳解~