理化学研究所と北海道大学の共同研究による「粘菌が迷路を解く」という発見が、2008年のイグ・ノーベル賞を受賞しました。さて、受賞は吉とでるか凶と出るか。
研究そのものの概要は、プレスリリースで読むことができます。また、迷路を解いた様子の写真はこちらのページで見ることができます。この発見、一読してすごい！と感じました。粘菌研究としてどうかは、私にはわかりませんが、コンピューティングの研究としてもっと光を当てられてしかるべきです*1。
粘菌による「計算」の手順は簡単です
- 迷路全体に粘菌を広がらせる
- 迷路の出口と入り口に餌を置く
すると、粘菌は出口と入り口をつなぐ最短経路に太いパイプを残して縮んでしまいます。おそらく与えられた餌で生きるためのエネルギーが最低な状態におちていくのでしょう。
これを役に立たないばかばかしい研究として笑うのは簡単です。が、コンピューティングの問題としては注目すべき点があります。というのは、アルゴリズムを別問題に変換したうまい例だからです。迷路探索アルゴリズムは、マイクロマウス競技でも取り上げられましたが、なかなかうまい手がない複雑な問題です。よく知られている左手法、右手法は巧妙に迷路を説くことができますが、最短ではない上に、浮島のなかに出口があると出口を見つけられないなどの問題があります。基本的にコンピュータによる迷路の探索は総当り式であり、迷路の面積*2に比例します。粘菌は浮島があっても問題なく経路を見つけられる上に、すべての通路を並列に評価できます。評価の時間はおそらくはもっとも長い袋小路の長さに比例するだろう事が、直感的にわかります*3。
複雑な問題を別分野に変換するというコンピューティング技法は、たとえばセールスマン巡回問題をDNAにマップさせた例などがあります。セールスマン巡回問題は、問題の計算時間が問題のサイズが大きくなるにつれ、爆発的に長くなるという頭の痛い問題ですが、DNAによる計算は、溶液中のDNA片を使って、「かき混ぜるだけで」一挙に並列評価を行うというものです。
非ノイマン式の、特にスイッチを使わない超並列計算方式では、原理的に早く計算できることがわかっていても、実際のアルゴリズムをその計算機上に実現する方法が鍵になります。この研究は、生きた生物に、それも単一個体*4の性質に計算をマップした点で、もっと評価されるべきです。
四半世紀ほど前の日経サイエンス誌に掲載されていたアナログ・ガジェットを思い出しました。
イグ・ノーベル賞の趣旨はいまいちわからないところがあるのですが、どう考えてもばかばかしい研究と一列に並べられたことが、この研究に吉と出るか凶とでるか、少し心配しています。
*1:中垣氏のページにはニューサイエンティスト誌に風変わりなコンピュータとして取り上げられたという報告がある
*2:迷路のサイズの自乗
*3:生物なので等速に収縮するかは別問題だが
*4:しかも単細胞！
