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

  • Состояния. Агент находится в одном из двух местонахождений, в каждом из которых может присутствовать или не присутствовать мусор. Поэтому существует 2х22=8 возможных состояний мира.
  • Начальное состояние. В качестве начального состояния может быть назначено любое состояние.
  • Функция определения преемника. Эта функция вырабатывает допустимые состояния, которые являются следствием попыток выполнения трех действий (Left, Right и Suck). Полное пространство состояний показано на рисунке.


  • Проверка цели. Эта проверка сводится к определению того, являются ли чистыми все квадраты.
  • Стоимость пути. Стоимость каждого этапа равна 1, поэтому стоимость пути представляет собой количество этапов в этом пути.

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

Задача игры в восемь, состоит из доски 3x3 с восемью пронумерованными фишками и с одним пустым участком. Фишка, смежная с пустым участком, может быть передвинута на этот участок. Требуется достичь указанного целевого состояния, подобного тому, которое показано в правой части рисунка. Стандартная формулировка этой задачи приведена ниже.

  • Состояния. Описание состояния определяет местонахождение каждой из этих восьми фишек и пустого участка на одном из девяти квадратов.
  • Начальное состояние. В качестве начального может быть определено любое состояние. Необходимо отметить, что любая заданная цель может быть достигнута точно из половины возможных начальных состояний.
  • Функция определения преемника. Эта функция формирует допустимые состояния, которые являются результатом попыток осуществления указанных четырех действий (теоретически возможных ходов Left, Right, Up или Down).
  • Проверка цели. Она позволяет определить, соответствует ли данное состояние целевой конфигурации, показанной на рисунке (Возможны также другие целевые конфигурации.)
  • Стоимость пути. Каждый этап имеет стоимость 1, поэтому стоимость пути равна количеству этапов в пути.

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


Задача игры в восемь относится к семейству задач со скользящими фишками, которые часто используются в искусственном интеллекте для проверки новых алгоритмов поиска. Известно, что этот общий класс задач является NP-полным, поэтому вряд ли можно надеяться найти методы, которые в наихудшем случае были бы намного лучше по сравнению с алгоритмами поиска, описанными в этой и следующей главах. Задача игры в восемь имеет 91/2 = 181 440 достижимых состояний и легко решается. Задача игры в пятнадцать (на доске 4x4) имеет около 1,3 триллиона состояний, и случайно выбранные ее экземпляры могут быть решены оптимальным образом за несколько миллисекунд с помощью наилучших алгоритмов поиска.

Задача игры в двадцать четыре (на доске 5x5) имеет количество состояний около 1025, и случайно выбранные ее экземпляры все еще весьма нелегко решить оптимальным образом с применением современных компьютеров и алгоритмов.

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

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

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

  • Состояния. Состоянием является любое расположение ферзей на доске в количестве от 0 до 8.
  • Начальное состояние. Отсутствие ферзей на доске.
  • Функция определения преемника. Установка ферзя на любой пустой клетке.
  • Проверка цели. На доске находится восемь ферзей, и ни один из них не атакован.

В этой формулировке требуется проверить 64 63 ... 57=3x1014 возможных последовательностей. В лучшей формулировке должно быть запрещено помещать ферзя на любую клетку, которая уже атакована, следующим образом.

  • Состояния. Состояниями являются расположения с n ферзями, где n >= 0 и n <= 8, по одному ферзю в каждой из находящихся слева п вертикалей, притом что ни один ферзь не нападает на другого.
  • Функция определения преемника. Установка ферзя на любой клетке в находящейся слева пустой вертикали таким образом, чтобы он не был атакован каким-либо другим ферзем.

Эта формулировка позволяет сократить пространство состояний задачи с восемью ферзями с Зх1014 до 2057, и поиск решений значительно упрощается. С другой стороны, для 100 ферзей первоначальная формулировка определяет приблизительно 10400 состояний, а улучшенная формулировка — около 1052 состояний.

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