堀山研究室の紹介

 堀山研究室では、情報処理技術の基礎としての 「アルゴリズム」の研究、 もう少し踏み込んで言うと「組合せ最適化」のための アルゴリズムの研究を行っています。 計算の本質的な複雑さとは何かを考え、 アルゴリズムの設計と解析に関して理論的なアプローチをしようと取り組んでいます。

研究室に来ると...

こうした能力は、例えば企業に入って 新しいことに挑戦する時、 研究職について 世界の最先端を切り開く時、 あなたの力になってくれます。

研究テーマ

 重要な組合せ問題なのに未解決、 という問題が世の中には沢山あります。 どうやって解くのか分からないのは、最初は誰だってそうです。 世界初のアルゴリズムを設計したり、 問題の構造を利用することで 従来のアルゴリズムより良いアルゴリズムを設計したり、 ということを目指して一緒にチャレンジしてみませんか。 以下は、研究テーマの例です。

オンライン問題

 後悔先に立たずという諺があります。 後になってから「あの時こうしてれば」 と思う経験は誰しもありますが、 これは、将来の情報がない状態で決断した行動と、 何とを比べているのでしょうか? 後から振り返ることで、「あの時」以降の将来の情報を持っていると仮定した場合の 最良の行動と比較して、あまり良くないと思う訳です。

 これをモデル化したのがオンライン問題です。 普段の授業で習うアルゴリズムは、 入力がポンとすべて与えられて、 何らかの条件を満たす最良の解を求めるものですよね。 しかし、将来の情報が分からない状況で、 入力が全部そろうまで待ってください という訳にはいきません。 オンライン アルゴリズムは、時系列にそって与えられる入力を順に受け取って、 その各時点で、それまでの入力をもとにその時に取るべき行動を決定します。 下手をすると、将来の入力を知っていれば絶対しないような行動を 選択することもあり得る訳です。 しかし、良いオンライン アルゴリズムを設計すると、 どんな入力が将来やってきても大きく後悔することはない、 しかも失敗をうまくリカバーする、ということができます。

メカニズム デザイン (オークション)

 オークションを例にとって考えてみましょう。 オークションには競売人と複数の入札者が参加します。 商品が1つの場合にお馴染みなのは、入札者が競り上げていく方法 (English auction) だと思います。 では、音楽ファイルのダウンロード販売など、 コピーのコストが無視できるほど小さく、 商品を無限にたくさん供給できる場合には、 どんなオークションにすれば良いでしょう?

 たとえば、各入札者は1回だけ入札する、 入札額は他の入札者には分からない (秘密入札) というオークションを考えてみます。 競売人と 複数の入札者は、 それぞれ自分の利益が最大となるように行動します。

 商品は無限にたくさんありますから、 売れば売るだけ競売人は儲かります。 入札額よりも高い値段では売れませんので、 競売人の利益を多くするには、 各入札者にその人の入札額そのままの価格で販売する、 というアルゴリズムを採用すれば良いように一見思います。 しかし、入札者がこの仕組みを知っていれば、 誰も正直に入札しなくなります。 入札者は自分の利益が最大になるように行動しますので、 必ず入札額通りの値段で買えると分かっていれば、 たとえ100万円の価値があると思っている商品でも、 1円で入札する訳です。 これでは、競売人の利益を最大化するはずが、 無残な結果になりますね。

 入札額から販売額を決める良いアルゴリズムを設計すると、 入札者が自分自身の利益を最大化するには 自分が思っている価値通りの額で入札するのが最良の戦略となります。 (誘因両立性を持つといいます。) このように、オークションのメカニズムを うまく設計することで、 自分の利益しか考えていない入札者に、 正直に入札させることができるようになります。

アルゴリズム論的ゲーム理論

列挙

 計算機の能力は、毎年すさまじく上がっていきます。 この能力を活かせば、問題の解を 1つだけではなく、何個も出せそうですよね。 ここで、1つの解を求めてから別の解を求めるのに、 また最初から考え直しだと時間がかかります。 そこで、問題の構造を利用して、効率よく列挙していこうという研究です。 これまでに、グラフの構造を利用した、様々な列挙アルゴリズムが提案されています。 グラフ以外の問題にも列挙アルゴリズムのアプローチを適用したいと考えています。

タイリングの列挙について、 「研究のお話」のページに書いています。

組合せ問題

 組合せ問題、特に組合せ最適化問題は、 与えられた条件を満たす解 (組合せ) のうち 最良のものを求めようという問題です。 何をもって良いというかの指標として 目的関数が与えられ、 これを最大 (または最小) にする解を求めようという訳です。 こちらの条件を満たすようにちょっと解を修正したら、 今度は別の条件を満たさなくなって… という意味で、パズルみたいなものですね。

 例えば、遠足のおやつをリュックに詰めていると思ってください。 「おやつは 500円まで」 の制約条件を満たす組合せ方のうち、好みをできるだけ反映させたものが、 「良い解」になります。 (これは、ナップザック問題 と呼ばれる有名な問題です。) 最も良い解は、求められますか?

 組合せ最適化問題を解こうとする場合、 最良の解を高速に求めるアルゴリズムがないか、 まず考えてみましょう。 不幸にして問題が難しい (NP困難など) と分かった場合には、 最適解を求めるには指数時間の計算がかかる可能性が濃厚ですが、 ここであきらめてはいけません。

 最良という条件を少しだけ緩めて、高速に解けないか考えてみます。 これが、最適解にどれだけ近いかを理論的に保証した 近似アルゴリズムの設計です。 たとえば、巡回セールスマン問題を例に考えてみます。 三角不等式が成り立つ距離空間上で、最小全域木を作ると、 これをもとに2倍近似のルートを簡単に見つけることができます。 また、マッチングを利用することで、 これを1.5倍近似のアルゴリズムに改良できることも知られています。

SAT

 論理式の充足可能性を判定する問題を SAT (satisfiability problem) といいます。 NP 完全性を示された最初の問題で、 情報科学の分野で現れる様々な問題と密接にリンクしています。 NP 完全な問題を多項式時間で解くアルゴリズムは見つかっていず、 また、理論計算機科学の研究者のほとんどは、 そのようなアルゴリズムは存在しないだろうと考えています。 (P ≠ NP 問題と呼ばれる懸賞問題で、100万ドルの賞金がかかっています。) でも、現実的な要請を考えると、 何とかして解く方法を考えないといけません。

 SAT は、単純に考えると、各変数に 0, 1 の2通りの割り当てをすべて試して、 2n に比例する時間で解くことができます。 これをもっと速く解こうというレースが世界レベルで行われています。 論理式の形を 3-CNF に限定した 3-SAT では、 その 3-CNF という形が与える情報を利用して、 1979年に 1.769n 時間のアルゴリズムが発表されました。 その後、少しずつ進歩していって、現在の最速は 決定性アルゴリズムで 1.473n、 確率的アルゴリズムで 1.329nです。 どれだけ速くなったか分かりますか? ちょっと計算してみてください。 2n と 1.329n の比は、 たった 1,000 変数 (n = 1000) で、3 x 10177倍も速く なります。

おまけ : 3 x 10177 を、べき乗を使わずに書くと、 10000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000 と、とんでもなく大きくなります。


[ 戻る ]
horiyama [ @ ] al.ics.saitama-u.ac.jp