HOME > 研究紹介 > アルゴリズム論研究室

研 究 紹 介
アルゴリズム論研究室 homepage
情報数理分野 山本 真基 准教授

アルゴリズムの設計と解析

アルゴリズムとは、問題を解くための機械的手順のことです。問題とは、例えば、足し算や掛け算といった四則演算を始め、素数判定問題、整列問題、最短経路問題、巡回セールスマン問題といったように、コンピュータで解くことのできる問題のことです。アルゴリズムの良し悪しで、問題を解く「効率」に大きな差が生じてきます。どのようにアルゴリズムを設計したら効率がよくなるか、アルゴリズムの設計及び解析を行っています。

アルゴリズム論研究室の研究テーマ

アルゴリズムの設計と解析が当研究室のメインテーマです。このテーマに関して当研究室が行っているものは、大まかに以下の研究項目があります。
1. アルゴリズムの新提案及び改良とその理論的解析
2. ヒューリスティックアルゴリズムの提案とその実験的評価
3. 既存アルゴリズムの平均時計算量の実験的評価
それ以外では、以下のような研究項目があります
4. 離散最適化問題に対するNP完全性の証明
5. 離散数学の問題、組合せ的ゲーム・パズルの問題など

アルゴリズムの新提案及び改良とその理論的解析

この研究項目が当研究室のメインテーマです。例えば、理論計算機科学の分野に充足可能性問題(SAT問題)という問題があります。これは、NP完全問題と呼ばれる問題であり、高速に(多項式時間で)解くことができないと考えられている問題です。一方で、指数時間をかければ、SAT問題を解くことは可能です。(例えば、解を全探索することにより。)とりわけ、SAT問題の特殊な問題、3SAT問題について、アルゴリズムの新提案及び改良、そして、解析手法の研究が活発になされています。n を変数の個数とした場合、決定性アルゴリズムでは O(1.3303^n) [1] が、乱択アルゴリズムでは O(1.308^n) [2] が、現在(2013年7月)の最速となっています。
[1]: K. Makino, S. Tamaki, and M. Yamamoto, Derandomizing HSSW algorithm for 3-SAT, COCOON2011.
[2]: T. Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General, FOCS2011.
この問題以外にも、多項式時間計算可能であると示された問題を含め、様々な離散最適化問題に対して、アルゴリズムの新提案及び改良とその理論的な解析を行っています。

ヒューリスティックアルゴリズムの提案とその実験的評価

一般に、理論的に解析ができるアルゴリズムは、その記述が単純なものに限られます。(複雑になればなるほど、理論的な解析が難しくなります。)一方で、実社会で使われているアルゴリズムは、様々なヒューリスティックが用いられているため、通常、より複雑な記述になっています。どのようなヒューリスティックを用いたらより効率がよくなるか、ヒューリスティックアルゴリズムの提案とその実験的評価を行っています。

既存アルゴリズムの平均時計算量の実験的評価

アルゴリズムの解析は、計算時間や計算領域といった「計算量」の解析となります。計算量の理論的な解析の多くは、最悪時計算量と呼ばれる計算量の解析です。これは、最悪時の例題における計算量です。最悪時の例題が稀である場合、特に、実社会への応用を考えた場合、平均時の計算量を解析することが重要になります。一般に、平均時計算量の理論的な解析は、最悪時計算量のそれに比べてより難しいものになります。最悪時計算量が示された既存アルゴリズムが、平均的にはどの程度の計算量であるのか、既存アルゴリズムの平均時計算量の実験的評価を行っています。

copyright(C) Seikei University. all rights reserved.