近似アルゴリズムとは?

Weblio 辞書 > 同じ種類の言葉 > 情報 > コンピュータ > アルゴリズム > 近似アルゴリズムの意味・解説 

近似アルゴリズム

読み方きんじあるごりずむ
【英】:approximate algorithm

概要

厳密解を求めることが保証される厳密解法 (exact algorithm) に対して,近似解を求めアルゴリズムのこと.NP難問題に対す多項式時間アルゴリズムなど,実用的計算時間実現するために厳密性を犠牲にすることが多い.発見的手法 (heuristic algorithm) とも呼ばれる.

詳説

 組合せ最適化問題中には, 最適解求めることが現実的に困難な問題数多く存在する. どのようなアルゴリズム用いて莫大計算時間, 計算量が必要になるような問題で, 計算機性能依存するというような次元の話ではなく, 問題構造そのもの依存するという意味である. NP完全, NP困難クラス属す問題はそのような問題の代表例である. ナップサック問題 (knapsack problem), 最大カット問題 (maximum cut problem), 集合カバー問題 (set covering problem)等の整数計画問題多くはこれらのクラス分類される. これらの問題を解くアルゴリズムには, その計算時間問題規模n\, 多項式として表されるものが一般的に存在しない考えられている. しかし, 問題中のパラメータを含めると多項式時間最適解求めることができる場合もあり, そのようなアルゴリズムを弱多項式時間アルゴリズム呼び, 動的計画法, 分枝限定法の手法が用いられる.

 NP完全, NP困難問題で弱多項式時間アルゴリズム存在しないもの, あるいは問題規模大きいものについて, 対処法がないわけではない. 問題を解く際, 常に厳密な最適解が必要かどうかというと, そうとは限らない場合多々ある. つまり, 時間労力, 更には経済的負担強いて厳密解を求めるよりも, 厳密な最適解はないけれども実際的応用差し支えない程度近似解を比較速い時間で簡単に求める方が現実的であると考えられる. このような近似解を求めアルゴリズム近似アルゴリズム (approximation algorithm)と呼ぶ. 欲張り法(greedy method)に代表されるように, それらのアルゴリズム発見的探索法に基づいていることから, ヒューリスティックアルゴリズムとも呼ばれる. 近似アルゴリズムは得られる近似解の精度, つまり近似解に対応する評価関数の値と厳密解に対応するそれとの差の比率\varepsilon\, に従って, ε-近似アルゴリズム (\varepsilon-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.


近似アルゴリズム (スケジューリングの)


近似アルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/04/14 10:07 UTC 版)

近似アルゴリズム(きんじアルゴリズム、: approximation algorithm)とは、組合せ最適化問題の近似解を得るためのアルゴリズムを言う[1]。近似解とは、実行可能解(かつ問題の何らかの制約を満たす解)ではあるが、正解(厳密解)ではないものを言う。これは組合せ最適化問題の正解(すなわち最適解)であることが(厳密には)保証されないところの解を得るものである。なお、問題を変形した近似問題に対する正解を得るアルゴリズムも、元の問題に対する近似アルゴリズムと言える。




  1. ^ David P. Williamson; David B. Shmoys (2011). The Design of Approximation Algorithms. ISBN 978-0521195270. 


「近似アルゴリズム」の続きの解説一覧



近似アルゴリズムと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「近似アルゴリズム」の関連用語

近似アルゴリズムのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



近似アルゴリズムのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2021 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの近似アルゴリズム (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2021 GRAS Group, Inc.RSS