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

Question

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

4  12 

6  6

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

所以，同样的最低金额是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 ³ )（较难实现）的实现。