Approximation algorithm: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Approximation algorithm''' --- аппроксимирующий алгоритм. For the ''travelling salesman problem'', as indeed for any other ''intractabl…»)
 
Нет описания правки
 
Строка 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, for a minimisation problem, be stated in
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.

Текущая версия от 16:30, 23 октября 2018

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.