北陸先端科学技術大学院大学 教授
上原 隆平（うえはら りゅうへい）
1965年生まれ、東京都出身。電気通信大学大学院にて論文博士（理学）を取得。キヤノン株式会社、東京女子大学助手、駒澤大学助教授などを経て、2004年に北陸先端科学技術大学院大学に着任。長年にわたりアルゴリズムや計算量の理論の観点から大きな研究成果を挙げている。コンピューティング科学研究領域長、JAISTギャラリー長。著訳書に「折り紙のすうり」「はじめてのアルゴリズム」など多数。
難しい問題を効率的に解くアルゴリズムを作成
上原研究室のメインテーマについて教えてください
私の専門分野である理論計算機科学は、難しい問題をより効率的に解く方法を考えたり、効率的に解けない問題に対してその難しさを理論的に証明したりと、数理モデル化した計算方式を数学的なアプローチで明らかにする学問になります。
おもな研究テーマとして「計算折り紙」や「ゲームやパズルの計算量」などがありますが、これらはすべてアルゴリズムで記述することができます。ではアルゴリズムとはなにか。コンピューターにおいては問題を解くときの計算方法と捉えられますが、本来は「ある目的を達成するための手順」を意味する言葉でもあります。すなわち折り紙やパズルといった、一見すると情報科学とは関係がなさそうなテーマの中にも、実はコンピューターサイエンスが隠れているのです。優れたアルゴリズムには単なる思い付き以上の理論的な保証があり、こうした効率的なアルゴリズムの理論保証も、上原研究室のメインテーマのひとつとなっています。
具体的にどのような研究をしていますか？
計算折り紙：数学者は紙と鉛筆さえあればどこでも研究できると言いますが、私の場合は紙切れ一枚あれば研究することができます。たとえば紙の“折り”を基本的な演算だと捉えると、折り紙を折るという行為はコンピューターでいうところのアルゴリズムに対応します。単純なジャバラ折りでは端から順に折り目をつけていけば簡単に折り目をつけることができますが、紙を重ねて一度に折ればもっと少ない手順で折り目をつけられるはず。実際、非常に高速にジャバラを折るアルゴリズムは存在し、そうした効率の良い折り手順を考え、その効率を理論的に評価することで、アルゴリズムの良さを示すことができます。その一方で、紙の重なりが多くなると誤差が出たり、折りにくくなったりしてしまう。こうした問題の抽象化や理論的な解析も、計算折り紙の重要なトピックとなっています。
ゲームやパズルの計算量：ゲームやパズルは理論的にいくらでも難しい問題を作ることができ、その難しさはアルゴリズムで示すことができます。それと同時にどれだけの難問でも、理論上は高スピードで解くアルゴリズムを組むことができる。そうした「この問題はこれくらい難しい」といったものを特徴づけるために、コンピューターのモデルを使用するのが一般的ですが、私はパズルや折り紙などの身近にあるものでも計算量の特徴付けができるという証明を脈々と示しているのです。
グラフアルゴリズム：折り紙にしてもパズルにしても、基本となる構造は点と線のつながりであり、グラフで表現することができます。計算量理論において、一般のグラフ上では困難だとされる問題がありますが、こうした問題はグラフを制限した場合には効率よく解ける場合があります。また、グラフ上での困難性の証明は、その問題の本質的な難しさを浮き彫りにもしてくれます。
研究成果はどのような形で応用されていますか？
アルゴリズムによる問題の抽象化はあらゆる分野で応用されており、その応用分野は建築、宇宙工学、医療、分子生物学など多岐にわたります。たとえば私たちの生活に浸透しつつあるものとして、宅配業における配送ルートの最適化が挙げられます。現在多くの配送会社では、複数の目的地を効率的に配達して回るためにはどうすれば良いのか、その最短ルートがアルゴリズムによって導き出されています。そのほか有名な例としては、海外の医療現場でインターン生と病院をマッチングする際に、双方が満足できるような最適化をアルゴリズムが行っています。
また、私自身は段ボールを生産する際に出るゴミを最小化する展開図の作成といった、環境保全を視野に入れたアルゴリズムの研究にも取り組んでいるほか、バイオインフォマティクスなどの研究現場で使われる、膨大な塩基配列データをグラフでモデル化して、そのカタログを作成して公開しています。
何よりも大切なのは、考え続けられる胆力と好奇心
上原研究室の特徴は？
プログラミングの理解を深めるためにアルゴリズムを学ぼうとする人、折り紙やパズルを数学的なアプローチで研究したい人など、なにを目的とするかは人それぞれですが、総じて考えることが好きな学生が集まっている印象があります。
アルゴリズムの研究をする上で、必要な知識や経験はありますか？？
離散数学やグラフ理論などの数学的な基礎知識、アルゴリズムとデータ構造に関する知識は必須となりますが、それらはJAISTに入学してからでも習得できるものです。それよりも大切なのは、考えることが好きであること。好きなことについてずっと考え続けられる好奇心と胆力こそが、研究開発には不可欠なのです。折り紙のような単純なモデルでも研究されていない領域は数多くあり、そこから面白い研究テーマを思いつけば論文にすることができる。どういった部分に目を付けるかが大切であり、必ずしも豊富な知識が必要になるとは限りません。
研究で学べること、身につくことは？
難しいとされる問題の何が難しく、どこに難しさの本質があるのか。そのエッセンスを抽象化して、上手く説明するのがこの分野の研究の醍醐味だと思っています。そうした研究によって、世の中にある非常に複雑な事柄をモデル化して、なぜ難しいのかを解析できる。そんな能力が身につくのではないでしょうか。また、研究活動においては十分なプレゼンテーション能力を身につけることができるほか、知的な基礎体力や長期的な問題解決能力も向上します。
アルゴリズム的思考はどんな分野でも通用する
学生を指導する上で大切にしていることはありますか？
まずは研究テーマとゴールをはっきりさせること。その上でゴールに向かう途中途中に、いくつかのサブゴールを設定するように促しています。中間地点で目標を達成することで、それを足がかりにしてさらに前に進むことができる。サブゴールの存在によって、漠然としか見えないゴールの世界がより鮮明にイメージできるようになると考えています。
学生の就職先は？
メーカー系SEとしてソフトウェアの設計や開発に携わるケースが多いですね。ほかにも情報通信業や情報処理産業、教育システムのWebサービス関連会社、パズルの制作会社など就職先は様々です。アルゴリズムは問題を解決するための手順や方法を数理的に考える道具であり、そういった意味ではどの分野にも通用するものなのではないでしょうか。
上原研究室の今後の目標は？
まずは引き続き、困難な問題を効率的に解くアルゴリズムの研究を進めていくこと。それと同時に、本校に併設されているJAISTギャラリーを通じて、これまで以上にパズルや折り紙の学問としての認知度を高めていきたいと思っています。
教えて！上原教授のプライベートな話
アルゴリズムの研究をはじめたきっかけは？
子どもの頃から電子工作が好きで、はんだごてを使ってよくラジオなんかを作っていました。大学でコンピューターを扱うようになってからはプログラムを書くのにハマって、プログラムを書いているうちに今度は数学に興味を持つようになって。当時はコンピューターにアルゴリズムを実装して、パズルを解いたりもしていましたね。
大学時代の思い出は？
大学の教員と共同でパズルに関する論文を書いたことでしょうか。それまでパズルは趣味として嗜んでいた程度で、研究の題材にしたことはありませんでした。そのときの経験が現在の研究の源流となっていると思うと、感慨深いものがありますね。
休日のリフレッシュ法を教えてください
自転車を漕いでいるときが一番幸せですね。脳のスイッチを切り替えるツールとしても優秀で、時折パッと頭の中に特殊な展開図が浮かんでくることがあるんです。それと海外出張したときはジョギングを欠かしません。観光名所をルートにして10kmほど。観光もできるし、運動もできるし、一石二鳥。いや、時差ボケが解消できて、土地勘も身につくし、それ以上かもしれませんね。
関連リンク