Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Эффективные алгоритмы для NP-полных проблем
NP-полные проблемы требуют обращения с помощью алгоритмов с экспоненциальной сложностью. Это означает такие большие затраты на вычисления, которые при определенных постановках задач находятся на границе того, что практически может быть осуществлено, а в некоторых случаях даже за пределами этих возможностей. Поэтому особенно важно для решения NP-проблем иметь возможно более эффективные алгоритмы.
NP-полные проблемы всегда можно понимать как проблемы поиска. Недетерминированной Т-машине мы можем предписать конечное дерево с ограниченной числом v степенью разветвления и с ограниченной полиномом р(п) его высотой. Детерминированный алгоритм должен по-существу обойти (просмотреть) это дерево, содержащее 0(vP(^) вершин. Часто NP-полные проблемы представляют собой задачу оптимизации типа «найти кратчайший путь», «найти оптимальный ход» и т. п.
Для эффективной обработки - в рамках экспоненциальной сложности - для NP-полных проблем можно выбирать, в частности, следующие методы.
(1) Branch and Bound (искусный бэктрекинг).
Поиск в пространстве решений организуется целенаправленно:
·
в первую очередь проходятся легко вычисляемые ветви;
· своевременно распознанные как неинтересные ветви обрезаются и не проходятся полностью.
К тому же, в частности, пытаются пространство решений трактовать как многомерное пространство. Для многих задач это вытекает уже из самих их постановок (найди вектор определенной длины, найди множество определенной мощности).
(2) Приближенные методы. В ряде постановок задач требуется найти оптимальное решение (например, кратчайший путь). Однако иногда достаточно иметь примерно оптимальное решение, благодаря чему может быть редуцирована сложность задачи. В таких случаях требуется найти компромисс между затратами и неполной оптимальностью.
(3) Динамическое программирование. При динамическом программировании число подлежащих исследованию кандидатов при наивном поиске уменьшается за счет более искусного образа действий.
