Существует ли алгоритм для нахождения минимальной суммы непересекающихся значений в двумерном массиве?

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

Да, существует стандартный алгоритм, который решает именно эту проблему. Его имя Hungarian algorithm.