中国の郵便配達員のバリエーション_

Question

今私の春期試験の準備を整えるために、私は勉強してグラフの問題を実験しています。

"Traveling Salesman"のような典型的な問題には既に慣れていますが、私が中国の郵便配達員の問題とそのバリエーションを詳しく見てみると、すぐに問題の重要な部分が失われているように感じました。そのため、特定の番号nの文字が正常に（新しいものを得るために）配送された後に、オフィスに戻る必要がある。それで最短経路を見つけるのはどうですか？

私はその関連性と実際の生活のための容易な適用性のために私はCPPに非常に興味を持っていましたが、この側面を追加することにより、さらに実際の生活が適用可能になると思います。

すべてのエッジを少なくとも1回は（CPP）出発点（ポストステーション）に戻る必要があるの制約を特定の無向グラフで最短パスを見つける方法についての任意のヘルプに感謝します手紙の数が納品されます。

---

EDIT（originial CPPの説明）。 「中国の郵便配達の問題またはルート検査の問題が（接続）無向グラフのすべてのエッジを訪問最短閉じた経路又は回路を見つけることであるグラフを有します オイラー回路（すべてのエッジを一度カバーするクローズドウォーク）で、その回路が最適解です。 グラフがオイラーでない場合は、奇数次の頂点が含まれている必要があります。これらの頂点の問題を解決するために、最小のT-joinを見つけるために、T-joinを2倍にしてEulerianグラフを作成する。元のグラフのPostman問題の解は、グラフ。 Src：wikipedia.org

Answer 1

あなたの亜種は、すべての値が厳密にB/4とB/2の間である3-partition problemなどからのNP-hardです。それはcapacitated vehicle routingと同じ方法のいくつかを使って "解決"されるかもしれません。しかし、CPPは、Tジョインを研究する言い訳よりも実際の問題ではないことを理解する必要があります。