Иван Братко - Программирование на языке Пролог для искусственного интеллекта

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

Мы будем представлять пространство состояний при помощи отношения

после( X, Y)

которое истинно тогда, когда в пространстве состояний существует разрешенный ход из вершины X в вершину Y. Будем говорить, что Y — это преемник вершины X. Если с ходами связаны их стоимости, мы добавим третий аргумент, стоимость хода:

после( X, Y, Ст)

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

Рассмотрим в качестве примера задачу манипулирования кубиками, проиллюстрированную на рис. 11.1. Мы будем рассматривать более общий случай, когда имеется произвольное число кубиков, из которых составлены столбики, — один или несколько. Число столбиков мы ограничим некоторым максимальным числом, чтобы задача была интереснее. Такое ограничение, кроме того, является вполне реальным, поскольку рабочее пространство, которым располагает робот, манипулирующий кубиками, ограничено.

Проблемную ситуацию можно представить как список столбиков. Каждый столбик в свою очередь представляется списком кубиков, из которых он составлен. Кубики упорядочены в списке таким образом, что самый верхний кубик находится в голове списка. "Пустые" столбики изображаются как пустые списки. Таким образом, исходную ситуацию рис. 11.1 можно записать как терм

[ [с, а, b], [], [] ]

Целевая ситуация — это любая конфигурация кубиков, содержащая, столбик, составленный из всех имеющихся кубиков в указанном порядке. Таких ситуаций три:

[ [a, b, c], [], [] ]

[ [], [а, b, с], [] ]

[ [], [], [a, b, c] ]

Отношение следования можно запрограммировать, исходя из следующего правила: ситуация Сит2есть преемник ситуации Сит1, если в Сит1имеется два столбика Столб1и Столб2, такие, что верхний кубик из Столб1можно поставить сверху на Столб2и получить тем самым Сит2. Поскольку все ситуации - это списки столбиков, правило транслируется на Пролог так:

после( Столбы, [Столб1, [Верх1 | Столб2], Остальные]) :-

% Переставить Верх1 на Столб2

удалить( [Верх1 | Столб1], Столб1, Столб1),

% Найти первый столбик

удалить( Столб2, Столбы1, Остальные).

% Найти второй столбик

удалить( X, [X | L], L).

удалить( X, [Y | L], [Y | L1] ) :-

удалить( L, X, L1).

В нашем примере целевое условие имеет вид:

цель( Ситуация) :-

принадлежит [а,b,с], Ситуация)

Алгоритм поиска мы запрограммируем как отношение

решить( Старт, Решение)

где Старт — стартовая вершина пространства состояний, а Решение — путь, ведущий из вершины Стартв любую целевую вершину. Для нашего конкретного примера обращение к пролог-системе имеет вид:

?- решить( [ [с, а, b], [], [] ], Решение).

В результате успешного поиска переменная Решениеконкретизируется и превращается в список конфигураций кубиков. Этот список представляет собой план преобразования исходного состояния в состояние, в котором все три кубика поставлены друг на друга в указанном порядке [а, b, с].

Существует много различных подходов к проблеме поиска решающего пути для задач, сформулированных в терминах пространства состояний. Основные две стратегии поиска — это поиск в глубину и поиск в ширину . В настоящем разделе мы реализуем первую из них.

Мы начнем разработку алгоритма и его вариантов со следующей простой идеи:

Для того, чтобы найти решающий путь Решиз заданной вершины Вв некоторую целевую вершину, необходимо: