Постановка 3.
Постановка 2.
Попередня задача при явній формі представлення графа двома списками: вершин і ребер. Ребро представляється структурою edge.
domains
edge= e(symbol, symbol) % аргументи - імена вершин
list1=symbol*
list2=edge*
graf = g(list1, list2)
predicates
path(graf, symbol, symbol) % відношення зв'язаності
вершин у графі
clauses
path (g([],[]),_,_).
path (g([X|_],[e(X,Y)|_]),X,Y).
path (g([X|T],[e(X,_)|T1]),X,Y):-
path (g([X|T],T1),X,Y).
path (g([X|T],[e(_, _)|T1]),X,Y):-
path (g([X|T],T1),X,Y).
path (g([X|T],[e(X,Z)|T1]),X,Y):-
path (g([X|T],T1),Z,Y).
goal
path (g([a, b, c, d],[e(a, b),e(b, c),e(a, d),e(c, b)]), a, c).
Пошук шляху на графі.
Шлях – це послідовність вершин, з'єднаних дугами. Для орграфа напрямок шляху має збігатись з напрямком кожної дуги шляху.
Цикл – це шлях, у якого збігаються початок і кінець.
Програми пошуку шляху на графі належать до недетермінованих програм з невідомим вибором альтернативи, оскільки в них невідомо, яке з рекурсивних правил буде виконано в процесі доказу, аж до успішного завершення обчислень. Такі програми є специфікацією алгоритму пошуку в глибину для розв'язку певної задачі.
Визначити шлях P між вершинами A та B графа, заданого неявно:
A – початок шляху;
B – кінець шляху;
P – ациклічний (не має повторів вершин) шлях на графі.
domains
top=symbol
listtop=top*
predicates
edge (top, top) % аргументи позначають імена вершин
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.