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