In dit verhaal zal ik de twee veelgebruikte algoritmen voor de basis van kunstmatige intelligentie en neurale netwerken vergelijken, namelijk depth-first-search en breadth-first-search. Als je deze twee algoritmen niet hebt begrepen, kijk dan in mijn andere artikelen voor een instructie van 5 minuten en je zult ze kunnen begrijpen.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
Ten eerste zijn het allebei niet-geïnformeerde zoekalgoritmen, wat betekent dat ze op een brute-force manier werken en geen aanvullende informatie over de staat of zoekruimte hebben, behalve hoe ze de boom moeten doorkruisen. Als je mijn vorige artikelen over DFS of BFS hebt gelezen, weet je dat geen van beide tijdens het zoekproces naar het gewicht van elke stap kijkt.
- Runtime: Beide algoritmen werken in O(n), omdat ze in het ergste geval elke knoop in de zoekruimte moeten bezoeken.
- wanneer DFS>BFS: Als de knoop die we zoeken erg diep ligt of er zijn meerdere doelknopen die vrij diep liggen, moeten we DFS gebruiken. In dit geval moet BFS alle knooppunten boven ons bezoeken voordat het de diep gelegen knooppunten bezoekt, wat te veel tijd kost.
- wanneer BFS>DFS: BFS kan worden gebruikt om het kortste pad met één bron te vinden in een ongewogen grafiek, omdat we in BFS een hoekpunt bereiken met een minimum aantal randen vanaf een bron hoekpunt. Aan de andere kant, in DFS, zouden wij door meer randen kunnen gaan om een bestemmingspunt vanaf een bron te bereiken.
- zoektype: beide zijn niet-geïnformeerde zoekopdrachten
- geheugenvergelijking: BFS zal meer geheugen in beslag nemen omdat het meer moet backtracken dan DFS in het algemeen zal doen.
- datastructuur: DFS gebruikt een stack, die knooppunten bevat van de root tot het knooppunt dat wordt doorzocht. BFS gebruikt een wachtrij, die knooppunten bevat die vooraan staan bij het zoeken.