Tävlingsprogrammering/Teori/Labyrintproblem

Labyrintproblem

Problem: Givet är en boolean-matris map[1..columns, 1..rows] där varje element map[x,y] är true om det är möjligt att befinna sig på positionen (x, y) och false om det är omöjligt. Ett "drag" är en förflyttning ett steg vågrätt eller lodrätt. Bestäm det minsta antalet drag som behövs för att ta sig från (start.x, start.y) till (slut.x, slut.y).

DFS-lösning

Oftast är det enklaste att köra djupet-först-sökning (DFS). Man gör ett "drag" och sedan rekurserar man, d.v.s. kör sin funktion en gång till på den nya ställningen, och ser till att man inte går runt i cirklar. Med DFS hittar man inte den bästa lösningen först, utan man måste testa alla möjligheter och spara den bästa. Fördelen är att det är väldigt enkelt att skriva, samt att man inte behöver så mycket minne, eftersom allting sparas på en stack när man rekurserar och stackdjupet aldrig överstiger maximalt antal drag.

DFS_solution(map[1..columns, 1..rows], start, slut)

   min := 1000000
   Håller reda på bästa lösningen. Det stora värdet betyder ingen lösning hittad.

   taken[1..columns, 1..rows] := false
   Håller reda på om positionen är besökt.

   Go(start.x, start.y, 0)

   if min = 1000000 then ****INGEN LÖSNING****
   else ****BÄSTA LÖSNING: min ****
   ____________________________________________

   Go(x, y, num)
   Rekursiv funktion som "går runt" i labyrinten.
   x, y = koordinaterna just nu,
   num = antal drag hittills

       if x > columns or x < 1 or y > rows or y < 1 then
           Utanför kartan
           return
       if (not map[x, y]) or taken[x, y] then
           Omöjlig position enligt kartan eller redan besökt
           return
       if x = slut.x and y = slut.y then
           Hittad lösning
           min = num
       if num >= min - 1 then
           Onödigt att leta om det inte går att hitta någon bättre lösning.
           return

       taken[pos] := true     Markera position som besökt

       Go(x + 1, y    , num + 1)   Höger
       Go(x - 1, y    , num + 1)   Vänster
       Go(x    , y + 1, num + 1)   Uppåt
       Go(x    , y - 1, num + 1)   Nedåt

       taken[x, y] := false
       Avmarkera positionen. OBS! Behöver endast göras när kortaste vägen ska hittas.

BFS-lösning

Bredden-först-sökning (BFS) är metoden då man från en situation gör alla möjliga drag och sparar dem längst bak i en kö, för att sedan hämta nästa situation först i kön och göra om samma procedur. Om man vet vilka situationer man kan nå med t.ex. 3 drag så kan man generera alla möjliga drag från dessa situationer och på så sätt få fram vilka situationer man kan nå med 4 drag. Med denna metod är man säker på att hitta bästa lösningen först, eftersom alla situationer med 3 drag testas innan man går vidare till 4 o.s.v.

BFS är lite krångligare att skriva, kräver mer minne och förutsätter att man har ett någorlunda litet antal situationer som är möjliga att komma till. Själva kön implementeras elegantast med en dynamiskt allokerad länkad lista, för att kunna frigöra minnet för de situationer som man redan har använt. På tävlingar är dock mängden situationer ofta begränsad så att man får plats även om man kör i en vanlig array.

BFS_solution(map[1..columns, 1..rows], start, slut)
   Q[1..maxNumSituations] innehåller själva kön. Varje element
   innehåller x- och y-koordinat för en situation och fältet num som
   anger hur många drag som har behövts för att ta sig dit (alltid minimalt).
   I detta fall kan maxNumSituations sättas till columns * rows.

   Q[1].x := start.x
   Q[1].y := start.y
   Q[1].num := 0     Placera startpositionen i kön med 0 drag.
   now := 1    Pekar på början av kön.
   next := 2   Pekar efter slutet av kön, där nya situationer ska placeras.

   while now < next do     Så länge kön inte är tom
       if Q[now].x = slutx and Q[now].y = sluty then
           ****BÄSTA LÖSNING: Q[now].num ****

       add(Q[now].x + 1, Q[now].y    , Q[now].num + 1)
       add(Q[now].x - 1, Q[now].y    , Q[now].num + 1)
       add(Q[now].x    , Q[now].y + 1, Q[now].num + 1)
       add(Q[now].x    , Q[now].y - 1, Q[now].num + 1)   Lägg till nya situationer

   Kön är tom, d.v.s. inga möjliga drag
   ****INGEN LÖSNING****

   ____________________________________________

   add(x, y, moves)
   Funktion som lägger till situationen sist i kön.
   x, y = koordinaterna för denna situation
   moves = antal drag som behövdes

       if x > columns or x < 1 or y > rows or y < 1 then
           Utanför kartan
           return
       if (not map[x, y]) or taken[x, y] then
           Omöjlig position enligt kartan eller redan besökt
           return

       Q[next].x := x
       Q[next].y := y
       Q[next].num := moves
       next := next + 1
       taken[x, y] := true    Markerar positionen som besökt

Lägg märke till skillnaden i användandet av taken. I denna form av DFS markeras en position som besökt enbart för att vi inte ska gå runt i cirklar. När vi väl har undersökt alla möjliga vägar från en position (oavsett om vi hittat en lösning eller inte), görs s.k. backtracking. Det betyder att vi "ångrar" det drag som ledde fram till positionen och istället väljer ett annat. När vi gör detta avmarkeras positionen, för det är ju möjligt att vi behöver använda denna position på någon annan väg. I BFS däremot avmarkeras aldrig en position. När vi väl har nått fram till en position vet vi ju att vi har gått den bästa vägen och det finns därför ingen anledning att söka efter andra vägar förbi samma position. Varje position besöks alltså endast en gång, vilket är anledningen till att i detta exempel BFS är mycket effektivare (linjär) än DFS (exponentiell).

Men, som antyddes innan, en vanlig form av DFS är när vi inte är intresserade av den optimala lösningen utan bara vill veta om det går överhuvudtaget. Då behöver vi inte avmarkera en position, för det är ju meningslöst att gå dit en gång till, och då blir även DFS linjär.

Det hela är ganska självklart, men det kan vara bra att vara medveten om skillnaderna när man väljer algoritm. Ofta ligger problemet i att situationerna inte kan beskrivas med bara x och y. T.ex. kanske du har 5 olika spelpjäser som vardera kan stå på 10 olika positioner. Då gäller det att beskriva varje av de 100000 situationerna med ett tal som du kan använda som index i taken. Samtidigt börjar det bli problem med att få plats med din BFS-kö i minnet.

Övningsuppgift 1

Med en enkel optimering kan du göra DFS-algoritmen effektivare och samtidigt ha kvar enkelheten. Det gäller att spara minsta antalet drag till varje situation. Ändra i DFS-algoritmen så att detta utnyttjas!

Övningsuppgift 2

Om det finns ett litet antal möjliga situationer, kan man skriva en enklare variant av BFS där man slipper hantera kön. Den går helt enkelt ut på att man bara använder taken-arrayen (fast med heltal istället för boolean) och sparar det minsta antalet drag för att komma till varje situation. I varje "omgång" letar man igenom arrayen efter situationer med minsta antalet drag t.ex. 3. Därifrån gör man de möjliga dragen och markerar de nya situationerna med 4. När man hunnit igenom hela arrayen gör man en ny omgång där man letar efter situationer markerade med 4, o.s.v. Det är ofta ett ganska ineffektivt sätt, men väldigt lätt att skriva, och ibland är ju det viktigast. Metoden påminner om Knapsack-algoritmen. Försök skriva om BFS-algoritmen på detta sätt!