选择元素对之间的最短距离

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