V tomto článku budu porovnávat dva běžně používané algoritmy pro založení umělé inteligence a neuronových sítí, a to hloubkové vyhledávání a široké vyhledávání. Pokud jste těmto dvěma algoritmům nerozuměli, podívejte se do mých dalších článků na pětiminutovou instruktáž a budete je moci pochopit.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
Za prvé, oba jsou neinformované vyhledávací algoritmy, což znamená, že pracují způsobem hrubé síly a nemají další informace o stavu nebo prohledávaném prostoru kromě toho, jak procházet strom. Pokud jste četli mé předchozí články o DFS nebo BFS, víte, že žádný z nich se během prohledávání nezabývá váhou jednotlivých kroků.
- Runtime: Oba algoritmy pracují v čase O(n), protože v nejhorším případě budou muset navštívit každý uzel v prohledávaném prostoru.
- kdy DFS>BFS: Pokud je hledaný uzel velmi hluboko nebo je několik cílových uzlů, které jsou dost hluboko, měli bychom použít DFS. V tomto případě musí BFS před návštěvou hlubokých uzlů navštívit všechny uzly nad nimi, což zabere příliš mnoho času.
- když BFS>DFS: BFS lze použít k nalezení jediné zdrojové nejkratší cesty v neváženém grafu, protože v BFS dosáhneme vrcholu s minimálním počtem hran ze zdrojového vrcholu. Naproti tomu v DFS můžeme projít více hran, abychom dosáhli cílového vrcholu ze zdroje.
- typ hledání: V obou případech se jedná o neinformované hledání
- paměťové porovnání:
- struktura dat: BFS zabere více paměti, protože musí zpětně procházet více než DFS obecně: DFS používá zásobník, který obsahuje uzly od kořene po prohledávaný uzel. BFS používá frontu, která obsahuje uzly na začátku prohledávání.
.