Длинейший путь графа - Prolog
Формулировка задачи:
Здраствуйте, помогите пожалуйста.
Нужно найти самый длиный простой путь в графе.
Написал программку которая ищет всет простые пути. Как найти только самый большой?
Решение задачи: «Длинейший путь графа»
textual
Листинг программы
domains
i=integer
s=char
list=s*
database arca(s,s)
predicates
add(list,char,list)
nondeterm posled(char,list)
nondeterm poisk(list,list)
member(s,list)
length(list,i)
nondeterm longer(i)
nondeterm longest(list)
clauses
posled(H,[_|T]):-posled(H,T).
posled(H,[H]).
add([H|T],X,[H|Res]):-add(T,X,Res).
add([],X,[X]).
poisk([],A):-arca(X,Y),poisk([X,Y],A).
poisk([H|T],A):-arca(X,Y),posled(Z,T),Z=X,not(member(Y,[H|T])),add([H|T],Y,K),poisk(K,A),!.
poisk(A,A).
arca('a','b').arca('b','c').arca('c','d').arca('b','d').arca('a','d').arca('d','a').
member(X,[X|_]):-!.
member(X,[_|Tail]):- member(X,Tail).
length([],0).
length([_|Tail],N):-length(Tail,N1),N=N1+1.
longer(N):-poisk([],Way), length(Way,Len),Len>N.
longest(Way):-poisk([],Way),length(Way,Len),not(longer(Len)).
goal
longest(L).