Главная arrow Поиск arrow Упрощенные задачи
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

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

  • Состояния. Агент находится в одном из двух местонахождений, в каждом из которых может присутствовать или не присутствовать мусор. Поэтому существует 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 состояний.

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