 |
|||
| HSG |
|
Ein Prolog-Programm soll dabei helfen, Lösungen zu finden, das
'Haus des Nikolaus' in einem Zug (ohne eine Kante doppelt zu durchlaufen) zu zeichnen.
Untenstehendes Programm findet 44 Möglichkeiten, das Haus des Nikolaus von a aus in einem Zug zu zeichnen. Von b aus gibt es natürlich auch 44 Möglichkeiten. Von c, d und e aus gibt es keine Möglichkeit. Woran könnte das liegen?
pfeil(a,b).
pfeil(a,c).
pfeil(a,e).
pfeil(b,c).
pfeil(b,e).
pfeil(c,d).
pfeil(c,e).
pfeil(d,e).
verbunden(X,Y):-pfeil(X,Y);pfeil(Y,X).
loesung(Start,L):-findall([X,Y],verbunden(X,Y),Kanten),pfad(Start,[Start],Kanten,L).
pfad(KnotenA,L,[],L):-!.
pfad(KnotenA,P1,Kanten1,L):-verbunden(KnotenA,KnotenN),
member([KnotenA,KnotenN],Kanten1),
delete(Kanten1,[KnotenA,KnotenN],Kanten2),
delete(Kanten2,[KnotenN,KnotenA],Kanten3),
append(P1,[KnotenN],P2),
pfad(KnotenN,P2,Kanten3,L).
alleLoesungen(Start,L,N):-findall(Weg,loesung(Start,Weg),L1),list_to_set(L1,L),
length(L,N).
Erläuterungen
Der Graph wurde zunächst als gerichtet modelliert. Die Regel verbunden wird wahr, wenn es einen Pfeil von X zu Y oder von Y zu X gibt. Dh. letztendlich wurde doch ein ungerichteter Graph modelliert.
findall([X,Y],verbunden(X,Y),Kanten) baut eine Liste der Kanten auf. Dabei wird z.B. die Kante zwischen a und b durch das Paar [a,b],...,[b,a] repräsentiert.
pfad(KnotenA,P1,Kanten1,L) wird wahr, wenn es möglich ist, einen schon begonnenen Pfad P1 vom KnotenA aus 'regelgerecht' zu erweitern. Dabei enthält die Liste Kanten1 die benutzbaren Kanten. Der Pfad P1 wird zur Lösung, wenn die Liste der noch benutzbaren Kanten leer ist. Im Einzelnen arbeitet die Regel so:
- es wird ein KnotenN gesucht, der mit dem KnotenA verbunden ist
- die Kante von KnotenA zu KnotenN muss in der Kantenliste sein
- die Kante wird aus der Kantenliste gelöscht; das bedarf wg. der speziellen Repräsentation zweier delete-Befehle
- der KnotenN wird an den bisherigen Pfad angehängt
- vom KnotenN aus wird weiter versucht, den Pfad zu erweitern
alleLoesungen schreibt zunächst alle 'regelgerechten' Pfade in eine Liste L1, diese Liste wird um Dopplungen zu vermeiden zur Menge gemacht, die 'Länge' der Menge gibt die Anzahl der Lösungen an.
