難問の巡回セールスマン問題、粘菌に学んだ新型コンピュータで北海道大学が解決
https://univ-journal.jp/68039/- もう量子コンピュータいらねーじゃん
やったね🤣 - すごいなあ
- 北海道大学の葛西誠也教授らの研究グループは、Amoeba Energy株式会社と共同で、アメーバ生物である粘菌の行動に学んだ新型アナログコンピュータを開発し、
代表的な組合せ最適化問題「巡回セールスマン問題」を解くことに成功した。巡回セールスマン問題とは、セールスマンが指定都市を各一度ずつ訪問し出発都市に戻る巡回経路のうち最短距離の経路を導く問題。
しかし、従来型デジタルコンピュータでは解決が難しく、近年は量子コンピュータなどによる提案が相次いでいる。アメーバ生物である単細胞の真性粘菌は、不定形の体を環境に最適な形に変形できる高度な計算能力を持つ。
先行研究で、アメーバ生物を組込んだ「粘菌コンピュータ」が巡回セールスマン問題に利用可能と分かっていた。そこで研究グループは、アメーバが変形するメカニズムをアナログ回路中の電子の動きで再現し、
都市配置や距離などの制約条件をコンパクトに表現できる仕組みの新方式コンピュータ「電子アメーバ」を開発。
これにより、巡回セールスマン問題の解を迅速に探し出すことに成功した。生物が獲得した探索能力を電子回路で再現した電子アメーバは、制約や要求が変わり続ける実社会の難しい課題の解決に貢献できる。
さらに、IoTデバイスなどに組込み可能な小型で低消費電力の新原理コンピュータの実現も期待される。 - コロナ蔓延してるのにセールスマンを巡回させるな😡
- >>5
まさにこれで、営業なんぞ今やれてるとこなんてあるのか？ - >>9
あるぞ - これ解決できない問題じゃない?
- 電子アメーバ「ジンルイハ…テキダ！！」
- 文章読んでも理解できなかった
- 毎年のように解決したというニュースを見てるような気がする
- 物流革命起こせそう
- >>11
配送業にはダイレクトに効くやつだもんなこれ - >>33
正直そうでもない
TSPの解を得るのは難しくても、解に近いものは比較的容易に得ることができるからな
古典的な問題ゆえに様々な手法で研究され続けているから調べてみると良い - >>45
三角不等式が成り立たない一般的な系でのTSP近似アルゴリズムってまともなのあったっけ - P=NP
- 田舎回りセールスマンの靴下が粘菌？
- 歌うセールスマン
- 遺伝的アルゴリズムの延長でいいんだよな
- 巡回セールスマン問題ってオーダーがn！になるからnが大きくなり過ぎると最適解を算出するのは困難っていう話だったけ？
- これめちゃくちゃすごいんじゃない？
- 単に距離の問題だから粘菌の必要性が全く読み取れないんだが
- >>19
巡回すべき点が多いと最短経路を通常の組み合わせ計算で解くのが困難になる粘菌の作るコロニー間のネバネバのアミアミが、各コロニーを結ぶ最短経路になることが知られているので
それを活用した手法
生き物ってすごい - >>19
黙ってれば恥をかかないで済むのに
進んでバカを晒すその姿勢、まさに馬鹿だね - ただ訪問するだけちゃうで
ノルマを達成する順序にしてな - アナログ回路ってのがすごい感動する
- イグノーベルからガチのノーベル賞が出たら笑うな
- アナログ回路はまだ発展の余地十分あるからなぁ
- nいくつまで行けるの？
- これはマジですごい
- AIだと5秒で答え出るやつでしょ？
- 【悲報】人間ップの知能、粘菌以下だった
- 巨大な問題になった瞬間に最適解は出せないよ
遺伝的アルゴリズム的なのができただけだろ - >>31
その通りで最適解ではない
粘菌を模した数理モデルは発展的に効率的な物質輸送ネットワークになっていく数理モデルだけど理論上の最適解にはならなかったりする
そこは初期状態と乱数次第なんだよだね
ただ最適でないにしても効率的な物質輸送ネットワークであることには変わりないので実用性はある - これ解けない問題じゃなかったのか？P≠NP問題と関係してなかった？
- 中垣先生関わってなくて糞笑える
どうすんだよ人脈だけが取り柄なのにこういうのにいっちょ噛みしてないとか終わってんなおい - アルゴリズムがあーだこーだだろ？
- NPじゃなかったってこと？
- 解けないんじゃなくて古典コンピュータだと何億年もかかるだけだぞ
逆にいえば普通のパソコンでも何億年も計算させれば解ける問題
解けなかったり、正解がない問題じゃない - >>37
何億年もかかったら実質解けないのと同じだろ - ディープラーニングで巡回セールスマン問題解決や！って思ってたら案外上手くいかなかったらしいな
ふわっとした印象でこういうのめっちゃ得意そうなのに意外だった - 別名無能なセールスマン問題
- アナログ電子回路久しぶりにやってみたい
- 粘菌「俺なんかやっちゃいました？」
- 高速でなおかつ精度の高い近似アルゴリズムを構築したって話だね
- ナビの輸送ルートの検索とかどうやってんだろな
- 解決とは多項式時間内で解けることを証明したという意味じゃないよね。
- 粘菌コンピュータ。。。
かっけえ。。。 - アメーバは混み合ったとこを嫌って外に広がる修正がある
ここらへんを再現してるみたい - 遺伝的アルゴリズムと一緒で局所解に陥りそうな気がするけど、必ず最適解に収束してくれるんかね
難問「巡回セールスマン問題」 北大が新型コンピュータを使って解くことに成功
コメント