Bei Verwendung von A * (oder eines anderen Algorithmus zur Ermittlung des besten Pfades) sollte die verwendete Heuristik zulässig sein , dh die tatsächliche Länge des Lösungspfades (oder der Bewegungen) sollte niemals überschätzt werden.
Wie stellt eine zulässige Heuristik eine optimale Lösung sicher? Ich suche vorzugsweise eine intuitive Erklärung.
Wenn Sie möchten, können Sie dies anhand der Manhattan- Entfernungsheuristik des 8-Puzzles erklären .
Antworten:
Während Antons Antwort absolut perfekt ist, möchte ich versuchen, eine alternative Antwort zu liefern: Zulässig zu sein, bedeutet, dass die Heuristik den Aufwand zum Erreichen des Ziels nicht überschätzt, dh für alle in der Zustandsraum (im 8-Puzzle bedeutet dies nur für jede Permutation der Kacheln und des Ziels, das Sie gerade betrachten), wobei die optimalen Kosten sind, um das Ziel zu erreichen.n h * ( n )h ( n ) ≤ h∗( n ) n h∗( n )
Ich denke, die logischste Antwort, um zu sehen, warum optimale Lösungen liefert, wenn zulässig ist, ist, weil es alle Knoten in OFFEN in aufsteigender Reihenfolge von sortiert und auch, weil es beim Erzeugen des Ziels nicht aufhört, sondern beim Erweitern: h ( n ) f ( n ) = g ( n ) + h ( n )EIN∗ h ( n ) f( n ) = g( n ) + h ( n )
Und das ist im Wesentlichen alles, was Sie im Originalbeweis von Nilsson et al. Finden.
Hoffe das hilft,
quelle
Wenn die heuristische Funktion nicht zulässig ist, können wir eine Schätzung haben, die größer ist als die tatsächlichen Pfadkosten von einem Knoten zu einem Zielknoten. Befindet sich diese Schätzung der höheren Pfadkosten auf dem Pfad mit den geringsten Kosten (den wir suchen), untersucht der Algorithmus diesen Pfad nicht und findet möglicherweise einen anderen Pfad (nicht die geringsten Kosten) zum Ziel.
Schauen Sie sich dieses einfache Beispiel an.
Lass die Heuristik sein
quelle