Theorie	Formale Sprachen und Automaten Berechenbarkeit, alt Berechenbarkeit Komplexitätstheorie Pfad: Startseite / Fächer / Informatik / Theorie
Autor: mk 17.02.2008 19:44:24 537	Das Problem des Handlungsreisenden

Aufgabe 1

Aufgabenstellung

Brute-Force-Lösung mit Prolog

% Autor: mk
% Datum: 17.2.2008
% d = unsymmetrische Distanz
d(a,a,0).
d(a,b,65).
d(a,c,127).
d(a,d,43).
d(a,e,38).
d(a,f,94).
d(b,b,0).
d(b,c,157).
d(b,d,100).
d(b,e,62).
d(b,f,29).
d(c,c,0).
d(c,d,92).
d(c,e,98).
d(c,f,181).
d(d,d,0).
d(d,e,31).
d(d,f,117).
d(e,e,0).
d(e,f,90).
d(f,f,0).

% dist = symmetrische Distanz
dist(X,Y,E) :- d(X,Y,E).
dist(X,Y,E) :- d(Y,X,E).

weg([_],0).
weg([K1,K2|R],N) :- dist(K1,K2,N1),weg([K2|R],N2),N is N1+N2.
rundweg([_],0).
rundweg([K|R],N) :- last(R,S),dist(S,K,N1),weg([K|R],N2),N is N1+N2.

staedte(L) :- findall(S,d(S,_,_),L1),list_to_set(L1,L).

alleWege(L) :- staedte(S),findall([N|P],(permutation(S,P),rundweg(P,N)),L).

optimalerWeg(W,N) :- alleWege(L1),sort(L1,L2),L2=[K|_],K=[N|W].

Schritt 2

Mutation beim Problem des Handlungsreisenden

Schritt 3

Rekombination beim Problem des Handlungsreisenden

Schritt 4

Selektion beim Problem des Handlungsreisenden

genAlg2.pl

lokal