研究室公開

OPEN LABORATORY

ロボット・人工知能

39

アルゴリズムの知られざるチカラ

君は最強のアルゴリズムに勝てるか!?

周・伊藤研究室

EXHIBIT

オープンキャンパスでの展示

アルゴリズムのすごさを体感しよう

数学の問題の答えは1つですが,解く方法は1つとは限りません.問題の解き方によって,簡単に解けたり,すごく時間がかかったりします.コンピュータが問題を解く方法を決めるのが「アルゴリズム」です.だから,アルゴリズムが変われば問題を解決する時間が変わります.パソコンやスマホがサクサク動くかどうかもアルゴリズム次第.アルゴリズムは,今やあらゆるシステムに導入され,システムの信頼性や高速性を握る重要な鍵となっています.

陣取りパズルに挑戦!!

陣取りパズルは自分の色を変えながら自分の陣地を拡げていくパズルゲームです.陣地の広がり方を先読みして,いかに効率よく色を変えていくかがポイント.陣取りパズルは単なるパズルゲームではなく,コンピュータウイルスや伝染病の拡がりを予測するシミュレーション等にも応用できます.アルゴリズムの世界で盛んに研究されている陣取りパズル.皆さんも,なるべく多くの陣地を奪えるよう挑戦してみてください.

スマホアプリが研究室をナビゲート

SmartCampusへ

より良いアルゴリズムの開発を

15人全員に,電話を使って,情報を伝えたいとしましょう.図に示すように電話連絡の仕方は様々で,それらは情報伝達のアルゴリズムとみなせます.どちらのアルゴリズムも,全員に情報が伝わるという点で正しいアルゴリズムですが,情報伝達にかかる時間には大きな差があります.同じことをやってくれるのならば,もちろん速い方がいいですよね.
私たちの研究室では,正確さを保証しつつも,いかにアルゴリズムを高速化できるか,その限界を研究しています.

身近にあるアルゴリズム

皆さんが使っているインターネットの世界にも,アルゴリズムがたくさん隠れています.例えばデータ通信するときに,みんなが一斉に同じ回線を使おうとしたら,その回線はパンクしてしまいます.そのようなことが起こらないように,うまく通信経路を分散させられるかどうかは,アルゴリズム次第.
こんな風に,皆さんに直接は見えないところで働いているアルゴリズムは,社会基盤を支える縁の下の力持ちなんです.

恋愛にもアルゴリズム!?

L.S. Shapleyは,1962年にD. Galeと一緒に「安定結婚問題」を解くアルゴリズムを考案し,2012年にノーベル経済学賞を受賞しました.安定結婚とは,結婚した後でお互いに「やっぱりあなたの方が良かった」というペアが生じないカップリングのことです.(もしそんなペアがいたら,駆け落ちの危険がありますね.)
実はこのアルゴリズム,結婚相手を見つけるだけでなく,研修医の配属先病院を決めるプログラムにも使われています.他にも,大学の研究室配属など,様々なマッチングに応用できる,正にノーベル賞級にすごいアルゴリズムなんです.