Eine Heuristik ist eine Schätzung der verbleibenden Kosten bis zum Ziel — eine Faustregel, die einem Suchverfahren sagt, welche Richtung vielversprechend ist. Sie muss nicht exakt sein, nur hilfreich.
Ein uninformiertes Verfahren erkundet den Raum blind (siehe Uninformierte Suche). Eine Heuristik gibt ihm einen Anhaltspunkt: Für jeden Zustand schätzt sie, wie teuer der Weg von dort zum Ziel noch wird. Das Verfahren kann daraufhin die aussichtsreichen Knoten zuerst betrachten und weite Teile des Raums unbesehen lassen.
Bei einer Routensuche ist die Luftlinie zum Ziel eine Heuristik. Sie ist nicht die tatsächliche Fahrstrecke — Straßen verlaufen selten schnurgerade —, aber sie unterscheidet zuverlässig zwischen einer Abzweigung, die zum Ziel führt, und einer, die davon wegführt. Beim Schiebepuzzle zählt man ersatzweise die falsch liegenden Steine oder addiert deren Abstände zu ihren Zielfeldern (Manhattan-Distanz).
Eine Heuristik heißt zulässig, wenn sie die tatsächlichen Restkosten nie überschätzt. Sie darf zu optimistisch sein, aber niemals zu pessimistisch. Nur unter dieser Bedingung findet die A*-Suche garantiert die günstigste Lösung: Ein Weg wird nur dann verworfen, wenn er nachweislich teurer ist. Die Luftlinie ist zulässig, weil keine Straße kürzer sein kann als die direkte Verbindung.
Stärker als die Zulässigkeit ist die Konsistenz: Die Schätzung darf sich von einem Knoten zum nächsten höchstens um die tatsächlichen Kosten dieses Schritts verringern — eine Form der Dreiecksungleichung. Jede konsistente Heuristik ist zulässig; für die praktische Arbeit ist Konsistenz die bequemere Eigenschaft, weil dann kein Knoten mehrfach überarbeitet werden muss.
Eine bewährte Methode ist das gelockerte Problem: Man streicht eine Regel und löst die einfachere Aufgabe exakt. Erlaubt man beim Schiebepuzzle, Steine übereinander zu schieben, ergibt die Summe der Einzelabstände genau die Manhattan-Distanz — und weil das gelockerte Problem nie schwerer ist als das echte, ist das Ergebnis automatisch zulässig. Heuristiken lassen sich auch aus Musterdatenbanken vorberechnen oder mit maschinellem Lernen schätzen.
Das Wort geht auf griechisch heuriskein, „finden", zurück. In der KI bezeichnet es allgemeiner jede Faustregel, die eine Lösung wahrscheinlicher oder schneller macht, ohne sie zu garantieren.
Hallo! Ich bin dein KI-Tutor.
Melde dich an, um mit mir zu chatten — ich erinnere mich dann auch an eure letzten Gespräche.
