Was ist der Unterschied zwischen der Graphensuche und der Baumsuchversion in Bezug auf DFS-, A * -Suchen in künstlicher Intelligenz ?

Nach den vorhandenen Antworten zu urteilen, scheint dieses Konzept sehr verwirrend zu sein.

Das Problem ist immer ein Diagramm

Die Unterscheidung zwischen Baumsuche und Diagrammsuche beruht nicht auf der Tatsache, ob das Problemdiagramm ein Baum oder ein allgemeines Diagramm ist. Es wird immer davon ausgegangen, dass es sich um ein allgemeines Diagramm handelt. Die Unterscheidung liegt in dem Durchlaufmuster , das zum Durchsuchen des Diagramms verwendet wird und das grafisch oder baumförmig sein kann.

Wenn Sie sich mit einem baumförmigen Problem befassen , führen beide Algorithmusvarianten zu gleichwertigen Ergebnissen. So können Sie die einfachere Baumsuchvariante auswählen.

Unterschied zwischen Diagramm- und Baumsuche

Ihr grundlegender Algorithmus für die Diagrammsuche sieht ungefähr so ​​aus. Mit einem Startknoten startwerden gerichtete Kanten als successorsund eine goalSpezifikation in der Schleifenbedingung verwendet. openhält die Knoten im Speicher, die derzeit in Betracht gezogen werden, in der offenen Liste . Beachten Sie, dass der folgende Pseudocode nicht in jedem Aspekt korrekt ist (2).

Baumsuche

open <- []
next <- start

while next is not goal {
    add all successors of next to open
    next <- select one node from open
    remove next from open
}

return next

Je nachdem, wie Sie implementieren select from open, erhalten Sie verschiedene Varianten von Suchalgorithmen, z. B. die Tiefensuche (DFS) (Neuestes Element auswählen), die Breitensuche (BFS) (Ältestes Element auswählen) oder die Suche nach einheitlichen Kosten (Element mit den niedrigsten Pfadkosten auswählen) ), die beliebte A-Stern-Suche durch Auswahl des Knotens mit den niedrigsten Kosten plus heuristischem Wert usw.

Der oben angegebene Algorithmus wird tatsächlich als Baumsuche bezeichnet . Es wird mehrmals einen Status des zugrunde liegenden Problemdiagramms aufrufen, wenn im Startstatus mehrere gerichtete Pfade zu diesem Rooting vorhanden sind. Es ist sogar möglich, einen Zustand unendlich oft zu besuchen, wenn er auf einer gerichteten Schleife liegt. Jeder Besuch entspricht jedoch einem anderen Knoten im Baum, der von unserem Suchalgorithmus generiert wird. Diese offensichtliche Ineffizienz wird manchmal gewünscht, wie später erläutert wird.

Grafische Suche

Wie wir gesehen haben, kann die Baumsuche einen Zustand mehrmals besuchen. Und als solches wird es den nach diesem Zustand gefundenen "Unterbaum" mehrmals untersuchen, was teuer sein kann. Die Diagrammsuche behebt dieses Problem, indem alle besuchten Zustände in einer geschlossenen Liste erfasst werden . Wenn ein neu gefundener Nachfolger nextbereits bekannt ist, wird er nicht in die offene Liste eingefügt:

open <- []
closed <- []
next <- start

while next is not goal {
    add next to closed
    add all successors of next to open, which are not in closed 
    remove next from open
    next <- select from open
}

return next

Vergleich

Wir stellen fest, dass die Diagrammsuche mehr Speicher benötigt, da sie alle besuchten Zustände verfolgt. Dies kann durch die kleinere offene Liste ausgeglichen werden, was zu einer verbesserten Sucheffizienz führt.

Optimale Lösungen

Einige Implementierungsmethoden selectkönnen garantieren, dass optimale Lösungen zurückgegeben werden - dh ein kürzester Pfad oder ein Pfad mit minimalen Kosten (für Diagramme mit Kosten, die an Kanten gebunden sind). Dies gilt grundsätzlich immer dann, wenn Knoten in der Reihenfolge steigender Kosten erweitert werden oder wenn die Kosten eine positive Konstante ungleich Null sind. Ein gängiger Algorithmus, der diese Art der Auswahl implementiert, ist die einheitliche Kostensuche oder bei identischen Schrittkosten BFS oder IDDFS . IDDFS vermeidet den aggressiven Speicherverbrauch von BFS und wird im Allgemeinen für die nicht informierte Suche (auch bekannt als Brute Force) empfohlen, wenn die Schrittgröße konstant ist.

EIN*

Auch das (sehr beliebt) A * Baumsuchalgorithmus liefert eine optimale Lösung , wenn sie mit einer verwendeten zulässigen Heuristik . Der A * Graph- Suchalgorithmus übernimmt diese Garantie jedoch nur, wenn er mit einer konsistenten (oder "monotonen") Heuristik verwendet wird (eine stärkere Bedingung als die Zulässigkeit).

(2) Fehler des Pseudocodes

Der Einfachheit halber enthält der dargestellte Code nicht:

• Behandeln Sie fehlgeschlagene Suchvorgänge, dh es funktioniert nur, wenn eine Lösung gefunden werden kann

Ein Baum ist ein Sonderfall eines Diagramms. Was auch immer für allgemeine Diagramme funktioniert, funktioniert für Bäume. Ein Baum ist ein Graph, in dem zwischen jedem Knotenpaar genau ein Pfad liegt. Dies impliziert, dass es keine Zyklen enthält, wie in einer vorherigen Antwort angegeben, aber ein gerichteter Graph ohne Zyklen (ein DAG, gerichteter azyklischer Graph) ist nicht notwendigerweise ein Baum.

Wenn Sie jedoch wissen, dass Ihr Diagramm einige Einschränkungen aufweist, z. B. dass es sich um einen Baum oder eine DAG handelt, können Sie normalerweise einen effizienteren Suchalgorithmus finden als für ein uneingeschränktes Diagramm. Zum Beispiel ist es wahrscheinlich nicht sehr sinnvoll, A * oder sein nicht heuristisches Gegenstück „Dijkstra-Algorithmus“ in einem Baum zu verwenden (wo ohnehin nur ein Pfad zur Auswahl steht, den Sie über DFS oder BFS finden können) oder auf einer DAG (wo ein optimaler Pfad gefunden werden kann, indem Eckpunkte in der Reihenfolge betrachtet werden, die durch topologische Sortierung erhalten wird).

Für gerichtete und ungerichtete Diagramme ist ein ungerichteter Graph ein Sonderfall eines gerichteten Graphen, nämlich der Fall, der der Regel folgt: „Wenn es eine Kante (Verknüpfung, Übergang) von u nach v gibt, gibt es auch eine Kante von v nach u .

Update : Beachten Sie, dass dies nicht die Antwort ist , wenn Sie sich eher für das Durchlaufmuster der Suche als für die Struktur des Diagramms selbst interessieren . Siehe z. B. die Antwort von @ ziggystar.

Der einzige Unterschied zwischen einem Diagramm und einem Baum ist der Zyklus . Ein Graph kann Zyklen enthalten, ein Baum nicht. Wenn Sie also einen Suchalgorithmus in einem Baum implementieren, müssen Sie die Existenz von Zyklen nicht berücksichtigen, aber wenn Sie mit einem beliebigen Diagramm arbeiten, müssen Sie diese berücksichtigen. Wenn Sie die Zyklen nicht handhaben, fällt der Algorithmus möglicherweise in eine Endlosschleife oder eine Endlosrekursion.

Ein weiterer zu berücksichtigender Punkt sind die Richtungseigenschaften des Diagramms, mit dem Sie sich befassen. In den meisten Fällen handelt es sich um Bäume, die Eltern-Kind-Beziehungen an jeder Kante darstellen. Ein DAG (gerichteter azyklischer Graph) zeigt ebenfalls ähnliche Eigenschaften. Bidirektionale Graphen sind jedoch unterschiedlich. Jede Kante in einem bidirektionalen Diagramm repräsentiert zwei Nachbarn. Daher sollten sich die algorithmischen Ansätze für diese beiden Diagrammtypen etwas unterscheiden.

GRAFIK GEGEN BAUM

• Diagramme haben Zyklen
• Bäume haben keine Zyklen "Stellen Sie sich zum Beispiel einen Baum in Ihrem Kopf vor, Zweige haben keine direkten Verbindungen zur Wurzel, aber Zweige haben Verbindungen zu anderen Zweigen nach oben."

Aber im Falle von AI Graph-Suche vs Baum-Suche

Die Diagrammsuche hat eine gute Eigenschaft: Wenn der Algorithmus einen neuen Knoten untersucht und ihn als besucht markiert, "unabhängig vom verwendeten Algorithmus", untersucht der Algorithmus normalerweise alle anderen Knoten, die vom aktuellen Knoten aus erreichbar sind.

Betrachten Sie beispielsweise das folgende Diagramm mit 3 Eckpunkten AB und C und die folgenden Kanten

AB, BC und CA, Nun, es gibt einen Zyklus von C nach A,

Und wenn DFS ausgehend von A, A einen neuen Zustand B erzeugt, erzeugt B einen neuen Zustand C, aber wenn C untersucht wird, versucht der Algorithmus, einen neuen Zustand A zu erzeugen, aber A wird bereits besucht, so dass er ignoriert wird. Cool!

Aber was ist mit Bäumen? Nun, Bäume Algorithmus markiert den besuchten Knoten nicht als besucht, aber Bäume haben keine Zyklen, wie würde es in einer Endlosschleife kommen?

Betrachten Sie diesen Baum mit 3 Eckpunkten und die folgenden Kanten

A - B - C wurzelt bei A nach unten. Nehmen wir an, wir verwenden den DFS-Algorithmus

A erzeugt einen neuen Zustand B, B erzeugt zwei Zustände A und C, da Bäume nicht "Markieren Sie einen besuchten Knoten, wenn er erkundet wird" haben. Daher wird der DFS-Algorithmus möglicherweise A erneut untersuchen und somit einen neuen Zustand B erzeugen Wir geraten in eine Endlosschleife.

Aber haben Sie etwas bemerkt, wir arbeiten an ungerichteten Kanten, dh es besteht eine Verbindung zwischen AB und BA. Dies ist natürlich kein Zyklus, da der Zyklus impliziert, dass die Eckpunkte> = 3 sein müssen und alle Eckpunkte mit Ausnahme des ersten und des letzten Knotens unterschiedlich sind.

ST A-> B-> A-> B-> A es ist kein Zyklus, weil es die Zykluseigenschaft verletzt> = 3. Aber tatsächlich ist A-> B-> C-> A ein Zyklus> = 3 verschiedene Knoten. Der erste und der letzte Knoten sind identisch.

Betrachten Sie noch einmal die Baumkanten A-> B-> C-> B-> A, natürlich ist es kein Zyklus, da es zwei Bs gibt, was bedeutet, dass nicht alle Knoten unterschiedlich sind.

Zuletzt könnten Sie einen Baumsuchalgorithmus implementieren, um zu verhindern, dass derselbe Knoten zweimal erkundet wird. Das hat aber Konsequenzen.

In einfachen Worten, Baum enthält keine Zyklen und wo als Grafik kann. Wenn wir also suchen, sollten wir Zyklen in Diagrammen vermeiden, damit wir nicht in Endlosschleifen geraten.

Ein weiterer Aspekt ist, dass der Baum normalerweise eine topologische Sortierung oder eine Eigenschaft wie den binären Suchbaum aufweist, die die Suche im Vergleich zu Diagrammen so schnell und einfach macht.