случай, когда имеется произвольное число кубиков, из которых составлены столбики, - один или несколько. Число столбиков мы ограничим некоторым максимальным числом, чтобы задача была интереснее. Такое ограничение, кроме того, является вполне реальным, поскольку рабочее пространство, которым располагает робот, манипулирующий - кубиками, ограничено.
Проблемную ситуацию можно представить как список столбиков. Каждый столбик в свою очередь представляется списком кубиков, из которых он составлен. Кубики упорядочены в списке таким образом, что самый верхний кубик находится в голове списка. 'Пустые' столбики изображаются как пустые списки. Таким образом, исходную ситуацию рис. 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, с].
Назад | Содержание | Вперёд
Назад | Содержание | Вперёд
11. 2. Стратегия поиска в глубину
Существует много различных подходов к проблеме