Ich habe über DFS und BFS viele Male, aber ich habe diesen Zweifel, der mich seit langem beschäftigt. In vielen Artikeln wird erwähnt, dass DFS in unendlichen Schleifen stecken bleiben kann.
Soweit ich weiß, kann diese Einschränkung leicht entfernt werden, indem die besuchten Knoten im Auge behalten werden. Tatsächlich ist dieser kleine Scheck in allen Büchern, die ich gelesen habe, ein Teil von DFS.
Warum werden 'unendliche Schleifen' als Nachteil von DFS erwähnt? Ist es nur, weil der ursprüngliche DFS-Algorithmus diese Überprüfung für besuchte Knoten nicht hatte? Bitte erläutern.
(1) Bei Graph-Suchalgorithmen [häufig bei AI verwendet] ist der Hauptvorteil von DFS Space Efficiency . Es ist sein Hauptvorteil auf BFS. Wenn Sie jedoch die besuchten Knoten im Auge behalten, verlieren Sie diesen Vorteil , da Sie alle besuchten Knoten im Speicher ablegen müssen. Vergessen Sie nicht, dass die Größe der besuchten Knoten im Laufe der Zeit drastisch ansteigt und bei sehr großen / unendlichen Graphen nicht in den Speicher passt.
(2) Manchmal kann DFS in einem unendlichen Zweig [in unendlichen Graphen] sein. Ein unendlicher Zweig ist ein Zweig, der nicht endet [hat immer "mehr Söhne"], und bringt Sie auch nicht zu Ihrem Zielknoten, so dass Sie für DFS diesen Zweig unendlich erweitern und den guten Zweig "verpassen" können. das führt zum Zielknoten.
Bonus:
Sie können diesen Fehler in DFS überwinden, während Sie mit einer Kombination aus DFS und BFS eine relativ kleine Speichergröße beibehalten: Iterative Deepening DFS
Ein konventioneller DFS-Algorithmus spürt Knoten auf. Ein lokaler Suchalgorithmus spürt keine Zustände auf und verhält sich mit Amnesie. Ich denke also, die Schleife bezieht sich hauptsächlich auf den einen unendlichen Zweig (ein Zweig mit unendlich vielen möglichen Zuständen). In diesem Fall geht das DFS einfach herunter und konzentriert sich auf einen Zweig.
Tags und Links algorithm search depth-first-search breadth-first-search