巡回セールスマン問題
トラベリング・セールスマン問題（TSPと呼ばれることが多い）は、コンピュータ・サイエンスやオペレーション・リサーチの分野における古典的なアルゴリズム問題です。これは最適化に焦点を当てています。この文脈では、より良い解決策とは、より安く、より短く、より速く解決することを意味することが多い。TSPは数学的な問題です。それは、ノードの集合の位置を記述するグラフとして最も簡単に表現されます。
巡回セールスマン問題は、1800年代にアイルランドの数学者W.R.ハミルトンとイギリスの数学者トーマス・カークマンによって定義された。ハミルトンのアイコシアン・ゲームは、ハミルトンのサイクルを見つけることに基づいたレクリエーション・パズルであった。TSPの一般的な形式は、1930年代にウィーンやハーバードの数学者、特にカール・メンガーによって最初に研究されたようです。メンガーは問題を定義し、明白なブルートフォースアルゴリズムを考慮し、最近傍ヒューリスティックの非最適性を観察しました。
我々はメッセンジャー問題をメッセンジャー問題と呼ぶ(実際にはこの問題は各郵便配達人によって解かれるべきであるが，いずれにせよ多くの旅行者によっても解かれるはずである)．もちろん，この問題は無限に多くの試行によって解くことができる．与えられた点の順列の数よりも試行回数を少なくするルールは知られていません．最初に始点から最も近い点に行き、次にこの点に最も近い点に行く、などというルールは一般的に最短ルートにはならない.
プリンストン大学のハスラーホイットニーは、すぐ後に名前の旅行セールスマンの問題を導入しました。
ウィリアム・ローワン・ハミルトン
ある営業マンは、すべての都市、A,B,C,Dを訪問したいと思っていますが、これを行うための最良の方法（最も安い航空券、最小限の移動時間）は何ですか？
ドイツの15大都市を訪問するセールスマンの最適ルート表示されているルートは、43,589,145,600可能なルートの中で最短のルートです。
問題点を述べる
巡回セールスマン問題は，N個の都市間を移動しなければならないセールスマンを描いた問題である．彼が旅の途中でそれぞれの都市を一度ずつ訪れて，最初にいた場所に到着する限り，旅をする順番は気にしない．それぞれの都市は，飛行機や道路，鉄道などで，近くにある他の都市やノードとつながっている．各都市間のリンクには、1つ以上の重み（またはコスト）が設定されています。コストは、グラフ上のこの辺を横断するのがどれだけ「難しい」かを表しており、例えば、飛行機の切符や電車の切符のコスト、あるいは辺の長さや横断を完了するのに必要な時間などで与えられることがある。セールスマンは、移動コストと移動距離の両方を可能な限り低く抑えたいと考えています。
巡回セールスマン問題は、長年にわたり数学者やコンピュータ科学者の興味をそそる「難しい」最適化問題の典型的なものです。最も重要なことは，この問題が科学や工学の分野で応用されていることです．例えば、回路基板の製造では、レーザーが何千個もの穴を開けるのに最適な順番を決めることが重要です。この問題を効率的に解決することで、製造業者の生産コストを削減することができます。
難易度
一般的に、巡回セールスマン問題は解くのが難しい。もしこの問題をより小さな構成要素の問題に分割する方法があるとすれば，構成要素は少なくとも元の問題と同じくらい複雑なものになるだろう．これがコンピュータ科学者がNP難問と呼ぶものです。
多くの人がこの問題を研究してきました。最も簡単な（そして最も高価な）解決策は，単純にすべての可能性を試してみることである．この場合の問題は、N個の都市に対して（N-1）の階乗の可能性があるということです。これは、たった10の都市に対して、18万通り以上の組み合わせがあることを意味します（開始都市が定義されているので、残りの9つの都市にも組み合わせがある可能性があります）。それぞれのルートには、同じ長さやコストのルートが逆にあるので、半分しか数えていません。9!/ 2 = 181 440
- 分岐アルゴリズムと境界アルゴリズムを使用して、問題の正確な解を見つけることができます。これは現在、最大85,900都市で可能です。
- ヒューリスティックなアプローチでは、次のノードを選択するための一連の指針となるルールを使用します。しかし，ヒューリスティックは近似的な結果をもたらすので，常に最適解を与えるわけではありません．しかし，高品質の許容可能なヒューリスティックであれば，問題の完全なブルートフォースに必要な時間の何分の一かの時間で有用な解を見つけることができます．ノードに対するヒューリスティックの例としては、接続されたノードの「近くにある」未訪問ノードの数の合計があります。これにより、セールスマンは、グラフ内の別の自然なクラスタに移動する前に、一緒にクラスタ化された近くにあるノードのグループを訪問するように促すことができます。モンテカルロアルゴリズムとラスベガスアルゴリズムを参照
質問と回答
Q: トラベリングセールスマン問題とは何ですか?
A: 巡回セールスマン問題（TSP）は、コンピュータサイエンスとオペレーションズリサーチの分野における古典的なアルゴリズム問題である。TSPは最適化に重点を置いており、より良い解とは、より安く、より短く、より速い解を意味することが多い。
Q: TSPはどのように表現されるのですか?
A: TSPは、ノードの位置を表すグラフとして最も簡単に表現することができます。
Q: TSPを最初に定義したのは誰ですか?
A: 巡回セールスマン問題は、1800年代にアイルランドの数学者W. R. Hamiltonとイギリスの数学者Thomas Kirkmanによって定義されました。
Q: 1930年代、誰がさらに研究したのですか?
A:1930年代にウィーンの数学者カール・メンガーとハーバードの数学者が研究を進めました。
Q: その後，ハスラー・ホイットニーは何を発表したのですか?
A:プリンストン大学のハスラー・ホイットニーが、定義後すぐに「巡回セールスマン問題」という名称を発表しました。
Q: 「より良い解」とはどういう意味か?
A: この文脈では、より良い解決とは、より安く、より短く、より速い解決という意味であることが多いです。
Q:メンガーがTSPを研究する際に、自明と考えたアルゴリズムは何か?
A:メンガーはTSPを研究する際に、明白なブルートフォースアルゴリズムを考え、最近傍発見的な使い方が常に最適な結果をもたらすとは限らないことを観察しました。
