[PROLOG] Suchbaum aufbauen
-
Momentan versuche ich mich in PROLOG hineinzudenken. An einer Stelle bin ich dabei auf Probleme gestoßen, die durch das folgende Beispiel hoffentlich deutlich werden:
Es gibt eine beliebig lange Liste, die einen Startzustand zu einem bestimmten Problem darstellt. Z.B.: [1,2,3,4].
Genauso liegt ein Zielzustand vor - also beispielsweise [4,3,2,1].Jetzt definiere ich n verschiedene Prädikate, mit denen jeweils zwei Elemente der Startliste unter gegenseitiger Abhängigkeit manipuliert werden können:
umformen1(Foo, Bar, FooNeu, BarNeu) :- ... . . . umformenN(Foo, Bar, FooNeu, BarNeu) :- ...Die Prädikate erhalten zwei Elemente aus der Liste, prüfen ob die jeweilige Umformung erlaubt ist, formen gegebenenfalls um und unifizieren FooNeu und BarNeu mit dem Ergebnis der Umformung.
Das Programm soll nun herausfinden, in welcher Reihenfolge welche Umformungen auf welche Elemente der Liste ausgeführt werden müssen, um vom Startzustand in den Zielzustand zu gelangen.
findeWeg(Startliste, Zielliste) :- ...Der naive - und damit mein
- Lösungsansatz ist das Aufspannen eines Suchbaums. Der erste Knoten ist der Startzustand. Dieser erhält soviele Folgeknoten, wie es mögliche Umformungen gibt. Daraufhin werden diese Folgezustände rekursiv an findeWeg/2 übergeben, geprüft und wenn das Ziel noch nicht erreicht ist wie ihr Vorgänger expandiert. (Endlosschleifen würden durch ein Speichern der bereits besuchten Zustände in einer Liste und einem "+\member(AktuellerZustand, BereitsBesuchteZustaende)" verhindert.)
Nur wie bekomme ich die Elemente der Eingangsliste in die Prädikate? "Einfach" die Elemente der Startliste durch entsprechende Listenoperationen isolieren und in jeder Kombination an jedes Prädikat übergeben? Das ist aber nun eine sehr prozedurale Vorgehensweise, die Lösung wirkt entsprechend wenig elegant und ressourcenschonend.
So wie ich Prolog kennengelernt habe müsste es doch eine Möglichkeit geben dem Compiler zu sagen "da ist eine Liste, da die Prädikate, jetzt tobe dich aus und suche per Backtracking einen Weg zu dieser Liste".
Gut, vielleicht nicht ganz so simpel aber zumindest eleganter als das oben geschilderte Verfahren. Ich suche eben eine Möglichkeit nur Start, Ziel und die Übergänge anzugeben, aber nicht das Lösungsverfahren. (Das ist ja die "Philosophie" von PROLOG, wenn ich nicht alles falsch verstanden habe ...)Wie geht ein richtiger PROLOGer an eine solche Situation ran? Bin für alle Hinweise dankbar, schon einmal vielen Dank für die Antworten.