Hoppa till huvudinnehåll

Tillämpningar av DFS i olika situationer

Depth First Search (DFS) är en kraftfull och flexibel algoritm som kan anpassas till många olika typer av problem , men hur vi använder den kan skilja sig beroende på situationen.

Image

DFS är en metod , inte en färdig lösning​

När vi pratar om DFS är det viktigt att förstå att algoritmen i sig bara beskriver hur man rör sig genom ett grafliknande system , den:

  • Börjar vid en startpunkt
  • Utforskar så långt det går i varje riktning
  • Backar (backtracking) om den når en återvändsgränd

Men i praktiken måste vi ofta justera DFS efter vad vi vill uppnå och vilken typ av data vi arbetar med.

Vad behöver vi spara under en DFS?​

I den klassiska versionen av DFS sparar vi oftast:

  • Vilka noder vi har besökt (t.ex. ett visited[]-array)
  • Grannarna till varje nod (adjacent list)

Men beroende på problemet, kan vi behöva spara mycket mer.

Exempel: DFS i Pac-Man​

Tänk dig att vi använder DFS i ett spel som Pac-Man, där Pac-Man ska ta sig från en punkt till en annan utan att krocka med väggar eller spöken.

Här räcker det inte med att bara spara "vilka rutor som har besökts".

Vi måste också:

  • Spara positionen (t.ex. (x, y))
  • Hålla koll på vilken väg vi tagit (t.ex. "höger → höger → ner → vänster")
  • Kanske också spara antal steg, energipoäng eller andra tillstånd

Exempel på vad vi kan behöva spara i ett Pac-Man-problem:

Position: (3, 5)
Path: ["höger", "höger", "ner", "vänster"]
Besökta: alla rutor vi redan varit på

Det viktiga är att du tänker som en problemlösare, inte som en kodmaskin.