TRIZ・ITソフトウェアキーワード：近似アルゴリズム

近似アルゴリズム

1 解説
　真の解をアルゴリズムによって得ることが不可能な問題や、解法に時間がかかる問題に対して近似値を得るためのアルゴリズムである。代表的な近似アルゴリズムであるナップザック問題では、すべての可能性を組み合わせて検証するのではなく、目的に合致するための指標単位を決定して優先的に検証するものである。数値計算に含まれるニュートン法やシンプソン法も近似アルゴリズムの一種である。
　近似アルゴリズムの中でも、そのアルゴリズムの出力する解の目的関数値と最適解の目的関数値の比（近似度）がある範囲内に収まることが保証されているもののことを特に、精度保証付き近似アルゴリズムと呼ぶ。そのような保証のないアルゴリズムは発見的手法（ヒューリスティクス）と呼ばれる。前者と後者を区別し、前者のみを近似アルゴリズムと呼ぶ場合もある。近似アルゴリズムは、主に多項式時間で厳密に解くことが難しいNP困難問題に対して考えられるが、多項式時間で計算可能な問題に対しても、より早い計算時間で解を求めるという目的で用いられることもある。アルゴリズム理論の分野においては近年の中心的話題のひとつで、さまざまな問題に対する近似アルゴリズムが考案されている。また、可能な近似度の下界値を示す近似不可能性に関する結果も多く得られており、PCP定理などが有名。例えば、最小頂点被覆問題には近似度2の単純なアルゴリズムが存在するが、近似度が定数の多項式時間アルゴリズムがないと考えられている問題もある。

2 所見
　特になし