5

我想用 C++ 解决以下问题：

我有 6 个元素：A1、A2、A3、B1、B2、B3。我想将一个 B 与一个 A 精确匹配，以使结果匹配的总和最小。

以下是我对编写一个简单的贪心算法的想法（可能不是最优的，但对我来说似乎已经足够好了）：

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

4

1 回答 1

5

这称为最大成本二分匹配，最通用的算法是贝尔曼福特算法（您可以将距离转换为负数以使算法直接适用）

您还可以使用匈牙利算法，这实际上是分配问题，通过将 A 顶点定义为工人，将 B 顶点定义为任务，并将距离放入成本矩阵中。

编辑：

对于简单的方法（例如您的 3 元素案例），您可以考虑完整搜索。这是因为我们可以将您的 nxn 距离矩阵视为一个棋盘，并且我们需要选择 n 个方格，使得每一行和每一列都有一个选定的方格。

浮动成本[n][n];
使用布尔[n]；

浮动解决（整数行）{
    浮动最小值 = 999999；// 这里放一个很大的数
    for(int i=0; i < n; i++){
        如果（！使用[i]）{
            使用[i] = 1;
            如果（我==n-1）{
                返回成本[行][i]；
            } 别的 {
                浮动总计 = 成本[行][i]+求解（行+1）；
                如果（总计<分钟）分钟=总计；
            }
            使用[i] = 0;
        }
    }
    返回最小值；
}

诠释主要（）{
    printf("%.2f\n",solve(0));
}

复杂度是 n^n，所以这只适用于 n <= 8。

于 2013-09-05T15:25:58.103 回答