algorithm - 複数の都市を訪問するTSPのバリエーション

Question

複数回の訪問でTSPの分枝限定法について話し合うことを検討しています（つまり、すべての都市を1回だけではなく、少なくとも1回訪問する必要があります）

編集：

Jitseが指摘したように、関連性がなかったため、疑いを取り除きました。これで、質問はより明確になります。

Answer 1

ノードAとBのペアごとに、AからBへの最短経路を表すエッジを追加するだけでグラフを拡張できます。Floyd-Warshallアルゴリズムを使用すると、O（n ^ 3）でこれを実行できます。任意のTSPアルゴリズム。これを行ったら、標準のTSP分枝限定法を使用します。 このサイトには、ウィキペディアのTSPエントリに従って、TSPの分枝限定法について説明しているApplegateの本からの情報がいくつかあります。

Answer 2

マーティン・ホックの提案を実行するのが簡単な可能性のある見落としに対処しているので、マーティン・ホックの答えに対するコメントとしてこれを提出したいと思います。

分枝限定アルゴリズムは、Floyd-Warshallアルゴリズムの出力を前提として、最小コストのパスを再構築するためのアルゴリズムと組み合わせる必要があります。分枝限定アルゴリズムは外側のループであり、未訪問のノードを選択します。次に、最小コストのパス再構築アルゴリズムを使用して、実際にエッジとノードをサイクルに追加します。ノードは、分枝限定法だけでなく、最小コストのパス再構築アルゴリズムによって訪問済みとしてマークする必要があります。