In dieser Geschichte werde ich die beiden häufig verwendeten Algorithmen für die Grundlage der künstlichen Intelligenz und der neuronalen Netze vergleichen, nämlich Depth-First-Search und Breadth-First-Search. Wenn Sie diese beiden Algorithmen noch nicht verstanden haben, schauen Sie in meinen anderen Artikeln nach einer 5-minütigen Anleitung und Sie werden sie verstehen können.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
Erstens sind beide uninformierte Suchalgorithmen, d.h. sie arbeiten mit roher Gewalt und haben keine zusätzlichen Informationen über den Zustand oder den Suchraum, außer wie man den Baum durchquert. Wenn Sie meine früheren Artikel über DFS oder BFS gelesen haben, wissen Sie, dass keiner von ihnen das Gewicht der einzelnen Schritte während des Suchprozesses berücksichtigt.
- Laufzeit: Beide Algorithmen arbeiten in O(n), da sie im schlimmsten Fall jeden Knoten im Suchraum besuchen müssen.
- wenn DFS>BFS: Wenn der gesuchte Knoten sehr tief liegt oder es mehrere Zielknoten gibt, die ziemlich tief liegen, sollte man DFS verwenden. In diesem Fall muss BFS jeden oberen Knoten besuchen, bevor es die tiefen Knoten besucht, was zu viel Zeit in Anspruch nimmt.
- wenn BFS>DFS: BFS kann verwendet werden, um den kürzesten Weg in einem ungewichteten Graphen zu finden, weil wir in BFS einen Knoten mit der minimalen Anzahl von Kanten von einem Quellknoten aus erreichen. Auf der anderen Seite kann es sein, dass wir bei DFS mehr Kanten durchqueren, um einen Zielknoten von einer Quelle aus zu erreichen.
- Suchtyp: Beide sind uninformierte Suche
- Speichervergleich: BFS benötigt mehr Speicher, weil es mehr Backtracking betreiben muss als DFS im Allgemeinen.
- Datenstruktur: DFS verwendet einen Stack, der Knoten von der Wurzel bis zum gesuchten Knoten enthält. BFS verwendet eine Warteschlange, die Knoten an der Spitze der Suche enthält.