W tej historii, będę porównywał dwa powszechnie używane algorytmy dla podstaw sztucznej inteligencji i sieci neuronowych, a mianowicie depth-first-search i breadth-first-search. Jeśli nie rozumiesz tych dwóch algorytmów, sprawdź moje inne artykuły dla 5 minutowej instrukcji i będziesz w stanie je zrozumieć.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
Po pierwsze, oba są algorytmami wyszukiwania bez informacji, co oznacza, że działają w sposób brute force-way i nie mają dodatkowych informacji o stanie lub przestrzeni wyszukiwania poza tym, jak przemierzać drzewo. Jeśli czytałeś moje poprzednie artykuły na temat DFS lub BFS, wiesz, że żaden z nich nie będzie patrzył na wagę każdego kroku podczas procesu wyszukiwania.
- Runtime: Oba algorytmy działają w O(n), ponieważ w najgorszym przypadku będą musiały odwiedzić każdy węzeł w przestrzeni wyszukiwania.
- gdy DFS>BFS: Jeśli węzeł, którego szukamy, jest bardzo głęboki lub istnieje kilka węzłów celu, które są dość głęboko, powinniśmy użyć DFS. W tym przypadku, BFS musi odwiedzić każdy węzeł powyżej przed odwiedzeniem głębokich węzłów, co zajmuje zbyt dużo czasu.
- gdy BFS>DFS: BFS może być użyty do znalezienia jednoźródłowej najkrótszej ścieżki w grafie nieważonym, ponieważ w BFS, osiągamy wierzchołek z minimalną liczbą krawędzi od wierzchołka źródłowego. Z drugiej strony, w DFS, możemy przejść przez więcej krawędzi, aby dotrzeć do wierzchołka docelowego ze źródła.
- typ wyszukiwania: oba są nieuświadomionym wyszukiwaniem
- porównanie pamięci: BFS zajmie więcej pamięci, ponieważ musi bardziej backtrack niż DFS w ogóle.
- struktura danych: DFS używa stosu, który zawiera węzły od korzenia do przeszukiwanego węzła. BFS używa kolejki, która zawiera węzły z przodu wyszukiwania.
.