フォロー
ドイツの半導体メーカー、インフィニオンテクノロジーズ製の32ビットCPU〔AFPBB News〕
巡回セールスマン問題
巡回セールスマン問題とは「セールスマンがいくつかの都市を1度ずつすべて訪問して出発点に戻ってくるときに、移動距離が最小になる経路」を求める問題のことで、組合わせ最適化問題の中でも有名な問題です。それはスーパーコンピューターを用いても最適解を求めることが困難だからです。
都市数をnとすると、可能な経路の総数はn!/2n通り存在します。 nが小さいときには、全ての組み合わせを調べることができるので最短経路も分かります。しかしnが大きくなると、この組み合わせの総数は爆発的に増加しすべてを調べることは事実上不可能になります。
例えば、10都市のときには、組み合わせ総数は181440通りですが、 30都市のときには、4.42×10の30乗通りになってしまいます。
これがどれだけ絶望的な数かと言えば、計算速度10テラフロップス（FLOPS＝Floating-point Operations Per Second）の計算機を用いた場合にすべての組合わせを調べるのになんと25京年（250000億年）以上かかるのです。宇宙ができて137億年ですから、比較にならないほど時間がかかることが理解できます。
ここでFLOPS とは計算機の処理速度を表す単位で、1秒間に実行できる浮動小数点数演算の回数を表します。
演算速度が1テラフロップスとは1秒間に10の12乗回の浮動小数点演算。ソニーの家庭用ゲーム機「プレステ4」は1.84テラフロップス、地球シミュレーターは35.86テラフロップス、そしてスーパーコンピューター「京」は1京フロップス＝10ペタフロップス＝10000テラフロップスです。
フェルマーの最終定理がそうであったように、このような圧倒的な難問だからこそその解法が進化してきました。中でも計算機科学（computer science）と呼ばれる分野です。
