I den här artikeln kommer jag att jämföra de två vanligaste algoritmerna som ligger till grund för artificiell intelligens och neurala nätverk, nämligen depth-first-search och breadth-first-search. Om du inte har förstått dessa två algoritmer, kolla mina andra artiklar för en 5 minuters instruktion så kommer du att kunna förstå dem.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
För det första är de båda algoritmerna oinformerade sökalgoritmer, vilket innebär att de arbetar på ett brute force-manér och inte har någon ytterligare information om tillståndet eller sökutrymmet förutom hur trädet ska korsas. Om du har läst mina tidigare artiklar om DFS eller BFS vet du att ingen av dem tittar på vikten av varje steg under sökprocessen.
- Runtime: Båda algoritmerna arbetar på O(n) eftersom de i värsta fall måste besöka varje nod i sökutrymmet.
- när DFS>BFS: Om noden vi letar efter är mycket djup eller om det finns flera målnoder som ligger ganska djupt bör vi använda DFS. I detta fall måste BFS besöka alla noder ovanför innan man besöker de djupa noderna, vilket tar för lång tid.
- när BFS>DFS: BFS kan användas för att hitta den kortaste vägen med en enda källa i en oviktad graf, eftersom vi i BFS når en topp med minsta möjliga antal kanter från en källpunkt. Å andra sidan kan vi i DFS gå igenom fler kanter för att nå en målpunkt från en källa.
- Söktyp: Båda är oinformerade sökningar
- Minnesjämförelse: Båda är oinformerade sökningar: BFS kommer att ta mer minne i anspråk eftersom den måste backa mer än vad DFS kommer att göra i allmänhet.
- Datastruktur: DFS använder en stapel som innehåller noder från roten till den sökta noden. BFS använder en kö, som innehåller noder längst fram i sökningen.