在二维数组中，是否存在一种算法可以找到非交叉值的最小和？

Question

我正在寻找一种快速算法来确定给定的二维数组的特定最小属性 - 没有共同行或列的最小值之和。我相信这一定有一个名称，但我不知道它叫什么。

我有一个字符串匹配系统，它会将输入字符串按空格拆分并与搜索值语料库（也按空格拆分）进行比较，并返回每个字符串中标记之间的距离矩阵，我想通过采用不重复使用任何输入/输出标记组合的最小距离组合来将其减少为单个聚合距离。

举例：

{ 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。

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

- Dylan Beattie

---

匈牙利算法是一种解决指派问题的优化算法，它可以找到最小化或最大化指定代价函数的二分图中完美匹配的策略。该算法的时间复杂度为O(n^3)，其中n是一个集合中元素的数量。该算法被广泛应用于各种领域，例如作业分配、物流路线规划和DNA测序等。 - Evgeny Kluev

非常准确。你想把它发布为答案，这样你就可以获得甜蜜的声望分数了吗？ - Dylan Beattie

非常好。好的，我会将其移动到答案中。 - Alptigin Jalayr

Answer 1

是的，有一种标准算法可以完美地解决这个问题。它的名字叫做匈牙利算法。

- Evgeny Kluev