TSPアルゴリズムの説明

Question

現在、トラベリングセールスマン問題（TSP）の詳細を知りたいと思っています。 私は、アリのコロニー最適化、lin-kernighan、ペアワイズ交換など、これを解決しようとしているインターネットからいくつかの発見的アルゴリズムを見つけました。

一方、ヘルプ-karpと分岐と結合アルゴリズム。

彼らはTSPを解決していると述べましたが、ポイントAからポイントGまでの最短経路を見つけているように見えます。この場合

、私は、これらのアルゴリズムのいくつかは計算にweightageを使用している、彼らはその上でDijiktraアルゴリズム...

とかなり類似していることを考えています。彼らが使用する通常の重量は何ですか？それは距離ですか？実際にこれらの情報をどのように入手していますか？

私の理解から、TSPはいくつかの指定された場所に移動する必要があり、起点の元の場所に戻る必要がありますか？

ハンガリーアルゴリズムなどのアルゴリズムは、TSPにもっと適切に答えているようですね。

しかし、私はこのアルゴリズムに関する多くの研究論文を見つけることができません。

お知らせください。

Answer 1

TSPは、NPハード（非多項式）の問題で有名です。 問題は解決策がわからないわけではありませんが、すべての解決策はO（N！）の複雑さです。多くのアルゴリズムは明らかに悪い解を減らすために多くのスマートなことを行いますが、最悪の場合（等号付き完全グラフ）はO（N！）で実行されます。

ダイクストラは多項式アルゴリズムです。 TSPを解決することができれば、あなたは世界的な科学賞（1930年代から真実）を手にしています。

参考までに、ウィキペディアのものから始めることができます。