Depth-First Search (DFS)
Nu när vi vet lite mer om vad AI är och hur sökalgoritmer passar in,
är det dags att titta på den algoritm som den här workshopen fokuserar på:
Depth-First Search, eller Djupet-Först-Sökning , oftast förkortat DFS.
Vad är DFS?
DFS är en oinformerad sökalgoritm , det betyder att den inte har någon information om var målet finns.
Den testar bara olika vägar tills den hittar en lösning (eller har testat alla möjligheter).
DFS fungerar genom att gå så djupt som möjligt i en gren av sökträdet, innan den backar tillbaka och testar en annan väg.
Tänk dig att du ska hitta vägen genom en labyrint , DFS skulle välja en riktning och gå tills det inte går längre,
och först då vända om och prova nästa väg.
Hur fungerar DFS?
DFS använder en datastruktur som kallas stack (stack/minne).
Det betyder att algoritmen "kommer ihåg" vilka tillstånd den har varit i, och kan backa tillbaka om den fastnar.
Steg för steg:
- Börja från starttillståndet
- Lägg det på stacken
- Så länge stacken inte är tom:
- Ta det översta tillståndet (senast tillagda)
- Om det är målet → klart!
- Annars:
- Markera det som besökt
- Lägg alla dess grannar (barn) på stacken
Vad är en stack?
En stack är en datastruktur där det sista du lägger in är det första som tas ut.
Det kallas för LIFO , Last In, First Out.
Exempel:
Tänk dig en stapel med tallrikar , du lägger en ny tallrik ovanpå,
och när du tar en tallrik, tar du den som ligger överst.
I DFS betyder det att vi alltid utforskar den senaste vägen först, vilket gör att vi kommer så djupt som möjligt innan vi backar.
🔄 DFS jämfört med några andra algoritmer
| Algoritm | Typ | Datastruktur | Går på djupet? | Garanterar kortaste vägen? |
|---|---|---|---|---|
| DFS | Oinformerad | Stack | ✅ Ja | ❌ Nej |
| BFS | Oinformerad | Queue (kö) | ❌ Nej | ✅ Ja |
| A* | Informerad | Priority Queue | ❌ Nej | ✅ Ja (om heuristiken är korrekt) |
DFS är snabb i vissa fall , men kan gå vilse i stora eller oändliga grafer,
eftersom den inte vet hur långt det är till målet och bara fortsätter "på chans".
När används DFS?
DFS är användbar när:
- Vi vill utforska alla möjliga vägar (t.ex. i pussel eller mazer)
- Lösningen kanske ligger långt ner i sökträdet
- Minnesanvändning ska vara låg , DFS kräver mindre minne än t.ex. BFS
- Vi inte bryr oss om den kortaste vägen, bara att hitta en lösning
DFS i spel
DFS används i spel när en karaktär ska:
- Utforska en karta
- Lösa ett pussel
- Hitta en väg genom en labyrint
I denna workshop kommer vi att använda DFS för att styra Pac-Man genom en bana,
och visa exakt hur algoritmen väljer sin väg.
Nu när du vet vad DFS är och hur den fungerar, är du redo att implementera den i Python!
Gå vidare till nästa del för att se DFS i action , och börja koda!