Bergervei/Prolog-Das Haus des Nikolaus

Wiki-Quelltext dieser Seite.

<language>Prolog</language>
== Vollständige Strecken ==

<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 der vollständigen Strecke sein. Durch Tiefensuche werden nun die entsprechenden Kanten ermittelt und dabei aus der Streckenliste herausgestrichen. Eine vollständige Strecke ist dann gefunden, wenn die vorgegebene Streckenliste leer ist.
</td>
<td>
[[Datei:Nikolaushaus1.GIF|miniatur|Das Haus des Nikolaus]]
</td>
</tr>
</table>

<code id="51294af6f3bb8">
%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).

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="51294af6f3c37">
suche([a,b,c,d,e]).
</run>