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


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


     - если B - целевая вершина, то положить Solution = [B], или
     - если для исходной вершины B существует вершина - преемник  B1,
такая, что  можно провести путь Solution1 из B1 в целевую вершину,  то
положить
                Solution = [B|Solution1].
     На Прологе это правило имеет вид:
     solve(B,[B]) :- goal(B).
     solve(B,[B|Solution1]) :- after(B,B1), solve(B1,Solution1).
        Эта программа реализует поиск в глубину,  т.е. когда алгоритму
поиска в  глубину надлежит выбрать из нескольких вершин ту,  в которую
следует перейти для продолжения поиска, он предпочитает самую глубокую
из них. Самая глубокая вершина - та, которая расположена дальше других
от стартовой вершины.
        Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Обрабатывая цели Пролог - система сама
просматривает альтернативы  именно  в  глубину.
        Описанная процедура  поиска в глубину страдает одним серьезным
недостатком - она не работает в пространстве состояний, имеющем циклы.
        Добавим к нашей процедуре механизм обнаружения циклов. Ни одну
из вершин, уже содержащихся в пути, построенном из стартовой вершины в
текущую, не  следует  вторично рассматривать в качестве возможной альтернативы продолжения поиска.  Это правило можно сформулировать в виде
отношения
                in_depth(Path,Node,Solution).
        Здесь:
     - Node - вершина (состояние), из которой необходимо найти путь до
цели;
     - Path - список вершин (путь) между стартовой вершиной и Node;
     - Solution - путь, продолженный до целевой вершины.
        Для облегчения программирования вершины в списках, представляющих пути, будут расставляться в обратном порядке. Аргумент Path нужен
для того,
     (1) чтобы не рассматривать тех преемников вершины  Node,  которые
уже встречались (обнаружение циклов);
     (2) чтобы облегчить построение решающего пути Solution.
     Программа поиска в глубину без зацикливания имеет вид:
     solve(Node,Solution) :-in_depth([],Node,Solution).



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



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