2010年12月8日水曜日

ハチが巡回セールスマン問題を解く?

このエントリーをはてなブックマークに追加
Pocket

計算機工学の代表的な難問に、巡回セールスマン問題がある。この難問をマルハナバチが解いて行動していると、ロンドン大学ロイヤル・ホロウェイ校生物科学部のNigel Raine博士が主張しており、American Naturalist誌に研究が掲載されたそうだ(Mail Online)。

巡回セールスマン問題は、例えば幾つかの地点が与えらたときに、全ての地点を通過する経路の中で、最も移動する距離が少ないものを選択する問題だ。万能に使える楽な解法は未だに発見されておらず、全ての組み合わせを比較するしかない。4地点であれば24パターンを、5地点であれば120パターンを比較する必要があり、通過する地点が多くなればなるほど、飛躍的に計算量が増加する。

Raine博士は、造花を並べてマルハナバチがそれらの間を飛ぶ経路を観察したところ、見つけた順番で花と花の間を飛ばずに、一度花を見つけた後は、最短経路で花と花の間を飛ぶようになることが分かったそうだ。

もちろん、マルハナバチが巡回セールスマン問題を解いていると考えるのは早計だ。あるケースで最適解で飛ぶとしても、別のケースで最適解を選べるとは限らない。経験的に楽な経路で飛んでいても、偶然に最適解になるケースはあるからだ。「巡回セールスマン問題を解いている」なら「最適経路を選択する」が、「最適経路を選択する」からといって「巡回セールスマン問題を解いている」わけではない。実験的に言えることは、実験した範囲で「最適経路を選択する」ことだけであり、逆は真とは言えない。

実は10月に、「ハチの脳、コンピュータより優れている」(CNET Japan)、「ミツバチはコンピュータよりも速く巡回セールスマン問題を解ける」(./)などというセンセーショナルな見出しで話題になったのだが、ソーシャルサービスでは、本文を読んでがっかりだと言うコメントで溢れていた。なお、花が4つしかない実験だったとか、ミツバチではなくマルハナバチだとか、有益な情報提供が多数あるのが、せめてもの救いとなっている。

何はともあれ、Raine博士は研究を売り込みたくて故意に誤解を招くアピールをしたと思うが、その効果は十分に発揮されたようだ。

0 コメント:

コメントを投稿