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