c++ - 如何创建一个算法来找到所有可能的配对（参考中国邮递员问题）？

Question

在尝试解决中国邮递员问题时，您将必须找到图中所有奇数顶点的所有可能配对的最小成本并添加找到的边（配对），我的问题几乎就是这样。

如何实现一个返回所有可能配对的算法？ 或如何修复我的。

我有一个起点，但无法走得更远或想得更远。

我尝试查看以下主题，但不幸的是它们并没有帮助我。我应该如何为中国邮递员问题生成分区/对？或找到使权重总和最小化的配对？

std::vector<std::vector<int>> Postman::pairOdd(std::vector<int> vertices)
{   
    std::vector<std::vector<int>> pairs;
    if (vertices.empty()) {
        return std::vector<std::vector<int>>();
    }
    else {
        auto it = std::min_element(vertices.begin(), vertices.end());
        int i = *it;
        vertices.erase(it);
        for (int index = 0; index < vertices.size(); index++) {
            int j = vertices[index];
            vertices.erase(vertices.begin() + index);
            pairs.push_back(std::vector<int>{i, j});
            std::vector<std::vector<int>> returnValue = pairOdd(vertices);
            pairs.insert(pairs.end(), returnValue.begin(), returnValue.end());
            vertices.insert(vertices.begin(), j);
        }
        vertices.insert(vertices.begin(), i);
    }
    return pairs;
}

输出与

std::vector<std::vector<int>> res = pairOdd(std::vector<int>{1,2,3,4,5,6});
for (auto v : res) {
    for (auto u : v) {
        std::cout << u;
    }
    std::cout << std::endl;
}

应该：

1 2  3 4  5 6
1 2  3 5  4 6
1 2  3 6  4 5
1 3  2 4  5 6
1 3  2 5  4 6
1 3  2 6  4 5
1 4  2 3  5 6
1 4  2 5  3 6
1 4  2 6  3 5
1 5  2 3  4 6
1 5  2 4  3 6
1 5  2 6  3 4
1 6  2 3  4 5
1 6  2 4  3 5
1 6  2 5  3 4

但是：

我无法完全解决插入向量的方式。查看输出时，您可以看到它几乎是正确的（忽略格式）。第一行12 34 45是正确的。其次35 46，当它必须时12 35 36，似乎只有第一对丢失了，你会注意到它适用于每个配对。

更新：所以我想出了另一种似乎很有希望的算法，但是我没有丢失一些配对，而是得到了重复。高度赞赏解决方案。如果我自己找到一个，我会发布它。

std::vector<std::vector<int>> Postman::aaa(std::vector<int> vertices, std::vector<int> list, int in1, int in2)
{
    std::vector<std::vector<int>> pairs;
    if (vertices.empty()) {
        list.push_back(in1);
        list.push_back(in2);
        pairs.push_back(list);
        return pairs;
    }
    else {
        auto it = std::min_element(vertices.begin(), vertices.end());
        int i = *it;
        vertices.erase(it);
        for (int index = 0; index < vertices.size(); index++) {
            int j = vertices[index];
            vertices.erase(vertices.begin() + index);

            if (in1 != 0 && in2 != 0) {
                list.push_back(in1);
                list.push_back(in2);
            }

            std::vector<std::vector<int>> returnValue = aaa(vertices, list, i, j);
            pairs.insert(pairs.end(), returnValue.begin(), returnValue.end());

            vertices.insert(vertices.begin(), j);
        }
        vertices.insert(vertices.begin(), i);
    }
    return pairs;
}

输出：

score 0 · Accepted Answer

所以我找到了我提到的第二种算法的解决方案。问题是我将这对发送到下一个递归步骤，然后在此步骤中添加。因此，当您从递归步骤返回时，配对仍然存在。所以我只是删除了这对，所以可以添加新的。我不只是返回一个 int 向量，而是创建了一个对向量。更好地可视化返回值。我愿意听取对此算法的任何改进或任何好的做法。

我愿意听取对此算法的任何改进或任何好的做法。

std::vector<std::vector<std::pair<int, int>>> Postman::pairing(std::vector<int> vertices, std::vector<std::pair<int, int>> list)
{
    std::vector<std::vector<std::pair<int, int>>> pairs;
    if (vertices.empty()) {
        pairs.push_back(list);
        return pairs;
    }
    else {
        auto it = std::min_element(vertices.begin(), vertices.end());
        int i = *it;
        vertices.erase(it);
        for (int index = 0; index < vertices.size(); index++) {
            int j = vertices[index];
            vertices.erase(vertices.begin() + index);

            std::pair<int, int> pair(i, j);
            list.push_back(pair);

            std::vector<std::vector<std::pair<int, int>>> r = pairing(vertices, list);

            list.erase(list.end() - 1);

            pairs.insert(pairs.end(), r.begin(), r.end());

            vertices.insert(vertices.begin(), j);
        }
    }
    return pairs;
}

std::vector<std::vector<std::pair<int, int>>> a = pairing(vertices, std::vector<std::pair<int, int>>());
for (auto v : a) {
    for (auto p : v) {
        std::cout << '(' << p.first << ' ' << p.second << ')';
    }
    std::cout << std::endl;
}

c++ - 如何创建一个算法来找到所有可能的配对（参考中国邮递员问题）？

1 回答 1

Related

Reference