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