Hamilton Kreise
Inhaltsverzeichnis |
Einführung
Definitionen Graphentheorie
Einfacher Weg
Einfacher Kreis
Bewerteter Graph
Dijktra-Algorithmus
Hamilton Graphen
???
Hamiliton Wege
???
Hamilton Kreise
???
Traveling Salesman Problem (TSP)
???
Heuristiken
Begriff
Der Begriff Heuristik stammt von dem griechischen Wort "heurisko" ab, das heißt übersetzt etwa "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.
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
???
Pseudocode
???
Implementation
???
Vor.- und Nachteile
???
Nearest-Insertion-Heuristik
???
Farthest-Insertion-Heuristik
???
Minimum-Spanning-Tree-Heuristik (MST)
???
Anwendung in der Praxis
???