c++ - 如何在矩阵中添加数字以产生最小结果？

Question

这更像是一个算法/数学问题，但我希望在 C++ 中实现一个解决方案。

假设我有一个像这样的矩阵，其中的点代表整数：

   W  X  Y  Z
A  .  .  .  . 
B  .  .  .  .
C  .  .  .  .
D  .  .  .  .

如果我必须从每一列中选择一个数字以使每一行最多有一个数字，我将如何产生最小结果？

例如，我可以选择AW BX CY DZ or AZ BX CY DW but NOTAW BW CZ DZ

蛮力方法似乎需要 n！计算。有更快的方法吗？最终我想在大小约为 60 的矩阵中添加数字。

此外，所有数字的范围从 0 到 256。

Answer 1

如果您不想自己编写代码，您总是可以使用其他人的辛勤工作和善良的出版物。Haskell 中的这个，在我的旧笔记本电脑上用不到十分之二秒的时间解决了一个 60x60 的随机矩阵。多么棒的算法！

import Data.Algorithm.Munkres
import Data.Array.Unboxed
import Data.List (transpose)

solve n matrix = 
  hungarianMethodInt (listArray ((1,1),(n,n)) $ concat $ transpose matrix)