I denne historie vil jeg sammenligne de to almindeligt anvendte algoritmer til at danne grundlag for kunstig intelligens og neurale netværk, nemlig depth-first-search og breadth-first-search. Hvis du ikke har forstået disse to algoritmer, så tjek mine andre artikler for en 5 minutters instruktion, og du vil være i stand til at forstå 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ørst er de begge uinformerede søgealgoritmer, hvilket betyder, at de opererer på brute force-måde og ikke har yderligere information om tilstand eller søgerum ud over, hvordan træet skal gennemløbes. Hvis du har læst mine tidligere artikler om DFS eller BFS, ved du, at ingen af dem vil se på vægten af hvert trin under søgeprocessen.
- Runtime: Begge algoritmer opererer i O(n), da de i værste fald skal besøge hver eneste knude i søgerummet.
- når DFS>BFS: Hvis den knude, vi leder efter, er meget dyb, eller der er flere målknuder, der er ret dybt nede, bør vi bruge DFS. I dette tilfælde skal BFS besøge alle knuder ovenover, før den besøger de dybe knuder, hvilket tager for lang tid.
- når BFS>DFS: BFS kan bruges til at finde den korteste vej med en enkelt kilde i en uvægtet graf, fordi vi i BFS når et toppunkt med det mindste antal kanter fra et kildepunkt. På den anden side kan det i DFS være muligt at gå gennem flere kanter for at nå frem til et bestemmelsespunkt fra en kilde.
- Søgetype: Begge er uinformeret søgning
- Memory comparison: BFS vil tage mere hukommelse, fordi den skal foretage flere backtracks end DFS generelt.
- Datastruktur: DFS bruger en stak, som indeholder knuder fra roden til den knude, der søges i. BFS bruger en kø, som indeholder knuder forrest i søgningen.