algorithm - 给定二维矩阵，找到元素的最小总和，使得从每一行和每一列中选择一个元素？

Question

找到 n*n 2D 矩阵的元素的最小总和，这样我必须从每一行和每一列中选择一个且只有一个元素？例如

4  12 

6  6

如果我4从行中选择，1我也不能从 列中选择12行，我只能从第 2 行第 2 列中选择 6。11

所以同样的最小总和将4 + 6 = 10是6第二行第二列的位置

而不是第二行第一列的6 + 12 = 18位置6

也4 + 12不允许，因为两者都来自同一行

我想到了蛮力，一旦我从行和列中选择元素，我就无法选择另一个，但这种方法是O(n!) .

Answer 1

定理：如果一个数字被添加到矩阵的任何一行或列的所有条目中或从其中减去一个数字，则为获得所需的最小矩阵和而选择的元素与为获得所需的原始矩阵的最小和而选择的元素相同矩阵。

匈牙利算法（最小成本流问题的一个特例）使用这个定理来选择那些满足问题中给定约束的元素：

1. 从该行的所有条目中减去每行中最小的条目。
2. 从每列的所有条目中减去每列中最小的条目。
3. 通过适当的行和列画线，以便覆盖成本矩阵的所有零条目，并使用最少数量的此类线。
4. 测试最优性
   i。如果覆盖线的最小数量是 n，则可以进行最佳的零分配，我们就完成了。
   ii. 如果覆盖线的最小数量小于 n，则零的最佳分配是不可能的。在这种情况下，请继续执行步骤 5。
5. 确定未被任何行覆盖的最小条目。从每个未覆盖的行中减去此条目，然后将其添加到每个覆盖的列。返回步骤 3。

请参阅此示例以更好地理解。

这里详细解释了O(n ⁴ )（易于实现）和 O(n ³ )（难以实现）的实现。