Труднорешаемые задачи, в первую очередь NP-полные задачи, не имеющие полиномиального алгоритма для нахождения оптимальных решений, можно попытаться решить с помощью приближенного полиномиального алгоритма. Получаемое при этом решение не оптимальное, а некоторое приближение к нему, которое на практике может оказаться вполне приемлемым. Алгоритмы, дающие такие решения, называются приближенными алгоритмами.
Система оценок приближенных алгоритмов:
- Для оптимизационных задач можно говорить о решении с ошибкой не более, чем в r(n) раз. Если C* - оптимальное решение, а C – приближенное, то должно выполняться неравенство 1£ max (C/C*, C*/C) £ r(n).
Иногда качество алгоритма оценивают через относительную ошибку
çC – C*ú / C £ e (n) для входа длины n.
- Для некоторых задач r, e не зависят от длины входа n, в других случаях приходится довольствоваться алгоритмами, в которых оценка ошибки растет с ростом n.
- Иногда можно улучшить качество приближения, увеличив время работы алгоритма, которое будет ограничено полиномом p(n, 1/e), где n -длина входа и e - оценка относительной ошибки.
Далее рассматриваются полиномиальные приближения для трех NP-полных задач с разными оценками качества приближенных алгоритмов.
