1

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

给定一个匹配矩阵 M（不一定是正方形），找到最佳匹配元素。元素 i 通过值 M(i,j) 匹配元素 j。M(i,j) != M(j,i)。

由于#rows != #columns，找到最佳的 min(#rows,#columns) 匹配对 (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 的匹配 (d, 3)

最后“a”没有匹配。

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

PS：如果值多个匹配具有相同的值，只需选择其中一个 PS2：数组存储为int [,]

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

4

2 回答 2

3

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

（如果你没有最大化总和，你需要说明你选择的值的哪个函数最大化 - （1,3）比（2,2）好？否则你进入http://en.wikipedia。 org/wiki/Multi-objective_optimization，这是可能的，但更复杂）。

于 2012-06-15T04:15:15.167 回答
1

您可以首先按降序对矩阵的所有条目进行排序，然后处理排序后的列表。每当您看到不在已选择的行/列中的条目时，这意味着应该选择该条目，因此您标记相应的行/列并继续沿着列表向下继续，直到所有行或所有列都被选择.

于 2012-06-15T04:14:32.017 回答