|
|
難問 ? 巡回セールスマン問題 |
「巡回セールスマン問題」 が難問である理由は、その膨大な計算量にあります。
いま、訪問すべき得意先が３軒の場合を考えてみます。
最初に訪問する得意先は３軒の内の１軒ですから、３通りの選択肢があります。
２番目の訪問先は残った２軒のうちのどちらかになります。選択肢は２になります。
３番目の訪問先は残された最後の１軒です。選択肢は１です。
したがって巡回経路の数は ３×２×１＝６ ですから、全部で６通りあります。
しかし、３軒の得意先をそれぞれA、B、C とすると、
巡回経路は A-B-C、A-C-B、B-A-C、B-C-A、C-A-B、C-B-A の６種類です。
この中にはそれぞれ逆回りコースが含まれているため、
距離だけを考えるなら （３×２×１）÷２＝３ でいいことになります。
訪問先が４軒ある場合は、（４×３×２×１）÷２＝12 通り、
訪問先が５軒の場合は、（５×４×３×２×１）÷２＝60 通りの巡回経路があります。
このような、ｎ × (ｎ−１) × (ｎ−２) × … × ２ × １ という計算は ｎ！ と書き、
「階乗」 といいます。
訪問先が３軒の場合は ３！／２ ＝ ３ 通り、４軒の場合は ４！／２ ＝ 12 通り、
５軒の場合は ５！／２ ＝ 60 通りです。
コンピュータでこのような問題を解く場合、しばしば、すべての巡回経路の長さを計算して、
いちばん短かいものを選ぶという、総当たり式プログラムを作ります。
ばかばかしいようですが、コンピュータは圧倒的な早さで計算し、疲れも知らず、
プログラムは単純で、しかも結果が確実だからです。
では、訪問先が３２軒の場合、何通りの巡回経路の長さを計算すればいいでしょうか。
この問題では、すでに１軒目の訪問先にいることになっているので、 ３１！／２ でいいことになります。
これを計算すると、
３１！＝ （３１×３０×２９× …… ×４×３×２×１）／２ ≒
4.11 ×１０ 33 通りになります。
この、4.11 ×１０ 33 という数字が
ピンとこない人は、ガマンしてもう少しおつきあい下さい。
いまここに、32 軒の巡回経路の長さを １秒間に１兆回
計算できるスーパーコンピュータ があるとします
。
１秒間に １兆回 （１０12 回） の計算ができます。
このスーパーコンピュータを使って 4.11 ×１０33 回の計算をするには
4.11 ×１０21 秒が必要です。
１年は、約 ６０×６０×２４×３６５＝３１５３６０００≒
3.15 ×１０7 秒ですから、
4.11 ×１０21 秒を １年≒ 3.15 ×１０7 秒で割ると、
答は 1.3 ×１０14 年です。
すなわち、130 兆年 かかることになります。
この先 130 兆年の間、コンピュータは故障せず、停電もせず、人類も地球も宇宙も滅亡せず、
ひたすら動き続ければ… の話ですが、
残念なことに太陽の寿命はあと約50億年で、50億年後には太陽は赤色巨星と化して火星の軌道に近い大きさとなり、
水星も金星も地球も、みな太陽に飲み込まれてしまう運命のようです。
コンピュータだけが 130 兆年動き続けることは極めて困難なように思われます。
もちろん、近い将来、もっと高性能のコンピュータや、このような問題をまったく別の方法で、
短時間のうちに解いてしまうコンピュータが出現する可能性はあります。
しかし、少なくとも現在のコンピュータで、このような問題を総当たり方式で解くことは
とうてい不可能だということはお分かりいただけたでしょう。
このような理由によって、巡回セールスマン問題は 「難問」 とされています。
しかし、それでも、コンピュータに巡回セールスマン問題を解かせたい場合があります。
たとえば、コンピュータなどに使われているプリント基板には、
数千個もの小さい穴を開けなくてはなりません。
もちろん超高速の専用の機械を使いますが、穴は原則的に１個づつドリルで開けます。
どういう順序で開けていくとドリルの移動時間を最短にできるかという問題は、
「巡回セールスマン問題」そのものです。
穴は 数千個 もありますから、コンピュータの総当り方式は論外です。
人間は直感的に効率的な経路を判断できますが、
何千箇所もの加工経路を指示するという単純作業は苦手です。
１箇所でも忘れるとたいへんなことになります。
一般的には、コンピュータで近似解を求める方法が採られています。
必ずしも最短でなくてもいいから、できるだけそれに近いものを短時間で求めるために、
様々な工夫がされています。
last update: 2004.11.18 ueyama@infonet.co.jp