Korrekte Formulierung der A * -Algorithmus

Question

Ich betrachte Definitionen des A * Wegfindungsalgorithmus, und es scheint, an verschiedenen Orten etwas anders definiert werden.

Der Unterschied liegt in der Aktion ausgeführt wird, wenn durch die Nachfolger eines Knotens gehen, und festgestellt, dass ein Nachfolger auf der geschlossenen Liste ist.

• Ein Ansatz (von Wikipedia vorgeschlagen und hier und

  War es hilfreich?

  einreichen

  Lösung

  Der erste Ansatz ist optimal nur dann, wenn der optimale Weg zu jedem wiederholten Zustand ist immer die erste Folge zu leisten. Diese Eigenschaft gilt, wenn die heuristische Funktion die Eigenschaft Konsistenz (auch als monoticity ) hat. Eine heuristische Funktion ist konsistent, wenn für jeden Knoten n und jeder Nachfolger n' von n, die geschätzten Kosten für das Ziel von n erreichen nicht größer als der Schritt Kosten ist immer von n' plus der geschätzten Kosten für das Erreichen des Ziels von n n .

  Der zweite Ansatz ist optimal, wenn die heuristische Funktion nur zulässig ist, das heißt, es überschätzt nie die Kosten um das Ziel zu erreichen.

  Jede konsistente heuristische Funktion ist ebenfalls zulässig. Obwohl Konsistenz eine strengere Anforderung als Zulässigkeit ist, muss man ganz hart arbeiten, heuristische Funktionen zu brauen, die zulässig sind, aber nicht konsistent.

  So, obwohl der zweite Ansatz ist allgemeiner, da es mit einer streng größeren Teilmenge von heuristischen Funktionen arbeitet, der erste Ansatz ist in der Praxis in der Regel ausreichend.

  Referenz: der Unterabschnitt A * -Suche: Die Minimierung der geschätzten Gesamtkosten der Lösung in Abschnitt 4.1 Informed (Heuristic) Suchstrategien des Buches Künstliche Intelligenz: A moderner Ansatz .

Answer 1

Der erste Ansatz ist optimal nur dann, wenn der optimale Weg zu jedem wiederholten Zustand ist immer die erste Folge zu leisten. Diese Eigenschaft gilt, wenn die heuristische Funktion die Eigenschaft Konsistenz (auch als monoticity ) hat. Eine heuristische Funktion ist konsistent, wenn für jeden Knoten n und jeder Nachfolger n' von n, die geschätzten Kosten für das Ziel von n erreichen nicht größer als der Schritt Kosten ist immer von n' plus der geschätzten Kosten für das Erreichen des Ziels von n n .

Der zweite Ansatz ist optimal, wenn die heuristische Funktion nur zulässig ist, das heißt, es überschätzt nie die Kosten um das Ziel zu erreichen.

Jede konsistente heuristische Funktion ist ebenfalls zulässig. Obwohl Konsistenz eine strengere Anforderung als Zulässigkeit ist, muss man ganz hart arbeiten, heuristische Funktionen zu brauen, die zulässig sind, aber nicht konsistent.

So, obwohl der zweite Ansatz ist allgemeiner, da es mit einer streng größeren Teilmenge von heuristischen Funktionen arbeitet, der erste Ansatz ist in der Praxis in der Regel ausreichend.

Referenz: der Unterabschnitt A * -Suche: Die Minimierung der geschätzten Gesamtkosten der Lösung in Abschnitt 4.1 Informed (Heuristic) Suchstrategien des Buches Künstliche Intelligenz: A moderner Ansatz .