Эффективные алгоритмы для NP-полных проблем

NP-полные проблемы требуют обращения с помощью алгоритмов с экспоненциальной сложностью. Это означает такие большие затраты на вычисления, которые при определенных постановках задач находятся на границе того, что практически может быть осуществлено, а в некоторых случаях даже за пределами этих возможностей. Поэтому особенно важно для решения NP-проблем  иметь возможно более эффективные алгоритмы.

NP-полные проблемы всегда можно понимать как проблемы поиска. Недетерминированной Т-машине мы можем предписать конечное дерево с ограниченной числом v степенью разветвления и с ограниченной полиномом р(п) его высотой. Детерминированный алгоритм должен по-существу обойти (просмотреть) это дерево, содержащее 0(vP(^) вершин. Часто NP-полные проблемы представляют собой задачу оптимизации типа «найти кратчайший путь», «найти оптимальный ход» и т. п.

Для эффективной обработки - в рамках экспоненциальной сложности - для NP-полных проблем можно выбирать, в частности, следующие методы.

(1)        Branch and Bound (искусный бэктрекинг).

Поиск в пространстве решений организуется целенаправленно:

·

в первую очередь проходятся легко вычисляемые ветви;

·         своевременно распознанные как неинтересные ветви обрезаются и не проходятся полностью.

К тому же, в частности, пытаются пространство решений трактовать как многомерное пространство. Для многих задач это вытекает уже из самих их постановок (найди вектор определенной длины, найди множество определенной мощности).

(2)        Приближенные методы. В ряде постановок задач требуется найти оптимальное решение (например, кратчайший путь). Однако иногда достаточно иметь примерно оптимальное решение, благодаря чему может быть редуцирована сложность задачи. В таких случаях требуется найти компромисс между затратами и неполной оптимальностью.

(3)        Динамическое программирование. При динамическом программировании число подлежащих исследованию кандидатов при наивном поиске уменьшается за счет более искусного образа действий.