AuK/Näherungsverfahren 1 WS13-14

Wiki-Quelltext dieser Seite.

==Einleitung==
===Motivation===
Besonders in der Praxis sind NP-vollständige Probleme, für die es keine effizienten Algorithmen gibt, von großem Interesse. Dies zeigte sich bei der Diskussion des P-NP-Problems.
Durch Modifizierung des Problems können sogenannte "Ersatzalgorithmen" gefunden werden. Dies geschieht durch Verstärken oder Abschwächen von Nebenbedingungen oder durch das Einschränken auf Teilprobleme. Man bedient  sich also bestimmter Heuristiken, die zumindestens approximative (näherungsweise) Lösungen bieten. Doch es muss auch dafür gesorgt sein dass die Abweichung des Resultats von der unbekannten exakten Lösung möglichst gering ist.

===Heuristiken===
Heuristik stammt aus dem Griechischen und ist von dem Wort "heuriskien" abgeleitet und bedeutet so viel wie "(auf)-finden" bzw. "entdecken". Es handelt sich dabei um ein Verfahren mit dem man ein Problem sinnvoll löse kann, für das jedoch nicht garantiert werden kann das es zu 100% funktioniert. Bei diesem Verfahren wird aus einer Vielzahl von Möglichkeiten eine Gewissen Anzahl heraus gefiltert.  Die sogenannte Brute-Force-Methode ist das Gegenteil zu Heuristiken.

== Heuristiken für das Springerproblem ==
== Lokale Suche ==
===Verzweigen und Begrenzen===
===Greedy Heuristiken===
====Nearest neighbour heuristic====
====Farthest insertion====
====Random insertion====
====Best insertion====

===Hill Climbing===
===Threshold accepting===
===Simulatet annealing===
===Tabu-Suche===
===Der Sinflut-Algorithmus===
=Übungen=
=Literatur=
Christian Wagenknecht ''Algorithmen und Komplexität.'' Fachbuchverlag Leipzig, 2003, ISBN 3-446-22314-2, Seite 153-163