是否存在一种算法来查找2D数组中非交叉值的最小和？

Question

我正在寻找一种快速算法来确定给定2D阵列的特定最小属性 - 没有共同行或列的最小值之和.我敢肯定这必须有一个名字,但我不知道它叫什么.

我有一个字符串匹配系统,它将在空格上分割输入字符串并将其与搜索值的语料库(也在空格中分割)进行比较,并返回每个字符串中的标记之间的距离矩阵,我想减少通过采用不重复使用任何输入/输出令牌组合的最小距离组合,可以达到单个聚合距离.

例子:

{ 1, 2 }   => 5 (either 1+4, or 3+2)
{ 3, 4 }

{ 0, 2 }   => 6 (because 2+4 < 0+8)
{ 4, 8 } 

{ 1, 0, 0 }
{ 0, 1, 0 } => 0
{ 0, 0, 1 }

{ 2, 3, 4 }
{ 3, 2, 4 } => 6 (2+2+2)
{ 4, 3, 2 } 

我一直使用的天真算法看起来像这样(C#):

public static int Minimux(this int[,] array) {
  var xUsed = new bool[array.GetLength(0)];
  var yUsed = new bool[array.GetLength(1)];
  var xMax = array.GetLength(0);
  var yMax = array.GetLength(1);
  var minima = new List<int>();
  var limit = Math.Min(xMax, yMax);
  int xMin = 0, yMin = 0;
  while (minima.Count < limit) {
    var vMin = Int32.MaxValue;
    for (var x = 0; x < xMax; x++) {
      for (var y = 0; y < yMax; y++) {
        if (xUsed[x] || yUsed[y] || array[x, y] >= vMin) continue;
        vMin = array[x, y];
        xMin = x;
        yMin = y;
      }
    }
    xUsed[xMin] = true;
    yUsed[yMin] = true;
    minima.Add(vMin);
  }
  return (minima.Sum());
}

它基本上执行数组扫描,并且当它找到每个最小值时,它将行/列组合标记为"已使用",因此不会再次考虑 - 并且一旦列表中有最少的最小值,就会有最短的元素数组维度,它返回那些最小值的总和.

问题是它打破了这样的情况:

{ 0, 0, 0 }
{ 0, 0, 0 } => 3 (when it should be returning 1)
{ 1, 2, 3 } 

当扫描到达最后一行时,它已经将第0列和第1列标记为"已使用",因此第2行中的最小未使用值是3它应该实际使用的时间1

是否存在执行此操作的标准算法？

Answer 1

是的,存在一种标准算法可以解决这个问题.它的名字是匈牙利算法.