Approximation algorithm: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Approximation algorithm''' --- аппроксимирующий алгоритм. For the ''travelling salesman problem'', as indeed for any other ''intractabl…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Approximation algorithm''' | '''Approximation algorithm''' — ''[[аппроксимирующий алгоритм]].'' | ||
For the ''travelling salesman problem'', as indeed for any other | For the ''travelling salesman problem'', as indeed for any other | ||
''intractable problem'' it is useful to have a polynomial time algorithm which will | ''intractable problem'' it is useful to have a polynomial time [[algorithm]] which will | ||
produce, within known bounds, an approximation to the required result. | produce, within known bounds, an approximation to the required result. | ||
Such algorithms are called '''approximation algorithms'''. Let <math>L</math> be | Such algorithms are called '''approximation algorithms'''. Let <math>\,L</math> be | ||
the value obtained (for example, this may be the length of a travelling salesman's | the value obtained (for example, this may be the length of a travelling salesman's | ||
circuit) by an approximation algorithm and let <math>L_{0}</math> | circuit) by an approximation algorithm and let <math>\,L_{0}</math> | ||
be an exact value. We require a performance guarantee for | be an exact value. We require a performance guarantee for | ||
the approximation algorithm which could, | the approximation algorithm which could, for a minimisation problem, be stated in | ||
the form: | the form: | ||
| Строка 14: | Строка 14: | ||
For a maximisation problem | For a maximisation problem | ||
we invert the ratio <math>L/L_{0}</math>. Of course, we would like <math>\alpha</math> to be | we invert the ratio <math>\,L/L_{0}</math>. Of course, we would like <math>\,\alpha</math> to be | ||
as close to one as possible. | as close to one as possible. | ||
Unfortunately, not every heuristic produces a useful approximation algorithm. | Unfortunately, not every heuristic produces a useful approximation algorithm. | ||
Текущая версия от 14:29, 2 декабря 2011
Approximation algorithm — аппроксимирующий алгоритм.
For the travelling salesman problem, as indeed for any other intractable problem it is useful to have a polynomial time algorithm which will produce, within known bounds, an approximation to the required result. Such algorithms are called approximation algorithms. Let [math]\displaystyle{ \,L }[/math] be the value obtained (for example, this may be the length of a travelling salesman's circuit) by an approximation algorithm and let [math]\displaystyle{ \,L_{0} }[/math] be an exact value. We require a performance guarantee for the approximation algorithm which could, for a minimisation problem, be stated in the form:
[math]\displaystyle{ 1 \leq L/L_{0} \leq \alpha. }[/math]
For a maximisation problem we invert the ratio [math]\displaystyle{ \,L/L_{0} }[/math]. Of course, we would like [math]\displaystyle{ \,\alpha }[/math] to be as close to one as possible.
Unfortunately, not every heuristic produces a useful approximation algorithm.