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

Question

我想在C++中解决以下问题:

我有6个元素:A1,A2,A3,B1,B2,B3.我想将一个B恰好与一个A匹配,这样产生的匹配的总和就是最小的.

这是我如何考虑编写一个简单的贪婪算法(可能不是最优的,但对我来说似乎足够好):

1. 测量所有AB对之间的距离,将其保存在2D浮点数组中.
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个元素的性能,但是当元素的数量要大得多时,我真的对这个问题的真正解决方案感兴趣.

Answer 1

这称为最大成本二分匹配,最常用的算法是Bellman-Ford算法(您可以将距离转换为负值以使算法直接适用)

您还可以使用匈牙利算法(实际上是赋值问题),将A顶点定义为工作线程,将B顶点定义为任务,并将距离放在成本矩阵中.

编辑:

对于简单的方法(如3元素的情况),您可以考虑完整搜索.这是因为我们可以将您的nxn距离矩阵视为一个板,我们需要选择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.