近似アルゴリズム
出典: Wikipedio
|
|
近似アルゴリズム（きんじアルゴリズム）とは、最適化問題の近似解を得るための多項式時間アルゴリズムのこと。近似解とは、実行可能解（問題の制約を満たす解）ではあるが最適解とは限らない解のことを指す。
近似アルゴリズムの中でも、そのアルゴリズムの出力する解の目的関数値と最適解の目的関数値の比がある範囲内に収まることが保証されているもののことを特に、精度保証付き近似アルゴリズムと呼ぶ。そのような保証のないアルゴリズムは発見的手法（ヒューリスティクス）と呼ばれる。前者と後者を区別し、前者のみを近似アルゴリズムと呼ぶ場合もある。精度保証付き近似アルゴリズムの性能は、近似度によって評価される。
近似アルゴリズムは、主に多項式時間で厳密に解くことが難しいNP困難問題に対して考えられるが、多項式時間で計算可能な問題に対しても、より早い計算時間で解を求めるという目的で用いられることもある。アルゴリズム理論の分野においては近年の中心的話題のひとつで、さまざまな問題に対する近似アルゴリズムが考案されている。また、可能な近似度の下界値を示す近似不可能性に関する結果も多く得られており、PCP定理などが有名。
関連項目
Template:Sci-stubcs:Aproximační algoritmy de:Approximationsalgorithmus en:Approximation algorithm es:Algoritmo de aproximación fa:الگوریتمهای تقریبی fr:Algorithme d'approximation he:אלגוריתם קירוב ko:근사 알고리즘 pl:Algorytm aproksymacyjny th:ขั้นตอนวิธีการประมาณ zh:近似算法
