Совершенный алгоритм. Алгоритмы для NP-трудных задач - четвертая и заключительная часть лекций от Тима Рафгардена.

Для NP-трудных задач мы снова имеем треугольник, в котором для решения предлагается выбрать две характеристики из трех:

- Универсальность

- Правильность (точность)

- Скорость

Компромисс по универсальности рассмотрен вскользь на примере задач о рюкзаке и взвешенном независимом множестве (максимизация суммы весов несмежных вершин). Хотелось бы больше примеров на эту тему ведь данный подход может дать наилучший результат. Тут и там можно встретить дополнительные примеры частных случаев, но какая-либо систематизация по данной теме не приводится.

Неточные алгоритмы - самые многочисленные из рассмотренных в книге.