Eine Heuristik ist ein erfahrungsbasiertes Verfahren, das in kurzer Zeit eine gute, aber nicht garantiert optimale Lösung für ein Problem findet. Sie verzichtet bewusst auf eine Optimalitätsgarantie, um bei großen oder NP-vollständigen Problemen überhaupt noch in vertretbarer Zeit zu einer brauchbaren Antwort zu kommen.
Exakt vs. heuristisch
Exakte Algorithmen wie die Ungarische Methode beim Assignment-Problem oder der Gale-Shapley-Algorithmus liefern nachweisbar das Optimum. Sobald der Suchraum jedoch exponentiell wächst (etwa beim Handlungsreisenden- oder Rucksackproblem), explodiert die Laufzeit — dann sind Heuristiken oft die einzige praktikable Wahl.
Klassen von Heuristiken
- Greedy-Verfahren wählen in jedem Schritt die lokal beste Option — schnell, aber oft suboptimal.
- Backtracking und Tiefen-/Breitensuche durchsuchen den Raum systematisch; mit heuristischen Bewertungsfunktionen (z. B. A*) lenken sie die Suche gezielt in vielversprechende Bereiche.
- Metaheuristiken wie Simulated Annealing, genetische Algorithmen oder Tabu-Suche steuern die Suche auf einer höheren Ebene und entkommen lokalen Optima.
Von Approximationsalgorithmen unterscheiden sich Heuristiken dadurch, dass Approximationen eine beweisbare Gütegarantie relativ zum Optimum liefern, Heuristiken dagegen nicht.
Trade-off
Der Kern jeder Heuristik ist der Abwägung zwischen Laufzeit und Lösungsqualität, messbar mit der Big-O-Notation. In der Praxis kombiniert man oft mehrere Strategien: eine schnelle Greedy-Startlösung, danach eine lokale Verbesserung. Auch dynamische Programmierung kann bei strukturierten Teilproblemen helfen. Entscheidend bleibt: Eine Heuristik ist ein Werkzeug des Algorithmus-Baukastens für Fälle, in denen das perfekte Ergebnis unmöglich oder zu teuer ist.