給定2d矩陣找到元素的最小和，使得元素從每行和每列中選擇一個？

Question

找到n * n二維矩陣的元素的最小和，這樣我必須從每一行和每列中選擇一個且只有一個元素？ 如

4 12 

6 6 

如果讓我選擇從1行4我不能選擇從1也行12從列1， 我只能從行2列選擇6 2.

也照樣最低金額會4 + 6 = 10其中6來自第二行第二列

而不是6 + 12 = 18其中6來自第二行第一列列

也4 + 12是不允許的，因爲兩者都是從同一行

我想動粗，其中有一次，我挑元素從行和列，我不能選擇另一個，但這種做法是O(n!) 。

Answer 1

定理：如果數字加上或減去從基質中的任何一個行或列的條目的所有 ，然後選擇 元件獲得所需要的結果矩陣的最小總和 是相同的元件選擇以獲得原始矩陣的所需最小總和。

的Hungarian Algorithm（min-cost flow問題的一個特例）使用此定理來選擇那些滿足於您的問題給定的約束因素：

1. 從 行的所有條目中減去每行中最小的項。
2. 從列的所有條目 中減去每列中的最小值。
3. 通過適當的行和列繪製線條，以便覆蓋所有成本矩陣的零條目，並且使用這些線條的最小數量 。
4. 優化性測試
   i。如果覆蓋線的最小數量爲n，則可以進行最佳的零點分配，我們就完成了。二，如果覆蓋線的最小數量小於n，則最佳的零點分配不可能。在這種情況下，請繼續步驟5.
5. 確定任何行未涵蓋的最小條目。從每個未被覆蓋的行減去 此條目，然後將其添加到每個覆蓋的 列。回到步驟3

更好地瞭解見this example。

兩者爲O（n 4 ）（容易和快速執行）和O（N 3 ）（更難實現）實現進行了詳細here說明。