Wie implementiert man einen AO * -Algorithmus?

16

Mir ist aufgefallen, dass bei der Implementierung von Suchalgorithmen unterschiedliche Datenstrukturen verwendet werden. Beispielsweise verwenden wir Warteschlangen zur Implementierung der Breitensuche, Stapel zur Implementierung der Tiefensuche und Min-Heaps zur Implementierung des A * -Algorithmus . In diesen Fällen muss der Suchbaum nicht explizit erstellt werden.

Ich kann aber keine einfache Datenstruktur finden, um den Suchprozess des AO * -Algorithmus zu simulieren . Ich würde gerne wissen, ob die explizite Erstellung des Suchbaums die einzige Möglichkeit ist, den AO * -Algorithmus zu implementieren. Kann mir jemand eine effiziente Implementierung bieten?

algorithms graphs data-structures search-algorithms Zhang
quelle
3
Herzlich willkommen! Bitte denken Sie daran, Verweise auf nicht standardmäßiges Material beizufügen, das Sie verwenden. Da AO * keinen Wikipedia-Artikel hat, ist ein Link sicherlich in Ordnung. Ich hoffe, ich habe eine gute gefunden, bitte überprüfen Sie.
Raphael
1
Ist es nicht nur ein Graph (mit einer Funktion, die es einem erlaubt, zum "nächsten" Knoten zu gelangen)?
Soandos
Es wäre hilfreich, wenn jemand nur skizzieren würde, wie sich AO * vom A * -Algorithmus unterscheidet. Konnte nicht ganz aus dem Link herausfinden. Was die Implementierung angeht, scheint jede Struktur für Bäume vernünftig zu sein. Sie überquert einen Baum, oder?
vzn

Antworten:

1

In Bezug auf diesen Artikel müssen Sie bei jeder Erweiterung eines Knotens im AO * -Algorithmus rückwärts vorgehen, um die geschätzten Kosten aller Vorgänger zu aktualisieren.

Wenn Sie eine lineare Datenstruktur verwenden, um die Knoten aufzunehmen, müssen Sie die Datenelemente nacheinander durchlaufen, und es kann nur ein Datenelement direkt erfasst werden (Stapel, Warteschlange, Prioritätswarteschlange…).

In AO * durchläuft der Algorithmus jedes Mal, wenn ein Knoten auf der Grundlage seiner geschätzten Kosten zur Erweiterung herangezogen wird, alle Knoten, die seine Vorgänger sind (um ihre geschätzten Kosten zu aktualisieren). Das bedeutet, dass Sie das Element manchmal basierend auf den geschätzten Kosten und manchmal basierend auf dem Nachfolger nehmen sollten. Es gibt keine Sequenzreihenfolge, die im allgemeinen Fall beide Bedingungen erfüllen kann. Möglicherweise gibt es eine Möglichkeit, "verschachtelte" lineare Datenstrukturen zu verwenden, diese sollten jedoch nur eine Baumstruktur imitieren, und es ist besser, stattdessen den Suchbaum zu erstellen.

Anton
quelle
0

Ich gehe nur von der Beschreibung ab, mit der Sie verlinkt haben, aber was ist mit einer BST? Möglicherweise können Sie es so konstruieren, dass ungelöste Knoten ausgeglichen werden. Dies könnte Ihnen Zeit bei Schritt 2 sparen und dazu beitragen, die Gesamtzeit in Abhängigkeit von der Anzahl der Durchquerungen gering zu halten. Wenn Sie Ihren Baum nach ungelösten Knoten ausbalancieren / sortieren, sind Sie wahrscheinlich besser als eine vereinfachte Datenstruktur, die möglicherweise die logarithmische Zeit einhält.

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Univ426
quelle
2
Und kannst du das tun?
Raphael
Es ist mir nicht so klar, wie die BST verwendet werden würde, da BSTs einen numerischen Index für jeden Knoten haben und verwendet werden, um sie zu platzieren. Was ist der verwendete numerische Index?
vzn