複数都市を訪れるTSPのバリエーション

Question

複数の訪問を伴う TSP の分岐限定ソリューションについて議論しようとしています (つまり、すべての都市を 1 回だけではなく、少なくとも 1 回訪問する必要があります)。

編集：

Jitse が指摘したように関連性がなかったため、疑問を削除しました。さて、質問はより明確になりました。

Answer 1

ノード A と B のペアごとに、A から B への最短パスを表すエッジを追加するだけで、グラフを拡張できます。の フロイド・ウォーシャルアルゴリズム これを O(n^3) で実行でき、どの TSP アルゴリズムよりもはるかに高速です。これを完了したら、標準の TSP ブランチおよびバインド手法を使用します。 このサイト からの情報があります アップルゲイトの本, 、TSP の分岐と境界について説明します。 ウィキペディアの TSP エントリ.

Answer 2

私は彼の提案を実装作るのは簡単だろう可能監督に対処していますので、

私はむしろ、マーティン・ホックの答えにコメントとしてこれを提出すると思います。

分岐限定アルゴリズムがワーシャル - フロイド法の出力を所定の最小コスト経路を再構成するためのアルゴリズムと組み合わせることが必要です。分枝限定アルゴリズムは外側のループであり、それは未訪問のノードを選択します。次に、あなたが実際にあなたのサイクルにエッジとノードを追加するために最小コストパスの再構成アルゴリズムを使用します。分枝限定パーツによってだけではなく、最小コストパスの再構成アルゴリズムによって訪問としてノードがマークする必要があります。