Was ist der Unterschied zwischen Baumsuche und Diagrammsuche?

12

Ich habe an verschiedenen Stellen verschiedene Antworten auf diese Frage gelesen, aber mir fehlt noch etwas.

Was ich verstanden habe ist, dass eine Diagrammsuche eine geschlossene Liste mit allen erweiterten Knoten enthält, damit sie nicht erneut untersucht werden. Wenn Sie jedoch die Breitensuche oder die Suche nach einheitlichen Kosten in einem Suchbaum anwenden, tun Sie dasselbe. Sie müssen die erweiterten Knoten im Speicher behalten.

xava
quelle

Antworten:

7

Dieses Konzept ist immer sehr verwirrend, da die Benennung irreführend ist, da sowohl die Baum- als auch die Diagrammsuche einen Baum (aus dem Sie einen Pfad ableiten können) erzeugen, während Sie den Suchraum erkunden, der normalerweise als Diagramm dargestellt wird .

Unterschiede

Erstens müssen wir verstehen, dass das zugrunde liegende Problem (oder der Suchraum) fast immer als Diagramm dargestellt wird (obwohl das zugrunde liegende Diagramm möglicherweise keine Zyklen enthält, sodass es möglicherweise einen Baum darstellt). Der Unterschied besteht also nicht darin, ob das Problem ein Baum (eine spezielle Art von Grafik) oder eine allgemeine Grafik ist!

Die Unterscheidung besteht stattdessen darin, wie wir den Suchraum (als Grafik dargestellt) durchlaufen, um nach unserem Zielstatus zu suchen, und ob wir eine zusätzliche Liste (als geschlossene Liste bezeichnet ) verwenden oder nicht.

Die grundlegenden Unterschiede sind also

  1. Bei einer Diagrammsuche verwenden wir eine Liste, die als geschlossene Liste (auch als erforschte Menge bezeichnet ) bezeichnet wird, um die bereits besuchten und erweiterten Knoten zu verfolgen, damit sie nicht erneut besucht und erweitert werden.

  2. Im Falle eines Baumes suchen, können wir nicht halten diese geschlossene Liste. Folglich kann derselbe Knoten mehrmals (oder sogar unendlich oft) besucht werden, was bedeutet, dass der erzeugte Baum (durch die Baumsuche) denselben Knoten mehrmals enthalten kann.

Vorteile und Nachteile

Der Vorteil der Diagrammsuche besteht natürlich darin, dass wir die Suche nach einem Knoten nie wieder durchsuchen, wenn wir ihn beenden. Andererseits kann die Baumsuche denselben Knoten mehrmals besuchen.

Der Nachteil der Diagrammsuche besteht darin, dass sie mehr Speicher benötigt (den wir möglicherweise haben oder nicht) als die Baumsuche. Dies ist wichtig, da die Diagrammsuche im schlimmsten Fall einen exponentiellen Speicherbedarf hat, was sie ohne eine wirklich gute Suchheuristik oder ein äußerst einfaches Problem unpraktisch macht.

Es gibt also einen Kompromiss zwischen Raum und Zeit, wenn die Diagrammsuche verwendet wird, im Gegensatz zur Baumsuche (oder umgekehrt).

Fazit

Der Unterschied zwischen Baumsuche und Diagrammsuche besteht also nicht darin, dass die Baumsuche bei Bäumen funktioniert, während die Diagrammsuche bei Diagrammen funktioniert! Beide können an Bäumen oder Grafiken arbeiten (aber da Grafiken eine Verallgemeinerung von Bäumen sind, können wir einfach sagen, dass beide an Grafiken arbeiten, entweder Bäume oder nicht) und beide erzeugen einen Baum!

Anmerkungen

Die oben angegebenen Definitionen für Baumsuche und Diagrammsuche basieren auf den Definitionen in Abschnitt 3.3 (Seite 77) des Buches Künstliche Intelligenz: Ein moderner Ansatz (3. Auflage) von Stuart J. Russell und Peter Norvig -facto Standardbuch in künstlicher Intelligenz, daher sind diese Definitionen im Kontext der künstlichen Intelligenz anwendbar (was auch der Kontext dieser Site ist)!

Beachten Sie jedoch, dass gelegentlich der Begriff Baumsuche verwendet werden kann, um sich auf eine Baumdurchquerung zu beziehen , die verwendet wird, um auf eine Suche in einem Suchbaum (z. B. einem binären Suchbaum oder einem rot-schwarzen Baum) zu verweisen Ein Baum (dh ein Graph ohne Zyklen), der eine bestimmte Reihenfolge seiner Elemente beibehält. Dies ist ein weiterer Grund für die unterschiedliche Definition einer Baumsuche und für die Annahme, dass eine Baumsuche nur für Bäume funktioniert.

Amrinder Arora
quelle
Mein Verständnis von Baum ist, dass Bäume nicht nur eine Form eines gerichteten Graphen sind, sondern die Knoten BESTELLT sind, wodurch der Baum von einem Graphen einzigartig wird. Da ein Baum bestellt wird, gibt es keine Schleifen. Daher sollte ein Knoten niemals als mehrere verschiedene Knoten des Baums angezeigt werden, es sei denn, der Implementierer hat etwas sehr Falsches getan, da das Verfolgen der Liste der besuchten Knoten als Teil von Baumdurchlaufalgorithmen implizit ist.
Dunk
@Dunk Was meinst du mit "ein Baum ist bestellt"? Nicht bei allen Bäumen müssen die Elemente geordnet sein. Es gibt Bäume wie rot-schwarze Bäume (oder im Allgemeinen binäre Suchbäume), die eine bestimmte Reihenfolge ihrer gespeicherten Elemente beibehalten, aber nicht alle Bäume behalten eine bestimmte Reihenfolge ihrer Elemente bei. Ein Baum hat also keine Schleifen, nicht weil er geordnet ist, sondern weil es keine Zyklen (der Form A -> B -> A) gibt.
nbro
@Dunk In einem Suchbaum werden Knoten geordnet, aber nicht in Bäumen im Allgemeinen, außer im Sinne der Tiefe. Die Baumsuche ist jedoch keine "Suche nach Bäumen", sondern eine bestimmte Familie von Suchalgorithmen, die in der KI verwendet werden und die garantiert nur bei baumstrukturierten Problemen funktionieren, obwohl sie möglicherweise auf andere Probleme angewendet werden (wo sie können oder nicht). Scheitern).
John Doucette