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

Question

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

5

我希望在C ++中解决以下问题：

我有6个元素：A1，A2，A3，B1，B2，B3。我想要将一个B与一个A精确匹配，使得所得到的匹配总和最小。

这里是我想编写简单贪心算法的方法（可能不是最优的，但对我来说足够好）:

1.测量所有A-B对之间的距离，并将其保存在浮点数的二维数组中。 2.按照单个值对2D数组进行排序，类似于下面的排序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个元素方面谈论性能没有意义，但当元素数量更大时，我真的很想知道这个问题的真正解决方案。

- hyperknot

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- justhalf · Accepted Answer

这被称为最大费用二分匹配，最常用的算法是Bellman-Ford Algorithm（您可以将距离转换为负数，使算法直接适用）。

您还可以使用Hungarian Algorithm，它实际上是分配问题，通过将A顶点定义为工人，B顶点定义为任务，并在成本矩阵中放置距离来解决。

编辑：

对于简单的方法（如您的3元素情况），可以考虑完全搜索。这是因为我们可以将您的n x n距离矩阵视为一个棋盘，并且我们需要选择n个方块，以便每行和每列恰好有一个选定的方块。

float cost[n][n];
bool[n] used;
float solve(int row){
    float min = 999999; // 在这里放一个非常大的数字
    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。