「Ε-近似アルゴリズム」の版間の差分

2007年7月11日 (水) 15:35時点における版

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

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

${\frac {|f({\widehat {x}})-f(x^{*})|}{f(x^{*})}}\leq \varepsilon \,$

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

@@ 1行目: / 1行目: @@
 '''【いぷしろんきんじあるごりずむ (&epsilon;-approximation algorithm)】'''
-最適化問題の近似解を求める近似アルゴリズムについて, 目的関数(適応度関数)を$f(x)$, 最適解を$x^*$, また近似アルゴリズムによって得られる近似解を$\widehat{x}$としたとき, どのような問題例であっても\[ \frac{|f(\widehat{x})-f(x^*)|}{f(x^*)} \leq \varepsilon \]を満たすものを$\varepsilon$-近似アルゴリズムという. ただし, $f(x^*)>0$を仮定しており, $0\leq \varepsilon$である. $\varepsilon $が0に近いほど精度の高い近似アルゴリズムとなる.
+最適化問題の近似解を求める近似アルゴリズムについて, 目的関数(適応度関数)を<math>f(x) \,</math>, 最適解を<math>x^* \,</math>, また近似アルゴリズムによって得られる近似解を<math>\widehat{x} \,</math>としたとき, どのような問題例であっても
+<math>
+ \frac{|f(\widehat{x})-f(x^*)|}{f(x^*)} \leq \varepsilon
+\,</math>
+を満たすものを<math>\varepsilon \,</math>-近似アルゴリズムという. ただし, <math>f(x^*)>0 \,</math>を仮定しており, <math>0\leq \varepsilon \,</math>である. <math>\varepsilon  \,</math>が<math>0 \,</math>に近いほど精度の高い近似アルゴリズムとなる.