算法是否存在以找到二維數組中非相交值的最小總和？

我正在尋找一種快速算法來確定給定二維數組的特定最小屬性 - 最小值沒有共同行或列的總和。我確信這必須有一個名字，但我不知道它叫什麼。算法是否存在以找到二維數組中非相交值的最小總和？

我有一個字符串匹配系統，將空格上的輸入字符串拆分並將其與搜索值語料庫（也分隔空格）進行比較，並返回每個字符串內的記號之間的距離矩陣，以及我想通過採用不重複使用任何輸入/輸出標記組合的距離的最小組合來將其減少到單個聚合距離。

實例：

{ 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

是否存在執行此操作的標準算法？

來源

2013-03-12 Dylan Beattie

[匈牙利算法]（http://en.wikipedia.org/wiki/Hungarian_algorithm）。 – 2013-03-12 14:38:00

Spot-on。想要發佈這個答案，那麼你可以獲得甜美的聲譽點？ – 2013-03-12 14:43:20

美麗。是的，請將其移至答案。 – 2013-03-12 14:45:48

是的，存在一個標準的算法來解決這個問題。它的名字是Hungarian algorithm。

來源

2013-03-12 14:48:05

算法是否存在以找到二維數組中非相交值的最小總和？

回答

相關問題