Edge(e, d, 9)

Edge(b, d, 0).

Edge(c, d, 12).

Edge(a, b, 3).

Edge(a,c,8).

Clauses

Ucs(string,wlist,way).

Placeone(way,wlist,wlist).

Place(wlist,wlist,wlist).

Prolong(way,way).

Min_path(string,string,slist).

Member(string,slist).

E(string,string,integer).

Edge(string,string,integer).

Predicates

Domains

Постановка 8.

Path(_, _, G, Мax_path, Мax_cost),

Path(A, В, G, Мin_path, Мin_cost),

Постановка 7.

Not(member(X, Р1)),

Incident(X, Y, С_XY, G),

Постановка 6.

Member(edge(Y, X, С_XY), E).

Path1(A, P1, C1, G, Р, С)

Path(А, Z, G, Р, С)

Not (member(В, P)).

Not (top(В, G)),

Path(_, _, G, P),

Member(edge(Y, X), E).

Incident(X, Y, G)

означає, що в графі G існує дуга, яка веде з вершини Х у вершину Y. Визначення цього відношення залежить від форми подання графа. Якщо G представлений парою множин (вершин і ребер)

G = g(V, E),

то

incident(X, Y, g(V, E)):-

member(edge(X, Y), E);

пошук Гамільтонова циклу

Є класичною задачею на графах щодо пошуку ациклічного шляху крізь всі вершини графа. Рішення цієї задачі з використанням відношення path визначають так:

gamilt(G, P):-

alltop(P, G).

alltop(P, G):-

Тут top(В, G) означає: В - вершина графа G.

Вартість шляху

Кожному шляху можна приписати вартість, яка є сумою вартостей дуг шляху. Якщо дуги не помічені (не зважені, їм не приписані вартості), тоді маємо задачу довжини шляху.

Щоб відношення path і path1 могли працювати із вартостями, їх модифікують, додаючи аргумент:

Тут С – вартість шляху Р, a C1 - вартість шляху Р1. У відношенні incident теж додано аргумент – вартість дуги:

incident(X, Y, С_XY, g(V, E)):-

member(edge(X, Y, С_XY), E);

Побудова шляху з обчисленням його вартості на графі G, заданому явно.

path(А, Z, G, Р, С):-

path1(A, [Z], 0, G, Р, С).

path1(A, [А | Р1], С, G, [А | Р1], С).

path1(A, [Y | Р1], С1, G, Р, С):-

С2 іs С1 + С_XY,

path1(A, [X, Y | Р1], С2, G, Р, С).

Побудова шляху мінімальної вартості на графі G, заданому явно.

Шлях мінімальної вартості між вершинами A та B графа G можна побудувати, задавши для попередньої програми запит

not(path(A, В, G, _, С), С< Мin_cost)

Аналогічно, серед всіх шляхів між вершинами графа можна знайти шлях максимальної вартості, задавши ціль

not(path(_, _, G, _, С), С> Мax_cost)

Зауваження: ці визначення пошуку мінімальних і максимальних шляхів гранично неефективні, оскільки засновані на перегляді всіх можливих шляхів, і тому не підходять для великих графів.

Побудова на графі G, заданому неявно, мінімального min_path(Х,Y,L) за вартістю ребер шляху L між вершинами Х та Y.

slist=string*

l=slist*

way=w(integer,slist) %Зберігає вартість шляху і шлях

wlist=way*

e(A,B,C):-edge(A,B,C);edge(B,A,C). %граф не є орграф

min_path(A,B,P):-ucs(A,[w(0,[B])],w(_,P)).

ucs(A,[w(C,[A|Tail])|_],w(C,[A|Tail])):-!. %пошук

згідно вагової функції

ucs(A,[Path|Tail],R):-

findall(Z,prolong(Path,Z),NewPathes),!,

place(NewPathes,Tail,New),ucs(A,New,R).
ucs(A,[_|Tail],R):-ucs(A,Tail,R).

prolong(w(C,[X|T]),w(C1,[Y,X|T])):- % подовження

шляху

e(X,Y,E),not(member(Y,T)),C1=C+E.

place([],L,L). %нові шляхи розміщує згідно їхньої ваги

place([X|T],L,R):-placeone(X,L,L1),place(T,L1,R).

placeone(w(C,P),[w(C1,P1)|Tail],[w(C,P),w(C1,P1)|Tail]):-

C<=C1,!.

placeone(X,[H|Tail],[H|NewTail]):-

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