研究室公開

OPEN LABORATORY

ロボット・人工知能

33

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

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

周・伊藤(健)研究室

EXHIBIT

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

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

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

アルゴリズムに挑戦!!

最近「人間vsコンピュータ」という話題を良く見るようになりました.将棋や囲碁で,コンピュータがプロに勝利してニュースにもなりました.何億何兆という候補の中から,より良い答えを見つけるのもアルゴリズムの仕事.今回の展示では「数取りパズル」で様々なアルゴリズムと対戦できます.数取りパズルは2人で交互にチップを取り合って,取ったチップに書いてある数字の合計を競うパズルです.当研究室の誇る最強のアルゴリズムに,是非挑戦してみてください.

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

SmartCampusへ

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

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

身近にあるアルゴリズム

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

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

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