20021110　巡回セールスマン問題

　「巡回セールスマン問題$${^{*1}}$$」という数学の難問がある。沢山の得意先を一軒ずつ巡回して出発点に戻って来るにはどのような道筋で行けば歩く距離が最短になるか、という問題である。

　全ての巡回の組み合わせを計算してやれば、どの道筋が一番短いかは判るのであるが、訪問先が増えると巡回の組み合わせが爆発的に増えてくる。全部の組み合わせを計算しなくても、ある決まった手順に従えば最短の道筋が判るようにしたいのだが、まだその方法は見つかっていない$${^{*2}}$$という。最短の道筋を算出する方法は色々考え出されている$${^{*3}}$$ようだが、本当にどんな場合でもそれが最短か、と言われるとちょっと自信がなくなるらしい。厳密に最短の道筋が「この方法で導き出せる」というのはない様だ。これが難問と呼ばれる所以である。

　この「巡回セールスマン問題」を解くとどんな良いことがあるのだろうか。セールスマンが一日どれくらいの家を訪問するのだろう。呼び鈴を押して、その家の人が出てきて、話ができる場合もあれば、呼び鈴を押しても出てこないのを確認するのに時間が掛かる場合もある。その平均時間を5分として移動時間も平均5分とすると8時間みっちりやって50軒程度になる。道筋の組み合わせは3×10^64（10の64乗）となり、一つの組み合わせの距離を計算するするのに1秒しかかからなくても、10^57（10の57乗）年もかかってしまう。訪問するどころか、これでは地球も太陽も消滅してしまっている$${^{*4}}$$。

　しかし実際には移動する家と言えとの距離がそれぞれ短いので、厳密な最短距離を見つけなくても勘で適当に廻ればいいような気もする。団地を巡回する場合、上からがいいか下からがいいかぐらいを気にすればいいのかもしれない。

　「巡回セールスマン問題」の解き方を応用した例がある。厳密な最短距離は出せないが、大体の最短距離の導き方を利用して、電子回路のプリント基板$${^{*5}}$$にドリルで穴を開ける順番を計算している$${^{*6}}$$。これによって穴を開ける時間が短縮できたという。

　この「巡回セールスマン問題」を知った時、数学パズルのような感じで捉えていたが、今回、それを実用化しているのを知って少し驚いた。

*1　巡回セールスマン問題
*2　難問 ?　巡回セールスマン問題
*3　巡回セールスマン問題
*4　20000109　地蔵と弥勒
*5　日立IT 生産受託サービス プリント基板の組立
*6　Drill Route Optimization