パスワードを忘れた? アカウント作成
23220 story
バイオテック

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

ストーリー by nabeshin
膨大なスレッドによる総当たり 部門より

capra 曰く、

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

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • トップ10 (スコア:5, 参考になる)

    by motamota (30138) on 2008年04月14日 16時39分 (#1329670)
    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" ってのが何なのか分からないんですが。(まあ他のも分からないんですけど)
  • by superfox (31908) on 2008年04月14日 16時48分 (#1329683)
    確かマーティンガードナーの本で読んだと思うんだけど、
    プラトーの問題 [osaka-kyoiku.ac.jp]の話を
    知ったときは愕然としたな。

    何しろちょっと点数を増やすだけでコンピュータにはお手上げなのに
    石鹸膜が解いちゃうんだから。
    • by s02222 (20350) on 2008年04月14日 17時23分 (#1329723)
      >何しろちょっと点数を増やすだけでコンピュータにはお手上げなのに
      >石鹸膜が解いちゃうんだから。

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

      粘菌にせよシャボン膜にせよ、複雑な仕組みを使ってるわけでもないのにすごく良い解がいとも簡単に求まる、というのがミソで、 逆にその求まり方をコンピュータで再現しようとするネタもあります。
      親コメント
  • 迷路を解く粘菌 (スコア:2, おもしろおかしい)

    by fslasht (3370) on 2008年04月14日 16時11分 (#1329651) ホームページ 日記
    もやしもん [wikipedia.org]」のエピソードでも出てましたね。
    平成12年発表ということは、イブニングで連載されてた2004年の4年前。
    劇中の年代が連載開始時期または過去ということだと、樹教授が幼少時の長谷川に粘菌シャーレを渡した時点ではまだ発表前だなー。と、野暮なツッコミ
    • これはネットラジオのヴォイニッチの科学書 [c-studio.net]で取り上げられたネタですね。
      これはグラフ理論で言うところの「最小全域木」を粘菌を使って求めたんだな
      と放送を聴いたときに直感しました。難しい言葉ですけど、わかりやすく言えば
      なるべく最短距離で枝葉を張っていく行動を粘菌が行なったというわけです。
      カーナビで使っている、最短距離を求めるアルゴリズムで「ダイクストラ法」
      という有名なのがありますが、その親戚みたいなものですね。

      --
      clausemitz
      親コメント
      • by matto (35031) on 2008年04月15日 2時03分 (#1330098)
        迷路を解くアルゴリズムはアホなアルゴリズムでもたかだかO(N^2)で解けるはず。
        だから、別に粘菌の助けを求めなくても、ふつうのPCで簡単に解けるでしょ?
        これを巡回セールスマン問題と同等の問題であるかのように誇張するのはどうかと思うぞ。

        親コメント
      • by Anonymous Coward
        >なるべく最短距離で枝葉を張っていく行動を粘菌が行なった

        ちがう。
        広範囲に広がってた粘菌が最終的に最短距離を結ぶルートに縮まったという実験。
        あたかも粘菌が解いたみたいに言われてるけど、半ば液状の物質が表面張力により最小の表面積に落ち着くのは単なる摂理ですな。シャボン玉と一緒。
    • by Anonymous Coward
      あの粘菌の例を見るにつけ「表面張力じゃね?」と思ってしまいます。
    • by Anonymous Coward
      「粘菌が迷路を解く」こと自体は理研のその研究以前も知られていたような?
      ただ、「最適解」かどうかまでは言及されていなかったような?

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

      ##そーすみつけられないのでAC.
  • 実用性 (スコア:2, 参考になる)

    by Anonymous Coward on 2008年04月14日 16時54分 (#1329694)
    計算能力が増殖しているところが面白いと思いますが,あまり実用性がないでしょう.

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

    因みに粘菌を育てるのが大変らしく,問題を解ける前に全部死んでしまったこともよくあるようです.
    • Re:実用性 (スコア:1, 参考になる)

      by Anonymous Coward on 2008年04月14日 18時31分 (#1329799)
      > ただの総当たりの並列計算

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

      超並列計算を、そんなに速くなくてもいいから(どうせスケールアップすれば
      元は取れるので)、低消費エネルギーで効率良くやりたい、というのが、さまざまな
      代替コンピュータの発想なのではないかと思います。
      親コメント
  • by Anonymous Coward on 2008年04月14日 17時04分 (#1329698)
    特集「この数学はおもしろい!」の記事の一つとして取り上げられています. p.20~21の「アメーバに学ぶ最短経路探索法」がそれです.
  • 粘菌とかけて (スコア:2, おもしろおかしい)

    by parsley (5772) on 2008年04月14日 17時12分 (#1329708) 日記
    南方熊楠 [wikipedia.org]を検索しようとして、うっかり舛添要一 [wikipedia.org]を探し当ててしまう不思議

    # そりゃ「ねんきん」違いでしょうが~
    --
    Copyright (c) 2001-2014 Parsley, All rights reserved.
    • by Anonymous Coward
      そういえばドミニオンにそんなネタがあったような。
    • by Anonymous Coward
      森は脳だ。
      意志を持ってるのだ。粘菌はニューロンだ。
      南方はロボトミーを阻止しようとしたのだ。
  • 自己組織化 (スコア:2, 興味深い)

    by Anonymous Coward on 2008年04月14日 20時07分 (#1329859)
    アリの群れの自己組織化や粘菌の迷路ときってずいぶん前から研究されているし、既に経路探索などに実用化されているんですけど、知らない人って意外に多いんですね。

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

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

      結構ポピュラーで一般人がみても面白いので科学番組などでは繰り返し
      取り上げられるねたですね。30年以上前のNHK教育の番組でやってたのを
      小学校で見た記憶があります。
      アリのケースは個人でも簡単に実験できるので科学部とかが迷路作って
      やってたっけ。巨大迷路で人間を大勢詰め込んで同様のことをやると
      どうなるかという研究もあります。(結果はペーパーを読んでみて)
    • by Anonymous Coward
      人工知能系は今時流行らんってことなのかな?
  • by Anonymous Coward on 2008年04月14日 16時26分 (#1329662)
    どっちが出口でどっちが入口なのかな?
    • Re:これは、 (スコア:2, 興味深い)

      by Anonymous Coward on 2008年04月14日 16時34分 (#1329665)
      入り口と出口を結ぶ迷路のメタファは分かりやすいけど

      実際には

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


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

      迷路を解くのに、行き止まりを塗りつぶしていく方法があるでしょ?
      最終的に答えが白く浮かび上がるような
      あれをやってる事になりますね。
      親コメント
  • by Anonymous Coward on 2008年04月14日 17時10分 (#1329705)
    >迷路を説く粘菌

    迷路を説いちゃいかんでしょ。
  • by Anonymous Coward on 2008年04月14日 17時22分 (#1329722)
    粘菌の話を聞いて思っていたのが、最適解にたどり着けるのかな、ということ。
    迷路の出口が複数あって、それぞれ微妙に違うえさがあるばあい。

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

    # 沢山粘菌はなして一番多い出口?
    • by Anonymous Coward
      組み合わせ論的最適化問題は、最適解にたどり着くとは、限りません。
      局所解から抜け出すのが、アルゴリズムの目的です。
  • by Anonymous Coward on 2008年04月14日 18時50分 (#1329818)
    ええ、それではダメなことはわかりますが、基本原則はそっちの方向性で粘性が低い物を流したほうが手っ取り早くわかるんじゃない?自然界の法則にしたがって計算するならば。
    • by Anonymous Coward
      つまり入り口からなにかを流し込めば、
      どこをどう通ったかわからないが、
      とにかく出口から出てくる、ということか?
      ・・・それでなにがわかるというんだ?

      おまえは一体どこのマリー・アントワネット(ry
      #おやくそくなので
  • by Anonymous Coward on 2008年04月15日 10時57分 (#1330300)
    地球 [wikipedia.org]が入っていないのはどういうわけだ?
typodupeerror

物事のやり方は一つではない -- Perlな人

読み込み中...