AuK/Graphen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Python</language>
==Motivation und Definition==
Die Graphentheorie hat sich seit langem als Teilgebiet der Mathematik etabliert.
''Graphen'' eignen sich hervorragend zur Modellierung realer Systeme und von Prozessen. Die Abbildung von Straßennetzen in Navigationssystemen, von Netzwerken in Routern und Freundschaftsbeziehungen in sozialen Netzen sind nur einige Anwendungsbeispiele. Graphen für Überführungsfunktionen abstrakter Automaten stellen deren Verhalten, wenn Zustandswechsel ausgelöst werden, sehr anschaulich dar.
Ein Graph $G=(V,E)$ besteht aus einer Menge $V$ (vertex) von ''Knoten'' (Ecken) und einer Menge $E$ (edge) von Kanten, die je zwei ''adjazente'' (benachbarte) Knoten verbinden. Eine Kante die die Knoten $i$ und $j$ verbindet, wird als Zweiermenge $\{i, j\}$ bzw. als ein geordnetes Paar $(i, j)$ notiert.
Man sagt, eine Kante ''inzidiert'' mit den beiden Knoten, die sie verbindet. Prinzipiell sind auch mehrere parallele Kanten zwischen je zwei Knoten und reflexive Kanten (Schlinge: Kante von einem Knoten zu sich selbst) möglich. Diese Formen betrachten wir hier jedoch nicht. Der Grad eines Knotens ergibt sich aus der Anzahl der inzidierenden Kanten.
In der Informatik ist ein Graph ein abstrakter Datentyp (ADT), der die mathematische Definition geeignet abbildet. Im Folgenden werden wir nur Graphen betrachten, die (zwischen zwei beliebigen, nicht notwendigerweise verschiedenen Knoten) keine Mehrfachkanten besitzen.
<!-- Bei der Darstellung eines Graphen spielt die Art und Weise, wie die Kanten gezeichnet werden, keine Rolle. Entscheidend ist lediglich die Menge der Knoten und die Menge der Kanten, die die Knoten verbinden. Zwei unterschiedlich dargestellte Graphen mit den gleichen Knoten und Kanten werden als isomorphe Graphen bezeichnet. In der Regel betrachtet man isomorphe Graphen als äquivalente Graphen. -->
==Arten von Graphen==
===Ungerichteter Graph===
Bei einem ungerichteten Graphen wird die Richtung der Kanten nicht berücksichtigt, d.h. eine Kante $\{i, j\}$ bedeutet eine Direktverbindung vom Knoten $i$ zum Knoten $j$, als auch eine Direktverbindung von $j$ zu $i$. Somit gilt $(i, j) = (j, i)$.
Ein '''Weg''' ist eine Knotenfolge, die jeden Knoten aus $|V|$ höchstens einmal enthält.
'''Beispiel:''' Ungerichteter Graph mit $V = \{0,1,2,3,4\}$ und $E = \{\{0,1\},\{0,4\},\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{3,4\}\}$:
[[Datei:undirectedgraph.png|center|400px]]
Die Kanten eines ungerichteten Graphen werden als einfache Verbindungslinien, d.h. Strecken oder Bögen zwischen je zwei Knoten, dargestellt.
===Gerichteter Graph===
Bei einem gerichteten Graphen wird die Richtung der Kante berücksichtigt und durch einen Pfeil symbolisiert.
Eine gegebene Kante $(i, j)$ besagt lediglich, dass es einen Weg von $i$ nach $j$ gibt; nicht automatisch auch von $j$ nach $i$.
'''Beispiel:''' Gerichteter Graph mit $V = \{A,B,C,D,E,F\}$ und $E = \{(A,B),(B,C),(C,E),(D,B),(E,D),(E,F)\}$:
[[Datei:2000px-Directed_graph_cyclic.png|center|250px]]
Da eine Kante $\{i, j\}$ in einem ungerichteten Graph durch die beiden Kanten $(i, j)$ und $(j, i)$ in einem gerichteten Graphen dargestellt werden kann, kann jeder ungerichtete Graph in einen äquivalenten gerichteten Graph übertragen werden. Die Umkehrung gilt nicht.
===Gewichteter Graph===
Bei einem ''gewichteten Graphen'' wird jeder Kante ein numerischer Wert als ''Gewicht'' zugeordnet. Im Jargon spricht man auch von einem "kantengelabelten" Graphen.
Die Gewichte können dabei jegliche Arten von Kosten darstellen. Dies ist beispielsweise nützlich, um ein Straßennetz abzubilden und mit den Gewichten die Distanz zwischen Knotenpunkten (Städten) anzugeben. Bei einem Navigationssystem könnten auch die benötigte Reisezeit oder der Kraftstoffverbrauch durch die Gewichte ausgedrückt werden.
Ein gewichteter Graph kann sowohl ''gerichtet'', als auch ''ungerichtet'' sein.
[[Datei:graph-STL.png|center|250px]]
==Repräsentation von Graphen==
===Adjazenzmatrix===
Eine typische Form einen Graphen zu repräsentieren ist die ''Adjazenzmatrix'' (Nachbarschaftsmatrix). Dabei handelt es sich um eine ''quadratische Matrix'', deren Zeilen und Spalten den Knoten des Graphen entsprechen. Als konkrete Datenstruktur wird im Allgemeinen ein zweidimensionales Feld verwendet. Die Zeilenknoten interpretiert man als "von"-Knoten und die Spaltenknoten als die "nach"-Knoten. Der in der Matrix im Feld $[i,j]$ eingetragene Wert ist das Gewicht der Kante $(i,j)$. Existiert eine Kante nicht, so wird ein Ersatzwert, wie $\infty$ oder '''null''' verwendet. Handelt es sich um einen ungewichteten Graphen, so können auch Booleans oder $0/1$ für die Nicht/Existenz der betrachteten Kante verwendet werden.
'''Beispiel:''' Der Graph
[[Datei:graph-STL.png|center|250px]]
wird folgendermaßen dargestellt:
<!--
| von/nach | 0 | 1 | 2 | 3 |
| ---------|---|---|---|---|
| 0 | 0 | 10 | 3 | 2 |
| 1 | $\infty$ | 0 | $\infty$ | 7 |
| 2 | $\infty$ | $\infty$ | 0 | 6 |
| 3 | $\infty$ | $\infty$ | $\infty$ | 0 |
-->
{| class="wikitable" style="vertical-align:middle;margin:0 auto;"
|- style="font-weight:bold;"
! von/nach
! 0
! 1
! 2
! 3
|-
| 0
| 0
| 10
| 3
| 2
|-
| 1
| $\infty$
| 0
| $\infty$
| 7
|-
| 2
| $\infty$
| $\infty$
| 0
| 6
|-
| 3
| $\infty$
| $\infty$
| $\infty$
| 0
|}
Zugehörige Adjazenzmatrix:
$$
\begin{bmatrix}
0 & 10 & 3 & 2 \\
\infty & 0 & \infty & 7 \\
\infty & \infty & 0 & 6 \\
\infty & \infty & \infty & 0 \\
\end{bmatrix}
$$
Da es sich um eine quadratische Matrix handelt, beträgt der Speicheraufwand $\mathcal{O}({\lvert V \rvert}^2)$. $|V|$ steht für die Anzahl der Knoten.
Die Adjazenzmatrix ist als Repräsentationsform ungeeignet, wenn der Graph nur wenige Kanten besitzt, denn dann besteht die Matrix vor allem aus "Blindeinträgen", wie eben $\infty$.
===Adjazenzliste===
Eine alternative Repräsentation eines Graphen ist die ''Adjazenzliste'': Für jeden Knoten $v$ wir (in einer Liste) vermerkt, mit welchen Knoten $v$ verbunden (adjazent) ist und welches Gewicht die ggf. gerichtete Kante besitzt. Die Elemente der Adjazenzliste sind also `(node, weight)`-Paare. Bei ungewichteten Graphen ist das "Standardgewicht" jeder Kante eine $1$. (Dies kann auch für die Zählung von Niveaus oder Schritten von Vorteil sein.)
Handelt es sich um einen Graphen mit wenigen Kanten, so wird gegenüber einer Adjazenzmatrix weniger Speicherplatz verbraucht, da lediglich für die existierenden Kanten Speicher beansprucht wird. Die Worst-case-Speicherkomplexität beträgt aber ebenfalls $\mathcal{O}({\lvert V \rvert}^2)$, da es bis zu $\lvert V \rvert \cdot \left( \lvert V \rvert - 1 \right) \in \mathcal{O}({\lvert V \rvert}^2)$ Kanten geben kann.
<code>
class Node:
def __init__(self, name):
self.name = name
self.adj = []
def add_to_adj_lst(self, node, weight=1):
self.adj.append((node, weight))
def adjprint(self):
for p in self.adj:
print('v'+p[0].name, p[1], sep=',', end=' ')
</code>
<code>
v0 = Node('0')
v1 = Node('1')
v2 = Node('2')
v3 = Node('3')
v0.add_to_adj_lst(v1, 10)
v0.add_to_adj_lst(v2, 3)
v0.add_to_adj_lst(v3, 2)
v1.add_to_adj_lst(v3, 7)
v2.add_to_adj_lst(v3, 6)
</code>
<run>
v0.adjprint()
</run>
Im Programmbeispiel werden vier Knoten instanziiert. Von <var>v0</var> aus gibt es gewichtete Kanten zu <var>v1</var>, <var>v2</var> und <var>v3</var>.
Neben den beiden genannten Repräsentationsformen für Graphen gibt es weitere, die wir hier jedoch nicht betrachten.
==Graphalgorithmen==
===Breadth-First Search (BFS, Breitensuche)===
Eine typische Fragestellung für Graphen ist die nach der ''Erreichbarkeit von Knoten'' von einem bestimmten Startknoten aus. Dies ist oftmals verbunden mit der ''Frage nach dem kürzesten Weg vom Start- zum Zielknoten'' (Single-Source Shortest Path). Bei ungewichteten Graphen entspricht die Entfernung vom Start- zum Zielknoten der Anzahl der auf dem Weg liegenden Kanten. In folgendem Beispiel ist 2 die geringste Entfernung von Knoten 4 vom Startknoten 0, wegen $(0,2,4)$, nicht etwa 3, wegen $(0,5,3,4)$, oder 4, wegen $(0,5,3,2,4)$ bzw. $(0,1,2,3,4)$.
'''Beispiel:''' Wir starten im Knoten mit der Bezeichnung 0 des folgenden Graphen.
[[Datei:AuK_Graphen_Graph4.png|center|300px]]
<code id="5f389c2366e5c">
# Knoten
a = Node('0')
b = Node('1')
c = Node('2')
d = Node('3')
e = Node('4')
f = Node('5')
# Adjazenzlisten
a.add_to_adj_lst(b)
a.add_to_adj_lst(c)
a.add_to_adj_lst(f)
b.add_to_adj_lst(a)
b.add_to_adj_lst(c)
c.add_to_adj_lst(a)
c.add_to_adj_lst(d)
c.add_to_adj_lst(e)
d.add_to_adj_lst(c)
d.add_to_adj_lst(e)
d.add_to_adj_lst(f)
e.add_to_adj_lst(c)
e.add_to_adj_lst(d)
f.add_to_adj_lst(a)
f.add_to_adj_lst(d)
</code>
Die ''klassische Breitensuche (BFS)'' bildet die Grundlage für eine Reihe von Algorithmen zur Verarbeitung von Graphen.
Bei der Breitensuche in einem ungewichteten Graphen wird - anders als bei der weiter unten betrachteten ''Tiefensuche (Depth-First Search, DFS)'' - gleichmäßig vom Wurzelknoten (der Knoten, bei dem der gesuchte Pfad beginnt) aus vorwärts gegangen. "Gleichmäßig" bedeutet dabei, dass, bevor man weiter in die Tiefe des Graphen voran schreitet, zunächst alle Knoten einer Ebene festgestellt werden. Zwei Knoten sind dabei auf der gleichen Ebene, wenn sie gleich weit, d.h. um die gleiche Anzahl an Knoten, vom Wurzelknoten entfernt sind.
Wenn wir nach den kürzesten Wegen zu den Knoten eines Graphen vom Wurzelknoten aus fragen, ist sofort einzusehen, dass wir Kreise ausschließen müssen. Ein Weg (geschlossener Kantenzug), der außer dem Anfangs- und Endknoten jeden seiner Knoten nur einmal durchläuft, heißt '''Kreis'''. Im Beispielgraphen sind $(0,5,3,4,2,0)$ und $(0,5,3,2,0)$ solche Kreise. Wie im Kreisverkehr führt jede weitere Runde zurück zum Ausgangspunkt und macht die gefahrene Strecke nur länger. Wir müssen daher vermeiden, dass bereits besuchte Knoten erneut betreten/betrachtet werden. Diese "Erinnerung" erreicht man mit Markierungen.
Wir gehen folgendermaßen vor:
1. Wähle einen Startknoten, markiere ihn und schreibe ihn in eine Liste.
2. Streiche den ersten Knoten aus der Liste und nenne ihn ''aktiver Knoten''.
3. Markiere alle noch nicht markierten Nachbarn des ''aktiven Knotens''. Vermerke für alle nun markierten Nachbarn den aktiven Knoten als Vorgängerknoten (auf dem Weg zum Ziel).
4. Füge die neu markierten Knoten in der Liste (hinten) an.
5. Falls die Liste leer ist, dann Stopp, sonst weiter bei 2.
Wie man sieht, ist das BFS-Verfahren nicht rekursiv und es gibt auch kein Backtracking.
Die in den Schritten 2 und 4 angewandten Operationen (dequeue und enqueue) sind charakteristisch für '''Warteschlangen'''. Das Verarbeitungsprinzip heißt '''FIFO = First-In-First-Out''': Wer am Anfang einer Warteschlange steht, wird zuerst bedient; wer (irgendwann) bedient werden möchte, muss sich hinten anstellen. Eine dem entsprechende Datenstruktur nennt man [[AuK/Konkrete_Datenstrukturen/Queue|Queue]]. Sie ist in allen gängigen Programmiersprachen implementiert. In Python heißen die zugehörigen Methoden `put(node)` und `get()`.
Zur Erfassung des jeweiligen Vorgängerknotens wird im Programm eine Datenstruktur verwendet, die man [[AuK/Hashing_und_Hash-Tables#Dictionary|Dictionary]] nennt. Wir betrachten sie im Zusammenhang mit dem Thema ''Hashing'' etwas genauer. Es handelt sich um eine Menge von key-value-Paaren beliebigen Datentyps. Der zu einem Schlüssel (key) gehörende Wert (value) wird durch Angabe dieses Schlüssels (sehr effizient) gefunden. Ob eine bestimmte Eingabe tatsächlich ein Schlüssel ist, kann abgefragt werden:
<run id="5f3725b65ef8d">
wb1 = {'one' : 1, 'two' : 2, 'three' : 3}
print(wb1['two'])
if 'five' in wb1:
print(5)
else:
print('not in dict')
</run>
In der folgenden Funktion `bfs` sind sowohl die Schlüssel als auch die Werte des Dictionarys `pred` Knoten des betrachteten Graphen.
Der Eintrag des Vorgängerknotens in das Dictionary wird mit der Markierung des betrachteten Knotens verbunden, was genau dem Schritt 3 entspricht. Ein besuchter Knoten wird also dadurch markiert, dass er in der Dictionary erstmals erfasst wird.
<code id="5f389c2366f05">
import queue
def bfs(root):
pred = {} # Dictionary zur Aufnahme des Vorgängerknotens für jeden markierten Knoten
q = queue.Queue() # Warteschlange
q.put(root) # Zu Beginn root-Knoten in die Warteschlange legen
pred[root] = Node('-') # Markieren des Wurzelknotens
while not q.empty():
current = q.get() # aktiver Knoten
for node in current.adj: # Alle Nachbarknoten, ...
if node[0] not in pred: # die nicht markiert sind ...
q.put(node[0]) # in der Warteschlange hinten anfügen
pred[node[0]] = current # ersten Knoten aus Adjazenzliste markieren und Vorgängerknoten vermerken
for k in pred.keys():
print(k.name, pred[k].name) # Ausgabe des Vorgängerknotens für jeden markierten Knoten
</code>
<run id="5f389c2367a72">
bfs(a)
</run>
Aus diesen Angaben kann der BFS-Suchbaum für dieses Beispiel sehr einfach rekonstruiert werden. Jeder Knoten des Baumes besitzt genau einen Vorgänger.
[[Datei:AuK_Graphen_Graph5.png|center|200px]]
====Single-Source Shortest Path (SSSP)====
Um in einem ungewichteten Graphen (bzw. in einem gewichteten Graphen, bei dem alle Kanten das gleiche Gewicht haben) den kürzesten Weg von einem Quellknoten zu einem vorgegebenen Knoten zu finden, kann die Breitensuche verwendet werden. Da die Breitensuche gleichmäßig von Ebene zu Ebene expandiert, muss man während des BFS-Prozesses lediglich mitzählen, in welcher Ebene man sich befindet. Die Ebene gibt an, wie weit der jeweils gefundene Knoten vom Quellknoten entfernt ist (Anzahl der Kanten auf dem Pfad).
Mit Hilfe des folgenden Programms können wir die Aussage zum kürzesten Weg (2) von Knoten 0 (a) zum Knoten 4 (e) für unser obiges Beispiel vom Beginn des Abschnitts überprüfen. Die BFS als Basisprozesse ist deutlich erkennbar.
<code id="5f389c2366fbb">
def bfs_shortest_path(source, target):
if source == target:
return 0
node_to_level = {}
q = queue.Queue()
q.put(source) # Startknoten in Warteschlange legen
current_level = 0 # Niveau initialisieren
node_to_level[source] = current_level # Startknoten: Niveau 0
while not q.empty():
current = q.get()
current_level = node_to_level[current]
for node in current.adj:
if node[0] not in node_to_level:
if node[0] == target:
return current_level + 1
q.put(node[0])
node_to_level[node[0]] = current_level + 1
return None
</code>
<run id="5f389c2367b18">
print('distance from a to b: ', bfs_shortest_path(a, e))
print('distance from a to g: ', bfs_shortest_path(b, b))
print('distance from a to h: ', bfs_shortest_path(e, a))
</run>
===Depth-First Search (DFS, Tiefensuche)===
Eine BFS (in dieser Grundform) besucht für jeden Knoten alle Nachbarknoten des (zusammenhängenden) Graphen und setzt die Suche für diese entsprechend fort. Dies ist zwar sehr systematisch und für viele Aufgabenstellungen angemessen, kann aber in bestimmten Fällen aufwendiger sein.
Ein klassisches Beispiel ist das ''Labyrinthproblem''. Um von einem Startknoten (Eingang) aus den in einem (unbekannten) Zielknoten (Versteck) hinterlegten Schatz zu finden, ist eine systematische Suche erforderlich. Dafür hat sich (schon in der Antike) folgendes Verfahren herauskristallisiert: Markiere jede besuchte Kreuzung (Punkt mit mehreren Straßenabzweigungen) und setze die Suche bei einer der Folgekreuzungen fort. Gibt es an einer solchen keine unmarkierten Fortsetzungsmöglichkeiten, so gehe zurück zum letzten Entscheidungspunkt und wähle eine noch unmarkierte Folgekreuzung.
Diese Verfahren schreitet zuerst in die ''Tiefe'' des Suchbaums voran, nicht in die Breite, wie bei BFS. Es kann effizienter sein, da es viele Fortsetzungsmöglichkeiten unbetrachtet lässt. Im worst case muss dennoch der vollständige Suchbaum aufgebaut werden.
Nach dieser intuitiven Einführung können wir nun das Verfahren auf einer abstrakteren Basis mit Graphen präsentieren.
Die '''Depth-First Search (Tiefensuche)''' beginnt bei einem festgelegten Startknoten. Für jeden der zu diesem Startknoten adjazenten Knoten wird im Folgenden die Tiefensuche rekursiv durchgeführt. Man beginnt mit dem ersten dieser adjazenten Knoten und schreitet in die Tiefe (auf das nächste Niveau) rekursiv fort. Dies wird solange fortgesetzt, bis ein Knoten erreicht ist, der keine unbearbeiteten adjazenten Knoten hat. Die Rekursion sorgt dann automatisch dafür, dass zum letzten ausgewählten und nun vollständig bearbeiteten Knoten zurückgegangen wird. Die Fortsetzung erfolgt dort, wo die nächste Entscheidungsmöglichkeit besteht, d.h. beim nächsten adjazenten Knoten: ''Backtracking''.
Der beschriebene Prozess kann mit Hilfe eines '''Stacks''' (ADT) adäquat implementiert werden. Ein Stack arbeitet nach dem '''LIFO'''-Prinzip: ''Last-in-first out'': Das Element, das als letztes auf den Stack gelegt wurde, wird zuerst entfernt. Wie oben beschrieben, wird die Stackarbeit auf der Ebene der Programmiersprache durch die Verarbeitug ''rekursiver Prozeduren'' erledigt.
In folgendem Beispiel könnten Knotenvergleiche, die zur Elementsuche notwendig wären, leicht hinzugefügt werden.
'''Beispiel:'''
[[Datei:AuK_Graphen_Graph6.png|250px|center]]
<code id="5f3725b65e54d">
a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
e = Node('E')
f = Node('F')
g = Node('G')
a.add_to_adj_lst(b)
b.add_to_adj_lst(c)
b.add_to_adj_lst(e)
b.add_to_adj_lst(d)
c.add_to_adj_lst(e)
d.add_to_adj_lst(e)
e.add_to_adj_lst(f)
g.add_to_adj_lst(d)
</code>
Da die Reihenfolge, in der die zu B adjazenten Knoten C, E und D angegeben sind, für das Verfahren eine (gewisse) Rolle spielt, fragen wir danach:
<run id="5f389c2367bbe">
for i in b.adj:
print(i[0].name)
</run>
Nun können wir das DFS-Verfahren knapp und elegant rekursiv implementieren:
<code id="5f389c236707a">
def dfs(root):
print(root.name, end=' ')
for node in root.adj:
dfs(node[0])
</code>
<run id="5f389c2367c63">
dfs(a)
</run>
Es lohnt sich ein Ablaufprotokoll in Kurzform, A bedeutet dfs(A), anzufertigen:
[[Datei:WurzelbaumDSF01.png|center|200px]]
Die angegebenen Knoten werden unmittelbar nachdem sie das erste Mal besucht wurden, gedruckt. Fahren Sie mit dem Finger den Baum entlang und notieren Sie die jeweils erste (von jeweils drei) Knotenberührung(en). <tt>dfs(A)</tt> erfordert <tt>dfs(B)</tt>. Die Berechnung erfordert (bei oben ergründeter Reihenfolge der Adjazenzknoten $C, E, D$) <tt>dfs(C)</tt>. Daraus ergibt sich <tt>dfs(E)</tt> und schließlich <tt>dfs(F)</tt>. Da $F$ keinen Folgeknoten besitzt, liefert mehrfaches Backtracking die Fortsetzung bei <tt>dfs(E)</tt>, was wiederum <tt>dfs(F)</tt> aufruft. Der letzte Versuch findet mit <tt>dfs(D)</tt> statt, was wiederum <tt>dfs(E)</tt> und weiter <tt>dfs(F)</tt> berechnet. Es schließt sich mehrfaches Backtracking an, bis das Ausgangsniveau von $A$ wieder erreicht ist.
Es werden alle von A aus erreichbaren Knoten ausgegeben, entsprechend der Reihenfolge von DFS: Im Baum jeweils die erste Knotenberührung.
Der Knoten $G$ taucht nicht auf, da er von $A$ aus nicht erreichbar ist.
Da es mehrere Wege zu einem Knoten gibt, kommen Knoten mehrfach vor. Handelt es sich um einen Graphen mit ''Kreisen'' bzw. ''Zyklen'', so würde der Algorithmus nicht terminieren. Dies illustrieren wir an obigem Beispiel, indem wir eine Kante von $F$ nach $G$ hinzufügen, sodass mehrere Zyklen entstehen. (Es empfiehlt sich nach dem Experiment, die Kante wieder herauszukommentieren und alle Felder des Notebooks neu zu evaluieren.)
Um dies zu verhindern, kann man (z.B. in einem Dictionary) die bereits gefundenen Knoten speichern und den jeweils nächsten nur dann besuchen, wenn er vorher noch nicht betreten wurde. Dies vereinfacht auch die DFS in unserem obigen (zyklenfreien) Beispiel, wenn z.B. <tt>dfs(E)</tt> nicht mehrfach berechnet werden muss.
<code id="5f389c2367132">
def dfs_no_dupl(v, found={}):
if v not in found:
print(v.name, end=' ')
found[v] = True
for w in v.adj:
dfs_no_dupl(w[0], found)
</code>
<run id="5f389c2367d0b">
dfs_no_dupl(a)
</run>
Es folgt noch eine zweite Variante `dfs3`, die anstelle des Dictionarys für die markierten Knoten eine Menge verwendet. Man beachte, dass beide Funktionen zwar nicht in einen Endloszyklus hineinlaufen, wenn der Graph nicht zyklenfrei ist. Eine Vorabentscheidung, ob ein gegebener Graph einen Zyklus besitzt oder nicht, können sie beide nicht treffen. Wir geben sie an, weil daraus die Funktion `dfs_erreichbar` unmittelbar abgeleitet werden kann.
<code id="5f389c23671dd">
def dfs3(v, markiert=set()):
print(v.name, end=' ')
markiert.add(v)
for w in v.adj:
if w[0] not in markiert:
dfs3(w[0], markiert)
</code>
<run id="5f389c2367db3">
dfs3(a)
</run>
Alternativ ist es möglich, einen noch unbetrachteten Knoten weiß, einen noch nicht vollständig einbezogenen grau und einen vollständig berücksichtigten schwarz zu färben.
<code id="5f389c236728a">
farbe = {} # global gültiges Dictionary
for u in [a, b, c, d, e, f, g]:
farbe[u] = 'weiß'
def dfs1(u):
print(u.name, end=' ')
farbe[u] = 'grau'
for v in u.adj:
if farbe[v[0]] == 'weiß':
dfs1(v[0])
farbe[u] = 'schwarz'
</code>
<run id="5f389c2367e6f">
dfs1(a)
</run>
Da jeder Knoten und jede Kante jeweils maximal einmal besucht werden, beträgt die Laufzeit $\mathcal{O}(\lvert V \rvert + \lvert E \rvert)$. Handelt es sich um einen zusammenhängenden Graphen gilt $|E|\geq |V|-1$, sodass man den Aufwand mit $\mathcal{O}(|E|)$ abschätzen kann.
Die Graphentheorie definiert eine große Palette von Eigenschaften, die ein Graph besitzt oder nicht. Darunter gibt es Eigenschaften, die für die Informatik von besonderer Bedeutung sind, weil sie Standardfälle der Modellierung darstellen.
====Erreichbarkeit====
Ein Knoten $w$ eines (gerichteten oder ungerichteten) Graphen heißt von $v$ '''erreichbar''', wenn es einen Weg von $v$ nach $w$ gibt. Wir bestimmen die Menge der von $v$ erreichbaren Knoten.
Wie weiter oben angekündigt entwickeln wir `dfs_erreichbar` aus `dfs3` heraus, indem wir auf die Ausgabe der besuchten Knoten verzichten und sie in einer Menge zusammenfassen. Man beachte, dass Mengen ''ungeordnete'' Zusammenfassungen von Elementen sind. Das Aufrufbeispiel zeigt beispielsweise, dass die Knoten $A,B$ und $C$ von $G$ nicht erreichbar sind.
<code id="5f389c2367337">
def dfs_erreichbar(v, markiert, erreichbare_Knoten):
# if erreichbare_Knoten == set(): print(v.name) # für Kontrollzwecke
erreichbare_Knoten.add(v) # gegenüber dfs3 hinzugefügt
markiert.add(v)
for w in v.adj:
if w[0] not in markiert:
dfs_erreichbar(w[0], markiert, erreichbare_Knoten)
return erreichbare_Knoten
</code>
<run id="5f389c2367f1a">
for v in (a, b, c, d, e, f, g):
print(v.name)
for w in dfs_erreichbar(v, set(), set()):
print(w.name, end=' ')
print()
</run>
====Zusammenhängender ungerichteter Graph====
Ein ''ungerichteter Graph'' ist '''zusammenhängend''', wenn jeder Knoten mit jedem anderen durch einen ''Weg'' (Pfad, Kantenzug) verbunden ist. Ein Weg wird als Folge der zugehörigen Knoten, die durch Kanten verbunden sind, angegeben. Die Länge eines Weges ergibt sich aus der Anzahl der darin vorkommenden Kanten.
In einem zusammenhängenden Graphen muss jeder Knoten von jedem Knoten ''erreichbar'' sein. Dies können wir mit `dfs_erreichbar` feststellen. Besteht ein Graph aus mehreren nicht zusammenhängenden Teilen, so nennt man diese Zusammenhangskomponenten.
Für das obige Beispiel eines gerichteten Graphen ergänzen wir die jeweilige gerichtete Kante in Gegenrichtung, um einen de facto ungerichteten Graphen zu erhalten.
<code id="5f389c23673fa">
def zusammenhaengend(knotenmenge):
knotenanzahl = len(knotenmenge)
result = True
for v in knotenmenge:
erreichbare_Knoten = dfs_erreichbar(v, set(), set())
print(v.name, len(erreichbare_Knoten))
if len(erreichbare_Knoten) < knotenanzahl:
result = False
break
return result
</code>
<run id="5f389c2367fd9">
print(zusammenhaengend({a, b, c, d, e, f, g}))
</run>
<!--
E 2
False
-->
Entfernt man beispielsweise die gerichtete Kante von $F$ nach $E$, können von $F$ aus keine Knoten erreicht werden.
====Gerichteter zyklenfreier Graph (DAG)====
Häufig werden gerichtete Graphen (''Digraphen'') verwendet, die keinen ''Zyklus'' besitzen dürfen. Man nennt sie '''DAG''' (''directed acyclic graph''). Einen Weg $(v_1,v_2,\ldots,v_m)$, bei dem der Start- $v_1$ mit dem Endknoten $v_m$ übereinstimmt, nennt man '''Zyklus'''. Wenn dies der einzige wiederholte Knoten in der Knotenfolge ist, heißt er '''Kreis'''. Ein Zyklus ist nicht identisch mit einer Schleife/Schlinge, also einer reflexiven Kante $(v,v)$ zum gleichen Knoten in einem gerichteten Graphen.
Ein typisches Beispiel für die Anwendung von DAGs sind ''Ablaufplanungen mit Vorrangbedingungen''. Als solche sind sie in vielen Bereichen (Haushalt, Produktion, Finanzplanung usw.) anzutreffen. Studierende können die Wahl der Vorlesungen von fachlichen Voraussetzungen, wie sie in einem Modulhandbuch hinterlegt sind, abhängig machen. Auf diese Weise kann eine studierbare Sequenz aufeinander aufbauender Module zusammengestellt werden.
Eine von Knoten $A$ zu Knoten $B$ zeigende Kante drückt aus, dass Vorlesung $B$ erst dann gehört werden sollte, wenn der betreffende Studierende den Inhalt aus Vorlesung $A$ aufgenommen hat. Ein nach dieser Vorgehensweise modellierter Graph besteht also aus einer ''unvollständig geordneten Knotenmenge'', denn nicht jedes Knotenpaar gehört zu einer solchen ''Voraussetzungsrelation''. Mit Hilfe des '''topologischen Sortierens''' wird daraus eine vollständige Ordnung hergestellt. "Hält man" einen bestimmten Knoten fest, so zeigen sämtliche Kanten nach unten und drücken die Abhängigkeits(richtung) aus.
Ist dies an einer oder mehreren Stellen verletzt, sodass auch Aufwärtskanten vorkommen, liegt ein Fehler vor. Der Digraph ist dann nicht ''zyklenfrei'', also kein DAG. Da Graphen im Allgemeinen sehr viele Knoten, Kanten und damit Zyklen haben können, lautet die Grundaufgabe der Zykluserkennung: Besitzt der vorgelegte Digraph (mind.) einen Zyklus? (Aufgrund der gegebenen Anwendungsbreite beschränken wir unsere Betrachtung auf Digraphen, obwohl Zyklen auch in ungerichteten Graphen auftreten können.)
Wir entwickeln die Lösung auf der Basis einer Tiefensuche (DFS). Die Stack-Verwaltung bei der Ausführung der rekursiven DFS-Funktion wirkt wie der ausgerollte Faden zur Rückkehr zum Eingang des Labyrinths: Wir finden den Weg von $w$ zum Eingang $v$ zurück, indem wir der Knotensequenz beim Abbau des Stacks folgen. Es gibt also einen Weg von $w$ nach $v$. So interpretieren wir den Stack-Inhalt $w=F,E,C,B,v=A$ (top of stack ist links) für den aktuellen Weg, der mit dem Knoten $v=A$ beginnt und in der Folge die Knoten $B, C, E$ und $F$ besucht. Finden wir nun eine gerichtete Kante von $v$ zu irgendeinem dieser auf dem Weg liegenden Knoten $w$, so liegt ein Zyklus vor, denn diese Kante vervollständigt den Zyklus.
Vor dem Aufruf (beider Funktionen) fügen wir obigem DAG noch die gerichtete Kante von $D$ zu $A$ hinzu, sodass Zyklen entstehen. Die ansonsten hinzugefügten Kanten zur Herstellung eines zugehörigen ungerichteten Graphen, müssen wieder entfernt werden: Herauskommentieren der Kanten.
<!--<code id="5f389c23674ad">
#z = Node('Z')
d.add_to_adj_lst(a) # Kante von D nach A
#z.add_to_adj_lst(a)
</code>-->
<code id="5f389c236755b">
d.add_to_adj_lst(a) # Kante von D nach A
</code>
<code id="5f389c2367609">
def dag(v, markiert, aufWeg):
aufWeg.append(v)
#print(v.name, len(aufWeg)) # für Kontrollzwecke
markiert.add(v)
for w in v.adj:
if not(w[0] in markiert):
dag(w[0], markiert, aufWeg)
else:
if w[0] in aufWeg:
print('Zyklus bei ', w[0].name)
aufWeg.remove(v)
def DiCycle():
for v in (a,b,c,d,e,f,g):
dag(v, set(), [])
</code>
<run id="5f389c2368084">
DiCycle()
</run>
<!--
Zyklus bei A
Zyklus bei B
Zyklus bei D
Zyklus bei D
-->
Für die Startknoten $A$, $B$, $D$ und $G$ werden Zyklen gefunden, für die übrigen Knoten nicht. Fazit: Der vorliegende Graph mit Kante von $D$ nach $A$ ist kein DAG!
Die Komplexität des Verfahrens entspricht der von DFS.
Alternative Überlegung: Bei der Tiefensuche in einem Graphen kann es drei verschiedene Arten von Kanten geben: Vorwärts-, Quer- und Rückwärtskanten. Nur ''Rückwärtskanten'', die auf Knoten zeigen, die sich noch in Bearbeitung befinden, d.h. die besucht aber noch nicht verlassen wurden, bilden Zyklen.
[https://link.springer.com/chapter/10.1007/978-3-540-76394-9_9 Taschenbuch der Algorithmen, S. 86ff]
<code id="5f3725b65ecb9">
## Suche von Rückwärtskanten (Verbot für DAG)
## Lit.: V. Turau: Alg. Graphentheorie (S. 94f)
besucht = {} # dictionary
verlassen = {} # dictionary
zyklus = False # global
def zyklusfrei():
for v in (a, b, c, d, e, f, g):
besucht[v] = False # Kein Knoten wurde besucht.
verlassen[v] = False # Kein Knoten wurde vollst. bearbeitet
for v in (a,b,c,d,e,f,g):
if not(besucht.get(v)):
zyklussuche(v)
def zyklussuche(v):
global zyklus
besucht[v] = True
for w in v.adj: # Nachfolgerknoten von v
#print(w[0].name)
if not(besucht.get(w[0])): # Vorwärtskante
zyklussuche(w[0])
else: # Quer- oder Rückwärtskante
if not(verlassen.get(w[0])): # Rückwärtskante
#print('Zyklus', w[0].name)
zyklus = True
verlassen[v] = True # Knoten ist vollst. bearbeitet
</code>
<run id="5f389c2368130">
zyklusfrei()
if zyklus:
print('nicht zyklusfrei')
else:
print('zyklusfrei')
</run>
<!--
nicht zyklusfrei
-->
'''Hinweis''': Die ''Schleifensuche in einfach verketteten Listen'' kann mit dem [https://de.wikipedia.org/wiki/Hase-Igel-Algorithmus Hase-Igel-Algorithmus] mit ''linearem Aufwand'' $\mathcal{O}(n)$ bewerkstelligt werden.
Das Verfahren ist nicht mit dem Floyd-Warshall-Algorithmus zur Bestimmung der kürzesten Wege für alle Knotenpaare zu verwechseln!
====Baum====
Ist ein gegebener Graph ein Baum? Dies können wir unter Verwendung der oben bereitgestellten Verfahren entscheiden. Ein '''[[AuK/Bäume|Baum]]''' ist ein ''ungerichteter azyklischer zusammenhängender Graph''. Ein '''Wurzelbaum''' ist ein Baum mit einem als Wurzel markierten Knoten.
Ein [[AuK/Greedy Algorithmen#Minimal aufspannender Baum (MST)|aufspannender Baum]] eines zusammenhängenden Graphen ist ein Baum, d.h. ein kreisfreier und zusammenhängender Teilgraph $G'=(V',E')$, mit $V'=V$ und $E'\subseteq E$.
''kreisfrei'' bedeutet eine Knotenfolge ohne Knotenwiederholung. <!-- mit Ausnahme des Start- und Endeknotens.-->
Ein Graph, der selbst ein aufspannender Baum ist, heißt ''Baum''. In einem Baum sind je zwei Knoten durch genau einen Weg miteinander verbunden.
====Anwendungsbeispiel: 0/1-Rucksackproblem====
Beim Rucksackproblem ist eine nichtleere Menge von $n$ Gegenständen mit den Gewichten (weight) $w_1, w_2, \dotsc, w_n$ mit $w_i > 0$ und den zugehörigen Werten (value) $v_1, v_2, \dotsc, v_n$ mit $v_i>0$ gegeben. Das Gewicht des $i$-ten Gegenstands beträgt $w_i$, dessen Wert ist $v_i$.
Die Interpretation des Wertes wird durch den jeweiligen Sachkontext bestimmt: Denkt man an Schmuck, so kann der Wert im potenziellen Verkaufserlös bestehen. Handelt es sich um Utensilien eines Bergwanderes, richtet sich der Wert eines Gegenstandes eher nach dessen Beitrag zur Absicherung einer unfallfreien Begehung.
Der Rucksack ist nur beschränkt belastbar. Das zulässige Maximalgewicht sei $K$, d.h. das aktuelle Gesamtgewicht darf $K$ keinesfalls überschreiten. Zu beachten ist, dass beim 0/1-Rucksackproblem, im Gegansatz zum Bruchteil-Rucksackproblem, ein Gegenstand entweder in den Rucksack gepackt werden kann oder nicht, eine Teilung des Gegenstands und anteilige Mitnahme sind bei "0/1" nicht möglich.
Die Optimierungsaufgabe besteht nun darin, einen Rucksack so zu füllen, dass die Wertsumme der eingepackten Gegenstände – unter Beachtung der Kapazitätsbeschränkung des Rucksacks – maximal ist.
Zum Finden der Lösungen dieses Problems unter Nutzung der Tiefensuche
[[Datei:Depth-first.gif|center|300px]]
muss ein ''Entscheidungsbaum'' (ungerichteter, azyklischer und zusammenhängender Graph) aufgestellt werden.
In jedem Schritt gibt es für jedes aktuelle Blatt genau eine Ja/Nein-Entscheidung, d.h. zwei Möglichkeiten (Binärbaum): entweder wird der $i$-te Gegenstand in den Rucksack gepackt oder nicht. Der Entscheidungsbaum hat folglich die Höhe $n$ ($n$ = Anzahl der Gegenstände). Die Wurzel repräsentiert den anfangs leeren Rucksack. Sie liegt auf Niveau $0$ des Baumes. Die Blätter des Baums auf Niveau $n$ repräsentieren alle Gegenstandskombinationen der Rucksackbefüllung.
Der Entscheidungsbaum liegt nicht als Datenstruktur vor, sondern stellt das Aufbauschema für die Rucksackbefüllungen dar. Man kann es sich als ein Protokoll der Berechnung aller Möglichkeiten vorstellen. Diese Berechnung kann systematisch mit Tiefensuche vorgenommen werden.
Da es sich um einen Binärbaum handelt, beträgt die Anzahl der Bätter höchstens $2^n$. Insgesamt besteht der Baum aus $\sum_{i=0}^n 2^i = 2^{n+1} - 1 \in \mathcal{O}(2^n)$ Knoten. Die Laufzeit des Algorithmus' liegt folglich in $\mathcal{O}(2^n)$. Zur Ermittlung ''aller'' infrage kommenden Packvarianten (Blätter) ist ein exponentieller Zeitaufwand erforderlich.
'''Beispiel:'''
Für drei Gegenstände ($n=3$) mit den Gewichten 50 (Wert: 30), 30 (Wert: 20) und 10 (Wert: 25) ergibt sich der folgende Entscheidungsbaum. (Die Reihenfolge der Gegenstände in der Liste spielt dabei keine Rolle.)
[[Datei:Knapsack_tree.png|center|650px]]
Wie erwartet besitzt der Baum $2^3=8$ Blätter.
Mit <tt>knapsack_dfs</tt> wird die gesamte Knotenfolgenfolge bei zugrunde liegender Tiefensuche (unbeschränkter DFS-Durchlauf) aufgelistet. Sie kann im Graph sehr gut nachvollzogen werden (Backtracking).
Die Blätter des Baumes sind in der Ausgabe (<tt>print</tt>) mit <tt>Rucksack:</tt> eingeleitet. Danach folgt die Angabe der eingepackten Gegenstände als Liste von Gewicht-Wert-Paaren, wohingegen die Gegenstände in der Knotennotation nur mit ihrem Gewicht angegeben werden. Mehrere Gegenstände bilden eine Liste ihrer Gewichte. Diese einfache Notation muss für Beispiele mit gewichtsgleichen Gegenständen verändert werden.
<code id="5f389c23676ba">
def knapsack_dfs(items, k, knapsack):
print(list(map(lambda x: x[0], knapsack)))
if len(items) == 0:
print("Rucksack:", knapsack)
else:
knapsack_dfs(items[1:], k - items[0][0], knapsack + [items[0]])
print(list(map(lambda x: x[0], knapsack)))
knapsack_dfs(items[1:], k, knapsack)
print(list(map(lambda x: x[0], knapsack)))
</code>
<run id="5f389c23681dc">
K = 0 # K spielt zunächst keine Rolle!
items = [(50, 30), (30, 20), (10, 25)]
knapsack_dfs(items, K, [])
</run>
Als Nächstes wird die Kapazitätsbeschränkung des Rucksacks einbezogen. Hierfür muss gegenüber <tt>knapsack_dfs</tt> lediglich eine Programmzeile eingefügt werden: Die Mitnahme eines Gegenstandes findet grundsätzlich nur dann statt, wenn er noch in den Rucksack passt, d.h. wenn dessen Gewicht die aktuelle Restkapazität des Rucksacks nicht überschreitet: <tt>items[0][0] <= k</tt>.
Für $K=62$ wird die Zahl der Knoten (zulässige Rucksackbefüllungen) reduziert:
[[Datei:Knapsack_tree-reduce.png|center|650px]]
<code id="5f389c236776c">
def knapsack_dfs_ltd(items, k, knapsack):
print(list(map(lambda x: x[0], knapsack)))
if len(items) == 0:
print("Rucksack:", knapsack)
else:
if items[0][0] <= k:
knapsack_dfs_ltd(items[1:], k - items[0][0], knapsack + [items[0]])
print(list(map(lambda x: x[0], knapsack)))
knapsack_dfs_ltd(items[1:], k, knapsack)
print(list(map(lambda x: x[0], knapsack)))
</code>
<run id="5f389c2368287">
K = 62
items = [(50, 30), (30, 20), (10, 25)]
knapsack_dfs_ltd(items, K, [])
</run>
Für $K=41$ wird der ursprünglich vollständige Binärbaum noch mehr reduziert.
[[Datei:Knapsack_tree-reduce2.png|center|650px]]
An der exponentiellen Aufwandsordnung ändert sich jedoch nichts.
Nachdem sämtliche Rucksackbelegungen (Blätter), die die Gewichtsbeschränkung respektieren, gefunden wurden, bestimmen wir deren Gesamtwerte durch Summieren der Einzelwerte und ermitteln die Belegung(en) mit dem Maximalwert.
Die Modifikation von <tt>knapsack_dfs_ltd</tt> sind geringfügig: Die gültigen Belegungen werden in der mit <tt>validKnapsacks</tt> bezeichneten Liste gesammelt.
Um zu demonstrieren, dass es mehrere Packmöglichkeiten mit einem maximalen Gesamtwert geben kann, verwenden wir die folgenden drei Gegenstände: 50 (Wert: 45), 30 (Wert: 20), 10 (Wert: 25) bei einer Gewichtsbeschränkung auf $K=52$.
<code id="5f389c236781e">
#helper function to get the value of a knapsack
def value(knapsack):
sum_value = 0
for item in knapsack:
sum_value += item[1]
return sum_value
validKnapsacks = [] # global variable
def knapsack_dfs_ltd_value(items, k, knapsack):
#print(list(map(lambda x: x[0], knapsack)))
if len(items) == 0:
#print("Rucksack:", knapsack)
validKnapsacks.append(knapsack) # changes the value of a global variable!!!
else:
if items[0][0] <= k:
knapsack_dfs_ltd_value(items[1:], k - items[0][0], knapsack + [items[0]])
#print(list(map(lambda x: x[0], knapsack)))
knapsack_dfs_ltd_value(items[1:], k, knapsack)
#print(list(map(lambda x: x[0], knapsack)))
</code>
<run id="5f389c2368335">
K = 52
items = [(50, 45), (30, 20), (10, 25)]
knapsack_dfs_ltd_value(items, K, [])
print("valid knapsacks:", validKnapsacks)
solutions = []
maxValue = 0
for knapsack in validKnapsacks:
if value(knapsack) > maxValue:
solutions = list(knapsack)
maxValue = value(knapsack)
elif value(knapsack) == maxValue:
solutions.append(knapsack)
print("solutions:", solutions, "max. value:", maxValue)
</run>
<!--
valid knapsacks: [[(50, 45)], [(30, 20), (10, 25)], [(30, 20)], [(10, 25)], []]
solutions: [(50, 45), [(30, 20), (10, 25)]] max. value: 45
-->
Im Beispiel sind prinzipiell 5 Rucksackbelegungen möglich aber nur zwei davon, nämlich [50] (Wert: 45) und [30, 10] (Wert: 20+25=45), erzielen den Maximalwert in Höhe von 45.
====Anwendungsbeispiel: n-Damenproblem====
Das $n$-Damenproblem ist ein schachmathematisches Problem und eine Verallgemeinerung des 8-Damenproblems.
Die Aufgabe besteht darin, 8 Damen auf einem $8\times 8$-Schachbrett so zu platzieren, dass keine Dame gemäß den Schachregeln eine andere Dame bedroht, d.h. schlagen kann. Dies bedeutet, dass keine zwei Damen auf der selben Linie (a-h), Reihe (1-8) oder Diagonale stehen dürfen. Im Unterschied zur Begrifflichkeit im Schach gehen wir hier von einer Matrixgestalt aus und bezeichnen die Zeilen und Spalten mit $0, 1, \ldots, 7$. Es spielt auch keine Rolle, ob das Feld rechts unten ein weißes ist. Im Schach wäre das Pflicht.
Eine Lösung für das 8-Dameproblem ist die folgende:
[[Datei:8queens.jpg|center|250px]]
Das 8-Damenproblem lässt sich sinngemäß auf ein $n$-Damenproblem ausweiten, d.h. $n$ Damen sollen bedrohungsfrei auf einem $n\times n$-Schachbrett platziert werden.
Zur Lösung dieses Problems kann ebenfalls Depth-First-Search eingesetzt werden.
Dabei nutzen wir eine Liste mit bis zu $n$-Elementen als Datenstruktur, die am Index $i$ angibt, in welcher Zeile in der $i$-ten Spalte eine Dame platziert wurde. Aufgrund der Tatsache, dass eine Dame ihre komplette Spalte schlägt, ist es trivial, dass sich in jeder Spalte nur höchstens eine Dame befinden kann. Da $n$ Damen auf $n$ Reihen verteilt werden, folgt, dass in jeder Spalte genau eine Dame stehen muss.
Die Liste [0, 4, 7, 5, 2, 6, 1, 3] beschreibt folgende Stellung:
[[Datei:8-queens2.png|center|250px]]
Sie repräsentiert eine Lösung. Dies kann man leicht überprüfen. Uns geht es jedoch um einen Algorithmus zum Finden ''einer'' solchen Stellung. Ergänzend fragt man sich natürlich, wie viele Lösungen es für ein gegebenes $n$ gibt.
Man beginnt mit einem leeren Schachbrett -- dies wird durch eine leere Liste repräsentiert. Nun soll schrittweise in jeder Spalte eine Dame platziert werden. Dabei werden alle Zeilen von 0 bis $n-1$ systematisch durchprobiert. Dies bedeutet, dass $n$-mal die Tiefensuche mit der entsprechenden Konfiguration aufgerufen wird. Es wird dabei geprüft, ob es sich bei der angegebenen Stellung noch um eine gültige Stellung handelt, d.h. keine Dame kann eine andere Dame schlagen. Ist dies der Fall, so wird der Algorithmus für die nächste Spalte mit den Zeilen 0 bis $n-1$ rekursiv aufgerufen. Handelt es sich nicht um eine gültige Stellung, so wird eine leere Liste als Lösungsmenge zurückgegeben und ein Backtracking ausgeführt: Rückkehr zum letzten Entscheidungspunkt. Dieser Ablauf wird vollständig durch die rekursive Natur von DFS gesteuert.
Die hier beschriebene DFS minimiert die Anzahl der zu überprüfenden Stellungen enorm, da - im Gegensatz zu einem Brute-Force-Ansatz, bei dem alle Stellungen durchprobiert werden - nun auch die jeweils folgenden Stellungen ausgeschlossen werden.
<code id="5f389c23678d1">
def feasible(setting):
if len(set(setting)) != len(setting):
return False
for i in range(len(setting)):
for j in range(len(setting)):
if j != i and (setting[j] == setting[i] - i + j or setting[j] == setting[i] + i - j):
return False
return True
def n_queens(n, setting=[]):
if not feasible(setting):
return []
if len(setting) == n:
return [list(setting)]
solutions = []
for i in range(n):
solutions += n_queens(n, setting + [i])
return solutions
</code>
<run id="5f389c23683e4">
print('Solutions of the 4 queens problem:', n_queens(4), end='\n')
print('Number of solutions of the 8 queens problem:', len(n_queens(8)), end='\n')
</run>
<!--
Solutions of the 4 queens problem: [[1, 3, 0, 2], [2, 0, 3, 1]]
Number of solutions of the 8 queens problem: 92
-->
Rucksack- und $n$-Damenproblem sind zwei klassische Problemstellungen, die mit DFS oftmals effizienter gelöst werden können als mit Brute-Force-Ansatz. Im schlechtesten Fall muss dennoch der gesamte Baum traversiert werden. Dies führt zu exponentiellem Aufwand. Bis heute sieht es so aus, als ob es kein Verfahren gibt, dass diese Problemstellungen besser als mit exponentiellem Aufwand (exakt) löst.