都市を旅行する旅行者を含む旅行者

Question

伝統的に旅行セールスマンの問題は、その起源から都市から都市への距離に作用します。これは、都市間の旅行費用と比較して都市内の旅行費用を無視することができれば、完璧に機能します。だから問題は、都市を通る旅費を無視できないときに、最短ルートを見つけることができるかどうかです。

問題をより簡単に説明する最も簡単な方法は、貪欲なアルゴリズムを取ることです。例えば、AからBに行き、次に2つのオプションを持つ、1つはCに5コスト、もう1つはDに6コスト。最初はCが安いオプションのように見えるが、Bに行くためには都市を旅行するのは3コストがかかり、Dに行くためにはDを使うだけで済むので、最終的にDを取る方が安い選択肢になるだろう。

各都市間の移動コストを含む地図を作成する前に、例を見てもわかるように、都市を旅行することは実際の移動コストに大きな影響を与えます。

どのようにこのような問題に取り組んでいますか？

EDIT：出発点（都市を通行していない）で優先エッジを選択できます。 セールスマンが都市に入ると目的地に到達します（都市を経由しない）。都市を旅行する は両方向で同じコストです。

Answer 1

私の考えは、すべての都市ノードCをサイズn = |隣人（C）|のクリークで置き換えることです。 Cのすべての隣接ノードをクリーク内のノードに接続します。

クリーク内部のエッジは、Cを介して「トランジット」を表し、対応するトランジットコストが関連付けられています。次に、各クリークを訪問する代わりに、各都市クリークの少なくとも1つのノードを訪問するために、旅人の「目標」を変更する必要があります。または訪問したすべての都市クリークノードを訪問したことをマークします。

Answer 2

開始ノードと終了ノードにも都市コストが存在すると仮定すると、そのコストを道路に含めるべき頂点に追加する必要があります。頂点のコストがnでターゲットのコストがmでエージェントが都市を通過しなければならない場合、コストはn + mです。始点ノードと終点ノードが都市内交通コストに含まれている場合は、出発都市のコストに合計旅費を初期化する必要があります。頂点を通過するたびに目標都市のコストを追加することができます。そうでない場合は、コストを0で初期化し、最後のステップでない場合は都市旅行費用を加算します。

エージェントがすべての都市を正確に1回訪れなければならない場合、都市コストはアルゴリズムから無視することができます。これは、計算して最適な頂点道路コストに加算できる定数です。