0

中国の郵便配達員の問題を解決しようとするとき、グラフ内のすべての奇数頂点のすべての可能なペアリングの最小コストを見つけ、見つかったエッジ (ペアリング) を追加する必要があります。これは私の質問のほとんどです。

すべての可能な組み合わせを返すアルゴリズムを実装する方法は? または私の修正方法。

私は出発点を得ましたが、それ以上進んだり考えたりすることができません。

次のトピックを調べてみましたが、残念ながら役に立ちませんでした。 中国の郵便配達員の問題のパーティション/ペアをどのように生成すればよいですか? または重みの合計が最小になるような組み合わせを見つけますか?

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
56
35
46
36
45
13
24
56
25
46
26
45
14
23
56
25
36
26
35
15
24
36
23
46
26
34
16
25
34
24
35
23
45

ベクトルへの挿入方法を完全に修正できません。出力を見ると、ほぼ正しいことがわかります (書式は無視されます)。最初の行12 34 45は正しいです。2つ目は、最初のペアだけが欠落しているように見えますが、これはすべてのペアリングに適用されます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;
}

出力：

123456
12123546
1212123645
132456
13132546
1313132645
142356
14142536
1414142635
152436
15152346
1515152634
162534
16162435
1616162345
4

1 に答える 1