粘菌はDPなのでは・・？

夜景の美しい長崎を涼しい土地のなまら広い海際にぶちまけて，稲佐山の頂点を1m高くし，路面電車にロシア人ハーフのむすめを乗せて200円に値上げし，出島ワーフをレンガ造りにし，プロテスタントに改宗すれば函館になったりはしません．

FIT2011の10周年記念特別講演は粘菌の研究で超有名な中垣俊之氏．
確かに最短経路問題を解けない学生は単細胞どころか精魂の有無が疑われそうなほど生気がなさそうだけど，同問題を解くアルゴリズムとしてダイクストラ法（DA）を引き合いに出した点には「あれ？」と思った．むしろ，動的計画法（DP）を挙げるべきではなかろうか？

DAとDP，どちらも最短経路問題を解ける．私は不勉強なので，DAとDPの関係について知っているのはこの論文だけ．私の解釈が正しければ，要点は以下の通り（日高レポート風味で）：

• DAとDPは本質的には同じ．
• 距離は非負で，経路に沿って距離が増えることはないから，訪問を省略できる点がある．この性質を活かして，DPによる最短経路問題の解法の手間を減らしたのがDA．
• 負の距離も許す問題設定の場合，DAでは解が見つからないことがある．
• DAはもともと，Operations Research由来のアルゴリズムだが，なぜかORよりComputer Scienceの分野で大活躍している．
• DAの第一発明者はDijkstraじゃない．ORの分野では同じアルゴリズムがDijkstraより前に何度も提案されていた．
• DPが本質なので，DAよりDPを先に教育（勉強）した方がよい．

粘菌は最短経路も含めていくつかの経路を評価しており，可能性が低い経路が徐々に消失していく．局所的な評価を連結させて最短経路を見つけるその振る舞いは，まるであらゆる部分経路で頻繁にバックトラックして再評価を繰り返しているかのようで，DAというより，生きているDPと考える方がふさわしい気がする．素人の直観で「気がする」と言うだけなのは無責任だけれど，DAよりDPの方が解ける問題が広いようなので，粘菌の振る舞いの解釈としてどちらと比較考察するのが適切なのか，重要なポイントとなるはずだ．粘菌にとって負の距離に相当する環境が何なのか私にはわからないが，粘菌がDPをしているのならば，粘菌はDAよりも潜在能力があるはずで，それを活かす探究も必要ではないだろうか．数理と生命の間にある中垣氏の研究の興味はとても奥深いし，その動機は万人ウケしやすいけれど，粘菌の振る舞いをモデル化する研究は，そもそも粘菌が解ける問題のクラスを解明するアプローチとして有意義なので，意識的にもっとその方向に研究の進展をアピールしてほしいと思った．優秀な研究者の方々と共同研究されているはずだから，私の浅知恵に言われる余地などないとは思うが．

以上，北の誉一杯で約1200文字．