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

Question

当试图解决中文 postman 问题时，您将必须找到图中所有奇数顶点的所有可能配对的最小成本，并添加找到的边（配对），我的问题几乎是关于.

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

我有一个起点，但无法继续或进一步思考。

我尝试查看以下主题，但不幸的是它们对我没有帮助。 How should I generate the partitions / pairs for the Chinese Postman problem? or Find the pairings such that the sum of the weights is minimized?

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 时，似乎只缺少第一对，您会注意到它适用于所有配对。

更新：所以我想出了另一种看起来很有前途的算法，但我没有遗漏一些对，而是得到了重复的。高度赞赏解决方案。如果我自己找到一个，我会 post 它。

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;
}

输出：

Answer 1

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

我愿意倾听对这个算法的任何改进或任何好的实践。

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;
}

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

How to create an algorithm to find all possible pairings (referring to the chinese postman problem)?

c++

chinese-postman