粘菌が組み合せ最適化問題を解く

capra 曰く、

New Scientestの選ぶ「一風変わったコンピュータ トップ10（Ten Weirdest Computers）」が本家にて紹介されています。リストには量子コンピュータもあれば、水の波紋なども含まれていますが、日本の中垣俊之氏らによる研究である迷路を説く粘菌もランクインしています。迷路に広がった粘菌は、入り口と出口に餌を置くと迷路の解を最短ルートで結び、他の関係ない経路に広がった部分を撤退させるそうです。この迷路解きは、従来のコンピュータには難しいとされている「巡回セールスマン問題」のような組み合わせ最適化問題の一つであり、情報科学分野での応用が期待されるとのことです。

トップ10

[motamota (30138)]

1. 光コンピュータ （Optical computing）
2. 量子コンピュータ （Quantum computing）
3. DNAコンピュータ （DNA computing）
4. 可逆コンピュータ （Reversible computing）
5. ビリヤード・ボール・コンピュータ （Billiard Ball computing）
6. ニューロン・コンピュータ （Neuronal computing）
7. 磁気（核磁気共鳴）コンピュータ （Magnetic (NMR) computing）
8. Glooper Computer
9. 変形菌コンピュータ （Mouldy computers）
10. 波紋コンピュータ （Water wave computing）

"8. Glooper Computer" ってのが何なのか分からないんですが。（まあ他のも分からないんですけど）

Re:トップ10

[Jubilee (20038)]

9. 変形菌コンピュータ （Mouldy computers）

なんだ、ルーディ・ラッカーのおかげか…。

「フリーウェア」http://en.wikipedia.org/wiki/Ware_Tetralogy#Freeware [wikipedia.org]に登場する「有機コンピュータ＋デザイナー・カビ」の(すごくいろいろ略すと)知的共生生命体が「モールディ」。

--
Jubilee

モールディ

[Anonymous Coward]

サンタクルーズにいっぱいいるよ。

タイムマシンコンピュータ

[Deasuke (34806)]

SFネタですが。
http://homepage3.nifty.com/iromono/hardsf/ctccomp.html

--
Best regards, でぃーすけ

Re:トップ10

[127.0.0.1 (33105)]

>10. 波紋コンピュータ （Water wave computing）

ジョジョネタかと思う人は多いと思う。

Re:

[Anonymous Coward]

学者「この問題の最適解は何だね？」
COM「お前は今まで食べたパンの枚数を覚えているのか？」

Re:

[Anonymous Coward]

学者「教えてやろう、9万8753枚だ」

Re:トップ10

[Nuisan (34779)]

「2, 3, 5, 7, 11,..., 98753」って数えて落ち着こうと思ったのに、98753は素数じゃなかった・・・

＃98753=17×37×157
＃ちなみに98753の直前の素数は98737で直後の素数は98773みたいです。

Re:トップ10

[elderwand (34630)]

> "8. Glooper Computer" ってのが何なのか分からないんですが。

こんなのが [urbandictionary.com]ヒットしましたが、2. の定義は down が付いてるので注意。わかんないけど、スライムとか言ってるような物？

次点（Re:トップ10

[Anonymous Coward]

11. 勘ピュータ (sixth sense computers)

Re:

[Anonymous Coward]

あとこんなのとか。マッチ箱の脳 [amazon.co.jp]

コンピュータというよりは、アルゴリズム、ですが。

プラトーの問題

[superfox (31908)]

確かマーティンガードナーの本で読んだと思うんだけど、
プラトーの問題 [osaka-kyoiku.ac.jp]の話を
知ったときは愕然としたな。

何しろちょっと点数を増やすだけでコンピュータにはお手上げなのに
石鹸膜が解いちゃうんだから。

Re:プラトーの問題

[s02222 (20350)]

>何しろちょっと点数を増やすだけでコンピュータにはお手上げなのに
>石鹸膜が解いちゃうんだから。

コンピュータで手に負えないのは、数学的にそれ以上良い解が無いと証明できる最適解を求めたい場合です。 その石鹸膜で求めた解は、それが最も良い解だという保証がないハズです。 点の数を増やすと、かなり良い線いってるけど完璧ではない状態、みたいなのも出てきます多分 (もっと極端なところでは、乱暴に扱ってシャボンが割れちゃった、みたいな事態も起こりえますし)。

粘菌にせよシャボン膜にせよ、複雑な仕組みを使ってるわけでもないのにすごく良い解がいとも簡単に求まる、というのがミソで、 逆にその求まり方をコンピュータで再現しようとするネタもあります。

Re:プラトーの問題

[superfox (31908)]

> その石鹸膜で求めた解は、それが最も良い解だという保証がない

そうです。でも、最適かどうかの判定は楽 [wikipedia.org]なので、その簡単な方法を何度か繰り返せば良いよ、という話だったような。

「参考になる」モデついてるけど

[superfox (31908)]

門外漢なので全く自信はないので参考にはしない方が良いです。
その法則に従っているからといって
組合わせが「最適」とは限らないかもだし。

迷路を解く粘菌

[fslasht (3370)]

「もやしもん [wikipedia.org]」のエピソードでも出てましたね。
平成12年発表ということは、イブニングで連載されてた2004年の４年前。
劇中の年代が連載開始時期または過去ということだと、樹教授が幼少時の長谷川に粘菌シャーレを渡した時点ではまだ発表前だなー。と、野暮なツッコミ

最小全域木

[clausemitz (30680)]

これはネットラジオのヴォイニッチの科学書 [c-studio.net]で取り上げられたネタですね。
これはグラフ理論で言うところの「最小全域木」を粘菌を使って求めたんだな
と放送を聴いたときに直感しました。難しい言葉ですけど、わかりやすく言えば
なるべく最短距離で枝葉を張っていく行動を粘菌が行なったというわけです。
カーナビで使っている、最短距離を求めるアルゴリズムで「ダイクストラ法」
という有名なのがありますが、その親戚みたいなものですね。

--
clausemitz

Re:最小全域木

[matto (35031)]

迷路を解くアルゴリズムはアホなアルゴリズムでもたかだかO(N^2)で解けるはず。
だから、別に粘菌の助けを求めなくても、ふつうのPCで簡単に解けるでしょ?
これを巡回セールスマン問題と同等の問題であるかのように誇張するのはどうかと思うぞ。

Re:

[Anonymous Coward]

＞なるべく最短距離で枝葉を張っていく行動を粘菌が行なった

ちがう。
広範囲に広がってた粘菌が最終的に最短距離を結ぶルートに縮まったという実験。
あたかも粘菌が解いたみたいに言われてるけど、半ば液状の物質が表面張力により最小の表面積に落ち着くのは単なる摂理ですな。シャボン玉と一緒。

Re:

[Anonymous Coward]

あの粘菌の例を見るにつけ「表面張力じゃね？」と思ってしまいます。

Re:

[Anonymous Coward]

｢粘菌が迷路を解く」こと自体は理研のその研究以前も知られていたような？
ただ、「最適解」かどうかまでは言及されていなかったような？

#学生時代（90年代）、南方熊楠にはまって粘菌関係の本読んでいたら
#「粘菌は迷路を解く」ってのを見かけた記憶が。
##熊楠の研究として、かどうかは記憶にない

##そーすみつけられないのでAC.

実用性

[Anonymous Coward]

計算能力が増殖しているところが面白いと思いますが，あまり実用性がないでしょう．

ある研究会で講演を聞きました．（数時間？数日？かけて）苦労して解けた例のサイズが10ぐらいでしたので，気になって実用性について質問をしたところ，今のところはみえないとのことでした．というのは，巡回セルスマン問題は難しい問題なのですが，10ぐらいのサイズでしたら，普通のPCでもミリ秒単位で解けるでしょうし，どうみても粘菌解法は，ただの総当たりの並列計算を粘菌にやらせているだけなので，計算そのものが高速になっていないと思われますから．

因みに粘菌を育てるのが大変らしく，問題を解ける前に全部死んでしまったこともよくあるようです．

Re:実用性

[Anonymous Coward]

> ただの総当たりの並列計算

いまのコンピュータの弱いところは、まさしくそこなんじゃないでしょうか。
量子コンピュータにせよ、DNAコンピュータにせよ、超並列ということがウリですし。
脳だって、素子ひとつひとつは遅いし大したことないけど、超並列だから
なんだかすごいことができている、と考えられていますし。

超並列計算を、そんなに速くなくてもいいから（どうせスケールアップすれば
元は取れるので）、低消費エネルギーで効率良くやりたい、というのが、さまざまな
代替コンピュータの発想なのではないかと思います。

「数学セミナー」(2008年5月号)に記事あり

[Anonymous Coward]

特集「この数学はおもしろい！」の記事の一つとして取り上げられています． p.20～21の「アメーバに学ぶ最短経路探索法」がそれです．

粘菌とかけて

[parsley (5772)]

南方熊楠 [wikipedia.org]を検索しようとして、うっかり舛添要一 [wikipedia.org]を探し当ててしまう不思議

# そりゃ「ねんきん」違いでしょうが～

--
Copyright (c) 2001-2014 Parsley, All rights reserved.

Re:

[Anonymous Coward]

そういえばドミニオンにそんなネタがあったような。

Re:

[Anonymous Coward]

森は脳だ。
意志を持ってるのだ。粘菌はニューロンだ。
南方はロボトミーを阻止しようとしたのだ。

Re:粘菌とかけて

[parsley (5772)]

私の身分について調査すればいいでしょう。それが答えでしょう。

--
Copyright (c) 2001-2014 Parsley, All rights reserved.

あー

[Anonymous Coward]

…マジレスさせちゃいましたか。すいません
文面と1ch.tv辺りでググってくださいな。

自己組織化

[Anonymous Coward]

アリの群れの自己組織化や粘菌の迷路ときってずいぶん前から研究されているし、既に経路探索などに実用化されているんですけど、知らない人って意外に多いんですね。

アリの生態にみる自己組織化のルール − ＠IT情報マネジメント [atmarkit.co.jp]

Re:

[Anonymous Coward]

同感。
知らなかった人が騒いでるんでしょう。
（まあ、たいていのことは後から知って騒ぐってことが多いものだけどね）

結構ポピュラーで一般人がみても面白いので科学番組などでは繰り返し
取り上げられるねたですね。30年以上前のNHK教育の番組でやってたのを
小学校で見た記憶があります。
アリのケースは個人でも簡単に実験できるので科学部とかが迷路作って
やってたっけ。巨大迷路で人間を大勢詰め込んで同様のことをやると
どうなるかという研究もあります。（結果はペーパーを読んでみて）

Re:

[Anonymous Coward]

人工知能系は今時流行らんってことなのかな？

これは、

[Anonymous Coward]

どっちが出口でどっちが入口なのかな？

Re:これは、

[Anonymous Coward]

入り口と出口を結ぶ迷路のメタファは分かりやすいけど

実際には

変形体が迷路の道筋全体に広がった後、餌を入口と出口に与えると、
１）行き止まりの経路にある部分を衰退させ、入口と出口をつなぐ経路全てに管を残します。
２）最終的に、最短距離の管を選んで１本の太い管を残します。

という事なので、入り口と出口の区別は無いですな。

迷路を解くのに、行き止まりを塗りつぶしていく方法があるでしょ？
最終的に答えが白く浮かび上がるような
あれをやってる事になりますね。

誤変換ですよ。

[Anonymous Coward]

>迷路を説く粘菌

迷路を説いちゃいかんでしょ。

Typo もあるよ。

[Another Coward (33409)]

> New Scientestの選ぶ「一風変わった...

s/Scientest/Scientist/

でしょ。

最適解？

[Anonymous Coward]

粘菌の話を聞いて思っていたのが、最適解にたどり着けるのかな、ということ。
迷路の出口が複数あって、それぞれ微妙に違うえさがあるばあい。

粘菌の個体差によりその評価値が違うのであれば
それぞれ別の出口にたどり着く事もあるのかな、と。

# 沢山粘菌はなして一番多い出口？

Re:

[Anonymous Coward]

組み合わせ論的最適化問題は、最適解にたどり着くとは、限りません。
局所解から抜け出すのが、アルゴリズムの目的です。

粘菌がだめなら津波を起こせばいいじゃない

[Anonymous Coward]

ええ、それではダメなことはわかりますが、基本原則はそっちの方向性で粘性が低い物を流したほうが手っ取り早くわかるんじゃない？自然界の法則にしたがって計算するならば。

Re:

[Anonymous Coward]

つまり入り口からなにかを流し込めば、
どこをどう通ったかわからないが、
とにかく出口から出てくる、ということか？
・・・それでなにがわかるというんだ？

おまえは一体どこのマリー・アントワネット(ry
#おやくそくなので

地球

[Anonymous Coward]

地球 [wikipedia.org]が入っていないのはどういうわけだ？

Re:地球

[ryo_jp (9684)]

おおっぴらにやると亜空間ハイウェイを建設するという名目で計算を実力で阻止されてしまうからです