Declaratieve Talen/Oplossing Handelsreiziger verplaatsen

De oplossing werk slecht voor één reiziger, aanpassing voor meerdere reizigers is triviaal.

buurvan(f,c).
buurvan(f,e).
buurvan(e,d).
buurvan(d,c).
buurvan(d,a).
buurvan(a,b).

hotel(f).
hotel(a).
hotel(b).

%verplaats_min/2
verplaats_min(Stad,Route) :-
	findall(Route, verplaats(Stad,Route),Routes),
	min(Routes,Route).

%min
min([Route],MinRoute) :- MinRoute = Route.
min([Route|Rest],MinRoute) :-
	min(Rest,RecurMinRoute),
	length(RecurMinRoute,RecurLength),
	length(Route,Length),
	(Length < RecurLength ->
		MinRoute = Route
		;
		MinRoute = RecurMinRoute
	).
	

%verplaats/2
verplaats(Stad,Route) :-
	hotel(HotelStad),
	pad(Stad,HotelStad,Route).
	

%buur/2
buur(X,Y) :-
	buurvan(X,Y);
	buurvan(Y,X).
%pad/2
pad(X,Y,Pad) :-
	pad2(X,Y,[X],Pad).
%pad/3
pad2(X,Y,_,Pad) :-
	buur(X,Y),
	Pad = [X,Y].
pad2(X,Y,History,Pad) :-
	X \= Y,
	buur(X,Z),
	nonmember(Z,History),
	pad2(Z,Y,[Z|History],PadRecur),
	Pad = [X|PadRecur].
	
%member(X,Lijst)
nonmember(_,[]).
nonmember(X,[L|Rest]):-
	X \== L,
	nonmember(X,Rest). 

--Beau 15 jun 2006 11:44 (CEST)

Een oplossing die ongeveer tien keer zo snel is. Merk wel op dat bij mijn oplossing verplaats ENKEL een resultaat teruggeeft indien er een buur is die een hotel heeft (zo heb ik de oplossing begrepen). Ze maakt gebruik van iterative deepening. Ze werkt ook voor meerder reizigers.

verplaats_1((Persoon,Plaats),(Persoon, Plaats, Plaats2)):-
	(	buurvan(Plaats,Plaats2);
		buurvan(Plaats2,Plaats)
	),
	hotel(Plaats2).

verplaats([],[]).
verplaats([A|B],[C|D]):- 
	verplaats_1(A,C),
	verplaats(B,D).

verplaats_beste_1((Persoon,Plaats),[Persoon,Plaats,Plaats2|Rest]):- 
	
	(	
	bagof(Pl,((buurvan(Plaats,Pl);buurvan(Pl,Plaats)),hotel(Pl)),Lijst) ->
		Lijst=[Plaats2|_],
		Rest=[]
	;	
		bagof(Buur,((buurvan(Plaats,Buur);buurvan(Buur,Plaats)),verplaats_beste_1((Persoon,Buur),[Persoon,Buur|Rest])),[Plaats2|_])
	),
	!.	

verplaats_beste([],[[]]).
verplaats_beste([X|Xs],[Y|Ys]):-
	verplaats_beste_1(X,Y),
	verplaats_beste(Xs,Ys).

--Bart 11 jan 2009 10:26 (UTC)