Поиск пути в графе

Определим отношение path(A,Z,P),

где P - ациклический путь между вершинами A и Z в графе G, представленном следующими дугами:

arca(a,b). arca(b,c). arca(c,d). arca(b,d).

Один из методов поиска пути основан на следующих соображениях:

- если A = Z, то положим P = [A];

- иначе нужно найти ациклический путь P1 из произвольной вершины Y в Z, а затем найти путь из A в Y, не содержащий вершин из P1.

Введем отношение path1(A,P1,P),

означающее, что P1 - завершающий участок пути P.

Между path и path1 имеет место соотношение:

path(A,Z,P):- path1(A,[Z],P).

Рекурсивное определение отношения path1 вытекает из следующих посылок:

- “граничный случай”: начальная вершина пути P1 совпадает с начальной вершиной A пути P;

- в противном случае должна существовать такая вершина X, что: 1) Y - вершина, смежная с X, 2) X - не содержится в P1, 3) для P выполняется отношение path (A,[Y|P1],P).

Пример 1. Программа нахождения пути.

arca(a,b). arca(b,c). arca(c,d). arca(b,d).

member(X,[X|_]).

member(X,[_|Tail]):- member(X,Tail).

path(A,Z,Path):- path1(A,[Z],Path).

path1(A,[A|Path1],[A|Path1]).

path1(A,[Y|Path1],Path):- arca(X,Y), not(member(X,Path1)),

path1(A,[X,Y|Path1],Path).

Чтобы отношения path и path1 могли работать со стоимостями (весами), их нужно модифицировать введением дополнительного аргумента для каждого пути:

path(A,Z,P,C),

path1(A,P1,C1,P,C),

где C и C1 - стоимости путей P и P1 соответственно.

Отношение смежности arca включает дополнительный аргумент - стоимость дуги:

arca(X,Y,C).

Пример 2. Программа построения пути минимальной стоимости между заданными вершинами графа.

arca(a,b,1). arca(b,c,3). arca(c,d,1). arca(b,d,7). arca(a,d,1).

member(X,[X|_]).

member(X,[_|Tail]):- member(X,Tail).

path(A,Z,Path,C):- path1(A,[Z],0,Path,C).

path1(A,[A|Path1],C,[A|Path1],C).

path1(A,[Y|Path1],C1,Path,C):- arca(X,Y,CXY), not(member(X,Path1)),

C2=C1+CXY, path1(A,[X,Y|Path1],C2,Path,C).

% поиск пути минимальной стоимости между вершинами X и Y

db0(X,Y):-path(X,Y,P,C), assert(db_path(X,Y,P,C)).

db(X,Y):-db_path(X,Y,P,C), path(X,Y,MP,MC), MC<C,!,

retract(db_path(X,Y,P,C)), assert(db_path(X,Y,MP,MC)), db(X,Y).

db(_,_).

Следующий запрос определяется путь MP минимальной стоимости MC между вершинами a и b:

db0(a,d), db(a,d), db_path(a,d,MP,MC), write("\nMP=",MP,"\nMC=",MC).