Расширение пределов разрешимости

Хотя в начале книги изучались методы эффективного решения задач, в последних главах мы какое-то время занимались классами задач, для которых, как считается, эффективных решений не существует (NP-полными и PSPACE-полными задачами).

И на основании того, что мы при этом узнали, был неявно сформирован двусторонний подход к решению новых вычислительных задач: сначала мы пытаемся найти эффективный алгоритм; а если попытка оказывается неудачной, мы пытаемся доказать его NP-полноту (или даже PSPACE-полноту).

Если один из этих двух методов оказывается успешным, вы получаете либо решение проблемы (алгоритм), либо веское «обоснование» возникших трудностей: эта задача по крайней мере не проще многих знаменитых задач из области вычислительной теории.

К сожалению, на этой стратегии далеко не уедешь. Если существует задача, которую действительно важно решить, вряд ли кто-нибудь удовлетворится вашим заявлением о том, что задача является NP-сложной1 и на нее не стоит тратить время. От вас хотят увидеть как можно лучшее решение — даже если оно и не является точным или оптимальным.

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

Но для начала рассмотрим несколько ситуаций, в которых возможно точное решение экземпляров NP-полных задач с разумной эффективностью. Как появляются такие ситуации? Вспомните основной смысл NP-полноты: экземпляры этих задач в худшем случае очень сложны и, скорее всего, не решаются за полиномиальное время.

Однако конкретный экземпляр задачи может и не оказаться «худшим случаем» — более того, может оказаться, что рассматриваемый экземпляр имеет особую структуру, которая упрощает задачу.

Итак, в этой главе мы рассмотрим ситуации, в которых можно дать количественную оценку «простоты» данного экземпляра по сравнению с худшим случаем, чтобы использовать эти ситуации при их возникновении.

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

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

Затем мы исследуем идею о том, что многие NP-полные задачи графов становятся решаемыми за полиномиальное время, если потребовать, чтобы входные данные представляли собой дерево.

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

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

Впрочем, при этом следует подчеркнуть, что основное положение остается неизменным: экспоненциальные алгоритмы очень плохо масштабируются.

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