Решение задачи построения плана с полиномиальным пространством - PSPACE: класс задач за пределами NP

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

Задача

Вспомните, что в формулировке задачи используется множество условий C = {C₁, ..., C_n} и множество операторов {O₁, ..., O_k}. Каждый оператор O_i имеет список предусловий P_i, список добавления A_i и список удаления D_i. Обратите внимание: оператор O_i может применяться и при наличии условий, не входящих в P_i, и он не влияет на условия, не входящие в A_i или D_i.

Конфигурация определяется как подмножество C' ⊆ C; состояние задачи в любой момент времени идентифицируется уникальной конфигурацией C', которая определяется условиями, действовавшими на тот момент. Для исходной конфигурации C₀ и целевой конфигурации C* требуется определить, существует ли последовательность операций, которая переходит из C₀ в C*.

Экземпляр задачи построения плана может рассматриваться в контексте очень большого, неявно определенного направленного графа G. В G существует узел для каждой из 2ⁿ возможных конфигураций (то есть для каждого возможного подмножества C); и в G существует ребро от конфигурации C' к конфигурации C'', если на одном шаге один из операторов может преобразовать C' к C''.

В контексте этого графа задача построения плана имеет очень естественную формулировку: существует ли в G путь из C₀ в C*? Такой путь точно соответствует последовательности операторов, приводящей от C₀ к C*.

Экземпляр задачи может иметь короткое решение (как в случае с головоломкой “15”), но в общем случае на это не стоит рассчитывать. Другими словами, в G не всегда существует короткий путь из С₀ в С* — и это неудивительно, так как в G экспоненциальное количество узлов. Однако интуицию следует применять осторожно, поскольку граф G имеет особую структуру: он очень компактно определяется в контексте n условий и k операторов.

(9.6) Существуют экземпляры задачи построения плана с n условиями и k операторами, для которых существует решение, но кратчайшее решение имеет длину 2ⁿ - 1.

Доказательство. Приведем короткий пример такого экземпляра; по сути, он кодирует задачу увеличения n-разрядного счетчика из состояния “только нули” в состояние “только единицы”.

♦ Имеются условия С₁, С₂, ..., С_n.

♦ Имеются операторы O_i для i = 1, 2, ..., n.

♦ Оператор O₁ не имеет предусловий или списка удаления; он просто добавляет С₁.

♦ Для i > 1 предусловиями O_i являются С_j для всех j < i. При вызове он добавляет С_i и удаляет С_j для всех j < i.

Вопрос: существует ли последовательность операторов, которая переводит от С₀ = φ к С* = С₁, С₂, ..., С_n}?

Следующее утверждение доказывается индукцией по i:

Из любой конфигурации, не содержащей С_j для всех j ≤ i, существует последовательность операторов, которая достигает конфигурации, содержащей С_j для всех j ≤ i; но любая такая последовательность состоит не менее чем из 2ⁱ - 1 шагов.

Для i = 1 истинность утверждения очевидна. Для больших значений i одно из возможных решений выглядит так:

♦ По индукции достигнуть условий {С_i-1, ..., С₁} с использованием операторов O₁, ..., O_i-1.

♦ Теперь вызовем оператор O_i, добавляя С_i, но удаляя все остальное.

♦ Снова по индукции достигнуть условий {С_i-1, ..., С₁} с использованием операторов O₁, ..., O_i-1. Обратите внимание: условие С_i при этом сохраняется.

Теперь разберемся со второй частью шага индукции — что любая такая последовательность требует не менее 2ⁱ - 1 шагов. Рассмотрим момент первого добавления С_i. На этом шаге С_i-1, ..., С₁должны присутствовать, и по индукции для этого должно было потребоваться не менее 2^i-1 - 1 шагов. Условие С_i может быть добавлено только оператором O_i, приводящим к удалению всех С_jдля j < i. Теперь нужно снова достичь условий {С_i-1, ..., С₁}; по индукции это потребует еще 2^i-1 - 1 шагов, что в сумме дает не менее 2(2^i-1 - 1) + 1 = 2ⁱ - 1 шагов.

Общая граница доказывается применением этого утверждения с i = n. ■

Конечно, если бы каждый “положительный” экземпляр задачи построения плана имел решение полиномиальной длины, то задача принадлежала бы NP — можно было бы просто представить решение. Но (9.6) показывает, что кратчайшее решение не обязательно является хорошим сертификатом для задачи построения плана, потому что оно может иметь длину, экспоненциальную по размеру входных данных.

Однако (9.6) фактически определяет худший случай. Граф G содержит 2ⁿ узлов, и если существует путь из С₀ в C*, то кратчайший такой путь не посещает ни один узел более одного раза. Из этого следует, что кратчайший путь может содержать не более 2ⁿ - 1 шагов после выхода из C₀.

(9.7) Если экземпляр задачи планирования с n условиями имеет решение, то он имеет и решение, использующее не более 2ⁿ - 1 шагов.

Разработка алгоритма

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

Собственно, в данном случае дело обстоит именно так: мы проектируем алгоритм для решения задачи построения плана с полиномиальным пространством.

Некоторые экспоненциальные методы

Чтобы задача стала более понятной, мы сначала рассмотрим алгоритм “грубой силы”. Построим граф G и воспользуемся любым алгоритмом связности графа (поиском в глубину или поиском в ширину) для принятия решения о том, существует ли в графе путь от С₀ к C*.

Конечно, для наших целей этот алгоритм слишком примитивен; построение графа G потребует экспоненциальных затрат пространства. Можно опробовать метод, в котором граф G реально не строится, а для него просто моделируется поведение поиска в ширину или глубину. Впрочем, это решение тоже неприемлемо; для поиска в глубину неизбежно придется вести список всех узлов в текущем исследуемом пути, а он может разрастись до экспоненциального размера. Для поиска в ширину потребуется список всех узлов текущего “фронта” поиска, который тоже может вырасти до экспоненциального размера.

Похоже, мы оказались в тупике. Наша задача по сути эквивалентна поиску пути в G, а известные нам стандартные алгоритмы поиска путей слишком неэкономны в расходовании пространства. Не существует ли принципиально иного алгоритма поиска пути?

Более эффективный по затратам пространства способ построения путей

Оказывается, принципиально иная разновидность алгоритмов поиска пути существует и обладает как раз нужными нам свойствами. Основная идея, предложенная Савичем в 1970 году, заключается в умном применении принципа “разделяй и властвуй”. Впоследствии этот прием был заложен в основу сокращения затрат пространства в задаче выравнивания последовательностей; по этой причине общий подход может напомнить то, что обсуждалось ранее в разделе 6.7. Наш план, как и прежде, основан на умном повторном использовании пространства — откровенно говоря, за счет возрастания затрат времени. Как поиск в глубину, так и поиск в ширину не проявляет достаточного рвения в повторном использовании пространства; оба должны постоянно вести большой исторический список. Нам нужен способ решить половину задачи, отбросить почти всю промежуточную работу, а затем решить другую половину задачи.

Ключевая роль в этом алгоритме отводится процедуре, которую мы назовем Path(C₁, C₂, L). Процедура определяет, существует ли последовательность операторов, состоящая не более чем из Lшагов, которая приводит из конфигурации C₁ в конфигурацию C₂. Итак, исходной задачей является определение результата (да или нет) для Path(C₀, C*, 2ⁿ). Поиск в ширину может рассматриваться как следующая реализация этой процедуры средствами динамического программирования: чтобы определить Path(C₁, C₂, L), мы сначала определяем все C', для которых выполняется Path(C₁, C', L - 1); затем мы проверяем для всех таких C', ведет ли какой-нибудь оператор напрямую из C' в C₂.

Это отчасти демонстрирует неэффективность в отношении затрат пространства, присущую поиску в ширину. Мы генерируем множество промежуточных конфигураций только для того, чтобы уменьшить параметр L на 1. Эффективнее было бы попытаться определить, существует ли какая-либо конфигурация C', которая служит срединной точкой пути из C₁ в C₂. Можно сначала сгенерировать все возможные срединные точки C'. Затем для всех C' можно рекурсивно проверить, можно ли перейти из C₁ в C' не более чем за L/2 шагов и можно ли перейти из C' в C₂ не более чем за L/2 шагов. Для этого потребуются два рекурсивных вызова, но нас интересуют только результаты “да/нет” для каждого из них; в остальном пространство можно использовать повторно.

Позволит ли этот прием сократить затраты пространства до полиномиальной величины? Сначала тщательно сформулируем процедуру, а затем проанализируем ее. Для наших целей L будет считаться степенью 2.

И снова обратите внимание на то, что эта процедура решает проблему обобщения исходного вопроса, относившегося к Path(C₀, С* 2ⁿ). Однако это означает, что L следует рассматривать как экспоненциально большой параметр: log L = n.

Анализ алгоритма

Следующее утверждение показывает, что задача построения плана может быть решена с полиномиальными затратами пространства.

(9.8) Path(C₁, С₂, L) возвращает “да” в том, и только в том случае, если существует последовательность операторов длины не более L, ведущая из С₁ в С₂. Ее использование пространства полиномиально по n, k и log L.

Доказательство. Утверждение доказывается индукцией по L. Оно очевидным образом выполняется при L = 1, так как все операторы рассматриваются явно. Теперь рассмотрим большее значение L. Если существует последовательность операторов из С₁ в С₂ длины L' ≤ L, то существует конфигурация С', находящаяся в позиции [L'/2] в этой последовательности. По индукции оба вызова Path(C₁, С', [L/2]) и Path(C', С₂, [L/2]) вернут “да”, поэтому Path(C₁, С₂, L) вернет “да”. И наоборот, если существует конфигурация С', при которой Path(C₁, С', [L/2]) и Path(C', С₂, [L/2]) вернут “да”, то из гипотезы индукции следует, что существуют соответствующие последовательности операторов; объединяя эти две последовательности, получаем последовательность операторов из С₁ в С₂ длины не более L.

Теперь рассмотрим требования к пространству. Помимо затрат в рекурсивных вызовах, каждый вызов Path требует затрат пространства, полиномиальных по n, k и log L. Но в любой заданный момент времени активен только один рекурсивный вызов, и промежуточные результаты всех остальных рекурсивных вызовов были удалены. Следовательно, для полиномиальной функции pтребования к пространству S(n, k, L) удовлетворяют рекуррентному отношению

Раскручивая рекуррентное отношение для O(log L) уровней, мы получаем границу S(n, k, L) = O(log L ∙ p(n, k, log L), полиномиальную по n, k и log L. ■

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

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