Declaratieve Talen/Oplossing Handelsreiziger verplaatsen

Uit Wina Examenwiki
Versie door Beau (overleg | bijdragen) op 15 jun 2006 om 09:44 (oplossing handelsreiziger)
(wijz) ← Oudere versie | Huidige versie (wijz) | Nieuwere versie → (wijz)
Naar navigatie springen Naar zoeken springen

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)