Prolog - Rekursion - Kürzester Weg

Unregistriert

Hallo zusammen,

ich bin schon eine weile dabei ein Prolog Programm zu schreiben mit dem ich den kürzesten Weg ausgeben kann.

Der Code sieht bisher so aus:

nachbar(downtown,uptown,6).
nachbar(downtown,middletown,8).
nachbar(downtown,westtown,2).
nachbar(middletown,uptown,3).
nachbar(easttown,uptown,5).
nachbar(easttown,westtown,4).

loesung2(Start,Ziel):-
weg2(Start,Ziel,[Start],Pfad), % Aufruf der Tiefensuche
write('Pfad: '),
write(Pfad).

% weg2(Startknoten, Zielknoten, Liste der besuchten Knoten, Ergebnispfad)

weg2(Start,Ziel,Liste,Pfad):-
Start = Ziel, % Rekursionsausstieg, wenn aktueller Knoten mit Zielknoten identisch,
Pfad = Liste. % dann Übergabe der Liste als Tiefensuchpfad

weg2(Start,Ziel,Liste,Pfad):-
neben(Start,Knoten,L), % Ermittlung eines Knotens, der vom Startknoten wegführt
not(member(Knoten,Liste)), % Prüfung, ob Knoten schon mal besucht wurde (Zyklus)
weg2(Knoten,Ziel,[Knoten|Liste],Pfad). % Ermittelung der weiteren Wege ausgehend vom gefundenen Knoten zum Ziel,

neben(X,Y,D):- nachbar(X,Y,D).
neben(X,Y,D):- nachbar(Y,X,D).

...
Bis jetzt werden einfach alle möglichen Strecken ausgegeben ich bekomme es nichtmal hin einfach die Streckenlängen dann dahinterzuschreiben... Ziel wäre es dann nur den kürzesten Weg auszugeben

Würde mich über eine hilfreiche Antwort sehr freuen..

Mfg Tobi

The User

Wie wärs denn damit:

Code

weg2(Start, Ziel, Liste, Pfad, Länge)
...
weg2(Knoten,Ziel,[Knoten|Liste],Pfad,LS),
Länge is LS + L. % Gesamtlänge = Länge des vorherigen Weges + Länge des letzten Segments

In loesung2 kannst du die Länge noch ausgeben. Dann muss da natürlich noch ne Länge beim Abbruch festgelegt werden, aber das schaffst du schon.

Viele liebe Grüße
The User

Unregistriert

hallo User,

vielen Dank für deine Antwort.. also ich habe das mal probiert und komme irgendwie trotzdem nicht weiter.. also ich werde wohl keine Freund von Prolog.
Irgendwie kommt nun am Ende immer false raus und keine Ergebnisse.

->

nachbar(downtown,uptown,6).
nachbar(downtown,middletown,8).
nachbar(downtown,westtown,2).
nachbar(middletown,uptown,3).
nachbar(easttown,uptown,5).
nachbar(easttown,westtown,4).

loesung2(Start,Ziel):-
Länge is 0,
weg2(Start,Ziel,[Start],Pfad,Länge), % Aufruf der Tiefensuche
write('Pfad: '),
write(Pfad).

% weg2(Startknoten, Zielknoten, Liste der besuchten Knoten, Ergebnispfad)

weg2(Start,Ziel,Liste,Pfad,_Länge):-
Start = Ziel, % Rekursionsausstieg, wenn aktueller Knoten mit Zielknoten identisch,
Pfad = Liste. % dann Übergabe der Liste als Tiefensuchpfad

weg2(Start,Ziel,Liste,Pfad,Länge):-
neben(Start,Knoten,LS), % Ermittlung eines Knotens, der vom Startknoten wegführt
not(member(Knoten,Liste)), % Prüfung, ob Knoten schon mal besucht wurde (Zyklus)
weg2(Knoten,Ziel,[Knoten|Liste],Pfad,LS), % Ermittelung der weiteren Wege ausgehend vom gefundenen Knoten zum Ziel,
Länge is Länge + LS.

neben(X,Y,D):- nachbar(X,Y,D).
neben(X,Y,D):- nachbar(Y,X,D).

Nach langem probieren kommt zwar keine Exception mehr aber dafür nur noch false.
Wo liegt mein Fehler?

Mfg Tobi

The User

Mach das Länge = 0 einmal weg.

Unregistriert

hmm.. also wenn ich das wegmache sagt er mir das "Länge" nicht mehr initialisiert wird. Wenn ich dann weg(Start,Ziel,[Start],Pfad,0), anstatt weg(Start,Ziel,[Start],Pfad,Länge), am Anfang schreibe dann gehts zwar wieder aber es kommt dann wieder "false" raus.

hm

The User

Das erste weg2, das Rekursionsende musst du ändern, dort muss _Länge auf 0 gesetzt werden.

Unregistriert

Hallo,

also das funktioniert jetzt endlich soweit .. Vielen Dank dafür

nun kommt ein weiteres Problem auf mich und zwar wollte ich eine Liste neu belegen nur irgendwie nimmt der mir das nicht.. wie bekomme ich es denn hin wenn in einer Liste z.b. Y=[a,b,c]drinsteht das ich ihr z.b. die Werte einer Liste X=[1,2,3] zuweise???

Y = X geht nicht und Y is X auch irgendwie nicht. Wieso denn nicht?

Hoffe jemand kann mir weiterhelfen..

Mfg
Tobi

Tags