イベント / EVENT

平成30年度 第6回 リポート

現実の入力に合わせた効率的なアルゴリズムを考える

 国立情報学研究所は12月11日、平成30年度 市民講座「情報学最前線」第6回を開催し、情報学プリンシプル研究系 岩田 陽一助教が「計算の理論と現実-難しいはずの計算が実はいとも?簡単に-」と題して講義しました。

pic_shimin_report_h30_6-1.jpg

 岩田助教は、大学時代、ACM国際大学対抗プログラミングコンテスト(ACM-ICPC)出場を機にプログラミングコンテストに没頭。これまでに、ICFPプログラミングコンテストで4度優勝(2013年、2015年、2016年、2018年)、TopCoder Open優勝(2010年)、Google Code Jam 3位(2009年)と、競技プログラミングの世界で数々の挙げてきました。現在は、研究者として、実際の入力構造を活用し、より効率的に計算を行うアルゴリズムの研究に取り組んでいます。

 まず、岩田助教は、アルゴリズムについて「問題を解くための手順」と述べ、「小学校で習う筆算も、実はアルゴリズムの一つです。掛け算を九九までしか覚えていなくても、筆算を使えば、何桁の掛け算でもできるように、単純な計算しかできない機械でも、アルゴリズムを組み合わせて使えば、複雑な計算ができるようになります。同じ問題を解くのにも、使うアルゴリズムによって必要な計算時間が大きく異なってくるのです」と説明しました。

 また、「現実の問題をコンピュータで解くためには、その問題を『グラフ』などコンピュータが理解できる形式で表す必要があります。グラフというのは、棒グラフや折れ線グラフではなく、頂点と辺で構成される要素のつながりを抽象化したものです。2点の最短距離や友人関係など、さまざまな現実の問題を統一的に扱うことができます」と説明しました。

 次に、岩田助教は「計算の難しさ」を理論的に証明する「計算量理論」に触れました。これまでに、コンピュータで計算を高速に行うために効率的に働くアルゴリズムが開発されてきましたが、その一方で、100万ドルの懸賞金がかけられている数学の七つの未解決問題の一つ「P≠NP予想」(*1)のように、効率的な計算方法が存在しないであろうと信じられている問題があります。ところが、理論上は解くのが難しいはずの問題が実際には現実には解けていることがあります。岩田助教は、「効率化の限界というのは、『どんな入力に対しても』速いアルゴリズムが存在しないのではなく、『特殊ケース』に対してはもっと速いアルゴリズムがあるかもしれない、ということ」と説明。「現実の入力は、特殊ケースです。地図グラフの性質、友人グラフの性質など、特殊な性質がある入力に対するアルゴリズムと計算量を考える必要があります」と話しました。

pic_shimin_report_h30_6-2.jpgpic_shimin_report_h30_6-3.jpg

 そこで、岩田助教は、特殊なグラフの例として、閉路がない「木」の形状のグラフを挙げ、「木っぽいグラフ」のある数点を取り除くと、大きさを半分くらいに分割することができ、その分計算が速くなると説明。「実際の問題は割と木っぽい。例えば、最短路を考える場合、遠くに行くために現実では高速道路に乗ります。だから、インターチェンジの距離を前計算しておけば、グラフを小さく分けて考えられるから計算が速くなります」と具体例を交えて分かりやすく解説しました。

 講義終了後の質疑応答で、参加者から「研究をしていて、一番おもしろいと感じるのはどんな時ですか」という質問がありました。これに対し、岩田助教は「突如、アイデアがパッとひらめいた瞬間です」と答えましたが、続けて、「でも、そのアイデアを論文にするのはすごく大変です。考えるのは楽しくて、そこから先は辛い部分です」と、研究者としての苦労を明かしました。

 次回は、「テラヘルツ電磁波の新展開-遠赤外線はコーヒー豆を煎るだけではない-」と題して、平川 一彦 東京大学生産技術研究所 教授/国立情報学研究所 量子情報国際研究センター/新学術領域「ハイブリッド量子科学」研究メンバーが講義します。

 詳細、お申し込みは以下のウェブサイトよりお願いします。
 https://www.nii.ac.jp/event/shimin/#7th


(*1) 「P≠NP予想」:問題の集合PとNPが等しくないという予想。Pというのは多項式時間で解ける問題(効率的なアルゴリズムによって解ける問題)、NPは多項式時間で正解が本当に正しいか判定できる問題。もし、P=NPなら、あらゆるNP問題が全て多項式時間で解けることになり、それはありそうにないだろうという予想。ちなみに、P=NPだと素因数分解の難しさを利用した現代の主要な暗号は破られてしまう。

shimin 2018-report-6 page3446

注目コンテンツ / SPECIAL