algorithm - TSP をハミルトン閉路に縮小する

Question

巡回セールスマン問題の (決定版) をハミルトン閉路問題に変換するにはどうすればよいですか (つまり、TSP を HCP に還元して、HCP の解決策がある場合、その解決策を使用して TSP 問題を解決する方法)。

score 5 · Accepted Answer

NP のすべての問題は、多項式時間で任意の NP 完全問題に縮小できます。これが、NP 完全問題を非常に重要なものにしています。

これが削減の連鎖です。

TSP は NP の問題であるため、途方もなく長い多項式時間でハミルトニアンサーキットに還元できます。

score 0 · Accepted Answer

ハミルトニアンサイクル問題は NP 完全であることが証明されています (現在のところ、解けることが知られている最高性能のアルゴリズムは指数関数的な複雑さを持っています)。

また、ハミルトニアンサイクル問題は決定問題 (グラフが与えられた場合、すべての頂点をカバーする重なり合わないエッジを持つループはありますか?) であるのに対し、TSP は探索問題です (すべてのハミルトニアンサイクルの中で、料金）。

だから....あなたが求めている削減が存在するとは思わない（直感的にTSPはより複雑です）。存在する場合、ハミルトン問題がNP完全（指数関数的複雑さは、十分に大きな問題には実用的ではありません)。

TSP を解決したいだけの場合は、既知のアルゴリズムの 1 つを使用するだけです。それらのいくつかは、少数の頂点に対して適度にうまく機能するように設計されています (それで十分かもしれません)。

注: TSP 探索問題とハミルトニアンサイクル決定問題を意味していると仮定していますが、そうではない可能性があります。

score 0 · Accepted Answer

グラフを取得して、すべてのエッジを削除します。任意の頂点 v を取り、追加されたエッジの宛先が tsp 決定問題からの長さ定数 k よりも v から遠くない場合、その頂点から始まる有向エッジを追加し直します。

構築されたグラフにハミルトンサイクルがある場合、元のグラフでは長さ < k のツアーでもあり、TSP の解になります。

逆に、グラフにハミルトニアンサイクルがない場合: 頂点 v から始まる長さ < k のすべてのパスを構築し、TSP の解として、v から始まる長さ < k のパスとハミルトニアンサイクル、元のグラフには TSP の解はありません。

score -1 · Accepted Answer

ハミルトン閉路問題に関するウィキペディアの記事から、ヒントが得られるかもしれません。

「ハミルトン閉路問題も巡回セールスマン問題の特殊なケースであり、2つの都市間の距離を隣接している場合は1に設定し、隣接していない場合は2つに設定し、移動距離の合計がnに等しいことを確認します（その場合、ルートはハミルトン閉路です。ハミルトン閉路がない場合は、最短ルートが長くなります。」

score -1 · Accepted Answer

さて、問題はあなたが正確に何をしたいのかです。通常、TSP はsmallest道を見つけることです。最小の方法を見つけたい場合は、この方法ではできません。ハミルトン問題からすべての解がある場合のみ。
ハミルトン問題は辺の重みを気にしませんが、セールスマンには必要です。

例: A-(10)-B、B-(10)-C、C-(1)-A のグラフ A、B、C

明らかに、A->B->C はハミルトン法ですが、TSP の最適解は A->C->B です。

必ずしも最小ではなく、TSP の任意のソリューションを見つけたい場合は、TSP ノードをハミルトンノードにマッピングし、それを解決し、マッピングに戻るだけで完了です。

score -1 · Accepted Answer

TSP の入力インスタンスは完全なグラフであり、Ham_Cycle の入力インスタンスは無向グラフ G(u,v) です。次に、変換関数はグラフ G を完全なグラフにマップする必要があります。

6 に答える 6