問題タブ [chinese-postman]

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

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

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

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

で出力

次のようにする必要があります。

しかし、次のとおりです。

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

更新: そこで、有望と思われる別のアルゴリズムを思いつきましたが、いくつかのペアが欠落する代わりに、重複が発生します。解決策は高く評価されます。自分で見つけたら投稿します。

出力：