Hamilton Kreise
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
== Einführung ==
=== Definitionen Graphentheorie ===
==== Einfacher Weg ====
Für $n ≥ 2$ nennt man einen Graphen $P_n$ 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.
[[Bild:Jowolf_EinfacherWegCEFG.png]]
siehe auch: [[Grundbegriffe_der_Graphentheorie_1|Grundbegriffe der Graphentheorie 1]]
==== Einfacher Kreis ====
Für $n ≥ 3$ nennt man einen Graphen $P_n$ 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.
[[Bild:Jowolf_EinfacherKreisFGJF.png]]
siehe auch: [[Grundbegriffe_der_Graphentheorie_1|Grundbegriffe der Graphentheorie 1]]
==== Bewerteter Graph ====
<table border=1>
<tr>
<th width=50%>kantenabhängig</th>
<th width=50%>knotenabhängig</th>
</tr>
<tr>
<td>Eine Kantenmarkierung eines Graphen $G =(V, E)$ ist eine Abbildung $b:E \rightarrow 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)$.</td>
<td>Eine Knotenmarkierung eines Graphen $G =(V, E)$ ist eine Abbildung $b:V \rightarrow M$ die jedem Knoten $v$ einen Wert oder ein Symbol zuordnet.</td>
</tr>
</table>
siehe auch: [[Grundbegriffe_der_Graphentheorie_2|Grundbegriffe der Graphentheorie 2]]
<language>Scheme</language>
==== Dijkstra-Algorithmus ====
Der Dijkstra-Algorithmus gehört in die Gruppe der Greedy-Algorithmen. Er dient zur Berechnung der kürzesten Pfade von einem bestimmten Startknoten aus. <br>
[[Bild:Jowolf_Dijkstra_Animation.gif]]
siehe auch: [[Kürzeste_Wege_in_Graphen#Algorithmus_von_Dijkstra|Kürzeste Wege in Graphen]]
== Hamilton Graphen ==
Das [[Euler-Kreise_und_-Wege|Euler-Kreis-Problem]] behandelt die Kantenproblematik. Das Hamilton-Kreis-Problem ist das Gegenstück davon. Es handelt sich also um Knotenproblem.<br>
Gegeben ist ein beliebig großer Graph. Wir suchen nun einen Teilgraph, der alle $n$ Knoten des Graphen einmal durchläuft.
<div style= "background-color:#F5D0A9; padding:10px">
Es sei $G = (V,E)$ ein Graph mit $n$ Knoten. Der Teilgraph $C$, der alle $n$ Knoten genau einmal durchläuft nennt man Hamilton Graph.
</div>
=== 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 muss. Wenn in dem Graphen ein Hamilton Weg zu finden ist, so nennt man den Graphen auch semihamiltonisch.
<div style= "background-color:#F5D0A9; padding:10px">
Es sei $G = (V,E)$ ein Graph mit $n$ Knoten. Ein Teilgraph $C$ heißt Hamilton Weg, wenn der Teilgraph ein einfacher Weg ist, der alle $n$ Knoten genau einmal durchläuft. Der Graph $G$ wird dann auch als semihamilonisch bezeichnet.
</div>
<b> Beispiel Hamilton Weg: </b>
Finden sie ein Hamilton Weg.
[[Bild:Jowolf_HamiltonGraph_leer.png]]
=== 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.<br>
<div style= "background-color:#F5D0A9; padding:10px">
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.
</div>
<b> Beispiel mit 4 Knoten: </b>
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.
[[Bild:Jowolf_HamiltonKreis-4Knoten.png]]
<popup name="Lösung">
[[Bild:Jowolf_HamiltonKreis-4Knoten-1.png]]
[[Bild:Jowolf_HamiltonKreis-4Knoten-2.png]]
[[Bild:Jowolf_HamiltonKreis-4Knoten-3.png]]
</popup>
<b> Beispiel Bekanntheitsgraph: </b>
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.
[[Bild:Jowolf_Verwandtschaftsbeziehung.png]]
<popup name="Lösung">
[[Bild:Jowolf_Verwandtschaftbeziehung_marked.png]]
[[Bild:Jowolf_Verwandtschaftbeziehung_fertig.png]]
</popup>
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.<br>
==== 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. Dies ist ab einer bestimmten Größe nicht mehr effizient. <br>
Unter der Annahme, dass $10^{30}$ Lösungen pro ns berechnet werden können. Kann man zu folgender sehr erstaunlichen Tabelle kommen.
<table border=1>
<tr>
<th width=10%>Anzahl Knoten</th>
<th width=45%>Anzahl möglicher Lösungen</th>
<th width=45%>Benötigte Zeit</th>
</tr>
<tr>
<td>5</td>
<td>$12$</td>
<td></td>
</tr>
<tr>
<td>10</td>
<td>$181440$</td>
<td></td>
</tr>
<tr>
<td>15</td>
<td>$4,36 \cdot 10^{10}$</td>
<td></td>
</tr>
<tr>
<td>20</td>
<td>$6,08 \cdot 10^{16}$</td>
<td></td>
</tr>
<tr>
<td>25</td>
<td>$3,1 \cdot 10^{23}$</td>
<td></td>
</tr>
<tr>
<td>30</td>
<td>$4,42 \cdot 10^{30}$</td>
<td>4,42 ns</td>
</tr>
<tr>
<td>35</td>
<td>$1,48 \cdot 10^{38}$</td>
<td>0,15 s</td>
</tr>
<tr>
<td>40</td>
<td>$1,02 \cdot 10^{46}$</td>
<td>118 Tage</td>
</tr>
<tr>
<td>45</td>
<td>$1,33 \cdot 10^{54}$</td>
<td>$9,21 \cdot 10^7$ Jahre</td>
</tr>
<tr>
<td>50</td>
<td>$3,04 \cdot 10^{62}$</td>
<td>$9,6 \cdot 10^{15}$ Jahre</td>
</tr>
</table>
'''Gedankenexperiment:'''<br>
Wir haben einen gegeben Graphen. Hat das hinzufügen einer Kante Auswirkungen auf die Existenz eines Hamilton Graphen bzw. Hamilton Kreis.<br>
''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: <br>
<popup name="Paul Dirac">
[[Bild:Jowolf_Paul_Dirac.jpg]]
* 1902 in Bristol geboren
* 1984 in Tallahassee gestorben
* britischer Physiker (Quantenphysik)
* 1928 entwickelte er die Dirac-Gleichung, die die Relativitätstheorie von Einstein mit der Quantenphsik zusammengebracht hat
* legte Grundlagen für den Beweis der Antimaterie
* 1933 erhielt er den Nobelpreis mit Erwin Schrödinger "für die Entdeckung einer neuen, nützlichen Form der Atomtheorie"
</popup>
<div style= "padding:10px"> Dirac's Theorem (1952). Jeder (einfache) Graph mit wenigstens n≥3 Knoten ist hamiltonisch, wenn jeder seiner Knoten mindestens den Grad $\tfrac{n}{2}$ besitzt.</div>
Dass der Grad jedes Knotens mindestens $\tfrac{n}{2}$ beträgt, ist eine hinreichende, jedoch keine notwendige Bedingung dafür, dass der Graph hamiltonisch ist. <br>
In folgendem Beispiel gelten $n=9$ und der Mininmalgrad ist $2$. Dennoch ist der Graph hamiltonisch. <br>
[[Bild:Jowolf_Dirac-Widerlegung.png]]
<br>
In den folgenden Jahren fand man Bedingungen für die Existenz eines Hamilton Kreises:
<ol>
<li>Entfernt man aus einem hamiltonischen Graphen einen Knoten, so bleibt der Graph zusammenhängend. </li>
<li>Ein hamiltonischer Graph mit $n$ Knoten hat einen Durchmesser (maximaler Abstand zwischen 2 Knoten) von höchstens $\dfrac{n}{2}$ </li>
</ol>
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 $\mathcal O = 2^n$.<br>
===== Code =====
<code id="566be70b2b300">
#lang racket
(define staedte-permut
(lambda (n)
(letrec
((helfer
(lambda (i)
(if (= i 1)
'()
(cons i (helfer (- i 1)))))))
(let (( ls (helfer n)))
(map
(lambda (x)
(cons 1 (append x (list 1))))
(permut ls))))))
(define permut
(lambda (ls)
(cond
((null? ls) '())
((null? (cdr ls))(list(list(car ls))))
(else
(apply
append
(map (lambda (zeichen)
(map
(lambda (x) (cons zeichen x))
(permut (delete zeichen ls))))
ls))))))
(define delete
(lambda (item ls)
(cond
((null? ls) '())
((eqv? (car ls) item) (cdr ls))
(else
(cons (car ls) (delete item (cdr ls)))))))
</code>
<popup name="Laufzeit">
<document>Jowolf_Staedte-permut_laufzeit-diagramm.pdf</document>
</popup>
==== Anzahl an Hamilton Kreisen ====
'''Voraussetzung:''' Jeder Knoten ist mit jedem Knoten durch eine Kante verbunden. Es handelt sich um einen vollständigen Graphen.
<div style= "background-color:#F5D0A9; padding:10px">
Im vollständigen Graphen $K_n$ gibt es $\dfrac{1}{2} (n-1)!$ verschiedene Hamilton-Kreise.</div>
'''Begründung:''' Wir starten an einem beliebigen Startknoten, der eine Anzahl $n$ an Kanten hat. Wir haben $n-1$ Möglichkeiten die richtige Kante zum nächsten Knoten zu wählen. An diesem Knoten habe wir nur noch $n-2$ Kanten zur Wahl, da 2 Kanten zu bereits durchlaufenen Knoten führen. An dem nächsten Knoten haben wir dann nur noch die Wahl aus $n-3$ Möglichkeiten. Daraus ergibt sich dann $(n-1)!$.<br>
'''Beispiel:''' Wir haben einen vollständigen Graphen mit 5 Knoten. Wie viele Hamilton Kreise kann man finden?
<popup name="Lösung">
'''12'''
[[Bild:Jowolf_Anzahl-1.png]]
[[Bild:Jowolf_Anzahl-2.png]]
[[Bild:Jowolf_Anzahl-3.png]]
[[Bild:Jowolf_Anzahl-4.png]]
[[Bild:Jowolf_Anzahl-5.png]]
[[Bild:Jowolf_Anzahl-6.png]]
[[Bild:Jowolf_Anzahl-7.png]]
[[Bild:Jowolf_Anzahl-8.png]]
[[Bild:Jowolf_Anzahl-9.png]]
[[Bild:Jowolf_Anzahl-10.png]]
[[Bild:Jowolf_Anzahl-11.png]]
[[Bild:Jowolf_Anzahl-12.png]]
</popup>
'''Kritische Betrachtung des Verfahrens:''' Wie viele Hamilton Kreise kann man für eine Knotenanzahl von 20 Städten finden?
<popup name="Lösung">
60 Billiarden
</popup>
Eine Auflistung und Auswahl des minimalen Kreises gestaltet sich als sehr schwierig, da bei einer relativ geringen Anzahl an Knoten eine mächtige Menge von Hamilton Kreisen zustande kommt. Wenn wir jetzt durch die gesamte Menge durch iterieren wollen ist der Aufwand extrem.
=====Beweis der Komplexität (Stirlingsche Formel)=====
Zum Beweis der Komplexität ziehen wir die Stirlingsche Formel zur Hilfe. Diese hat ähnliche Eigenschaften, wie die Fakultät und hat eine sehr geringe Abweichung von der Fakultät.
[[Bild:Jowolf_Stirlingsche_Formel_und_Fakultät.png]]
[[Bild:Jowolf_StirlingscheFormel_Abweichung_von_Fakultät.png]]
Die Stirlingsche Formel lautet:
$$n! \sim \sqrt{2 \pi n} (\dfrac{n}{e})^n; n \rightarrow \infty$$
Aus dieser Grundformel kann man dann auf die folgende Gleichung kommen. Mehr Informationen dazu gibt es hier [https://www.staff.uni-mainz.de/pommeren/Kryptologie04/Klassisch/1_Monoalph/Stirling.pdf].
$$n! = \sqrt{2 \pi n} (\dfrac{n}{e})^n (1+\dfrac{1}{12n}+\dfrac{1}{288n^2}+\mathcal O (\dfrac{1}{n^3}))$$
Aus dieser Formel lässt sich dann der exponentielle Aufwand herleiten.
== Traveling Salesman Problem (TSP) ==
Das TSP ist ein klassischer Anwendungsfall der Hamilton Kreise. Das Ziel des TSP liegt darin, die günstigste Reise in einem bewertetem Graphen durch alle Orte zu finden. Seit mehreren Generationen ist dies ein sehr wichtiges Problem. Durch die sehr einfache Vorstellung des Problems ist die Einarbeitung in das Problem sehr einfach. Leider gibt es keinen allgemeinen Lösungsansatz, der das Problem in adäquater Zeit löst. Heuristiken können zwar eine Lösung bieten, diese kann aber sehr ungenau sein und wird dadurch nicht als befriedigend eingestuft.<br>
<div style= "background-color:#F5D0A9; padding:10px">
Das Problem des Handlungsreisenden (Travelling Salesman Problem) besteht darin, auf einem vollständigen bewerteten Graphen $K_n$ einen (im Sinne der Bewertung) kürzesten Hamilton-Kreis zu finden. Gilt für die Bewertung zuätzlich die Dreiecksungleichung, so spricht man von einem Rundreiseproblem.
</div>
=== Dreiecksungleichung ===
Die Dreiecksungleichung entspricht dem normalen Entfernungsverständnis im Alltag. Wenn ich also von Görlitz nach Dresden fahren möchte fahre ich nicht über Berlin, weil dieser Weg länger ist und ein direkter Weg vorliegt.
<div style= "background-color:#F5D0A9; padding:10px">
Im vollständigem Graphen $K_n$ ist die Dreiecksungleichung erfüllt, wenn für alle Knoten $u$,$v$ und $w$ gilt: $$d(u,v) \leq d(u,v)+d(w,v)$$
</div>
=== Erschöpfende Suche ===
Die erschöpfende Such oder auch exhaustive search dient zur Berechnung der kompletten Menge aller Lösungen des Problems. Die Lösungsmenge enthält in jedem Fall die optimale Lösung. Diese herauszufinden kann je nach Problem sehr einfach sein z.B. durch einen Vergleich der Kosten.<br>
In unserem Fall ist es theoretisch einfach so etwas aufzubauen, jedoch wird die Berechnungszeit bei größeren Graphen enorm ansteigen. Wir müssten für jeden Knoten $n$ aus unserem Graphen $K_n$ einen Hamilton Kreis finden. Aus dieser entstehende Menge müsste man den Kreis herausfinden, der das geringste Gewicht hat.
== Komplexitätsklassen ==
Bisher haben wir die Komplexität von bestimmten Algorithmen im Einzelnen betrachtet. In der Komplexitätstheorie werden Algorithmen bezüglich ihres unterschiedlichen Aufwands in Klassen eingeteilt. Zur Einteilung in diese Klassen sind die elementaren Rechenschritte von Bedeutung.
<popup name="Exkurs zu den Komplexitätsmaßen">
In der Empirischen Analyse steht die Untersuchung von Algorithmen anhand von gewählten Problemgrößen und deren zeitlichen Aufwand im Vordergrund.
Diese Zeitmessungen sind nicht immer sehr objektiv, an einem verteilten System kann es aufgrund der Ressourcenzuteilung zu erheblichen Abweichungen kommen.
Hier ist es angebracht eine andere Maßeinheit zu benutzen, diese kann die Anzahl der Grundoperationen sein. Für diese Betrachtung sieht man die Addition und Multiplikation als Grundoperationen an. Diese Grundoperationen kann der Prozessor mit unterschiedlichen Wortbreiten durchführen (16 Bit, 32 Bit, 64 Bit). Wenn eine Zahl zu einer anderen addiert werden soll, zum Beispiel $65000 + 13000$, dann kann der Prozessor dies in einer Operation erledigen und das Liefern des Ergebnisses hat genau eine Operation (Grundoperation) gedauert. Hierbei spricht man auch vom ''uniformen Komplexitätsaufwand'', d. h. der Aufwand wird durch eine Konstante beschränkt. Das Theoretische Modell hierfür ist die ''Registermaschine''.
Wenn jetzt die Wortbreite der Eingabewörter dazuführt, dass bei der einer Grundoperation die Wortbreite des Resultates überschritten wird, dann ist das ''uniforme Komplexitätsmaß'' nicht mehr ausreichend, weil das Resultat nicht mehr mit einer Grundoperation beschrieben werden kann.
Wenn das ''uniforme Komplexitätsmaß'' nicht ausreicht, verwendet man die ''Bit-Komplexität''. Hierbei hängt der Aufwand einer Operation von der Wortbreite (Bitlänge des Eingabewortes) der Eingabe ab. Das zugehörige theoretische Modell ist die ''Turing-Maschine''. Hierbei ergibt sich der Aufwand aus der Zahl der Bit-Rechenoperationen zur Lösung eines bestimmten Problems.
</popup>
===Die ''time'' und ''TIME'' Funktion===
Als Voraussetzung muss der entsprechende Algorithmus als Turing-Programm formuliert sein.
<div style= "background-color:#F5D0A9; padding:10px">
:$time(w) = \text{Anzahl der Rechenschritte der TM bei eingabe von}$ $ w$
</div>
<div style= "background-color:#F5D0A9; padding:10px">
:$TIME(f) = \lbrace L \subseteq \Sigma^{*} | \text{ Es gibt eine TM mit } L = L(TM) \text{ und } time(w) \leq f(|w|) \text{ für alle } w \in L\rbrace$
</div>
===Die Komplexitätsklasse P===
<div style= "background-color:#F5D0A9; padding:10px">
:Die Klasse P lässt sich definieren als Klasse aller Probleme, die mit deterministischen Algorithmen in polinomialer Zeit gelöst werden können.
</div>
Definition mit Hilfe der Turingmaschine:
<div style= "background-color:#F5D0A9; padding:10px">
:<math>\text{P} = \bigcup_{\text{p Polynom}} \text{TIME}\left(p\right)</math>
</div>
;Diese Problemklasse lässt sich effizient mit Algorithmen lösen.
===Die Komplexitätsklasse NP===
<div style= "background-color:#F5D0A9; padding:10px">
:Die Komplexitätsklasse der NP-Probleme ist die Menge aller Probleme, die nichtdeterministisch in Polynomzeit gelöst werden können.
</div>
Definition mit Hilfe der Turingmaschine:
<div style= "background-color:#F5D0A9; padding:10px">
:<math>\text{NP} = \bigcup_{\text{p Polynom}} \text{NTIME}\left(p\right)</math>
</div>
;In dieser Klasse gibt es keine effizienten Algoritmen zur Lösung der Probleme.
== Heuristiken ==
===Motivation===
Von Bedeutung sind diese Verfahren, wenn es zwar theoretisch optimale Lösungen für bestimmte Probleme gibt, diese jedoch in der Praxis aufgrund extrem langer Rechenzeiten verworfen werden müssen.
===Begriff===
Der Begriff Heuristik stammt von dem griechischen Wort "heurisko" ab, das übersetzt etwa "ich finde", "ich suche" bedeutet.
<language>Java</language>
===Definition===
<div style= "background-color:#F5D0A9; padding:10px">
Heuristiken sind durch Erfahrung gewonnene Regeln und Verfahren, die in akzeptabler Zeit zu einer zufriedenstellenden Lösung führen. Man weiß zwar nicht, ob die gefundene Lösung optimal ist, man ist aber mit dem Ergebnis zufrieden, wenn sich abschätzen lässt, wie gut oder wie schlecht die gefundene Lösung ist. Durch Probieren wird versucht das Ergebnis weiter zu verbessern.
Es handelt sich um Faustregeln oder Handlungsempfehlungen, basierend auf intuitiven Regeln, ähnlich den Bauernregeln für das Wetter. Aus einer Vielzahl von Möglichkeiten werden einige herausgefiltert.
</div>
====Beispiele hierfür sind:====
:das 0/1 Rucksackproblem,
:das TSP,
:das Springerproblem beim Schach.
<popup name="Springerproblem">
Das Springerproblem untersucht die Frage: "Gibt es einen Weg, bei dem der Springer jedes Feld eines n mal n großen Schachbretts genau einmal besucht?".
</popup>
===Heuristiken und Algorithmen===
<table border=1>
<tr>
<th width=50%>1. Fall</th>
<th width=50%>2. Fall</th>
</tr>
<tr>
<td>Es gibt eine exakte Lösung des Problems.</td>
<td>Es gibt keine exakte Lösung des Problems.</td>
</tr>
<tr>
<td>Anwendung eines Verfahrens/Algorithmus, welches das Optimalitätskriterium für ein bestimmtes Problem erfüllt.</td>
<td>Das Optimalitätskriterium wird nicht immer erfüllt.</td>
</tr>
<tr>
<td>Hier spricht man von einem <b>Algorithmus</b>.</td>
<td>Diese Verfahren können <b>Heuristiken</b> sein.</td>
</tr>
</table>
<div style= "background-color:#F5D0A9; padding:10px">
Also kann man festhalten: $Heuristiken \subset Algorithmen$.
</div>
;Wenn die Lösung nicht exakt ist, bleibt die Frage nach Ihrer Güte.
;D. h. wie groß ist die Abweichung von dem exakten Ergebnis?
;Diese Betrachtung in Bezug auf die Heuristiken erfolgt weiter unten!
==Heuristiken für das TSP==
=== Nearest-Neightbor-Heuristik ===
Ein weiterer Name dafür ist der "Best-Successor-Algorithmus", man spricht ebenfalls von der "Methode des Besten Nachfolgers".
====Gruppe:====
Greedy Algorithmen
=====Aufbau=====
;siehe auch: [[Matching-Probleme|Aufbau Greedy Algorithmus/Greedy Matching Algorithmus]]
=====Allgemeine Greedy Charakteristik=====
:lokale Suche nach bestem Nachfolger (Happen)
:kein Backtracking, revidieren der Entscheidung
:keine vorübergehende Verschlechterung durch Vorausschau
====Prinzipelles Vorgehen des Verfahrens====
Eingabe: ''Vollständig bewerteter Graph'' $K_n$
<table>
<tr>
<td width=10%>Schritt 1:</td>
<td width=90%>Beginne an einem beliebigen Knoten mit leerer Tour $v \in V$ und $T = \emptyset$.</td>
</tr>
<tr>
<td>Schritt 2:</td>
<td>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$.</td>
</tr>
<tr>
<td>Schritt 3:</td>
<td>Solange es noch unbesuchte Knoten gibt, gehe zu Schritt 2. Ansonsten gehe zurück zum Anfang $v$ und füge $v$ der Tour hinzu $T = T \cup \{v\}$</td>
</tr>
</table>
Ergebnis: ''Hamilton-Kreis''
====Beispiel für ein TSP====
<b>Wenden sie die Greedy Heuristik auf alle möglichen Startpunkte an und geben sie alle Touren und Kosten an.</b>
[[Bild:Gawantka.falko_Neues_Bsp.png]]
<popup name="Lösung">
Tour1 = (A,C,B,D,A), Kosten der Tour = 13
Tour2 = (B,C,A,D,B), Kosten = 13
;Tour3 = (C,A,B,D,C), Kosten = 6
Tour4 = (D,B,C,A,D), Kosten = 13
:Bemerkung: Die Lösungen wurden mit Hilfe der Adjazenzmatrix ermittelt, darin sind die Knoten lexikografisch geordnet. Bei gleichen Kosten zu einem Nachbarknoten wurde die erste Fundstelle in der Matrix ausgewählt.
</popup>
<popup name="Güte von Nearest Neighbor">
:Die Nearest Neighbor Heuristik kann beliebig schlecht sein, ausgehend davon welchen Punkt man als Startpunkt wählt. Oftmals ist es so, dass wenn alle Kanten durchlaufen sind und am Ende nur eine extrem teure Kante übrig bleibt, diese ausgewählt werden muss.
</popup>
====Komplexität der Heuristik====
Die Komplexität der Heuristik beträgt $\mathcal O(n^2)$ laut Literatur. Somit liegt die Heuristik in der Komplexitätsklasse P und ist effizient lösbar.
Die empirische Laufzeitanalyse ergab folgende Werte.
<popup name="Ergebnisse der Analyse">
<table border=1>
<tr>
<th>Anzahl der Städte</th><th>worst case in ms</th><th>average case in ms</th><th>best case in ms</th>
</tr>
<tr>
<td>500</td><td>9</td><td>6,6</td><td>5</td>
</tr>
<tr>
<td>1000</td><td>19</td><td>14</td><td>11</td>
</tr>
<tr>
<td>1500</td><td>33</td><td>21,5</td><td>15</td>
</tr>
<tr>
<td>2000</td><td>38</td><td>29,5</td><td>24</td>
</tr>
<tr>
<td>3000</td><td>69</td><td>63</td><td>56</td>
</tr>
<tr>
<td>4000</td><td>152</td><td>133,7</td><td>121</td>
</tr>
<tr>
<td>5000</td><td>347</td><td>289,1</td><td>227</td>
</tr>
<tr>
<td>6000</td><td>677</td><td>551,3</td><td>414</td>
</tr>
<tr>
<td>7000</td><td>968</td><td>871,4</td><td>708</td>
</tr>
<tr>
<td>8000</td><td>1831</td><td>1532,7</td><td>1175</td>
</tr>
<tr>
<td>9000</td><td>3375</td><td>2733,9</td><td>2124</td>
</tr>
<tr>
<td>10000</td><td>4833</td><td>3987,6</td><td>2751</td>
</tr>
<tr>
<td>11000</td><td>7480</td><td>6325,9</td><td>5174</td>
</tr>
<tr>
<td>12000</td><td>10509</td><td>9006,5</td><td>7044</td>
</tr>
<tr>
<td>13000</td><td>15214</td><td>12993,3</td><td>10083</td>
</tr>
<tr>
<td>14000</td><td>19312</td><td>17839,7</td><td>15931</td>
</tr>
<tr>
<td>15000</td><td>27605</td><td>24206,6</td><td>20199</td>
</tr>
<tr>
<td>16000</td><td>36549</td><td>31421,1</td><td>27192</td>
</tr>
<tr>
<td>17000</td><td>43864</td><td>41390,2</td><td>37233</td>
</tr>
<tr>
<td>18000</td><td>59230</td><td>55143</td><td>48109</td>
</tr>
<tr>
<td>19000</td><td>74463</td><td>66823,1</td><td>48109</td>
</tr>
<tr>
<td>20000</td><td>91193</td><td>83231,7</td><td>77400</td>
</tr>
<tr>
<td>21000</td><td>114162</td><td>104193,2</td><td>96325</td>
</tr>
<tr>
<td>22000</td><td>1352932</td><td>121255,2</td><td>110611</td>
</tr>
<tr>
<td>23000</td><td>162269</td><td>145085,4</td><td>121671</td>
</tr>
<tr>
<td>24000</td><td>178185</td><td>167577,2</td><td>156745</td>
</tr>
<tr>
<td>25000</td><td>211800</td><td>200697,3</td><td>186271</td>
</tr>
</table>
</popup>
<popup name="Graph:">
[[Bild:Graph_v4.png]]
</popup>
====Implementation====
<code id="566f435566a2e">
public static int[] nearestNeighbor (int[][] adjmatrix) {
int[] result = new int[adjmatrix.length + 1];
result[0] = 0;
int min = Integer.MAX_VALUE;
int zeile = 0;
int tempzeile = 0;
for(int i = 0; i < result.length - 1; i++) {
min = Integer.MAX_VALUE;
for(int spalte = 0; spalte < adjmatrix.length; spalte++) {
if (adjmatrix[zeile][spalte] != 0 && adjmatrix[zeile][spalte] < min && !Contains(result, spalte)) {
min = adjmatrix[zeile][spalte];
tempzeile = spalte;
}
}
result[i] = zeile;
zeile = tempzeile;
}
result[adjmatrix.length] = 0;
return result;
}
</code>
====Vor- und Nachteile====
<table border=1>
<tr>
<th width=50%>Vorteile</th>
<th>Nachteile</th>
</tr>
<tr>
<td>schnelles Verfahren</td>
<td>keine optimalen Ergebnisse</td>
</tr>
<tr>
<td>geeignet für große Problemgrößen</td>
<td>keine globale suche</td>
</tr>
<tr>
<td>praktikabel</td>
<td></td>
</tr>
<tr>
<td>kann ein praktisch unlösbares Problem lösen</td>
<td></td>
</tr>
</table>
=== Insertion-Heuristiken===
Es gibt unterschiedliche Insertion Heuristiken, bei denen, wie der Name vermuten lässt, in eine bestehende Tour Knoten eingefügt werden. Man unterscheidet folgende Heuristiken: ''Farthest-Insertion'', ''Random-Insertion'' und ''Best-Insertion''. Im Folgenden wird auf ''Random-Insertion'' eingegangen.
====Gruppe:====
Greddy Algorithmen
====Prinzipielles Vorgehen des Verfahrens====
Eingabe: Vollständig bewerteter Graph $K_n$
<table>
<tr>
<td width=10%>Schritt 1:</td>
<td width=90%>Wähle 3 Startknoten und bilde eine Rundreise durch diese.</td>
<tr>
<td></td>
<td>''1.1'' Diese Tour besteht aus 3 Toursegmenten, nämlich den Kanten zwischen den vorhandenen Knoten.</td>
</tr>
<tr>
<td>Schritt 2:</td>
<td>Solange noch Knoten existieren, die noch nicht der Tour hinzugefügt wurden, wiederhole die folgenden Schritte</td>
</tr>
<tr>
<td></td>
<td>''2.1'' Wähle zufällig einen noch nicht zur Tour hinzugefügten Knoten Z aus.</td>
</tr>
<tr>
<td></td>
<td>''2.2'' Berechne die Distanz von Z zu allen Knoten in der Tour.<td/>
</tr>
<tr>
<td></td>
<td>''2.3'' Bestimme die zwei benachbarten Knoten P und Q der bisherigen Tour, sodass, wenn man Z zwischen Ihnen einfügt, die aktuelle Rundreise minimal verlängert wird.</td>
</tr>
<tr>
<td></td>
<td>''2.4'' Füge Z zur aktuellen Tour hinzu, indem die Strecke PQ durch PZ und ZQ ersetzt wird.</td>
</tr>
</table>
Ergebnis: $Hamilton-Kreis$
====Beispiel ====
;Auswahl eines beliebigen Knotens
<popup name="Bild1">
[[Bild:Gawantka.falko_Rand_insert_1.png]]
</popup>
;Hinzufügen des Knoten in bestehende Tour
<popup name="Bild2">
[[Bild:Gawantka.falko_Rand_insert_2.png]]
</popup>
====Komplexität der Heuristik====
Die Komplexität die für ''Random-Insertion'' wird in der Literatur mit $\mathcal O(n^2)$ angegeben. Somit liegt diese Heuristik ebenfalls in der Komplexitätsklasse P.
====Vor- und Nachteile====
Im Allgemeinen gelten die gleichen Vor- und Nachteile, wie bei der Nearest-Neighbor-Heuristik, jedoch liefern die Insertion Heuristiken oftmals bessere Lösungen, aufgrund der Tatsache, dass die Suche nicht streng lokal, wie bei Nearest-Neighbor, ist.
=== Minimum-Spanning-Tree-Heuristik (MST)===
====gehört zur Gruppe:====
Approximationsalgorithmen
<popup name="Definition">
Ein Approximationsalgorithmus ist ein Algorithmus, der versucht ein Problem näherungsweise zu lösen. Der Algorithmus wird jedoch nur in den seltensten Fällen die exakte Lösung erreichen.
</popup>
====Prinzipelles Vorgehen des Verfahrens====
Eingabe: Vollständiger bewerteter Graph $K_n$
<table>
<tr>
<td width=10%>Schritt 1:</td>
<td width=90%>Bestimmung eines minimal spannenden Baums $B$ in $G$ durch den [[Minimal_aufspannende_Bäume#Algorithmus_von_Prim|Algorithmus von Prim]] oder [[Minimal_aufspannende_Bäume#Algorithmus_von_Kruskal|Algorithmus von Kruskal]]</td>
<tr>
<td>Schritt 2:</td>
<td>Verdopple jede Kante in $B$</td>
</tr>
<tr>
<td>Schritt 3:</td>
<td>Bestimme einen Eulerkreis $K$ in $B$. Der Startknoten ist beliebig.</td>
</tr>
<tr>
<td>Schritt 4:</td>
<td>Erstelle einen neuen Graphen $K'$. Übernimm dabei alle Kanten aus $K$ und entferne alle Kante, die bereits zu besuchten Knoten führen. Ersetze diese Kante durch eine Kante zum Knoten der im Eulerkreis an nächster Stelle kommt. Ausnahme dabei ist der Startknoten.</td>
</tr>
</table>
Ergebnis: $Hamilton-Kreis$
====Beispiel für ein TSP====
[[Bild:Jowolf_MST-Heuristik-1.png]]
<popup name="1. Schritt">
[[Bild:Jowolf_MST-Heuristik-2.png]]
<popup name="2. Schritt">
[[Bild:Jowolf_MST-Heuristik-3.png]]
<popup name="3. Schritt">
Eulerkreis: $K = ${$D, C, D, B, D, A, D, E, D$}
<popup name="4. Schritt">
[[Bild:Jowolf_MST-Heuristik-4.png]]
Hamilton-Kreis: {$D, C, B, A, E, D$}
</popup>
====Komplexität der Heuristik====
Die Komplexität der Heuristik ist polynomiell, da der Algorithmus von Prim bzw Kruskall in Polynomialzeit durchführbar ist.
<table border=1>
<tr>
<th width=100>Schritt</th>
<th width=200>Komplexität</th>
</tr>
<tr>
<td><p align=center>1</p></td>
<td>$$\mathcal O (n^2)$$</td>
</tr>
<tr>
<td><p align=center>2</p></td>
<td>$$\mathcal O (n)$$</td>
</tr>
<tr>
<td><p align=center>3</p></td>
<td>$$\mathcal O (n)$$</td>
</tr>
<tr>
<td><p align=center>4</p></td>
<td>$$\mathcal O (n)$$</td>
</tr>
</table>
====Vor.- und Nachteile====
<table border=1>
<tr>
<th width=50%>Vorteile</th>
<th>Nachteile</th>
</tr>
<tr>
<td>schnelles Verfahren</td>
<td>keine exakte Lösung, da das Gewicht des MST größer als die optimale Rundreise sein kann</td>
</tr>
<tr>
<td>geeignet für große Problemgrößen</td>
<td></td>
</tr>
<tr>
<td>praktikabel</td>
<td></td>
</tr>
<tr>
<td>kann ein praktisch unlösbares Problem lösen</td>
<td></td>
</tr>
</table>
== Anwendung in der Praxis ==
Ein Außendienstmitarbeiter soll alle Kunden die ein bestimmtes Produkt benutzen aufsuchen und ein neues vorstellen. Gesucht ist der kürzestes Weg der alle Kunden beinhaltet.
Ein Mitarbeiter von einem Pflegedienst soll in einem bestimmten Stadtbezirk die Patienten so abfahren das der weg am geringsten ist.
Das bohren von Leiterplatten in der Elektronik. Hier bei sind Leiterbahnen in Platinen geätzt jetzt sollen Löcher so gebohrt werden das der Abstand zwischen bestimmten Bauteilen minimal ist.
In der Automobil Industrie soll ein Schweißroboter so schnell wie möglich festgelegte Schweißnähte an der Karosserie ziehen. Dabei liegt ist es für die Hersteller wichtig, dass der Schweißroboter so wenig wie möglich Weg ohne das Ziehen einer Schweißnaht zurück legt.
== Quellen ==
* Krischke/Röpcke, 2015, Graphen und Netzwerktheorie
* Wagenknecht, 2003, Algorithmen und Komplexität
* Vossen/Witt, 2000 , Grundlagen der Theoretischen Informatik mit Anwendungen
* Schöning, 1992, Theoretische Informatik kurz gefasst
* Hartmann, 2015, Mathematik für Informatiker
* Gumm/Sommer, 2013, Einführung in die Informatik
* [https://www.dropbox.com/sh/8jakxwbw6txwowt/AACFReP2kd3bfjh1NDlTT4B0a?dl=0]