ВУЗ:
Составители:
Рубрика:
58
path (top, top, listtop)
/*Предикат path( top, top, listtop) создает список из вершин,
составляющих путь.*/
clauses
edge (a, b).
edge (b, c).
edge (c, a).
edge (b, d).
edge (d, e).
path (A, A, [A]).
path (A, B, [A\P]):-edge(A, N), path(N, B, P).
С помощью поиска в глубину осуществляется корректный обход
любого конечного дерева или ориентированного ациклического графа.
Однако, встречаются задачи, где требуется производить обход графа с
циклами. В процессе вычислений может образоваться бесконечный
программный цикл по одному из циклов графа.
Неприятностей
с зацикливанием можно избежать двумя способами:
ограничением на глубину поиска или накоплением пройденных вершин.
Последний способ можно реализовать при помощи модификации отношения
path. К аргументам отношения добавляется дополнительный аргумент,
используемый для накопления уже пройденных при обходе вершин, для
исключения повторного использования одного и того же состояния
применяется проверка.
Пример 71: написать программу
обхода конечного ориентированного
графа, представленного на рисунке.
domains
top=symbol
listtop=top*
predicates
edge(top,top)
path (top,top,listtop,listtop)
path (top,top)
member(top,listtop)
reverse(listtop,listtop,listtop)
clauses
c d
е
а
b
Страницы
- « первая
- ‹ предыдущая
- …
- 56
- 57
- 58
- 59
- 60
- …
- следующая ›
- последняя »
