旅行セールスマンに関連する

Question

私は関連するグラフを持っています。各エッジにはコストがかかります。私は各ノードを訪問するパスを見つける必要があり（一度も可能ではない）、コストは最低です。パスは同じノードで開始し、終了する必要があります。この問題は説明されていますか？これは旅行セールスマンの問題ではなく、ノードは複数回訪問することができます。

Answer 1

あなたの質問に基づいて、私はあなたが記述されている次のような状況のかわからないです：すべてのノード一定回数、及びその数は1より大きくてもよい

1. セールスマン必見訪問（ノードごとに異なる場合もあります）。
2. セールスマンは、各ノードを複数回訪問します（ただし、必ずしもそうする必要はありません）。ネットワークは完全なネットワークです（各ノードのペアの間にエッジがあります）。
3. セールスマンが各ノードを複数回訪問し、ネットワークが完全ではありません。

場合この場合は1

、各ノードの複製コピーを作成する - ノードはすべて同じであり、その後、あなたはそれの3つのコピーを持っているよ、3回を訪問しなければならない場合場所。おそらく、訪問の間にノードを離れる必要があります（3回連続して訪問することはできません）。その場合、ノードのコピーと別のコピーの間の距離は無限でなければなりません。

ケース2

ただ、問題に通常の方法を解決します。ノードを複数回訪問することは決して最適ではありません（距離がすべて非負であると仮定して）。この場合、3

ケースは私はあなたが一度すべてのノードを訪問しなければならないと仮定して、あなただけの別のノードから、あなたのように「通過」している場合、あなたはそれを追加回を訪問することができます。ここでのアプローチは、ノードの各ペア間の最短パス距離を計算し、それを標準TSPの距離行列として使用することです。標準のTSPでは、ノードを複数回訪問していることを「認識」していませんが、最適なソリューションと対応する最短パスから何回ノードにアクセスしたかを知ることができます。