Prolog

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

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

Существует много различных подходов к проблеме