Am besten ist die erste Suche ein Suchalgorithmus, der einen Graphen durch die Erweiterung des viel versprechendsten gemäß einer angegebenen Regel gewählten Knotens erforscht.

Judea Pearl hat am besten die erste Suche als das Schätzen der Versprechung des Knotens n nach einer "heuristischen Einschätzungsfunktion beschrieben, die im Allgemeinen von der Beschreibung von n, der Beschreibung der Absicht, die Information abhängen kann, die durch die Suche bis zu diesem Punkt gesammelt ist, und auf irgendwelchen Extrakenntnissen über das Problem-Gebiet am wichtigsten ist."

Einige Autoren haben "am besten die erste Suche" verwendet, um sich spezifisch auf eine Suche mit einem heuristischen zu beziehen, der versucht vorauszusagen, wie nahe das Ende eines Pfads zu einer Lösung ist, so dass Pfade, die, wie man beurteilt, an einer Lösung näher sind, zuerst erweitert werden. Dieser spezifische Typ der Suche wird die gierige beste erste Suche genannt.

Die effiziente Auswahl am aktuellen besten Kandidaten für die Erweiterung wird normalerweise mit einer Vorzugswarteschlange durchgeführt.

Der A* Suchalgorithmus ist ein Beispiel der besten ersten Suche. Am besten werden die ersten Algorithmen häufig für die Pfad-Entdeckung in der kombinatorischen Suche verwendet.

Algorithmus

ÖFFNEN SIE SICH = [anfänglicher Staat]

während OFFEN, ist nicht leerer

tun Sie

1. Entfernen Sie den besten Knoten vom OFFENEN, nennen Sie ihn n.

2. Wenn n der Absicht-Staat, backtrace Pfad zu n (durch registrierte Eltern) und Rückpfad ist.

3. Schaffen Sie die Nachfolger von n.

4. Bewerten Sie jeden Nachfolger, fügen Sie es hinzu, um seinen Elternteil ZU ÖFFNEN, und zu registrieren.

getaner

</Quelle>

Bemerken Sie, dass diese Version des Algorithmus nicht abgeschlossen ist, d. h. es keinen möglichen Pfad zwischen zwei Knoten immer findet, selbst wenn es dasjenige gibt. Zum Beispiel bleibt es in einer Schleife stecken, wenn es in einem toten Punkt ankommt, der ein Knoten mit dem einzigen Nachfolger ist, der sein Elternteil ist. Es würde dann seinem Elternteil zurückgehen, fügen Sie den Sackgasse-Nachfolger der Liste wieder und so weiter hinzu.

Die folgende Version erweitert den Algorithmus, um eine zusätzliche Liste zu verwenden, alle Knoten enthaltend, die bewertet worden sind und auf wieder nicht geschaut werden. Da das jeden Knoten vermeiden wird, der zweimal wird bewertet, ist es unendlichen Schleifen nicht unterworfen.

ÖFFNEN SIE SICH = [anfänglicher Staat]

GESCHLOSSEN = []

während OFFEN, ist nicht leerertun Sie

1. Entfernen Sie den besten Knoten vom OFFENEN, nennen Sie ihn n, fügen Sie es zum GESCHLOSSENEN hinzu.

2. Wenn n der Absicht-Staat, backtrace Pfad zu n (durch registrierte Eltern) und Rückpfad ist. 3. Schaffen Sie die Nachfolger von n.

4. Weil jeder Nachfolger tut:

a. Wenn es nicht im GESCHLOSSENEN ist: Bewerten Sie es, fügen Sie es hinzu, um seinen Elternteil ZU ÖFFNEN, und zu registrieren.

b. Sonst: Ändern Sie registrierten Elternteil, wenn dieser neue Pfad besser ist als vorheriger.

getaner</Quelle>

Bemerken Sie auch, dass der gegebene Pseudocode von beiden Versionen gerade endet, wenn kein Pfad gefunden wird. Eine wirkliche Durchführung würde natürlich das spezielle Berühren dieses Falls verlangen.

Gieriger BFS

Mit einem gierigen Algorithmus, breiten Sie den ersten Nachfolger des Elternteils aus. Nachdem ein Nachfolger erzeugt wird:

1. Wenn der heuristische Nachfolger besser ist als sein Elternteil, wird der Nachfolger an der Front der Warteschlange (mit dem Elternteil wieder eingesetzt direkt dahinter), und die Schleife-Wiederanfänge gesetzt.
2. Sonst wird der Nachfolger in die Warteschlange (in einer Position eingefügt, die durch seinen heuristischen Wert bestimmt ist). Das Verfahren wird die restlichen Nachfolger (wenn irgendwelcher) des Elternteils bewerten.

Siehe auch

• Balken-Suche
• A* Suchalgorithmus
• Der Algorithmus von Dijkstra

Links

http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html