In questa storia, confronterò i due algoritmi comunemente usati per la fondazione dell’intelligenza artificiale e delle reti neurali, cioè depth-first-search e breadth-first-search. Se non avete capito questi due algoritmi, controllate i miei altri articoli per un’istruzione di 5 minuti e sarete in grado di capirli.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
In primo luogo, sono entrambi algoritmi di ricerca disinformati, cioè operano in modo brute force e non hanno informazioni aggiuntive sullo stato o sullo spazio di ricerca oltre a come attraversare l’albero. Se avete letto i miei precedenti articoli su DFS o BFS, sapete che nessuno di loro guarderà il peso di ogni passo durante il processo di ricerca.
- Runtime: Entrambi gli algoritmi operano in O(n) poiché, nel caso peggiore, dovranno visitare ogni nodo nello spazio di ricerca.
- quando DFS>BFS: Se il nodo che stiamo cercando è molto profondo o ci sono diversi nodi obiettivo che sono piuttosto in profondità, dovremmo usare DFS. In questo caso, BFS deve visitare ogni nodo superiore prima di visitare i nodi profondi, il che richiede troppo tempo.
- quando BFS>DFS: BFS può essere usato per trovare il percorso più breve di una singola fonte in un grafico non pesato, perché in BFS, raggiungiamo un vertice con il minimo numero di bordi da un vertice sorgente. D’altra parte, in DFS, potremmo attraversare più bordi per raggiungere un vertice di destinazione da una fonte.
- tipo di ricerca: entrambi sono ricerca non informata
- confronto di memoria: BFS prenderà più memoria perché deve fare più backtracking rispetto a DFS in generale.
- struttura dei dati: DFS usa una pila, che contiene i nodi dalla radice al nodo da cercare. BFS usa una coda, che contiene i nodi in testa alla ricerca.
.