効率の良いアルゴリズム: 計算困難な問題への挑戦

研究概要

計算機で解きたい問題の中には『どうしようもなく難しい』ということが理論的に示されてしまう場合があります． 難しいからといってあきらめられればよいのですが，そうも言っていられません． こうした『計算が困難な問題』に対して，何らかの妥当性をもつ解を，現実的な時間で与えることが 上原研究室のメインテーマです．

多くの問題はグラフと呼ばれる，点と線だけを使って表現することができます． こうしたモデル化や定式化を行ない，どちらかといえば理論的，基礎的な研究をしています． 上記の妥当性として，具体的には次の３つのアプローチで研究を進めています． これらのアプローチは独立なものではなく，組み合わせて使うとより効果的な場合もあります． もっと詳しい内容は学内向けページを御覧下さい．

入力の条件を利用する

問題をモデル化したときに，問題に固有の性質を使って，入力に制限を与えることができる場合があります． 例えば地図データなら，平面上に描くことができるし，寄り道をして距離が短くなることはありません． こうした条件を利用すると，困難な問題がなんとかなる場合があります．

近似解を求める

理論的に正確な厳密解でなくても十分な場合があります．例えば最適解を求めるには１カ月かかるけれども， 最適解の１０３％に収まることが保証されている解が１分で求まるなら， そちらを選ぶ人は多いのではないでしょうか． 最適解を求める問題は計算困難でも，近似率が保証された近似解を求める問題はなんとかなる場合があります． (最適解を求めなくても近似率を評価できる場合がある，という事実は意外かもしれません．)

確率的な方法を使う

これは乱択アルゴリズムとも呼ばれています．具体的には乱数を利用した計算です． もっと簡単に言えば，コインを投げ，その結果に応じて次に行なう処理を決める計算方法です． 例えばx回コインを投げて「連続して表が出た長さ」の最大値を求めると， それだけで関数 log x を計算することができます． ( この話をもっと詳しく知りたい人はこちらを参照して下さい．) このように，乱数を使わない場合よりも，ずっと単純な方法で問題が解決できたり， ずっと高速に解を計算できることがあります．

Last modified: Mon Feb 7 13:12:48 JST 2005 by R.Uehara (uehara@jaist.ac.jp)