Warum ist die A * -Suchheuristik optimal, auch wenn sie die Kosten unterschätzt?

Eine * Suche findet eine optimale Lösung für Probleme, solange die Heuristik zulässig ist. Dies bedeutet, dass die Kosten des Pfads von einem bestimmten Knoten zu einem nie überschätzt werden (und konsistent sind, aber konzentrieren wir uns darauf, im Moment zulässig zu sein).

Aber warum findet es immer die optimale Lösung, wenn die Heuristik unterschätzt? Wenn zum Beispiel ein nicht optimaler Pfad um mehr als das unterschätzt wird, was er den optimalen Pfad unterschätzt, ist das nicht gleichbedeutend mit einer Überschätzung?

A * verwaltet eine Prioritätswarteschlange mit Optionen, die in Betracht gezogen werden, geordnet nach der Qualität. Es sucht so lange, bis es einen Weg zum Ziel findet, der so gut ist, dass keine der anderen Optionen es möglicherweise verbessern könnte. Wie gut eine Alternative sein könnte, hängt von der Heuristik und den tatsächlichen Kosten ab, die bisher bei der Suche ermittelt wurden.

Wenn die Heuristik unterschätzt wird, sehen die anderen Optionen besser aus als sie wirklich sind. A * glaubt, dass diese anderen Optionen die Route verbessern könnten, und überprüft sie daher. Wenn die Heuristik nur ein wenig unterschätzt wird, erweisen sich einige dieser Routen möglicherweise als nützlich. Auf der anderen Seite kann A *, wenn die Heuristik überschätzt, denken, dass die Alternativen zur Route, die es bereits gibt, alle schrecklich sind, so dass es nicht die Mühe macht, sie anzusehen. Aber die Heuristik überschätzt, so dass sie viel besser sein könnten, als sie scheinen.

Angenommen, Sie versuchen, von Chicago nach New York zu fahren, und Ihre Freunde denken über Ihre Geografie. Wenn Ihr erster Freund sagt: "Hey, Boston liegt in der Nähe von New York" (unterschätzt), verschwenden Sie Zeit damit, sich Routen über Boston anzusehen. In Kürze werden Sie feststellen, dass jede vernünftige Route von Chicago nach Boston bereits vor Erreichen von Boston ziemlich nahe an New York heranreicht und dass die Fahrt über Boston nur noch mehr Meilen bringt. Sie hören also auf, Routen über Boston in Betracht zu ziehen, und fahren fort, um die optimale Route zu finden. Ihr unterschätzter Freund hat Sie ein wenig Planungszeit gekostet, aber am Ende haben Sie den richtigen Weg gefunden.

Angenommen, ein anderer Freund sagt: "Indiana ist eine Million Meilen von New York entfernt!" Nirgendwo sonst auf der Welt sind es mehr als 21.000 Kilometer von New York. Wenn Sie also den Rat Ihres Freundes wörtlich nehmen, werden Sie nicht einmal eine Route durch Indiana in Betracht ziehen. Dadurch fahren Sie fast doppelt so lange und legen 50% mehr Strecke zurück . Hoppla.

Es ist wahr, dass wenn es einen nicht optimalen Pfad um mehr als den optimalen unterschätzt, es diese Pfade untersucht, bevor es den optimalen Pfad erkundet. Was wichtig ist und was die Zulässigkeit garantiert, ist, dass es beim Erkunden dieser nicht optimalen Pfade das Ziel nicht findet und die Suche beendet, bevor es den optimalen Pfad erkundet. Dies liegt daran, dass sich die Kosten / Länge dieser nicht optimalen Pfade summieren, wenn sie auf den ersten Blick großartig erscheinen, und dass der Algorithmus irgendwann zurückkehrt, um den optimalen Pfad zu erkunden. Wenn wir die Kosten für das Ziel überschätzen könnten und dies auf dem optimalen Weg tun würden, könnten wir tatsächlich den nicht optimalen Weg beschreiten und das Ziel finden (was die Suche beendet).

Der wichtige Unterschied zwischen A * und Best-First-Suche besteht darin, dass A * den durch die Schätzfunktion angegebenen Wert kombiniert $e$ mit der Länge des (kürzesten derzeit bekannten) Pfades zum betrachteten Knoten.

Angenommen, Ihr optimaler Weg zum Ziel hat Länge $k$;; dann ist die Schätzung für Ihren Startzustand höchstens$k$und für die $i$-th Knoten entlang des optimalen Pfades, die Schätzung ist höchstens $k-i$. Dies gibt eine Grenze dafür, wie weit der Algorithmus einem falschen Pfad folgen wird$p$;; sobald du mehr genommen hast als$k$ Schritte entlang $p$Das aktuell untersuchte Präfix des optimalen Pfads sieht besser aus $p$ wird aufgegeben.

Im Wesentlichen liegt die A * -Suche zwischen Breadth-First (nicht informiert, garantiert auf dem kürzesten Weg, aber langsam) und Best-First (geleitet von einer Schätzfunktion, möglicherweise schnell, aber sehr abhängig von der Qualität der Schätzungen).