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

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