ドイツの半導体メーカー、インフィニオンテクノロジーズ製の32ビットCPU〔AFPBB News〕
巡回セールスマン問題
巡回セールスマン問題とは「セールスマンがいくつかの都市を1度ずつすべて訪問して出発点に戻ってくるときに、移動距離が最小になる経路」を求める問題のことで、組合わせ最適化問題の中でも有名な問題です。それはスーパーコンピューターを用いても最適解を求めることが困難だからです。
都市数をnとすると、可能な経路の総数はn!/2n通り存在します。 nが小さいときには、全ての組み合わせを調べることができるので最短経路も分かります。しかしnが大きくなると、この組み合わせの総数は爆発的に増加しすべてを調べることは事実上不可能になります。
例えば、10都市のときには、組み合わせ総数は181440通りですが、 30都市のときには、4.42×10の30乗通りになってしまいます。
コメント 0