Warum ist A * optimal, wenn die heuristische Funktion zulässig ist?

Eine Heuristik ist zulässig, wenn sie die tatsächlichen Kosten für das Erreichen des Zielknotens niemals überschätzt$n$. Wenn eine Heuristik konsistent ist , dann ist der heuristische Wert von$n$ ist nie höher als die Kosten seines Nachfolgers, $n'$plus den heuristischen Wert des Nachfolgers.

Warum ist A * mit Baum- oder Diagrammsuche optimal, wenn eine zulässige Heuristik verwendet wird?

Dies wird im entsprechenden Kapitel von Russell & Norvig (Kapitel 3.5, Seiten 93 bis 99 (dritte Ausgabe)) ausführlich behandelt . Überprüfen Sie das für weitere Details.

Lassen Sie uns zunächst die Definitionen überprüfen:

Ihre Definitionen von zulässig und konsistent sind korrekt.

Eine zulässige Heuristik ist grundsätzlich nur "optimistisch". Eine Entfernung wird nie überschätzt.

Eine konsistente Heuristik ist eine, bei der Ihre früheren Überzeugungen über die Entfernungen zwischen Zuständen selbstkonsistent sind. Das heißt, Sie glauben nicht, dass es 5 von B bis zum Ziel, 2 von A bis B und dennoch 20 von A bis zum Ziel kostet. Sie sind erlaubt allerdings zu optimistisch sein. Man könnte also glauben, dass es 5 von B zum Ziel, 2 von A nach B und 4 von A zum Ziel sind.

Eine Baumsuche ist eine allgemeine Suchstrategie für Suchprobleme mit einer Baumstruktur: Das heißt, es ist niemals möglich, von einem späteren Zustand zu einem früheren Zustand zurückzukehren. Dies modelliert bestimmte Arten von Spielen, wie zum Beispiel Tic-Tac-Toe. Die Baumsuche merkt sich nicht, welche Staaten sie bereits besucht hat, sondern nur den "Rand" der Staaten, die sie noch nicht besucht hat.

Eine Graphensuche ist eine allgemeine Suchstrategie für die Suche nach grafisch strukturierten Problemen, bei der es möglich ist, zu einem früheren Zustand zurückzukehren, wie im Schach (z. B. können beide Spieler ihre Könige einfach hin und her bewegen). Um diese Schleifen zu vermeiden, verfolgt die Diagrammsuche auch die Zustände, die sie verarbeitet hat.

Weitere Informationen zur Suche nach Bäumen und Diagrammen finden Sie in den guten Antworten auf diese Frage zum Stapelüberlauf .

Okay, jetzt lassen Sie uns die Intuition hinter den Beweisen durchgehen.

Das wollen wir zuerst zeigen

Wenn $h(n)$ ist zulässig, A * mit Baumsuche ist optimal.

Der übliche Beweis ist der Widerspruch.

1. Angenommen, A * mit Baumsuche und zulässiger Heuristik war nicht optimal.

2. Nicht optimal zu sein bedeutet, dass der erste vollständige Pfad vom Start bis zum von A * entdeckten Ziel (nennen Sie dies) $q$) wird länger sein als irgendein anderer Pfad $p$, die A * bis zu einem gewissen Grad erkundet hat $s$, aber nicht weiter.

3. Da die Heuristik zulässig ist, ergeben sich die geschätzten Kosten für das Erreichen des Ziels aus $s$ muss kleiner sein als die tatsächlichen Kosten.

4. Um 3 und die Tatsache, dass wir wissen, wie viel es kostet, zu erreichen $s$ entlang $p$, die geschätzten Gesamtkosten von $p$und damit die Kosten für die Erweiterung $s$ muss kleiner sein als die tatsächlichen Kosten von $p$.

5. Da die wahren Kosten von $p$ ist kleiner als die Kosten von $q$ (um 2) die geschätzten Kosten für die Erweiterung $s$ muss kleiner sein als die tatsächlichen Kosten von $q$.

6. A * wählt immer den Pfad mit den vielversprechendsten Gesamtkosten für die nächste Erweiterung aus, und die Kosten für die Erweiterung des Zielstatus ergeben sich aus der Gesamtweglänge, die erforderlich ist, um ihn zu erreichen.

7. 5 und 6 bilden einen Widerspruch, daher muss unsere Annahme in 1 falsch gewesen sein. Daher muss A * optimal sein.

Der Diagrammsuchnachweis verwendet eine sehr ähnliche Idee, berücksichtigt jedoch die Tatsache, dass Sie möglicherweise zu früheren Zuständen zurückkehren.