出発点に戻ることを考慮せずにトラベリングセールスマン問題（TSP）の問題名は何ですか？

Question

私は、開始点に戻る方法とこれを解決するアルゴリズムを考慮して、TSPなしの問題名を知りたいと思います。

私は、最短経路問題に見えたが、それは私が探していますものではありません、問題は2つの割り当てられたポイントからの最短経路を見つけます。しかし、私が探しているのは、私たちがnポイントを与え、開始点を1つだけ入力するという問題です。次に、すべてのポイントを正確に1回移動する最短経路を見つけます。 （エンドポイントは、任意の点となります。）私もハミルトン経路問題に見えたが、私の定義された問題を解決するのではなくハミルトン経路があるかどうかを見つけることではないようだ

。

私にお勧めします、ありがとう！私が正しく理解していれば

Answer 1

私はthis bookに私の質問への答えを見つけました。これは、コンピュータやその他のデジタルシステムの設計において繰り返し発生するコンピュータ配線の問題と同じです。その目的は、ワイヤの全長を最小にすることです。したがって、それは確かに最小長のハミルトニアンパスです。本は示唆何

は、その距離が他のすべての点に0であるため、問題は、（N + 1）-City対称TSPなるダミーポイントを作成することです。解決したら、ダミーポイントを削除してから最小長のハミルトニアンパスを解くと、開始ポイントを返さずにTSPパスを得ることができます。

Answer 2

は、あなたが（いくつかの頂点sから開始）と二度同じノードを訪問することなく、グラフ内のすべてのノードを経由する最短経路を見つけたいです。より単純な問題は、ハミルトニアン経路の問題です。あなたが言ったように、天候にはそのような道が存在するかどうか尋ねられます。その問題はNP困難であり、あなたの問題より簡単です。問題を解決するには少なくともNP困難です。あなたの問題はの決定の問題ではないので、そうではありません。しかし、それはあなたの問題のための多項式アルゴリズムがないことをほとんど確かめることができるということです。

あなたは近似値に頼ることができます。メトリックTSPの近似値は、http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSPです。