Е. И. Большакова , М. Г. Мальковский , В. Н. Пильщиков - Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие)

карте дорог и в список-описание не включен город, в который надо произвести переезд. Например, оператор переезда в город B неприменим к состоянию (A B C D), но применим к состоянию (A D).


Рис. 4. Задача о коммивояжере: часть пространства состояний

Обратимся теперь к известной задаче об обезьяне и банане, простейшую формулировку которой мы и рассмотрим. В комнате находятся обезьяна, ящик и связка бананов, которая подвешена к потолку настолько высоко, что обезьяна может до нее дотянуться, только встав на ящик. Нужно найти последователь­ность действий, которые позволят обезьяне достать бананы. Предполагается, что обезьяна может ходить по комнате, двигать по полу ящик, взбираться на него и хватать бананы.
Ясно, что описание состояния этой задачи должно включать следующие сведения: местоположение обезьяны в комнате – в горизонтальной плоскости пола и по вертикали (т.е. на полу она или на ящике), местоположение ящика на полу и наличие у обезьяны бананов. Все это можно представить в виде 4-элементного списка (ПолОб, ВертОб, ПолЯщ, Цель), где
ПолОб – положение обезьяны на полу (это может быть двухэлементный вектор координат);
ПолЯщ – положение ящика на полу;
ВертОб – это символ П или Я в зависимости от того, где находится обезьяна, на полу или на ящике;
Цель – это число 0 или 1 в зависимости от того, достала ли обезьяна бананы или нет.
Зафиксируем также три следующие значимые точки в плоскости пола:
ТО – точка первоначального местоположения обезьяны;
ТЯ – точка первоначального расположения ящика;
ТБ – точка пола, расположенная непосредственно под связкой бананов.
Тогда начальное состояние задачи описывается списком (ТО, П, ТЯ, 0), а целевое состояние задается как любой список, последний элемент которого равен 1.
Операторы в этой задаче можно определить так:
1) Перейти (W) – обезьяна переходит в точку W плоскости пола;
2) Передвинуть (V) – обезьяна передвигает ящик в точку V пола;
3) Взобраться – обезьяна взбирается на ящик;
4) Схватить – обезьяна хватает связку бананов.
Условия применимости и действие этих четырех операторов легко задать в виде правил продукций вида:
аргумент оператора  результат оператора,
причем
X, Y, Z, W, V – это переменные:
1. Перейти (W) : (X, П, Y, Z )  (W, П, Y, Z)
2. Передвинуть (V) : (X, П, X, Z)  (V, П, V, Z)
3. Взобраться : (X, П, X, Z)  (X, Я, X, Z)
4. Схватить : (ТБ, Я, ТБ , 0)  (ТБ, Я, ТБ , 1)


Рис. 5. Пространство состояний в задаче об обезьяне
Если считать, что для решения задачи значимы лишь вышеупомянутые точки пола ТО, ТЯ, ТБ, тогда получим пространство состояний задачи, изображенное на рис.5. Это пространство содержит только 13 состояний, дуги графа-пространства помечены порядковым номером применяемого оператора. Пространство содержит четыре цикла хождения обезьяны между тремя значимыми точками (с ящиком или без него). В пространстве есть также две тупиковые ветви – когда обезьяна залезает на ящик, но не под связкой бананов. Жирными дугами (стрелками) показан решающий путь, состоящий из четырех операторов:
Перейти (ТЯ); Передвинуть (ТБ); Взобраться; Схватить.
Рассмотренный пример показывает, сколь важен для успешного и эффективного решения задачи выбор определенного представления. Такое небольшое по размерам пространство состояний получено, в частности, вследствие того, что игнорировались все точки пола, кроме трех, соответствующих первоначальному расположению обезьяны, ящика и бананов.
Мощным приемом сужения пространств состояний является применение так называемых схем состояний и схем операторов, в которых для описаний состояний и операторов используются переменные. Тем самым схема состояния описывает целое множество состояний, а не только одно, а схема оператора определяет все множество действий некоторого типа. В рассмотренном нами представлении задачи об обезьяне использовались схемы операторов, но не схемы состояний. Другое представление этой задачи с использованием как схем состояний, так и схем операторов приведено в [Нильсон73, раздел 2.7].
​ 1.2 Редукция задач
​ 1.2.1 Основные понятия
Кроме уже рассмотренного подхода – представления задач в пространстве состояний – для решения ряда задач возможен и другой, более сложный подход. При этом подходе производится анализ исходной задачи с целью выделения такого набора подзадач, решив которые, мы решим исходную задачу. Каждая из выделенных подзадач в общем --">