Tässä jutussa vertailen kahta yleisesti käytettyä algoritmia tekoälyn ja neuroverkkojen perustana, nimittäin depth-first-search ja breadth-first-search. Jos et ole ymmärtänyt näitä kahta algoritmia, käy muissa artikkeleissani katsomassa 5 minuutin ohje, niin pystyt ymmärtämään ne.
DFS:https://medium.com/@tingyan.deng/depth-first-search-short-tutorial-165b41f1b1c0
BFS:https://medium.com/@tingyan.deng/breadth-first-search-short-tutorial-a1ceb78b0c11
Ensinnäkin, molemmat ovat informoimattomia hakualgoritmeja, mikä tarkoittaa sitä, että ne toimivat raa’alla voimalla, eikä niillä ole mitään lisäinformaatioita tilasta tai hakuavaruudesta, sen lisäksi, että miten ne kulkevat puussa. Jos olet lukenut aiemmat artikkelini DFS:stä tai BFS:stä, tiedät, että kumpikaan niistä ei tarkastele kunkin askeleen painoa hakuprosessin aikana.
- Ajoaika:
- milloin DFS>BFS: Jos etsimämme solmu on hyvin syvällä tai on useita melko syvällä olevia tavoitesolmuja, kannattaa käyttää DFS:ää. Tällöin BFS:n täytyy käydä jokaisessa yläpuolella olevassa solmussa ennen kuin se käy syvällä olevissa solmuissa, mikä vie liikaa aikaa.
- when BFS>DFS: BFS:ää voidaan käyttää yhden lähteen lyhimmän polun etsimiseen painottamattomassa graafissa, koska BFS:ssä päästään pisteeseen, jossa on minimaalinen määrä särmiä lähdepisteestä. Toisaalta DFS:ssä saatamme kulkea useamman särmän läpi saavuttaaksemme määränpääpisteen lähteestä.
- hakutyyppi: Molemmat ovat tietämättömiä hakuja
- muistivertailu: BFS vie enemmän muistia, koska se joutuu jäljittämään enemmän taaksepäin kuin DFS yleensä.
- tietorakenne: DFS käyttää pinoa, joka sisältää solmut juuresta haettavaan solmuun. BFS käyttää jonoa, joka sisältää solmut haun alkupäässä.