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)

Nog een oplossing. Misschien niet optimaal ofzo maar ze is duidelijk ;)

%Hulppredicaat
buur(X,Y):- 
    buurvan(X,Y).
buur(X,Y):-
    buurvan(Y,X).

%Oplossing
%enkel verplaats_beste gedaan. verplaats is trivaal natuurlijk.
verplaats_beste([] , []).
verplaats_beste([(Persoon, StartLocatie)|Rest], [(Persoon,Pad)|RestPaden]):-
    verplaatspersoon_beste(StartLocatie, Pad),
    verplaats_beste(Rest, RestPaden).
   

%verplaatspersoon(StartLocatie, Pad)
%Geeft het pad om naar een hotel te geraken vanuit een gegeven startlocatie
verplaatspersoon(StartLocatie, Pad):-
    verplaatspersoon(StartLocatie, [StartLocatie], Pad).

%Een pad eindigt als je aangekoment bent in een plaats met een Hotel
verplaatspersoon(HuidigeLocatie, _PadTotNuToe, [HuidigeLocatie]):- 
    hotel(HuidigeLocatie), !.
verplaatspersoon(HuidigeLocatie, PadTotNuToe, [HuidigeLocatie|RestPad]):-
    buur(Volgend, HuidigeLocatie),
    \+ member(Volgend, PadTotNuToe),
    append([Volgend], PadTotNuToe, PadVanafNu),
    verplaatspersoon(Volgend, PadVanafNu, RestPad).
    
verplaatspersoon_beste(StartLocatie, Pad):-
    findall(MogelijkPad-PadLengte, (verplaatspersoon(StartLocatie, MogelijkPad), length(MogelijkPad, PadLengte)), Paden),
    findall(Lengte, member(_Pad-Lengte, Paden), Lengtes),
    min_list(Lengtes, KortsteLengte),
    member(Pad-KortsteLengte, Paden).