Программирование на Турбо-Прологе


Программирование на Турбо-Прологе - стр. 25


     Проблемная ситуация - список столбиков.  Каждый столбик -  список
кубиков, из  которых  он составлен.  Кубики упорядочены в списке таким
образом, что самый верхний кубик находится в  голове  списка. "Пустые"
столбики изображаются как пустые списки.
     Отношение следования вытекает из правила:
     Ситуация Sit2  - преемник ситуации Sit1,  если в Sit1 имеется два
столбика Stolb1 и Stolb2 такие, что верхний кубик из Stolb1 можно поставить сверху на Stolb2 и получить тем самым Sit2.
     Поскольку все ситуации - списки столбиков,  правило транслируется
на Пролог так:
     after(Stolbs,[Stolb1, [Up1|Stolb2],Rest]) :-
                delete([Up1|Stolb1],Stolbs,Stolbs1),
                delete(Stolb2,Stolbs1,Rest).
     delete(X,[X|L],L).
     delete(X,[Y|L],[Y|L1]) :- delete(X,L,L1).
     Здесь:
        - Stolbs - множество столбиков в ситуации Sit1;
        - Stolbs1 - множество столбиков без первого столбика;
        - Rest - множество столбиков без первого и второго.
     Целевое условие в данном примере имеет вид:
                goal(Sit) :- member([a,b,c],Sit).
     Алгоритм поиска программируется как отношение
                solve(Start,Solution),
где
     - Start - стартовая вершина пространства состояний,
     - Solution - путь,  ведущий из вершины Start в любую целевую вершину.
     Для конкретного примера обращение к Пролог- системе имеет вид:
        solve([[c,a,b],[],[]],Solution).
     Исходная ситуация
        [[c,a,b],[],[]].
     Целевые ситуации:
        [[a,b,c],[],[]]
        [[],[a,b,c],[]]
        [[],[],[a,b,c]]
     Список Solution  представляет собой план преобразования исходного
состояния в состояние, в котором три кубика поставлены друг на друга в
указанном порядке : [a,b,c].
6.2. Стратегия поиска в глубину
     Основные стратегии  поиска решающего пути - поиск в глубину и поиск в ширину.
Идея алгоритма поиска в глубину заключается в следующем. Чтобы найти путь Solution из заданной вершины B в некоторую целевую вершину, необходимо:



- Начало -  - Назад -  - Вперед -



Книжный магазин