Ни одну из вершин, уже

Ни одну из вершин, уже содержащихся в пути, построенном из стартовой вершины в текущую вершину, не следует вторично рассматривать в качестве возможной альтернативы продолжения поиска. Это правило можно сформулировать в виде отношения

        вглубину( Путь, Верш, Решение)

Как видно из рис. 11.6, Верш - это состояние, из которого необходимо найти путь до цели; Путь - путь (список вершин) между стартовой вершиной и Верш; Решение

- Путь, продолженный до целевой вершины.



Рис. 11. 6.  Отношение вглубину( Путь, В, Решение).

Для облегчения программирования вершины в списках, представляющих пути, будут расставляться в обратном порядке. Аргумент Путь

нужен для того,

(1)        чтобы не рассматривать тех преемников вершины Верш, которые уже встречались раньше (обнаружение циклов);

(2)        чтобы облегчить построение решающего пути Решение. Соответствующая программа поиска в глубину показана на рис. 11.7.

line();

        решить( Верш, Решение) :-

                вглубину( [ ], Верш, Решение).

        вглубину( Путь, Верш, [Верш | Путь] ) :-

                цель( Верш).

        вглубину( Путь, Верш, Реш) :-

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

                not принадлежит( Верш1, Путь),

                                        % Цикл ?

                вглубину( [Верш | Путь], Верш1, Реш).


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

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---

---

---