Hamilton Kreise
Inhaltsverzeichnis |
Einführung
Definitionen Graphentheorie
Einfacher Weg
Für n ≥ 2 nennt man einen Graphen Pn mit der Knotenmenge V(P_n) = {v_0, v_1, . . . , v_n} und der Kantenmenge E(P_n) = {{v_0, v_1}, {v_1, v_2}, . . . , {v_{n−1}, v_n}} einen einfachen Weg der Länge n, sofern keine Kante und kein Knoten mehrfach durchlaufen wird.
siehe auch: Grundbegriffe der Graphentheorie 1
Einfacher Kreis
Für n ≥ 3 nennt man einen Graphen Pn mit der Knotenmenge V(P_n) = {v_0, v_1, . . . , v_n} und der Kantenmenge E(C_n) = {{v_0, v_1}, {v_1, v_2}, . . . , {v_{n−1}, v_n}} einen einfachen Weg (oder Pfad) der Länge n, sofern keine Kante und kein Knoten mehrfach durchlaufen wird.
siehe auch: Grundbegriffe der Graphentheorie 1
Bewerteter Graph
| kantenabhängig | knotenabhängig |
|---|---|
| Eine Kantenmarkierung eines Graphen G =(V, E) ist eine Abbildung b:E->M die jeder Kante e einen Wert oder ein Symbol zuordnet. Für die Bewertung der Kante {u, v} schreiben wir dann kurz b(u, v). | Eine Knotenmarkierung eines Graphen G =(V, E) ist eine Abbildung b:V->M die jedem Knoten v einen Wert oder ein Symbol zuordnet. |
siehe auch: Grundbegriffe der Graphentheorie 2
Dijktra-Algorithmus
Der Dijktra-Algorithmus gehört in die Gruppe der Greedy-Algorithmen. Er dient zur Berechnung der kürzesten Pfade von einem bestimmten Startknoten aus.
siehe auch: Kürzeste Wege in Graphen
Hamilton Graphen
Das Euler-Kreis-Problem behandelt die Kantenproblematik. Das Hamilton-Kreis-Problem ist das Gegenstück davon. Es handelt sich also um Knotenproblem. Gegeben ist ein beliebig großer Graph. Wir suchen nun einen Teilgraph, der alle Knoten des Graphen durchläuft und ein möglichst minimal ist.
Hamiliton Wege
Ein Hamilton Weg ist, wie der Name schon sagt ein Weg, um genau zu sein ein einfacher Weg, da jeder Knoten nur einmal benutzt werden darf. Wenn in dem Graphen ein Hamilton Weg zu finden ist, so nennt man den Graphen auch semihamiltonisch.
Beispiel Hamilton Graph:
Finden sie ein Hamilton Graph.
Hamilton Kreise
Wenn wir von einem Hamilton Kreis sprechen ist in dem Graphen ein einfacher Kreis enthalten, der alle Knoten des Graphen berührt. Diesen Graphen nennt man hamiltonisch.
Es sei G = (V,E) ein Graph mit n Knoten. Ein Kreis C auf G heißt Hamilton Kreis, falls er jeden der n Knoten von G genau einmal durchläuft. G heißt dann auch hamiltonischer Graph.
Beispiel mit 4 Knoten: Hier ist nun ein Graph mit 4 Knoten und ziemlich vielen Kanten gegeben. Das macht die Suche relativ einfach. Tragen sie alle möglichen Hamilton Kreise zusammen.
Beispiel Bekanntheitsgraph: Wir wollen eine Geburtstagsparty feiern. Wir haben verschieden Leute eingeladen und wollen nun die beste Tischordnung finden, dass jede Person eine bekannte Person an seiner rechten und eine bekannte an seiner linken Seite hat. Finden Sie einen Kreis, der diese Kriterien erfüllt. Entfernen sie dann alle Kanten, die nicht zum Graphen gehören und ordnen sie den Graphen.
Man merkt, dass es immer schwieriger wird ein Hamilton Kreis zu finden. Es gibt kein effizientes Verfahren, der uns die Existenz und das Finden des Kreises erleichtert. Man spricht auch von einem NP-vollständigem Problem.
Naive Suche
Gäbe es ein Kriterium für die Existenz eines Hamilton Kreises wäre das Finden des Kreises leichter, da man weiß, dass es mindestens einen Hamilton Kreis gibt. Demzufolge muss es auch mindestens einen minimalen Kreis geben. Durch eine Auflistung aller können wir nun den günstigsten finden. Dies ist ab einer bestimmten Größe nicht mehr effizient.
Unter der Annahme, dass 10^{30} Lösungen pro ns berechnet werden können. Kann man zu folgender sehr erstaunlichen Tabelle kommen.
| Anzahl Knoten | Anzahl möglicher Lösungen | Benötigte Zeit |
|---|---|---|
| 5 | 12 | |
| 10 | 181440 | |
| 15 | 4,36 \cdot 10^{10} | |
| 20 | 6,08 \cdot 10^{16} | |
| 25 | 3,1 \cdot 10^{23} | |
| 30 | 4,42 \cdot 10^{30} | 4,42 ns |
| 35 | 1,48 \cdot 10^{38} | 0,15 s |
| 40 | 1,02 \cdot 10^{46} | 118 Tage |
| 45 | 1,33 \cdot 10^{54} | 9,21 \cdot 10^7 Jahre |
| 50 | 3,04 \cdot 10^{62} | 9,6 \cdot 10^{15} Jahre |
Gedankenexperiment:
Wir haben einen gegeben Graphen. Hat das hinzufügen einer Kante Auswirkungen auf die Existenz eines Hamilton Graphen bzw Hamilton Kreis.
JA desto mehr Kanten im Graph sind, umso wahrscheinlicher ist es, dass der Graph semihamiltonisch oder sogar hamiltonisch ist. Aus diesem Experiment hat Paul Dirac (1952) als erster Wissenschaftler sich diesem Problem angenommen und den folgenden Satz formuliert:
Leider ist diese Aussage falsch. Grund dafür ist dieser Graph:
Er besitzt den Minimalgrad von 2 und ist trotzdem hamiltonisch.
In den folgenden Jahren fand man Bedingungen für die Existenz eines Hamilton Kreises:
- Entfernt man aus einem hamiltonischen Graphen einen Knoten, so bleibt der Graph zusammenhängend.
- Ein hamiltonischer Graph mit n Knoten hat einen Durchmesser (maximaler Abstand zwischen 2 Knoten) von höchstens \dfrac{n}{2}
Diese Bedingungen zeigen, dass ein Graph nicht hamiltonisch ist. Dies ist eigentlich nicht das gesuchte Ziel. Man kann es aber trotzdem benutzen. Nachteilig ist außerdem, dass man jeden Knoten probieren muss, um den Minimalgrad der Aussage bestimmen zu können. Die Komplexität ist ???.
Traveling Salesman Problem (TSP)
???
Heuristiken
Begriff
Der Begriff \color{red}{Heuristik} stammt von dem griechischen Wort "heurisko" ab, das \color{red}{heißt} übersetzt etwa \color{red}{"ich finde"}, "ich suche". Eine heuristik beschreibt ein Verfahren, welches zur Lösung eines Problems genutzt wird. Dieses Verfahren liefert, wenn es erfolgreich ist eine gute jedoch nicht unbedingt eine optimale Lösung des Problems.
Es handelt sich um Faustregeln, basierend auf intuitiven Regeln, ähnlich den Bauernregeln für das Wetter. Aus einer Vielzahl von Möglichkeiten werden einige herausgefiltert.
Definitionen
bla
Motivation
Von Bedeutung sind diese Verfahren wenn es zwar theoretische optimale Lösungen für bestimmte Probleme gibt, diese jedoch in der Praxis verworfen werden müssen aufgrund extrem langer Rechenzeiten. Dies ist zu Beispiel bei NP-vollständigen Problemen der Fall, hier liefern Heuristiken praktikable Näherungen.
Beispiele hierfür sind:
das Rucksack problem
das TSP
Heuristiken versus Algorithmen
?????
Beispiele
Heuristiken für das Springerproblem beim Schach
Heusritiken für das Travelling Salesman Problem
Heuristiken für das TSP
Nearest-Neightbor-Heuristik
Ein weiterer Name für dieses ist der "Best-Successor-Algorithmus", man spricht ebenfalls von der "Methode des Besten Nachfolgers".
gehört zur Gruppe:
der greedy Verfahren
Komplexität des Algorithmus
???
Prinzipelles Vorgehen des Verfahrens
Eingabe: Vollständiger bewerteter Graph \color{red}{K_n}
| Schritt 1: | Beginne an einem beliebigen Knoten mit leerer Tour v \in V und T = \emptyset. |
| Schritt 2: | Bestimme einen noch nicht besuchten Knoten, mit der geringsten Entfernung zu v w \ne v und setze T = T \cup \{v,w\}, sowie v = w. |
| Schritt 3: | Solange es noch unbesuchte Knote gibt gehe zu Schritt 2. Ansonsten gehe zurück zum Anfang v und füge v der Tour hinzu T = T \cup \{v\} |
Ergebnis: \color{red}{Hamilton-Kreis}
Pseudocode
???
Implementation
???
Vor.- und Nachteile
???
Nearest-Insertion-Heuristik
???
Farthest-Insertion-Heuristik
???
Minimum-Spanning-Tree-Heuristik (MST)
???
Anwendung in der Praxis
???