Курсовая работа: Экспертная система для решения задачи о коммивояжере

arca(f,x,1).

Дуги прописаны согласно рис.1.

Для реализации метода поиска выберем метод поиск в глубину, который основан на следующих соображениях:

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

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

Введем отношение

path1(A,P1,P, D ),

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

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

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

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

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

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

Отношение можно реализовать согласно:

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).

Где отношение member - определяет принадлежит ли элемент списку, реализованное следующим кодом:

member(Head,[Head|_]).

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

Для реализации выбора оптимального выбора (минимальная длина) среди перечня путей введем отношение db0 и db:

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).

Отношение db0 инициализирует первый возможный путь. Если данный путь не единичен, то db инициализирует следующий путь, и в то же время сравнивает длины двух данных путей. В процессе последующих рекурсий и сравнения остается только один путь, длина которого минимальна.

Текст программы :

domains

i=integer