Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Suchen in Graphen


Ein Graph ist anschauliches mathematisches Modell, das Beziehungen zwischen Objekten beschreibt. Es sollen Suchvorgänge in Graphen untersucht werden.

Motivation

Herr Paulsen ist Vertreter einer großen Versicherungsagentur. Er möchte seine Kundenbesuch möglichst effektiv gestalten und nimmt sich vor, von seinem Wohnort Hohenwulsch aus, die Orte der Kunden zu bereisen. Dabei möchte er jedes Dorf nur einmal besuchen und am Ende des Tages wieder in Hohenwulsch sein. Natürlich sind die dabei anfallenden Kosten/gefahrene Kilometer zu minimieren.

Die Lösung des Problems dürfte Herrn Paulsen viel Kopfzerbrechen bereiten, denn es handelt sich um eines der schwierigsten Probleme der Informatik und trägt den Namen "Das Problem des Handlungsreisenden (TSP)"

Wir wollen uns dem Problem vorsichtig nähern und untersuchen die Wege im dargestellten Graphen.

Definition und Arten von Graphen

Ein Graph G besteht aus einer Menge von Punkten (Knoten) und einer Menge von Linien (Kanten), die diese Punkte verbindet.

Es wird unterschieden in 

ungerichteter, unbewerteter Graph gerichteter, unbewerteter Graph gerichteter, bewerteter Graph
Besonderheit: Schlinge im Knoten d
Bild 2 Bild 3 Bild 4

Für die Untersuchung in Graphen spielen die Wege darin die zentrale Rolle. 

Ein Weg w von p0 nach pn ist eine Folgen von Punkten w = (p0, p1, ..., pn)  , wenn die jeweils aufeinander folgenden Punkte durch eine Kante verbunden sind. p0 ist der Anfangspunkt, pn der Endpunkt. 

Ein Zyklus/Kreis liegt vor, wenn der Anfangs- und Endpunkt übereinstimmen.

Ein Weg heißt einfach, wenn keiner der Punkte in der Folge mehrfach auftritt.

Beispiele:

Der Graph in Bild 2 hat u. a. den Zyklus a - b - c, der Graph in Bild 3 hat keinen Zyklus

Implementationsmöglichkeiten  

Die Graphentheorie nutz zur Darstellung von Graphen die sog. Adjazenzmatrix. Dazu werden die Knoten fortlaufend nummeriert und die Beziehungen als Matrix notiert. Liegt ein unbewerteter Graph vor, so entsteht eine Boolsche Matrix.

Beispiel für die obigen Bilder 2 bis 4:

ungerichteter, unbewerteter Graph gerichteter, unbewerteter Graph gerichteter, bewerteter Graph
Besonderheit: Schlinge im Knoten d
  a b c d e f g
a   1 1 1      
b 1   1        
c 1 1     1 1  
d 1         1 1
e     1        
f     1 1      
g       1      
  a b c d e f g
a              
b 1            
c 1 1       1  
d 1            
e     1        
f       1      
g       1      
  a b c d e f g
a              
b 4            
c 10 6       4  
d 7     1      
e     2        
f       6      
g       6      

In der imperativen Programmierung kann man nun entweder diese Matrix implementieren oder man greift auf andere Möglichkeiten, z. B. verkettete Listen zurück. Die logische Programmierung mit PROLOG bietet eine einfache Variante zur Speicherung der Informationen: jede Kante wird als Fakt notiert. 

Beispiel:

ungerichteter, unbewerteter Graph gerichteter, unbewerteter Graph gerichteter, bewerteter Graph
Besonderheit: Schlinge im Knoten d
kantegerichtet(a,b).
kantegerichtet(a,c).
kantegerichtet(a,d).
kantegerichtet(b,c).
kantegerichtet(c,e).
kantegerichtet(c,f).
kantegerichtet(d,f).
kantegerichtet(d,g).

kante(X,Y):-kantegerichtet(X,Y).
kante(X,Y):-kantegerichtet(Y,X).

kante(a,b).
kante(a,c).
kante(a,d).
kante(b,c).
kante(c,e).
kante(d,f).
kante(d,g).
kante(f,c).
kante(a,b,4).
kante(a,c,10).
kante(a,d,7).
kante(b,c,6)
kante(c,e,2).
kante(d,d,1)
kante(d,f,6).
kante(d,g,6).
kante(f,c,4).

Suchen in Graphen

Es ist eine PROLOG-Prädikat weg(P1,P2) zu finden, dass 

a) testet, ob ein Weg von P1 zu P2 existiert,
b) zu einem gegebenen Startpunkt P1 alle Punkte ausgibt, die mit ihm durch den Graphen verbunden sind.

Die Suche nach dem Weg kann nach dem Prinzip der Tiefen- oder Breitensuche erfolgen.

Tiefensuche 

Tiefensuche bedeutet, dass man beginnend im Startknoten so weit wie möglich entlang der bestehenden Kanten in die Tiefe geht, ehe man zurückläuft und dann in bislang unbesuchte Teilbäume absteigt.

Da PROLOG selbst nach dem Prinzip der Tiefensuche arbeitet, ist die (rekursive) Implementierung nicht so schwer.

1. Versuch:

weg(X,Y):-kante(X,Y).
weg(X,Y):-kante(X,Z),weg(Z,Y).

Es handelt sich um den "üblichen" rekursiven Aufruf. Das System arbeitet fehlerfrei, solange kein Zyklus im Graph existiert, ansonsten kommt das System in eine Endlosschleife. 

2. Versuch:

Nun soll der Lösungspfad im Graphen mit ausgegeben werden. Das Startprädikat heißt loesung1 und ruft die eigentliche Prozedur weg1/4 auf. Beim ersten Aufruf sorgt das Argument [Start] dafür, dass der Startknoten Bestandteil der Merkliste wird. Das Argument Pfad enthält den Tiefensuchpfad, falls die Suche erfolgreich war.

loesung1(Start,Ziel):-
weg1(Start,Ziel,[],Pfad), % Aufruf der Tiefensuche
write('Pfad: '),
write(Pfad).

% weg1(Startknoten, Zielknoten, Liste der besuchten Knoten, Ergebnispfad)

weg1(Start,Ziel,Liste,Pfad):-
Start = Ziel, % Rekursionsausstieg, wenn aktueller Knoten mit Zielknoten identisch,
 Pfad = Liste. % dann Übergabe der Liste als Tiefensuchpfad


weg1(Start,Ziel,Liste,Pfad):-
kante(Start,Knoten), % Ermittlung eines Knotens, der vom Startknoten wegführt
weg1(Knoten,Ziel,[Knoten|Liste],Pfad). % Ermittelung der weiteren Wege ausgehend vom gefundenen Knoten zum Ziel,
% gefundener Knoten wird zur Merkliste hinzugefügt
% Aufrufbeispiel für Beispielgraph im Bild 3:
?- loesung1(a,e).
Pfad: [e, c, b, a]
% Aufrufbeispiel für Beispielgraph im Bild 2:
?- loesung1(a,d).
Error: Out of local stack

Das Programm versagt also bei Graphen mit Zyklen. Um dieses Problem zu lösen, muss sich das Programm prüfen, ob der nächste Knoten schon mal besucht wurde. 

3. Versuch:

Das Programm prüft mit not(member(Knoten, Liste), ob der gefundene Knoten schon in der Lösungsliste ist. 

loesung2(Start,Ziel):-
weg2(Start,Ziel,[],Pfad), % Aufruf der Tiefensuche
write('Pfad: '),
write(Pfad).

% weg2(Startknoten, Zielknoten, Liste der besuchten Knoten, Ergebnispfad)

weg2(Start,Ziel,Liste,Pfad):-
Start = Ziel, % Rekursionsausstieg, wenn aktueller Knoten mit Zielknoten identisch,
 Pfad = Liste. % dann Übergabe der Liste als Tiefensuchpfad

weg2(Start,Ziel,Liste,Pfad):-
kante(Start,Knoten), % Ermittlung eines Knotens, der vom Startknoten wegführt
not(member(Knoten,Liste)), % Prüfung, ob Knoten schon mal besucht wurde (Zyklus)
weg2(Knoten,Ziel,[Knoten|Liste],Pfad). % Ermittelung der weiteren Wege ausgehend vom gefundenen Knoten zum Ziel,
% gefundener Knoten wird zur Merkliste hinzugefügt
% Aufrufbeispiel für Beispielgraph im Bild 2:
?- loesung2(a,d).
Pfad: [d, f, c, b, a]

In der Literatur finden sich oft Lösungen, die den Pfad in der richtigen Reihenfolge ausgibt. Dazu muss das reverse-Prädikat verwendet werden. Gleichzeitig werden einige verkürzte Schreibweisen benutzt.

loesung3(Start,Ziel):-
weg3(Start,Ziel,[],Pfad), % Aufruf der Tiefensuche
write('Pfad: '),
write(Pfad).

% weg3(Startknoten, Zielknoten, Liste der besuchten Knoten, Ergebnispfad)

weg3(Knoten,Knoten,Liste,Pfad):-
reverse(Liste,Pfad). % Rekursionsausstieg, wenn aktueller Knoten mit Zielknoten identisch,
% Übergabe der Liste als Tiefensuchpfad

weg3(Start,Ziel,Liste,Pfad):-
kante(Start,Knoten), % Ermittlung eines Knotens, der vom Startknoten wegführt
not(member(Knoten,Liste)), % Prüfung, ob Knoten schon mal besucht wurde (Zyklus)
weg3(Knoten,Ziel,[Knoten|Liste],Pfad). % Ermittelung der weiteren Wege ausgehend vom gefundenen Knoten zum Ziel,
% gefundener Knoten wird zur Merkliste hinzugefügt

Vor- und Nachteile:

Breitensuche

Breitensuche bedeutet, dass man beginnend im Startknoten alle direkt verbundenen Knoten besucht, bevor zur nächst tieferen Ebene gegangen wird.  

Zur Implementierung in PROLOG wird auf das Prädikat findall/3 zurückgegriffen, um alle Knoten zu finden, die direkt zu erreichen sind. 

loesung4(Start,Ziel):-
weg4([Start],Ziel,[],Pfad), % Aufruf der Breitensuche, Besonderheit: Startknoten wird als Liste übergeben
write('Pfad: '),
write(Pfad).

% weg4(Startknotenliste, Zielknoten, Liste der besuchten Knoten, Ergebnispfad)

weg4(Startliste,Ziel,_,Pfad):-
Startliste=[Ziel|_],
% Rekursionsausstieg, wenn Ziel in der Startknotenliste enthalten ist,
 reverse(Startliste,Pfad).
% Umdrehen der Liste und Übergabe als Breitensuchpfad

weg4(Startliste,Ziel,Liste,Pfad):-
Startliste=[Start|_], % erstes Element der Startliste holen
findall([Knoten|Startliste], % alle Nachfolgeknoten finden und
(kante(Start,Knoten), % prüfen, ob schon mal besucht
not(member(Knoten,Startliste))),
Knotenliste),
append(Liste,Knotenliste,Listeneu), % gefundene Elemente an Liste anhängen (Warteschlange)
Listeneu=[PfadN|RestPfad], % neue Liste zerlegen
weg4(PfadN,Ziel,RestPfad,Pfad). % Ermittelung der weiteren Wege ausgehend vom gefundenen Knoten zum Ziel

% Aufrufbeispiel für Beispielgraph im Bild 3: (Ausgabe von X wurde weggelassen)

?- loesung4(a,X).
Pfad: [a]
Pfad: [b, a]
Pfad: [c, a]
Pfad: [d, a]
Pfad: [c, b, a]
Pfad: [e, c, a]
Pfad: [f, d, a]
Pfad: [g, d, a]

Vor- und Nachteile:

Heuristische Suche

Heuristische Suche bedeutet, dass versucht wird, "günstige" Pfade zu gehen. Voraussetzung ist ein bewerteter Graph.

Günstige Pfade sind aufgabenabhängig. So kann es eine Kosten- oder Entfernungsminimierung/-maximierung sein.




zur Startseite
© Tino Hempel 1997 - 2006 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.