【数学】アメーバの一種「モジホコリ」を使って数学の難問「巡回セールスマン問題」を解くことができると判明［12/25］
■ このスレッドは過去ログ倉庫に格納されています
アメーバはべん毛や繊毛を持たず、細胞質を突出させた仮足を用いて移動する原生生物の総称です。日本の研究チームがモジホコリというアメーバの一種を使い、数学の難問として知られる「巡回セールスマン問題」を解くことに成功したと発表しています。
Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism | Royal Society Open Science
https://royalsocietypublishing.org/doi/full/10.1098/rsos.180396
Amoeba finds approximate solutions to NP-hard problem in linear time
https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html
An Amoeba-Based Computer Calculated Approximate Solutions to a Very Hard Math Problem - Motherboard
https://motherboard.vice.com/en_us/article/gy7994/an-amoeba-based-computer-calculated-approximate-solutions-to-a-very-hard-math-problem
慶應義塾大学の環境情報学部准教授である青野真士氏らの研究チームは、原形質流動によって移動して落ち葉や朽ち木の表面などに生息するアメーバの一種「モジホコリ」を使い、巡回セールスマン問題の解決に当たらせるという実験を行いました。モジホコリは脳を持たないにもかかわらず、高度な知能に匹敵するような記憶力・判断力を持っていることで知られる単細胞生物です。
巡回セールスマン問題とは組合わせ最適化問題の一種であり、同じ都市を2度訪問せずに複数の都市全てを訪問し、出発点に戻ってくる最短ルートを導き出すというもの。巡回セールスマン問題は巡回するべき都市の数が増えるにつれて、コンピューターが問題を解決するのに必要な時間が指数関数的に増えることで知られています。たとえば訪問都市が4つである場合は最適解のルートが3つしかありませんが、訪問都市が8つに増えた場合、最適解のルートが2520個にまで増加してしまいます。
研究チームは計64個の狭いルートを持つ星形プレートの下にモジホコリの栄養源となる寒天プレートを置き、その上にモジホコリをのせました。実験では研究チームがモジホコリに「巡回セールスマン問題を解くアルゴリズム」を与え、モジホコリはそのアルゴリズムに従って解を導き出すという一種のコンピューター的役割を果たしています。実験をまとめたムービーがこれ。
■動画
Physarum: Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism
https://youtu.be/8GCJq-HQbyk
モジホコリは秒速1mmのスピードで原形質を動かして仮足を伸ばし、プレート上を自由に動くことが可能です。モジホコリはなるべく多くの面積を寒天プレートと接触することで栄養を最大限吸収しようとしますが、光を嫌う性質を持っているために光で照らされた部分に体を広げることはできません。研究チームは星形プレートのルートを選択的に光で照らすことができる装置を開発し、狙ったルートからモジホコリを後退させることができるようになっていました。
続きはソースで
https://i.gzn.jp/img/2018/12/25/amoeba-solves-hard-math-problem/img-snap08038_m.jpg
GIGAZINE
https://gigazine.net/news/20181225-amoeba-solves-hard-math-problem/ もやしもんで、粘菌使って迷路解けるってやってたから
それと同じだろう。 多細胞生物から見た難問も単細胞生物から見ればごく簡単な問題に過ぎない。
不思議の国のアリスのような話だが、知性という物の奥深さを垣間見る思いだ。 >>45
ああそうか
サラリーマンを構成する億兆個の細胞に個別に巡回させれば短時間で解ける
すばらしい ちょうど１０年前に同じようなことでイグノーベル賞が取られているよ
それを踏まえた上での発展形じゃないのかなこれ >>2
光をあててアメーバを待避させるのは
「一度通ったルートを通らない」を機能させるためのギミック 粘菌だろ。３回目のイグ・ノーベル賞受賞確定かな。
粘菌にも永世イグ・ノーベル賞を与えて欲しい。 ウソから生まれた朝日新聞は
パヨク（ゴキブリ在日韓国人）
が支配していて、書いているのは
パヨク（ゴキブリ在日韓国人）
ばかりで、読んでいるのも
パヨク（ゴキブリ在日韓国人）
ばかりの
【朝】鮮【日】報の日本語版です ＞たとえば訪問都市が4つである場合は最適解のルートが3つしかありませんが、訪問都市が8つに増えた場合、最適解のルートが2520個にまで増加してしまいます。
最適解は基本的に一つだろ>>1 距離が遠いルートほど光が当たって仮足を後退させるらしいけど
このアルゴリズムならアメーバを使うまでもなくシミュレーションできそうな気も…？ >>57
規模が大きくなるとコンピュータに手には負えなくなるからアメーバ使おうって話だろ ソースだとまだn=8程度だし
このシステムだとn^2本の通路が必要だから 大規模化にも限度がありそうな…
面白い話だし研究の進展には期待してるけども >>8
は？解法は知られてるだろ
P≠NP予想の証明とごっちゃになってないかお前？ >>53
最適解は1つとは限らないかもしれないが、確かにそこは取りうるルートの数だな > 研究チームは星形プレートのルートを選択的に光で照らすことができる装置を開発し、狙ったルートからモジホコリを後退させることができるようになっていました。
人が動かしてるじゃん >>1
遙か前から粘菌で似たような実験やってなかったっけ >>20
>>21
おまいらがもっと戦って最後には猟奇殺人に発展してほしい アリとかもグループ全体で高等生物みたいな動きするらしいね ナビにこの機能つけないのはなぜかと思っていたが、そもそも解けてないのか 数学の難問とけた！すげえ！
っていうよりアメーバにもちゃんとしたセンサーと制御機構ついてることの証明みたいなもんだろ >>21
自由意志って今じゃ否定されているからな
腹減ったら喰う
喰われそうになったら逃げる
逃げれないならガキを残す
これをひたすらやるだけ 光で照らして行かせないとかやるのは人為的じゃないんか？ ちょwwwwwうけるwwwwwww
マジホコリwwwwwww >>73
>>3
何もしなきゃのべーって広がるだけじゃね？ 迷路の問題ではよくみると最短経路になっていない
https://gigazine.net/news/20161226-slime-molds/
今回のTSPについては見方がよくわからないが真の最短経路になってない可能性もある >>76
誰が最短経路って言った？
同じルートを通らないで特定地点を通過する問題だと書いてあるだろ
>>1も読めんのか >>13
そうなんだよね。
我々の知性とは違う知性が存在するかも
知れないと想像することがる。
もっと時間的スケールが違うものや、
ロジックそのものが違うというで、
知性とは何ぞやと思う。 ずーっと前に粘菌でやってた奴の二番煎じ
物理現象を利用して全ルート検索すると、ってこと
最短距離の確定値計算は出来ない
粘菌にもアメーバにも知性は無いよ
現代的なパソコンならほぼ最短距離なら高速に計算出来る
カーナビにも入ってるよね
確定値を計算するには計算量が爆発的に増えるので量子コンピュータが期待されてる
なお暗号に使う素数だけど、ほぼ素数だろう、で計算を簡略化してる。確実に素数かを検証するのは時間かかるので。それでも実用的に使える >>77
書いてあるよ
TSPは最短経路を求める問題だから覚えておいてね >>79
生物がNP困難な問題を解ける理屈がない気がしてる
量子に限らず物理現象を使うのが確実かなと >>20
その水の流れというので、己で巡回セールスマン問題やってみてくれ 粘菌は、仮足で何か所か栄養素をとらえたら、広がる力と栄養素を最短で運ぼう
とする力の拮抗で、迷路の最短経路を解く。
巡回セールスマン問題ではは、迷路の壁をあらかじめ設置できないため、光で
道筋を制限したけど、粘菌に問題を解かせる際の行動原理は全く一緒だと思われる。
ちなみに、モジホコリは粘菌である。
粘菌がアメーバの一種であるのか否かについては、まだ判然としない。
粘菌は子実体を生成して胞子で増殖する。 >>85
>>87
粘菌はアメーバの仲間
アメーボゾアというグループにまとめられる ☆ 改憲しましょう。総務省の、『憲法改正國民投票法』、でググって
みてください。国会の発ギはすでに可能です。平和は勝ち取るものです。
拡散も含め、ぜひよろしくお願い致します。☆ ■ このスレッドは過去ログ倉庫に格納されています
