загрузка...

АЛГОРИТМЫ - Разработка и применение - 2016 год

Глава 9. PSPACE: класс задач за пределами NP

9.2. Некоторые сложные задачи из PSPACE

Рассмотрим естественные примеры задач из PSPACE, которые, как принято считать, не принадлежат ни NP, ни co-NP.

Как и в случае с NP, чтобы разобраться в структуре PSPACE, можно рассмотреть конкретные задачи — самые сложные в классе. Задача X называется PSPACE-полной, если (i) она принадлежит PSPACE и (ii) для всех задач Y в PSPACE выполняется Y P X.

Оказывается, как и в случае с NP, существует широкий диапазон естественных задач, которые являются PSPACE-полными. Многие базовые задачи в области искусственного интеллекта являются PSPACE-полными; ниже описаны три категории таких задач.

Задачи построения плана

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

Очень похожие проблемы встречаются в сложных головоломках для одного игрока: например, в кубике Рубика или головоломке «15» — сетке 4 х 4 с 15 перемещаемыми плитками 1, 2, ..., 15 и одним пустым местом — перемещая плитки, игрок должен выстроить числа по возрастанию. (Вместо машин «скорой помощи» и снегоуборочных машин в этой задаче речь идет о таких операциях, как перемещение плитки 6 на одну позицию влево; но для этого нужно убрать с пути плитку 11, а для этого нужно переместить 9, которая находится в хорошем месте; и т. д.) Даже эти «игрушечные» задачи порой оказываются весьма нетривиальными и часто используются в области искусственного интеллекта для тестирования координационных алгоритмов.

Как же с учетом сказанного определить задачу построения плана на достаточно общем уровне, включающем все эти примеры? И у головоломок, и у помощи при стихийных бедствиях имеются некоторые общие абстрактные черты: есть ряд условий, которые достигаются в результате принятия решений, и множество допустимых операций, которые к этим условиям применяются. Таким образом, окружение моделируется множеством С = {С1, ..., Cn} условий: общее «состояние окружающего мира» задается подмножеством условий, действующих на данный момент. Для взаимодействия с окружением используются операторы, образующие множество {O1, ..., Ok}. Каждый оператор Oi определяется множеством предусловий, которые должны выполняться для выполнения Oi; списком добавления — множеством условий, которые станут истинными после выполнения Oi; и списком удаления — множеством условий, которые перестают действовать после выполнения O Например, при моделировании головоломки «15» можно определить условие для каждого возможного положения каждой плитки и оператор для перемещения каждой плитки между двумя парами соседних положений; предусловие для оператора заключается в том, что в двух указанных позициях должны находиться плитка и пустое место.

Обобщенная задача выглядит так: дано множество С0 начальных условий и множество С* целевых условий; возможно ли применить последовательность операторов, начиная с С0, и достичь ситуации, в которой выполняются только условия С* (и никакие другие)? Назовем эту формулировку задачей построения плана.

Кванторы

Как вы убедились в задаче 3-SAT, проверка возможности одновременного выполнения множества дизъюнктивных условий создает немалые трудности. С добавлением кванторов задача только усложняется.

Пусть Ф(х1, ..., xn) — булева формула вида

где каждый компонент Сi является дизъюнкцией трех литералов (другими словами, это экземпляр задачи 3-SAT). Для простоты будем считать, что n — нечетное число; задается вопрос:

То есть мы хотим знать, существует ли для x1 такой выбор, что для обоих вариантов выбора х2 существует выбор х3... и т. д., чтобы в итоге выполнялось Ф? Назовем эту задачу задачей 3-SAT с кванторами, или сокращенно QSAT.

Для сравнения, исходная задача 3-SAT задавала вопрос:

Другими словами, в задаче 3-SAT было достаточно найти одно значение для булевых переменных.

Следующий пример демонстрирует рассуждения, лежащие в основе экземпляра QSAT. Предположим, имеется формула

и задается вопрос:

Ответ на вопрос положителен: мы присваиваем х1 такое значение, чтобы для обоих вариантов х2 можно было задать х3 так, чтобы выполнялось Ф. А именно: можно присвоить х1 = 1; если затем х2 присваивается 1, то х3 можно присвоить 0 (с выполнением всех условий); а если х2 присваивается 0, х3 можно присвоить 1 (снова с выполнением всех условий).

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

Игры

В 1996 и 1997 годах в СМИ чемпиона мира по шахматам Гарри Каспарова называли защитником человеческой расы, когда он противостоял программе IBM Deep Blue в двух шахматных матчах. Даже один этот пример убедительно показывает, что интеллектуальные игры стали одним из самых заметных успехов в области современного искусственного интеллекта.

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

Задача конкурентного размещения, упоминавшаяся в главе 1, естественно укладывается в эту структуру (а заодно показывает, что игры могут пригодиться не только для времяпрепровождения, но и в конкурентных ситуациях в повседневной жизни). Вспомните, что в задаче конкурентного размещения задается граф G с неотрицательным значением b, связанным с каждым узлом i. Два игрока поочередно выбирают узлы G, так что множество выбранных узлов в любой момент образует независимое множество. Игрок 2 побеждает, если ему удастся выбрать узлы с суммарным значением не менее B для заданной границы B; игрок 1 побеждает, если ему удастся этому помешать. Вопрос: существует ли для заданного графа G и границы B стратегия, с которой игрок 2 может обеспечить себе выигрыш?





загрузка...

загрузка...