algorithm - 矩阵中的最大值

Question

所以这是 C# 中一个有趣的问题。我正在寻找一种更好的解决方法:

Given a matrix M (not necesarily square) of matches, find the best matching elements. Element i matches elem j by value M(i,j). M(i,j) != M(j,i).

Since #rows != #columns, find the best min(#rows,#columns) matching pairs (i,j).

基本上，问题是从每一行/列中选取最大值，这样就不会对任何行/列选取两次。

例子:

     1  2  3 
  +---------
a | 10  3  1
b | 12  99 2
c | 20  5  3
d |  5  7  4

此矩阵中的最大值为 99，因此最佳匹配为 (b,2)。对于下一个选择，我们不能再使用行 b 和列 2。就像切割它们一样

     1  2  3  or, if you prefer,       1   3
  +---------  a smaller matrix:      +------
a | 10 ||  1                       a | 10  1
b | ===++===                       c | 20  3
c | 20 ||  3                       d | 5   4
d |  5 ||  4             

最大值现在是 20，匹配是 (c, 1)。剩下的矩阵只有一列。 在另一次选择之后，我们将得到 match = 4 的 match (d, 3)

最后“a”没有匹配。

我当前的实现使用 2 数组来存储已经匹配的行/列，并且对于每个匹配遍历整个矩阵，选择属于不匹配的行/列的第一个最大值。

PS: value 多个匹配值相同的情况下，只选择其中一个 PS2:数组存储为int [,]

您将如何以更优化/更美观的方式解决这个问题？

Answer 1

如果您试图最大化所选单元格的总和，以便从每一行和每一列中恰好选择一个单元格，那么这是 http://en.wikipedia.org/wiki/Assignment_problem .如果您的矩阵不是正方形，您可以通过向它们添加行或列使其成为正方形，新单元格中的值意味着它们不会被选中，除非没有其他方法来填写解决方案。

(如果你没有最大化总和，你需要说出你正在最大化所选值的哪个函数 - (1,3) 比 (2,2) 好吗？否则你会进入 http://en.wikipedia.org/wiki/Multi-objective_optimization ，哪个是可能的，但更复杂)。