[請益] 匈牙利演算法的其中一步
看板Prob_Solve (計算數學 Problem Solving)作者vvrr (vvrr)時間12年前 (2012/09/17 18:49)推噓2(2推 0噓 10→)留言12則, 4人參與討論串1/1
這幾天在研究匈牙利演算法，但是對其中的一個步驟沒有頭緒……
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
→
09/17 20:50, , 1F
09/17 20:50, 1F
→
09/18 00:50, , 2F
09/18 00:50, 2F
→
09/18 00:50, , 3F
09/18 00:50, 3F
推
09/18 11:10, , 4F
09/18 11:10, 4F
→
09/18 11:11, , 5F
09/18 11:11, 5F
→
09/18 11:12, , 6F
09/18 11:12, 6F
→
09/18 19:39, , 7F
09/18 19:39, 7F
→
09/18 19:40, , 8F
09/18 19:40, 8F
→
09/18 19:42, , 9F
09/18 19:42, 9F
→
09/18 19:42, , 10F
09/18 19:42, 10F
推
09/22 01:15, , 11F
09/22 01:15, 11F
→
09/22 01:16, , 12F
09/22 01:16, 12F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
