ПРИМЕРЫ ЗАДАЧ
Описанный подход к решению задач был применен в очень многих вариантах экспериментальной среды. В этом разделе перечислены некоторые из наиболее известных примеров решения задач, которые подразделяются на два типа — упрощенные и реальные задачи. Упрощенная задача предназначена для иллюстрации или проверки различных методов решения задач. Ей может быть дано краткое, точное описание. Это означает, что такая задача может легко использоваться разными исследователями для сравнения производительности алгоритмов. Реальной задачей называется такая задача, решение которой действительно требуется людям. Как правило, такие задачи не имеют единого приемлемого для всех описания, но мы попытаемся показать, как обычно выглядят их формулировки.
Упрощенные задачи
В качестве первого примера рассмотрим мир пылесоса, впервые представленный в главе 2 (см. рис. 2.2). Деятельность в этом мире можно сформулировать в качестве задачи, как описано ниже.
• Состояния. Агент находится в одном из двух местонахождений, в каждом из которых может присутствовать или не присутствовать мусор. Поэтому существует 2х22=8 возможных состояний мира.
• Начальное состояние. В качестве начального состояния может быть назначено любое состояние.
• Функция определения преемника. Эта функция вырабатывает допустимые состояния, которые являются следствием попыток выполнения трех действий (Left, Right и Suck). Полное пространство состояний показано на рис. 3.2.
• Проверка цели. Эта проверка сводится к определению того, являются ли чистыми все квадраты.
• Стоимость пути. Стоимость каждого этапа равна 1, поэтому стоимость пути представляет собой количество этапов в этом пути.
По сравнению с задачей реального мира эта упрощенная задача характеризуется различимыми местонахождениями, возможностью определять наличие мусора, надежной очисткой, а также сохранением достигнутого состояния после очистки. (В разделе 3.6 некоторые из этих допущений будут исключены.) Необходимо учитывать, что состояние определяется и местонахождением агента, и наличием мусора. В более крупной среде с п местонахождениями имеется п-2п состояний.
Задача игры в восемь, экземпляр которой показан на рис. 3.3, состоит из доски 3x3 с восемью пронумерованными фишками и с одним пустым участком. Фишка, смежная с пустым участком, может быть передвинута на этот участок. Требуется достичь указанного целевого состояния, подобного тому, которое показано в правой части рисунка. Стандартная формулировка этой задачи приведена ниже.
• Состояния. Описание состояния определяет местонахождение каждой из этих восьми фишек и пустого участка на одном из девяти квадратов.
• Начальное состояние. В качестве начального может быть определено любое состояние. Необходимо отметить, что любая заданная цель может быть достигнута точно из половины возможных начальных состояний (см. упр. 3.4).
• Функция определения преемника. Эта функция формирует допустимые состояния, которые являются результатом попыток осуществления указанных четырех действий (теоретически возможных ходов Left, Right, Up или Down).
• Проверка цели. Она позволяет определить, соответствует ли данное состояние целевой конфигурации, показанной на рис. 3.3. (Возможны также другие целевые конфигурации.)
• Стоимость пути. Каждый этап имеет стоимость 1, поэтому стоимость пути равна количеству этапов в пути.
Какие абстракции здесь предусмотрены? Действия абстрагируются до уровня указания их начального и конечного состояний, при этом игнорируются промежуточные положения в процессе перемещения фишки. В ходе создания абстрактного описания исключены такие действия, как встряхивание доски, позволяющее передвинуть застрявшую фишку, или извлечение фишек с помощью ножа и повторное укладывание их в ящик. Исключено также описание правил игры, что позволяет обойтись без рассмотрения подробных сведений о физических манипуляциях.
Задача игры в восемь относится к семейству задач со скользящими фишками, которые часто используются в искусственном интеллекте для проверки новых алгоритмов поиска. Известно, что этот общий класс задач является NP-полным, поэтому вряд ли можно надеяться найти методы, которые в наихудшем случае были бы намного лучше по сравнению с алгоритмами поиска, описанными в этой и следующей главах. Задача игры в восемь имеет 9 ! / 2 = 181 440 достижимых состояний и легко решается. Задача игры в пятнадцать (на доске 4x4) имеет около 1,3 триллиона состояний, и случайно выбранные ее экземпляры могут быть решены оптимальным образом за несколько миллисекунд с помощью наилучших алгоритмов поиска. Задача игры в двадцать четыре (на доске 5x5) имеет количество состояний около 1025, и случайно выбранные ее экземпляры все еще весьма нелегко решить оптимальным образом с применением современных компьютеров и алгоритмов.
Цель задачи с восемью ферзями состоит в размещении восьми ферзей на шахматной доске таким образом, чтобы ни один ферзь не нападал на любого другого. (Ферзь атакует любую фигуру, находящуюся на одной и той же с ним горизонтали, вертикали или диагонали.) На рис. 3.4 показана неудачная попытка поиска решения: ферзь, находящийся на самой правой вертикали, атакован ферзем, который находится вверху слева.
Несмотря на то что существуют эффективные специализированные алгоритмы решения этой задачи и всего семейства задач с п ферзями, она по-прежнему остается интересной экспериментальной задачей для алгоритмов поиска. Для нее применяются формулировки двух основных типов. В инкрементной формулировке предусматривается использование операторов, которые дополняют описание состояния, начиная с пустого состояния; для задачи с восемью ферзями это означает, что каждое действие приводит к добавлению к этому состоянию еще одного ферзя.
Формулировка полного состояния начинается с установки на доску всех восьми ферзей и предусматривает их дальнейшее перемещение. В том и другом случае стоимость пути не представляет интереса, поскольку важно лишь достигнуть конечного состояния. Первая инкрементная формулировка, которая может применяться при осуществлении попыток решения этой задачи, приведена ниже.
• Состояния. Состоянием является любое расположение ферзей на доске в количестве от 0 до 8.
• Начальное состояние. Отсутствие ферзей на доске.
• Функция определения преемника. Установка ферзя на любой пустой клетке.
• Проверка цели. На доске находится восемь ферзей, и ни один из них не атакован.
В этой формулировке требуется проверить 64-63•...?57-3x1014 возможных последовательностей. В лучшей формулировке должно быть запрещено помещать ферзя на любую клетку, которая уже атакована, следующим образом.
• Состояния. Состояниями являются расположения с п ферзями (0<л<8), по одному ферзю в каждой из находящихся слева п вертикалей, притом что ни один ферзь не нападает на другого.
• Функция определения преемника. Установка ферзя на любой клетке в находящейся слева пустой вертикали таким образом, чтобы он не был атакован каким-либо другим ферзем.
Эта формулировка позволяет сократить пространство состояний задачи с восемью ферзями с 3x1014 до 2 057, и поиск решений значительно упрощается. С другой стороны, для 100 ферзей первоначальная формулировка определяет приблизительно 10400 состояний, а улучшенная формулировка — около 1052 состояний (см. упр. 3.5). Это — колоссальное сокращение, но улучшенное пространство состояний все еще слишком велико для того, чтобы с ним могли справиться алгоритмы, рассматриваемые в данной главе. В главе 4 описана формулировка полного состояния, а в главе 5 приведен простой алгоритм, который позволяет легко решить задачу даже с миллионом ферзей.