BFS & DFS i grafer
Hej, jag försöker att förstå hur BFS & DFS fungerar men blir inte riktigt klok när jag ser facit på denna uppgift.
Enligt grannlistorna nedan, skall jag ange vägen från 1-9 med hjälp av BFS & DFS i respektive graf.
// FACIT //
DFS = [1,2,3,6,5,4,7,8,9] i samtliga grafer.
BFS =
A) 1,2,3,6,9
B) 1,2,5,9
C) 1,5,9
D) 1,2,6,9
Antar att DFS väljer, enligt facit, i denna uppgift att gå till nästkommande obesökta nod i grannlistan.
Jag påstår dock att möjliga vägar med DFS är;
A) 1,2,3,6,9.
B) 1,2,5,9.
C) 1,5,9
D) 1,2,6,9
När det kommer till BFS, har jag fattat det som att vi så besöker alla barnnoder innan vi går vidare i sökningen med hjälp av en fifo-kö.
Alltså borde en möjlig BFS se ut såhär;
A) 1,2,4,3,5,7,6,8,9.
B) 1,2,4,3,5,7,6,9
C) 1,2,4,5,3,7,6,8,9
D) 1,2,4,5,3,6,7,8,9
Är jag ute och cyklar ?
//
För djupsökning (DFS) startar du i nod 1 och går sedan till nästa obesökta nod i grannlistan. Alltså nod 2, vidare till nod 3, till nod 6. Från nod 6 går du till den nästkommande obesökta noden i grannlistan. Listan är ordnad i stigande ordning. Så grannlistan för nod 6: [3,5,9]. Nod 3 är redan besökt så du rör dig till nod 5. Därifrån är det samma procedur fram tills du anländer till nod 9.
Felet du gör i ditt svar för A) är att du går från nod 6 till 9. Vad är det som gör att du väljer nod 9 över att gå till nod 6? Du vet inte i förhand att du ska skippa nod 6 så du måste gå blint på dina regler (att gå till nästkommande obesökta granne).
Bredd-sökning (BFS): undersök alla noder på samma nivå. Där har du gjort helt rätt!
Men du behöver "förkorta" eller ge dit slutgiltiga svar. Välj en väg för din BFS sökning och använd de noder som ger kortast väg men också lägst/först nummer i grannlistan. Då blir dit svar för A) 1,2,4,3,5,7,6,8,9 -> 1,2,3,6,9.
Hi-hat skrev:Felet du gör i ditt svar för A) är att du går från nod 6 till 9. Vad är det som gör att du väljer nod 9 över att gå till nod 6? Du vet inte i förhand att du ska skippa nod 6 så du måste gå blint på dina regler (att gå till nästkommande obesökta granne).
Anledningen att jag valde att gå från nod 6 till 9, var att jag i _många_ videor på nätet har hört att man får välja vilken grann-nod man vill gå till och att "storlek" på noderna inte har någon betydelse. Men jag förstår vad du menar att den inte bara kan skippa nod 5 i detta fall!
Bredd-sökning (BFS): undersök alla noder på samma nivå. Där har du gjort helt rätt!
Men du behöver "förkorta" eller ge dit slutgiltiga svar. Välj en väg för din BFS sökning och använd de noder som ger kortast väg men också lägst/först nummer i grannlistan. Då blir dit svar för A) 1,2,4,3,5,7,6,8,9 -> 1,2,3,6,9.
Ja men just det! BFS backtrackar ju inte, tänkte nog inte på att mina svar har flera olika vägar ...
Jag tackar så mycket för hjälpen, bra förklarat!
Froo skrev: Anledningen att jag valde att gå från nod 6 till 9, var att jag i _många_ videor på nätet har hört att man får välja vilken grann-nod man vill gå till och att "storlek" på noderna inte har någon betydelse. Men jag förstår vad du menar att den inte bara kan skippa nod 5 i detta fall!
Jag skulle säga att det alltid måste finnas regler för vilken grann-nod som skall väljas. Här har de valt den med lägst nummer, men det går ju också bra att slumpa eller ha en annan regel att följa.
Programkoden du skriver ska ju kunna köras utan att du väljer grann-nod manuellt. Eventuellt kan du programmera så att alla noder i grannlistan undersöks om de innehåller slutnoden och om ej så väljer du den med lägst siffra.
Om reglerna du ska följa ej angavs i uppgiften, så var det en dåligt formulerat uppgift ;)
Som @Hi-hat skrev så behöver reglerna anges i uppgiften.
Facit följer inte heller de underförstådda reglerna på något konsekvent sätt. Enligt facit på DFS måste varje nod följas i stigande nummerordning utan att förbise någon nod. Enligt facit på BFS måste inte noderna följas i stigande nummerordning utan det är det tillåtet att förbise vissa noder för att korta ned sökvägen. Att man enligt facit ska välja kortaste sökväg för BFS men inte ska välja kortaste sökväg för DFS är inkonsekvent. Om man dessutom ska analysera vilken algoritm som är bättre för att hitta en kort väg så blir jämförelsen orättvis.
Du visade själv en korrekt analys på BFS där du inte förbiser någon nod utan följer regeln om stigande nummerordning (som uppenbarligen gäller för DFS). Bra!
Fann en Python-implementation av BFS och DFS som tar fram samtliga sökvägar från 1 till 9 (oavsett nummerordningen för noderna). Skrev ett kort program som skrev ut alla möjliga vägar:
Visa spoiler
GRAPH 1
Possible DFS paths:
[[1, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 6, 9],
[1, 4, 7, 8, 5, 2, 3, 6, 9],
[1, 4, 5, 6, 9],
[1, 4, 5, 2, 3, 6, 9],
[1, 4, 5, 8, 9],
[1, 2, 5, 6, 9],
[1, 2, 5, 4, 7, 8, 9],
[1, 2, 5, 8, 9],
[1, 2, 3, 6, 9],
[1, 2, 3, 6, 5, 4, 7, 8, 9],
[1, 2, 3, 6, 5, 8, 9]]
Possible BFS paths:
[[1, 2, 3, 6, 9],
[1, 2, 5, 8, 9],
[1, 2, 5, 6, 9],
[1, 4, 5, 8, 9],
[1, 4, 5, 6, 9],
[1, 4, 7, 8, 9],
[1, 2, 3, 6, 5, 8, 9],
[1, 2, 5, 4, 7, 8, 9],
[1, 4, 5, 2, 3, 6, 9],
[1, 4, 7, 8, 5, 6, 9],
[1, 2, 3, 6, 5, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 2, 3, 6, 9]]
GRAPH 2
Possible DFS paths:
[[1, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 9],
[1, 4, 7, 8, 5, 6, 9],
[1, 4, 7, 8, 5, 3, 6, 9],
[1, 4, 7, 8, 5, 2, 3, 6, 9],
[1, 4, 5, 9],
[1, 4, 5, 8, 9],
[1, 4, 5, 6, 9],
[1, 4, 5, 3, 6, 9],
[1, 4, 5, 2, 3, 6, 9],
[1, 2, 5, 9],
[1, 2, 5, 8, 9],
[1, 2, 5, 6, 9],
[1, 2, 5, 4, 7, 8, 9],
[1, 2, 5, 3, 6, 9],
[1, 2, 3, 6, 9],
[1, 2, 3, 6, 5, 9],
[1, 2, 3, 6, 5, 4, 7, 8, 9],
[1, 2, 3, 6, 5, 8, 9],
[1, 2, 3, 5, 9],
[1, 2, 3, 5, 6, 9],
[1, 2, 3, 5, 4, 7, 8, 9],
[1, 2, 3, 5, 8, 9]]
Possible BFS paths:
[[1, 2, 5, 9],
[1, 4, 5, 9],
[1, 2, 3, 5, 9],
[1, 2, 3, 6, 9],
[1, 2, 5, 6, 9],
[1, 2, 5, 8, 9],
[1, 4, 5, 6, 9],
[1, 4, 5, 8, 9],
[1, 4, 7, 8, 9],
[1, 2, 3, 5, 8, 9],
[1, 2, 3, 5, 6, 9],
[1, 2, 3, 6, 5, 9],
[1, 2, 5, 3, 6, 9],
[1, 4, 5, 3, 6, 9],
[1, 4, 7, 8, 5, 9],
[1, 2, 3, 6, 5, 8, 9],
[1, 2, 5, 4, 7, 8, 9],
[1, 4, 5, 2, 3, 6, 9],
[1, 4, 7, 8, 5, 6, 9],
[1, 2, 3, 5, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 3, 6, 9],
[1, 2, 3, 6, 5, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 2, 3, 6, 9]]
GRAPH 3
Possible DFS paths:
[[1, 5, 9],
[1, 5, 8, 9],
[1, 5, 6, 9],
[1, 5, 4, 7, 8, 9],
[1, 5, 2, 3, 6, 9],
[1, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 9],
[1, 4, 7, 8, 5, 6, 9],
[1, 4, 7, 8, 5, 2, 3, 6, 9],
[1, 4, 5, 9],
[1, 4, 5, 6, 9],
[1, 4, 5, 2, 3, 6, 9],
[1, 4, 5, 8, 9],
[1, 2, 5, 9],
[1, 2, 5, 6, 9],
[1, 2, 5, 4, 7, 8, 9],
[1, 2, 5, 8, 9],
[1, 2, 3, 6, 9],
[1, 2, 3, 6, 5, 9],
[1, 2, 3, 6, 5, 4, 7, 8, 9],
[1, 2, 3, 6, 5, 8, 9]]
Possible BFS paths:
[[1, 5, 9],
[1, 2, 5, 9],
[1, 4, 5, 9],
[1, 5, 6, 9],
[1, 5, 8, 9],
[1, 2, 3, 6, 9],
[1, 2, 5, 8, 9],
[1, 2, 5, 6, 9],
[1, 4, 5, 8, 9],
[1, 4, 5, 6, 9],
[1, 4, 7, 8, 9],
[1, 2, 3, 6, 5, 9],
[1, 4, 7, 8, 5, 9],
[1, 5, 2, 3, 6, 9],
[1, 5, 4, 7, 8, 9],
[1, 2, 3, 6, 5, 8, 9],
[1, 2, 5, 4, 7, 8, 9],
[1, 4, 5, 2, 3, 6, 9],
[1, 4, 7, 8, 5, 6, 9],
[1, 2, 3, 6, 5, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 2, 3, 6, 9]]
GRAPH 4
Possible DFS paths:
[[1, 5, 6, 9],
[1, 5, 4, 7, 8, 9],
[1, 5, 2, 6, 9],
[1, 5, 2, 3, 6, 9],
[1, 5, 8, 9],
[1, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 6, 9],
[1, 4, 7, 8, 5, 2, 6, 9],
[1, 4, 7, 8, 5, 2, 3, 6, 9],
[1, 4, 5, 6, 9],
[1, 4, 5, 2, 6, 9],
[1, 4, 5, 2, 3, 6, 9],
[1, 4, 5, 8, 9],
[1, 2, 6, 9],
[1, 2, 6, 5, 4, 7, 8, 9],
[1, 2, 6, 5, 8, 9],
[1, 2, 5, 6, 9],
[1, 2, 5, 4, 7, 8, 9],
[1, 2, 5, 8, 9],
[1, 2, 3, 6, 9],
[1, 2, 3, 6, 5, 4, 7, 8, 9],
[1, 2, 3, 6, 5, 8, 9]]
Possible BFS paths:
[[1, 2, 6, 9],
[1, 5, 8, 9],
[1, 5, 6, 9],
[1, 2, 3, 6, 9],
[1, 2, 5, 8, 9],
[1, 2, 5, 6, 9],
[1, 4, 5, 8, 9],
[1, 4, 5, 6, 9],
[1, 4, 7, 8, 9],
[1, 5, 2, 6, 9],
[1, 2, 6, 5, 8, 9],
[1, 4, 5, 2, 6, 9],
[1, 5, 2, 3, 6, 9],
[1, 5, 4, 7, 8, 9],
[1, 2, 3, 6, 5, 8, 9],
[1, 2, 5, 4, 7, 8, 9],
[1, 4, 5, 2, 3, 6, 9],
[1, 4, 7, 8, 5, 6, 9],
[1, 2, 6, 5, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 2, 6, 9],
[1, 2, 3, 6, 5, 4, 7, 8, 9],
[1, 4, 7, 8, 5, 2, 3, 6, 9]]
