Точный алгоритм - Exact algorithm

В Информатика и исследование операций, точные алгоритмы находятся алгоритмы которые всегда решают проблему оптимизации до оптимальности.

Пока не P = NP, точный алгоритм для NP-жесткий проблема оптимизации не может работать в худшем случае полиномиальное время. Были проведены обширные исследования по поиску точных алгоритмов, время работы которых экспоненциально с низкой базой.^[1][2]

Смотрите также

• Приведение с сохранением аппроксимации
• APX класс задач с некоторым алгоритмом приближения постоянного множителя
• Эвристический алгоритм
• PTAS - тип алгоритма аппроксимации, который принимает коэффициент аппроксимации в качестве параметра

Рекомендации

1. Фомин, Федор В .; Каски, Петтери (март 2013 г.), «Точные экспоненциальные алгоритмы», Коммуникации ACM, 56 (3): 80–88, Дои:10.1145/2428556.2428575.
2. Фомин, Федор В .; Kratsch, Дитер (2010). Точные экспоненциальные алгоритмы. Springer. п.203. ISBN  978-3-642-16532-0.