Ε-近似アルゴリズムのソースを表示

'''【いぷしろんきんじあるごりずむ (&epsilon;-approximation algorithm)】'''

最適化問題の近似解を求める近似アルゴリズムについて, 目的関数(適応度関数)を<math>f(x) \,</math>, 最適解を<math>x^* \,</math>, また近似アルゴリズムによって得られる近似解を<math>\widehat{x} \,</math>としたとき, どのような問題例であっても


<center>
<math>
 \frac{|f(\widehat{x})-f(x^*)|}{f(x^*)} \leq \varepsilon 
\,</math>
</center>


を満たすものを<math>\varepsilon \,</math>-近似アルゴリズムという. ただし, <math>f(x^*)>0 \,</math>を仮定しており, <math>0\leq \varepsilon \,</math>である. <math>\varepsilon  \,</math>が<math>0 \,</math>に近いほど精度の高い近似アルゴリズムとなる.