開始点に戻る方法を考慮したTSPw/ oの問題名と、これを解決するためのアルゴリズムを知りたいです。
最短経路問題を調べましたが、それは私が探しているものではありません。問題は、割り当てられた2つのポイントから最短経路を見つけるだけです。しかし、私が探しているのは、nポイントを与え、1つの開始点のみを入力するという問題です。次に、すべてのポイントを1回だけ移動する最短経路を見つけます。（終点は任意の点にすることができます。）
ハミルトン閉路問題も調べましたが、定義された問題を解決するのではなく、ハミルトン閉路があるかどうかを調べました。
私はこの本で私の質問に対する答えを見つけました。コンピュータや他のデジタルシステムの設計で繰り返し発生するコンピュータ配線の問題についても同じです。目的は、ワイヤの全長を最小限に抑えることです。したがって、それは確かに最小長のハミルトン経路です。
この本が示唆しているのは、他のすべての点までの距離が0であるダミー点を作成することです。したがって、問題は（n + 1）都市対称TSPになります。解いた後、ダミーポイントを削除するだけで、最小長のハミルトンパスが解かれ、開始点に戻らずにTSPパスを取得できます。
私が正しく理解していれば、（いくつかの頂点から始まる）最短経路を見つけて、同じノードに2回アクセスすることなく、グラフ内のすべてのノードを通過する必要があります。より単純な問題は、ハミルトン閉路問題です。あなたが言ったように、それはそのような道が存在するかどうかを尋ねます。その問題はNP困難であり、問題よりも簡単なので、問題の解決は少なくともNP困難です。あなたの問題は決定問題ではないので、それは真実ではありません。しかし、それが言っていることは、あなたの問題に多項式アルゴリズムがないことをほぼ確信できるということです。
近似に頼ることができます。ここにメトリックTSPのかなりクールな近似があります：http：//en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP。