În această poveste, voi compara cei doi algoritmi utilizați în mod obișnuit pentru fundamentarea inteligenței artificiale și a rețelelor neuronale, și anume deep-first-search și breadth-first-search. Dacă nu ați înțeles acești doi algoritmi, consultați celelalte articole ale mele pentru o instruire de 5 minute și veți putea să îi înțelegeți.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
În primul rând, ambii sunt algoritmi de căutare neinformată, ceea ce înseamnă că operează în forță brută-way și nu au informații suplimentare despre starea sau spațiul de căutare în afară de modul de parcurgere a arborelui. Dacă ați citit articolele mele anterioare despre DFS sau BFS, știți că niciunul dintre ei nu se uită la greutatea fiecărui pas în timpul procesului de căutare.
- Runtime: Ambii algoritmi operează în O(n) deoarece, în cel mai rău caz, vor trebui să viziteze fiecare nod din spațiul de căutare.
- când DFS>BFS: Dacă nodul pe care îl căutăm este foarte adânc sau dacă există mai multe noduri de obiectiv care sunt destul de adânci, ar trebui să folosim DFS. În acest caz, BFS trebuie să viziteze fiecare nod de mai sus înainte de a vizita nodurile de adâncime, ceea ce necesită prea mult timp.
- când BFS>DFS: BFS poate fi utilizat pentru a găsi calea cea mai scurtă cu o singură sursă într-un graf neponderat, deoarece în BFS, ajungem la un vertex cu un număr minim de muchii de la un vertex sursă. Pe de altă parte, în DFS, este posibil să parcurgem mai multe muchii pentru a ajunge la un vertex de destinație de la o sursă.
- tip de căutare: ambele sunt căutări neinformate
- comparare în memorie: BFS va ocupa mai multă memorie deoarece trebuie să parcurgă mai mult traseul înapoi decât o va face DFS în general.
- structura datelor: DFS utilizează o stivă, care conține noduri de la rădăcină până la nodul căutat. BFS utilizează o coadă, care conține nodurile din fruntea căutării.
.