algorithm - 巡回セールスマン問題の始点と終点を修正するには?

Question

通常の対称 TSP 問題を解決するソルバーがあります。解は、どのノードがパスの最初と最後のノードであるかに制限されない、すべてのノードを経由する最短パスを意味します。

特定のノードを開始ノードとして、別のノードを終了ノードとして保証できるように問題を変換する方法はありますか?

1 つの方法は、I (非常に大きな距離) をこれらの開始/終了ノードと他のすべての間のすべての距離に追加することです (開始ノードと終了ノードの間の距離に I を 2 回追加します)。 1回（したがって、それらをパスの開始および終了として作成します）。

このアプローチの大きな欠点はありますか、またはこれを行うためのより良い方法はありますか?

Answer 1

重み 0 のエッジで開始ノードと終了ノードに接続するダミー ノードを追加できます。TSP にはダミー ノードが含まれている必要があるため、最終結果には開始 - ダミー ノード - 終了のシーケンスが含まれている必要があります (到達する他の方法はありません)。ダミーノード)。したがって、開始ノードと終了ノードを指定して、最短のハミルトン パスを取得できます。このソリューションは、グラフのエッジが負の場合でも機能するはずです。