Heuristische Suche und A*

Die heuristische Suche verwendet eine problemspezifische Schätzung der verbleibenden Kosten bis zu einem Ziel, um zu steuern, welche Zustände zuerst untersucht werden sollen; A* ist ihr kanonischer Algorithmus, der Zustände in der Reihenfolge der Summe aus bisherigen Kosten und geschätzten Restkosten erweitert.

Definition

Heuristische Suche ist eine informierte Suche, die die Grenze unter Verwendung einer Bewertungsfunktion ordnet, die die bekannten Kosten vom Start mit einer heuristischen Schätzung der verbleibenden Kosten kombiniert; A* verwendet f(n) = g(n) + h(n) und ist optimal, wenn h zulässig ist.

Scope

Dieses Thema behandelt informierte (heuristische) Suchstrategien, die sich auf die Best-First-Suche und den A*-Algorithmus konzentrieren, einschließlich des Entwurfs und der Eigenschaften heuristischer Funktionen (Zulässigkeit, Konsistenz/Monotonie), der Optimalitäts- und Effizienzgarantien, die diese Eigenschaften bieten, und speicherbegrenzter Varianten wie der iterativen Vertiefung A* (IDA*). Es wird behandelt, wie Heuristiken konstruiert werden (relaxierte Probleme, Musterdatenbanken) und wie sie Genauigkeit gegen Rechenaufwand abwägen. Das Lernen von Heuristiken aus Daten gehört zum Teilgebiet des maschinellen Lernens.

Core questions

• Was macht eine Heuristik zulässig, und warum garantiert die Zulässigkeit die A*-Optimalität?
• Wie stärkt Konsistenz (Monotonie) die Garantien und verhindert die erneute Expansion von Knoten?
• Wie werden gute Heuristiken entworfen, zum Beispiel aus relaxierten Versionen des Problems?
• Wie bewahren speicherbegrenzte Varianten wie IDA* die Optimalität bei begrenztem Speicherplatz?

Key concepts

• Bewertungsfunktion f = g + h
• zulässige Heuristik
• konsistente (monotone) Heuristik
• gierige Best-First-Suche
• A*-Suche
• iterative Vertiefung A* (IDA*)
• heuristische Dominanz
• relaxiertes Problem und Musterdatenbanken

Key theories

A*-Optimalität unter zulässigen Heuristiken

Wenn die Heuristik h die wahren verbleibenden Kosten niemals überschätzt, erweitert A* Knoten durch Erhöhung von f = g + h und liefert garantiert einen Pfad mit den geringsten Kosten; unter Algorithmen, die dieselben heuristischen Informationen verwenden, ist A* optimal effizient.

Heuristisches Design durch Relaxation

Zulässige Heuristiken können systematisch abgeleitet werden, indem eine relaxierte Version des Problems (eine mit weniger Einschränkungen für Aktionen) gelöst wird, da die exakten Kosten eines einfacheren Problems eine untere Schranke für das Original sind; dominierende (informiertere) Heuristiken erweitern weniger Knoten.

Speicherbegrenzte heuristische Suche

Die iterative Vertiefung A* führt aufeinanderfolgende Tiefensuche durch, die durch einen ansteigenden f-Kosten-Schwellenwert begrenzt ist, wodurch eine A*-ähnliche Optimalität mit linearem Speicherplatz in der Lösungstiefe erreicht wird.

Clinical relevance

Die heuristische Suche treibt die Routenfindung in Karten und Spielen, die Bewegungsplanung in der Robotik und die Suchmaschinen in automatisierten Planern und Rätsellösern an; die praktische Kunst des heuristischen Designs bestimmt direkt, ob große Probleme in akzeptabler Zeit lösbar sind.

History

Der A*-Algorithmus wurde von Hart, Nilsson und Raphael (1968) eingeführt und gab der heuristischen Suche eine formale Optimalitätsbasis. Pearls Monographie Heuristics von 1984 lieferte die definitive theoretische Behandlung, und Korfs IDA* von 1985 befasste sich mit den Speicherkosten von A*. Diese Ergebnisse bleiben Kernmaterial in der KI-Ausbildung.

Key figures

• Peter E. Hart
• Nils J. Nilsson
• Bertram Raphael
• Judea Pearl
• Richard E. Korf

Seminal works

• hart1968
• pearl1984
• korf1985

Frequently asked questions

Was ist eine zulässige Heuristik?

Eine Heuristik ist zulässig, wenn sie die wahren Kosten, um das Ziel von einem beliebigen Zustand aus zu erreichen, niemals überschätzt. Zulässigkeit ist die Bedingung, unter der A* garantiert eine optimale (kostengünstigste) Lösung findet.

Was ist der Unterschied zwischen gieriger Best-First-Suche und A*?

Die gierige Best-First-Suche erweitert den Zustand, der dem Ziel nach der Heuristik allein (h) am nächsten erscheint, was schnell ist, aber weit von optimal sein kann. A* addiert die bisher angefallenen tatsächlichen Kosten (g) und erweitert nach f = g + h, was die Optimalität bewahrt, wenn die Heuristik zulässig ist.