Hamilton Kreise

Wiki-Quelltext dieser Seite.

== 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. 

[[Bild:Jowolf_EinfacherWegCEFG.png]]

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. 

[[Bild:Jowolf_EinfacherKreisFGJF.png]]

siehe auch: [[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->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->M die jedem Knoten v einen Wert oder ein Symbol zuordnet.</td>
      </tr>
    </table>
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. <br>
[[Bild:Jowolf_Dijkstra_Animation.gif]]

siehe auch: [[Kürzeste_Wege_in_Graphen#Algorithmus_von_Dijkstra]]

== Hamilton Graphen ==
???

=== Hamiliton Wege===
???

=== Hamilton Kreise ===
???

== 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 $G = (V,E)$

Ergebnis: Hamilton-Kreis

: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\}$

====Pseudocode====
???

====Implementation====
???

====Vor.- und Nachteile====
???

=== Nearest-Insertion-Heuristik ===
???
=== Farthest-Insertion-Heuristik ===
???
=== Minimum-Spanning-Tree-Heuristik (MST)===
???

== Anwendung in der Praxis ==
???