「巡回セールスマン問題とは」から書き始めるのがセオリーかと思いこの記事を投稿します。
尚、知ってる人も知らない人も途中の文章は読み飛ばしても後々問題が起こることはないと思っています。
ただ、<strong>「巡回セールスマン問題とはどういう問題か？」</strong>は、理解する必要があると思います。
なんの必要かというと今後このブログの記事を読むための予備知識としての必要です。
ということで、もうこのブログには興味がないという方は全部スルーしても全く問題ありません。
<strong>７つのミレニアム懸賞問題</strong>
これらの懸賞問題は数学の分野において未解決とされている問題の中で特に重要と判断した？クレイ研究所が「解決した人には１００万＄差し上げますよ」とした問題です。
・ヤン-ミルズ方程式と質量ギャップ問題：わたしには設問の意味自体がわかりません。
・リーマン予想：同上です。
・ナビエ-ストークス方程式の解の存在と滑らかさ：同上です。
・ホッジ予想：多分、設問の意味自体を理解しようとしていない自分がいます。
・ポアンカレ予想：解決済みなのでミレニアム懸賞問題は６つになりました。
・バーチ・スウィンナートン＝ダイアー予想（BSD予想）：わたしには設問の意味自体がわかりません。
・P≠NP予想：巡回セールスマン問題が属する問題です。
<strong>P≠NP予想と巡回セールスマン問題</strong>
簡単に言えば（簡単過ぎるかな？）P≠NP予想は、計算複雑性理論（計算量理論）において膨大な計算量を処理できるんでしょうか？できないんでしょうか？という問題（設問）です。
例えば、N個という数のN！（階乗）の計算量があったとき、Nが１０００でも、現代のコンピュータでは宇宙が何回か生まれて消滅しても計算できないとされています（尚、少し前まではNが３０でも無理と言われていました）。確かに３０⇒１０００に増えたら進歩ですね。でもたかだかの進歩といわれています（計算量理論においては、「たかだか」という言葉がよく使われます）。
このP≠NP予想に属する数学の未解決問題は数十とも数百ともいわれていて、１つの問題が解けると全ての問題が解けるはずだともいわれています。
そして、その複数の問題は難易度によってクラス分けされています。
最も、難易度の高い問題は、NP完全とかNP困難のクラスに属します。
巡回セールスマン問題はNP困難クラスとされています。
<strong>巡回セールスマン問題とはどういう問題か？</strong>
巡回セールスマン問題を英語に訳すとTraveling Salesman ProblemとなるためTSPと呼ばれます。
設問をWIKIの引用で説明すると、
「都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求めよ」
となります。
これを簡単に説明すると「紙の上に適当な数の点を描いたとき、最短の距離で一筆書きをせよ」となります。
実は、この説明は不備なのですが、差し当たり問題は起こらないと思っています。
点数をN個としたとき、全ての点を１回だけ通過するルート（今後パスと呼ぶことにします）は、N！（階乗）個存在します。
実は、（N－１）！／２ルートなのですが、－１とか／２はたかだかとみなされます。
N！（階乗）は２からNまで掛け算をした数です。
つまり、２×３×４.....×Nです。
エクセルなどの表計算ソフトを持っている方は、どのくらいの数になるか試してみては如何でしょうか（少ない数で、エラーが出ると思います）。
この膨大なパス数の中から最短経路（つまり１パス）を選び出すことが命題となります。
