選擇元素對之間的最短距離

Question

我想用C++解決以下問題：

我有6個元素：A1，A2，A3，B1，B2，B3。我希望完全匹配一個B到一個A，以這樣的方式，所得匹配的總和最小。

這裏是我想過寫一個簡單的貪心算法（可能不是最優的，但似乎不錯，足以讓我）：

1. 測量所有AB對之間的距離，將其保存在一個二維數組彩車。
2. 將二維數組排序爲單個值，如下面的排序lambda：
3. 設置該A的最佳匹配，禁用搜索所選B和A（禁用2D中的一列和一行）。
4. 從仍然可用的數組中選擇最小的數字。
5. 等等，直到所有匹配成功。

這裏有兩個有趣的問題：

1. 你能告訴我怎麼叫這個問題，並指出我給它一些適當的解決方案，在它們存在的情況下？

2. 你能告訴我你將如何在C++中實現上述貪婪算法？到目前爲止，我想過使用此功能進行排序

下面是代碼：

float centerDistances[3][3]; // .. random distances 

vector<int> idx(9); 

for (size_t i = 0; i != idx.size(); ++i) idx[i] = i; 
sort(idx.begin(), idx.end(), [](int i1, int i2) 
{ 
    return centerDistances[0][i1] < centerDistances[0][i2]; 
}); 

我想我會保持一個vector<bool> selectedA, selectedB;跟蹤選定的元素，但我不知道它會如何。

注意：好的，關於3,3個元素的性能沒有意義，但是當元素數量大得多時，我真的很關心這個問題的真正解決方案。

Answer 1

這就是所謂的最高單偶匹配，併爲它的最普遍的算法是Bellman-Ford Algorithm（您可以在距離轉換爲負，使算法直接適用）

您還可以使用Hungarian Algorithm，這實際上是分配通過將A頂點定義爲工人，將B個頂點定義爲任務，並將距離放在成本矩陣中來解決問題。

編輯：

對於簡單的方法（如您3元的情況下），你可以考慮完整的搜索。這是因爲我們可以將n×n距離矩陣看作一個棋盤，我們需要選擇n個正方形，這樣每行和每列只有一個選定的正方形。

 
float cost[n][n]; 
bool[n] used; 

float solve(int row){ 
    float min = 999999; // Put a very large number here 
    for(int i=0; i < n; i++){ 
     if(!used[i]){ 
      used[i] = 1; 
      if(i==n-1){ 
       return cost[row][i]; 
      } else { 
       float total = cost[row][i]+solve(row+1); 
       if(total<min) min=total; 
      } 
      used[i] = 0; 
     } 
    } 
    return min; 
} 

int main(){ 
    printf("%.2f\n",solve(0)); 
} 

的複雜性爲n n次方，所以這只是對於n < = 8