Bergervei/Prolog-Das Haus des Nikolaus

Wiki-Quelltext dieser Seite.

<language>Prolog</language>
== Vollständiger Graphendurchlauf ==

<table border="0" cellspacing="0" cellpadding="0">
<tr valign="top">
<td>
Das bekannte Nikolaushaus soll in einem Zug gezeichnet werden, d.h. jede Kante wird dabei genau einmal durchlaufen. Im Gegensatz zum Königsberger Brückenproblem (Eulerzyklus) müssen dabei Start- und Zielknoten nicht übereinstimmen.

Zunächst werden alle in Frage kommenden Strecken aus der Datenbasis herausgesucht und in einer Streckenliste gesammelt. Das erste Element der gewünschten Reiseroute (Knotenliste) soll der Startknoten des vollständigen Graphendurchlaufs sein. Durch Tiefensuche werden nun die entsprechenden Kanten ermittelt und dabei aus der Streckenliste herausgestrichen. Eine vollständiger Durchlauf ist dann gefunden, wenn die vorgegebene Streckenliste leer ist.

Wie viele Möglichkeiten des vollständigen Durchlaufs dieses Graphen gibt es?
</td>
<td>
[[Datei:Nikolaushaus1.GIF|miniatur|Das Haus des Nikolaus]]
</td>
</tr>
</table>

<code id="5129508c3cfac">
%Festlegung des Graphen (Nikolaushaus)
kante(a,b). kante(b,c). kante(c,d). kante(d,e). kante(e,a).
kante(b,d). kante(a,d). kante(e,b).

verbunden(A,B):-kante(A,B).
verbunden(A,B):-kante(B,A).

%Rundstrecke
rundstrecke(Route,Weg):-
	Route=[Anfang|_],
        findall([A,B],
		(kante(A,B),element(A,Route),element(B,Route)),
		Strecken),
	tsuche(Anfang,[Anfang],Weg,Strecken).

%Tiefensuche
tsuche(Knoten,Weg,Weg,[]):-!.
tsuche(Knoten,Teilpfad,Weg,Strecken):-
	verbunden(Knoten,NKnoten),
	teilliste([Knoten,NKnoten],Strecken),
	streichliste([Knoten,NKnoten],Strecken,NStrecken),
	tsuche(NKnoten,[NKnoten|Teilpfad],Weg,NStrecken).

%Suche nach allen möglichen Rundstrecken
suche(Route):-
	findall(Weg,rundstrecke(Route,Weg),Liste),
	ausgabe(Liste).

%Bildschirmausgabe
ausgabe(Liste):-ausgabe_h(Liste,0).
ausgabe_h([],Anzahl):-
        write('Es gibt '),write(Anzahl),write(' Moeglichkeit(en)!'),nl,!.
ausgabe_h([Weg|Liste],Anzahl):-
	ausgabe_l(Weg),nl,
	NAnzahl is Anzahl+1,
	ausgabe_h(Liste,NAnzahl).
ausgabe_l([X]):-write(X).
ausgabe_l([X|Liste]):-ausgabe_l(Liste),write(', '),write(X).

%Hilfsprädikate
streichliste([A,B],[[A,B]|L],L):-!.
streichliste([A,B],[[B,A]|L],L):-!.
streichliste(X,[Y|L1],[Y|L2]):-streichliste(X,L1,L2).

teilliste([A,B],[[A,B]|L]):-!.
teilliste([A,B],[[B,A]|L]):-!.
teilliste(X,[Y|L]):-teilliste(X,L).

element(X,[X|L]):-!.
element(X,[Y|L]):-element(X,L).
</code>

<run id="5129508c3d017">
suche([a,b,c,d,e]).
</run>