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!
Tillbaka till Sökning (DFS och BFS)