Постановка 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.

Дата добавления: 2014-01-04