近似アルゴリズム
【きんじあるごりずむ (approximate algorithm)】
概要
厳密解を求めることが保証される厳密解法 (exact algorithm) に対して,近似解を求めるアルゴリズムのこと.NP困難問題に対する多項式時間アルゴリズムなど,実用的な計算時間を実現するために厳密性を犠牲にすることが多い.発見的手法 (heuristic algorithm) とも呼ばれる.
詳説
組合せ最適化問題の中には, 最適解を求めることが現実的に困難な問題が数多く存在する. どのようなアルゴリズムを用いても莫大な計算時間, 計算量が必要になるような問題で, 計算機の性能に依存するというような次元の話ではなく, 問題の構造そのものに依存するという意味である. NP完全, NP困難なクラスに属する問題はそのような問題の代表例である. ナップサック問題 (knapsack problem), 最大カット問題 (maximum cut problem), 集合カバー問題 (set covering problem)等の整数計画問題の多くはこれらのクラスに分類される. これらの問題を解くアルゴリズムには, その計算時間が問題の規模の多項式として表されるものが一般的には存在しないと考えられている. しかし, 問題中のパラメータを含めると多項式時間で最適解を求めることができる場合もあり, そのようなアルゴリズムを弱多項式時間アルゴリズムと呼び, 動的計画法, 分枝限定法等の手法が用いられる.
NP完全, NP困難な問題で弱多項式時間アルゴリズムも存在しないもの, あるいは問題規模の大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合も多々ある. つまり, 時間と労力, 更には経済的負担を強いて厳密解を求めるよりも, 厳密な最適解ではないけれども実際的な応用に差し支えない程度の近似解を比較的速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めるアルゴリズムを近似アルゴリズム (approximation algorithm)と呼ぶ. 欲張り法(greedy method)に代表されるように, それらのアルゴリズムが発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率に従って, ε-近似アルゴリズム (-approximation algorithm)という性能表現がなされ, 最近ではPTAS (polynomial time approximation scheme)のような新たな枠組みによる近似アルゴリズムの性能評価, 研究が行われている.
近似解法に関する研究は盛んに行われ, より精度の高い近似解を, より速く求めるために, 最近ではメタヒューリスティックスあるいはモダンヒューリスティックスと呼ばれる枠組が注目を集めている. この中の主なものとしてアニーリング法, タブー探索法, 遺伝的アルゴリズム等が挙げられるが, 基本的にこれらの手法は近似解を局所探索法 (local search)に基づき改善してゆくというものであり, 解の近傍生成法, 探索則, 解の更新則が性能評価のポイントとなる. つまり, 人間の発見的知識をどのような形でアルゴリズムに反映させるかということが非常に重要であり, 「メタ」と呼ばれる所以である.
参考文献
[1] C. R. Reeves, Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, 1993. 横山隆一, 奈良宏一, 佐藤晴夫, 鈴木昭男, 荻本和彦, 陳洛南 訳,『モダンヒューリスティックス』, 日刊工業新聞社, 1997.
[2] R. Sedgewick, Algorithms, 2nd ed., Addison Wesley, 1988. 野下浩平, 星守, 佐藤創, 田口東 訳,『アルゴリズム 第3巻』, 近代科学社, 1992.
[3] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, John Wiley & Sons, 1998.
[4] T. C. Hu, Combinatorial Algorithms, Addison Wesley, 1982.
[5] A. V. Aho, J. E. Hopcroft and J. D. Ullman, Data Structures and Algorithms, Addison Wesley, 1983.