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