Bahnauskunftssystem in Prolog

Versuch einer rekursiven Lösung

/* Datenbank */ /* nur aus Fakten bestehend */ /* strecke(Anfangsort,Endort,Laenge). */ strecke(erfurt,weimar,21). strecke(weimar,apolda,16). strecke(weimar,bad_berka,15). strecke(weimar,jena,23). strecke(apolda,naumburg,23). strecke(naumburg,halle,43). strecke(halle,leipzig,41). strecke(naumburg,leipzig,54). strecke(naumburg,camburg,13). strecke(camburg,jena,14). strecke(jena,stadtroda,15). strecke(stadtroda,hermsdorf,11). strecke(hermsdorf,gera,19). strecke(jena,kahla,15). strecke(kahla,orlamuende,5). strecke(orlamuende,rudostadt,12). strecke(orlamuende,poessneck,14). strecke(rudolstadt,saalfeld,11). strecke(saalfeld,probstzella,25). strecke(erfurt,soemmerda,25). strecke(soemmerda,sangerhausen,45). strecke(sangerhausen,eisleben,22). strecke(eisleben,halle,38). /* Regel, die sichert, dass die Verbindung reflexiv wird. */ direkte_verbindung(Von,Nach,Laenge):-    strecke(Von,Nach,Laenge);    strecke(Nach,Von,Laenge). /* Versuch einer rekursiven Loesung */ verbindung(Anfang,Ziel,Weg):-    direkte_verbindung(Anfang,Ziel,Weg). verbindung(Anfang,Ziel,Weg):-    direkte_verbindung(Anfang,Umsteige,Weg1),    verbindung(Umsteige,Ziel,Weg2),    Weg is Weg1 + Weg2.

Das Prädikat verbindung/3 verhält sich nicht wie erwartet. Manchmal wird ein Weg gefunden, oft tritt eine Endlosrekursion auf.

Zur Fehlersuche kann man sich die besuchten Orte ausgeben lassen: Dazu muss man das Prädikat verbindung/3 wie folgt abändern: verbindung(Anfang,Ziel,Weg):-    direkte_verbindung(Anfang,Ziel,Weg). verbindung(Anfang,Ziel,Weg):-    direkte_verbindung(Anfang,Umsteige,Weg1),    write(Anfang),    write('--->'),    write(Umsteige),    nl,    verbindung(Umsteige,Ziel,Weg2),    Weg is Weg1 + Weg2.

Es ist nun gut erkennbar, dass das Programm bei Endlosrekursion zwischen zwei Orten hin und her irrt. Dieser Fehler ist durch Führen der besuchten Orte in einer Liste abstellbar.

zum nächsten Lösungsschritt