В информатике и исследовании операций , точные алгоритмы являются алгоритмами , которые всегда решают проблему оптимизации для оптимальности.
Если P = NP , точный алгоритм для NP-сложной задачи оптимизации не может работать за полиномиальное время наихудшего случая . Были проведены обширные исследования по поиску точных алгоритмов, время работы которых экспоненциально с низкой базой. [1] [2]
Смотрите также
- Приведение с сохранением приближения
- APX - это класс задач с некоторым алгоритмом аппроксимации с постоянным коэффициентом.
- Эвристический алгоритм
- PTAS - тип алгоритма аппроксимации, который принимает коэффициент аппроксимации в качестве параметра
Рекомендации
- ^ Фомин, Федор В .; Kaski, Петтери (март 2013 г. ), "Точные экспоненциальные алгоритмы" , коммуникаций АСМ , 56 (3): 80-88, DOI : 10,1145 / 2428556,2428575.
- ^ Фомин, Федор В .; Kratsch, Дитер (2010). Точные экспоненциальные алгоритмы . Springer. п. 203 . ISBN 978-3-642-16532-0.