Чтение онлайн

Рассмотрим в качестве примера задачу манипулирования кубиками, проиллюстрированную на рис. 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, с].

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

11. 2. Стратегия поиска в глубину

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

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

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

если В– это целевая вершина, то положить Реш = [В], или

если для исходной вершины В существует вершина-преемник В1, такая, что можно провести путь Реш1 из В1 в целевую вершину, то положить Реш = [В | Peш1].

Рис. 11. 4. Пример простого пространства состояний: а– стартовая

вершина, f и j– целевые вершины. Порядок, в которой происходит

проход по вершинам пространства состояний при поиске в глубину:

а, b, d, h, e, i, j. Найдено решение [a, b, e, j]. После возврата

обнаружено другое решение: [а, с, f].

На Пролог это правило транслируется так:

решить( В, [В] ) :-

цель( В).

решить( В, [В | Реш1] ) :-

после( В, В1 ),

решить( В1, Реш1).

Эта программа и есть реализация поиска в глубину. Мы говорим "в глубину", имея в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска, он предпочитает самую "глубокую" из них. Самая глубокая вершина - это вершина, расположенная дальше других от стартовой вершины. На рис. 11.4 мы видим на примере, в каком порядке алгоритм проходит по вершинам. Этот порядок в точности соответствует результату трассировки процесса вычислений в пролог-системе при ответе на вопрос

?- решить( а, Реш).

Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Причина этого состоит в том, что, обрабатывая цели, пролог-система сама просматривает альтернативы именно в глубину.

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