Совершенный алгоритм. Алгоритмы для NP-трудных задач - четвертая и заключительная часть лекций от Тима Рафгардена.
Для NP-трудных задач мы снова имеем треугольник, в котором для решения предлагается выбрать две характеристики из трех:
Универсальность
Правильность (точность)
Скорость
Компромисс по универсальности рассмотрен вскользь на примере задач о рюкзаке и взвешенном независимом множестве (максимизация суммы весов несмежных вершин). Хотелось бы больше примеров на эту тему ведь данный подход может дать наилучший результат. Тут и там можно встретить дополнительные примеры частных случаев, но какая-либо систематизация по данной теме не приводится.
Неточные алгоритмы - самые многочисленные из рассмотренных в книге:
Алгоритмы Грэма и LPT (Longest Processing Time First) - жадные алгоритмы назначения заданий (минимизация производственной продолжительности)
Жадный алгоритм максимизации охвата элементов заданными подмножествами
Жадный алгоритм максимизации влияния (активация максимального числа вершин графа через заданный бюджет затравочных вершин)
Эвристический алгоритм ближайшего соседа для задачи коммивояжёра и улучшение тура двукратной заменой и локальным поиском
Небыстрых алгоритмов в книге рассмотрено еще меньше:
Алгоритм Беллмана-Хелда-Карпа для поиска тура с минимальной суммой рёберных стоимостей
Раскраска графа и использование панхроматических путей в задаче поиска самого дешёвого k-вершинного пути
Использование дискретных оптимизаторов MIP (Mixed Integer Programming) и решателей выполнимости булевых формул SAT (SATisfiability)
Как видно, собственно алгоритмов в книге представлено немного. При этом, 4-я часть самая большая по количеству страниц (304) в данной серии. Нельзя сказать, что каждый алгоритм прям разжёван до полной усвояемости. Частенько приходится посидеть с карандашом и бумагой, чтобы разобраться откуда что взялось и почему. Тем не менее, следуя стилям предыдущих трёх частей, автор старается объяснить каждую задачу, идею решения, разбирает примеры, приводит алгоритм и анализирует его характеристики. Это не каталог алгоритмов. Это лекции. И в четвёртой части лекций об алгоритмах теория занимает центральное место. И, как замечает сам автор, это лишь введение в NP-трудные задачи. Я бы сказал, что даже не вершина айсберга (автор приводит массу ссылок на дополнительную информацию по рассматриваемым темам). Возможно, вся эта теория - и не самая ценная информация для практика, который ждёт каталога готовых решений. Однако, без неё может быть сложно не только понять готовый алгоритм, но и вовсе сориентироваться в массе доступного инструментария.
Разбавляет всю эту теорию разбор примера перераспределения спектра радиочастот в США - реальная большая задача с массой особенностей. Для её решения была применена широкая номенклатура из того, что описано в книге. Подобный наглядный пример хорошо иллюстрирует введение в теорию NP-трудных задач.
Не могу сказать, что завершающая часть - лёгкое завлекающее чтиво. Приходится и вчитываться, и перечитывать, и математики хватает. Но, если у вас не было соответствующего курса в университете, то "Совершенный алгоритм. Алгоритмы для NP-трудных задач" - неплохая замена для старта в данной области. Считаю, что хорошо подойдёт и студентам ввиду детального разбора основ.
С полным оглавлением можно ознакомиться на сайте издательства: здесь.
Отзывы об остальных частях серии:
