Koodit: QB: Leveyshaku ja syvyyshaku
Kirjoittaja: Antti Laaksonen
Kirjoitettu: 31.08.2007 – 31.08.2007
Tagit: koodi näytille, vinkki
Leveyssuuntainen ja syvyyssuuntainen haku ovat keskeisiä tapoja verkkojen läpikäyntiin. Tässä koodivinkissä aiheeseen tutustutaan hieman tavallisesta poikkeavasti labyrintin avulla. Labyrintin sisältä löytää ulos sekä leveyssuuntaisella että syvyyssuuntaisella haulla, mutta välillä erot algoritmien tehokkuudessa ja muistinkäytössä ovat suuria.
Syvyyssuuntainen haku on ehkä luonnollisin tapa labyrintin tutkimiseen. Siinä labyrintissa tunkeudutaan eteenpäin niin syvälle kuin päästään ja jos joudutaan umpikujaan, palataan takaisin niin kauan, kunnes ollaan jälleen tienhaarassa, josta pystyy jatkamaan eteenpäin. Toisin sanoen reitin haarautuessa jokainen haara käsitellään yksi kerrallaan kokonaan, ja vasta kun kaikki haarat on tutkittu, palataan tarvittaessa takaisin johonkin aiempaan haaraan.
Seuraavissa kuvissa näkyy syvyyssuuntaisen haun kaksi vaihetta. Aloitusruutu on D2, josta lähdetään ensin oikealle. Tämä reitti johtaa kuitenkin umpikujaan, jonne juuri ollaan joutumassa ensimmäisessä kuvassa. Ennen toista kuvaa on peruutettu takaisin alkuun ja käyty vielä toisella harharetkellä ruudussa F8. Nyt labyrintin uloskäynti alkaa vihdoin häämöttää.
Kaikkia reitin varrelle jääneitä ruutuja säilytetään taulukossa, jonka nimi on pino, koska vain taulukon loppuun tehdään lisäyksiä ja poistoja. Aina lähtöruudussa poikettaessa taulukko on hetkellisesti tyhjä. Lisäksi karttaan merkitään, missä ruuduissa on jo käyty, jotta samaan paikkaan ei mennä uudestaan. Syvyyssuuntainen haku toteutetaan usein rekursiivisella funktiolla, jolloin reitin kirjanpito hieman helpottuu.
Syvyyssuuntaisen haun heikkous on, että jos haku sattuu lähtemään väärään suuntaan, se voi tuhlata hyvin paljon aikaa labyrintin umpikujissa. Kaikkein ikävintä on, jos lähtöpaikka on uloskäynnin vieressä, mutta haku valitsee väärän suunnan. Tällöin joudutaan käymään koko labyrintti läpi, ennen kuin lopulta palataan lähtöpaikalle ja löydetään ulos. Tämän ongelman ratkaisuna on leveyssuuntainen haku.
Leveyssuuntainen haku etsii labyrintin reittejä järjestyksessä niiden pituuden mukaan. Ensin haku etsii kaikki reitit, joissa siirrytään yksi askel johonkin suuntaan. Jos tämä ei johda ulospääsyyn, haku laajentaa reitteihin, joissa liikutaan kaksi askelta, sitten kolme askelta jne. Haun toimintaa voi ajatella niin, että aina kun reitti haarautuu, jokaista haaraa lähtee tutkimaan rinnakkain erillinen haku.
Seuraavissa kuvissa lähtöpaikka on ruudussa B6. Heti aluksi haku jakaantuu kahdeksi hauksi, joista toinen lähtee vasemmalle ja toinen oikealle. Toisessa kuvassa haku on ehtinyt hieman pidemmälle ja hakuja on jo kolme. Nyt alun perin vasemmalle lähtenyt haku on jo melkein päässyt ulos. Muut haut joutuvat tosin umpikujaan, mutta niiden kohtalo ei haittaa.
Leveyssuuntainen haku toteutetaan taulukolla, jonka nimi on jono, koska paikkoja lisätään taulukon loppuun ja paikkoja poistetaan taulukon alusta. Käsittelyyn otetaan kulloinkin taulukon alussa oleva ruutu, ja jos siitä pääsee ruutuihin, joita ei vielä ole tutkittu, nämä ruudut lisätään taulukon loppuun. Näin yhtään uutta ruutua ei aleta käsitellä, ennen kuin kaikki vanhat ruudut on käsitelty.
Leveyssuuntainen haku löytää varmasti lyhyimmän reitin ulos, kun taas syvyyssuuntainen haku saattaa päätyä pitempään reittiin, jos on useita eripituisia reittejä. Toisaalta leveyssuuntaisella haulla ei voi koskaan käydä hyvä onni: jos labyrintti haarautuu kymmeneen yhtä pitkään käytävään, joista vain yksi johtaa ulos, leveyssuuntainen haku tutkii järjestelmällisesti kaikki käytävät kokonaan.
Tässä esitetyillä hakumenetelmillä on valtavasti sovelluskohteita, koska hyvin monenlaisia ongelmia voi ajatella labyrintteina. Kun ongelmaa ratkaistessa pitää valita monesta vaihtoehdosta, tilanne vastaa labyrintin haaraa, ja kun valintaketju johtaa ongelman ratkaisuun, labyrintista päästään ulos. Usein tosin labyrinttia ei saa valmiina, vaan ohjelma muodostaa sitä pikku hiljaa, ja labyrintti jää ehkä keskeneräiseksi.
' Leveyssuuntainen ja syvyyssuuntainen haku
' Antti Laaksonen, 2007
SCREEN 1
DIM kartta%(0 TO 10, 0 TO 10)
DIM nimet$(1 TO 9, 1 TO 9)
DIM muisti%(1 TO 100, 1 TO 2)
' laby$ = "B"
' haku$ = "L"
' piirto$ = "N"
' GOTO jatko
CLS
PRINT "Valitse labyrintti:"
PRINT
PRINT " A = Labyrintti A"
PRINT " B = Labyrintti B"
PRINT " C = Labyrintti C"
DO
laby$ = UCASE$(INKEY$)
LOOP UNTIL laby$ = "A" OR laby$ = "B" OR laby$ = "C"
CLS
PRINT "Valitse hakutapa:"
PRINT
PRINT " L = leveyssuuntainen haku"
PRINT " S = syvyyssuuntainen haku"
DO
haku$ = UCASE$(INKEY$)
LOOP UNTIL haku$ = "L" OR haku$ = "S"
CLS
PRINT "Valitse piirtotapa:"
PRINT
PRINT " N = nopea piirto"
PRINT " H = hidas piirto"
PRINT " A = askellus"
DO
piirto$ = UCASE$(INKEY$)
LOOP UNTIL piirto$ = "N" OR piirto$ = "H" OR piirto$ = "A"
jatko:
SELECT CASE laby$
CASE "A"
RESTORE labya
CASE "B"
RESTORE labyb
CASE "C"
RESTORE labyc
END SELECT
CLS
FOR i% = 0 TO 9
FOR j% = 0 TO 9
LINE (j% * 16 + 3, i% * 16 + 3)-STEP(16, 16), , B
NEXT
NEXT
FOR i% = 1 TO 9
LOCATE 2, i% * 2 + 2: PRINT CHR$(48 + i%)
LOCATE i% * 2 + 2, 2: PRINT CHR$(64 + i%)
NEXT
FOR i% = 1 TO 9
READ rivi$
FOR j% = 1 TO 9
SELECT CASE MID$(rivi$, j%, 1)
CASE " "
kartta%(j%, i%) = 1
CASE "#"
kartta%(j%, i%) = 0
LINE (j% * 16 + 5, i% * 16 + 5)-STEP(12, 12), , BF
CASE "*"
nx% = j%: ny% = i%
LOCATE i% * 2 + 2, j% * 2 + 2: PRINT CHR$(1)
END SELECT
nimet$(j%, i%) = CHR$(64 + i%) + CHR$(48 + j%)
NEXT
NEXT
FOR i% = 1 TO 80
LOCATE (i% - 1) MOD 20 + 2, 24 + ((i% - 1) \ 20) * 4
PRINT "--"
NEXT
LOCATE 22: PRINT STRING$(40, "-")
IF haku$ = "S" THEN
GOSUB syvyys
ELSEIF haku$ = "L" THEN
GOSUB leveys
ELSE
GOSUB loppu
END IF
leveys:
muisti%(1, 1) = nx%
muisti%(1, 2) = ny%
alku% = 1: loppu% = 1
LOCATE (loppu% - 1) MOD 20 + 2, 24 + ((loppu% - 1) \ 20) * 4
PRINT nimet$(muisti%(loppu%, 1), muisti%(loppu%, 2))
loppu% = 2
DO WHILE alku% < loppu% AND INKEY$ <> CHR$(27)
ux% = muisti%(alku%, 1)
uy% = muisti%(alku%, 2)
viesti$ = "Jatketaan jonon alusta ruudusta " + nimet$(ux%, uy%)
GOSUB odota
LOCATE (alku% - 1) MOD 20 + 2, 24 + ((alku% - 1) \ 20) * 4
PRINT "xx"
alku% = alku% + 1
IF ux% = 1 OR uy% = 1 OR ux% = 9 OR uy% = 9 THEN
viesti$ = "Vihdoin löytyi reitti ulos!"
GOSUB odota
EXIT DO
END IF
vloppu% = loppu%
IF kartta%(ux% + 1, uy%) = 1 THEN
muisti%(loppu%, 1) = ux% + 1
muisti%(loppu%, 2) = uy%
kartta%(ux% + 1, uy%) = 2
LOCATE (loppu% - 1) MOD 20 + 2, 24 + ((loppu% - 1) \ 20) * 4
PRINT nimet$(muisti%(loppu%, 1), muisti%(loppu%, 2))
LOCATE uy% * 2 + 2, ux% * 2 + 2: PRINT "x"
LOCATE uy% * 2 + 2, (ux% + 1) * 2 + 2: PRINT CHR$(1)
loppu% = loppu% + 1
viesti$ = "Lisätään jonoon vapaa ruutu " + nimet$(ux% + 1, uy%)
GOSUB odota
END IF
IF kartta%(ux%, uy% + 1) = 1 THEN
muisti%(loppu%, 1) = ux%
muisti%(loppu%, 2) = uy% + 1
kartta%(ux%, uy% + 1) = 2
LOCATE (loppu% - 1) MOD 20 + 2, 24 + ((loppu% - 1) \ 20) * 4
PRINT nimet$(muisti%(loppu%, 1), muisti%(loppu%, 2))
LOCATE uy% * 2 + 2, ux% * 2 + 2: PRINT "x"
LOCATE (uy% + 1) * 2 + 2, ux% * 2 + 2: PRINT CHR$(1)
loppu% = loppu% + 1
viesti$ = "Lisätään jonoon vapaa ruutu " + nimet$(ux%, uy% + 1)
GOSUB odota
END IF
IF kartta%(ux% - 1, uy%) = 1 THEN
muisti%(loppu%, 1) = ux% - 1
muisti%(loppu%, 2) = uy%
kartta%(ux% - 1, uy%) = 2
LOCATE (loppu% - 1) MOD 20 + 2, 24 + ((loppu% - 1) \ 20) * 4
PRINT nimet$(muisti%(loppu%, 1), muisti%(loppu%, 2))
LOCATE uy% * 2 + 2, ux% * 2 + 2: PRINT "x"
LOCATE uy% * 2 + 2, (ux% - 1) * 2 + 2: PRINT CHR$(1)
loppu% = loppu% + 1
viesti$ = "Lisätään jonoon vapaa ruutu " + nimet$(ux% - 1, uy%)
GOSUB odota
END IF
IF kartta%(ux%, uy% - 1) = 1 THEN
muisti%(loppu%, 1) = ux%
muisti%(loppu%, 2) = uy% - 1
kartta%(ux%, uy% - 1) = 2
LOCATE (loppu% - 1) MOD 20 + 2, 24 + ((loppu% - 1) \ 20) * 4
PRINT nimet$(muisti%(loppu%, 1), muisti%(loppu%, 2))
LOCATE uy% * 2 + 2, ux% * 2 + 2: PRINT "x"
LOCATE (uy% - 1) * 2 + 2, ux% * 2 + 2: PRINT CHR$(1)
loppu% = loppu% + 1
viesti$ = "Lisätään jonoon vapaa ruutu " + nimet$(ux%, uy% - 1)
GOSUB odota
END IF
IF vloppu% = loppu% THEN
viesti$ = "Reitti päättyi umpikujaan ruudussa " + nimet$(ux%, uy%)
GOSUB odota
END IF
LOOP
GOSUB loppu
syvyys:
muisti%(1, 1) = nx%
muisti%(1, 2) = ny%
ylin% = 1
LOCATE (ylin% - 1) MOD 20 + 2, 24 + ((ylin% - 1) \ 20) * 4
PRINT nimet$(muisti%(ylin%, 1), muisti%(ylin%, 2))
ux% = nx%: uy% = ny%
DO WHILE ylin% > 0 AND INKEY$ <> CHR$(27)
IF kartta%(ux%, uy%) = 2 THEN
LOCATE uy% * 2 + 2, ux% * 2 + 2: PRINT "x"
ELSE
LOCATE uy% * 2 + 2, ux% * 2 + 2: PRINT " "
END IF
ux% = muisti%(ylin%, 1)
uy% = muisti%(ylin%, 2)
viesti$ = "Liikutaan pinon ylimpään ruutuun " + nimet$(ux%, uy%)
kartta%(ux%, uy%) = 2
LOCATE uy% * 2 + 2, ux% * 2 + 2: PRINT CHR$(1)
GOSUB odota
IF ux% = 1 OR uy% = 1 OR ux% = 9 OR uy% = 9 THEN
viesti$ = "Vihdoin löytyi reitti ulos!"
GOSUB odota
EXIT DO
END IF
LOCATE (ylin% - 1) MOD 20 + 2, 23 + ((ylin% - 1) \ 20) * 4
PRINT " "
poisto% = 0
IF kartta%(ux% + 1, uy%) = 1 THEN
ylin% = ylin% + 1
muisti%(ylin%, 1) = ux% + 1
muisti%(ylin%, 2) = uy%
viesti$ = "Lisätään pinoon vapaa ruutu " + nimet$(ux% + 1, uy%)
ELSEIF kartta%(ux%, uy% + 1) = 1 THEN
ylin% = ylin% + 1
muisti%(ylin%, 1) = ux%
muisti%(ylin%, 2) = uy% + 1
viesti$ = "Lisätään pinoon vapaa ruutu " + nimet$(ux%, uy% + 1)
ELSEIF kartta%(ux% - 1, uy%) = 1 THEN
ylin% = ylin% + 1
muisti%(ylin%, 1) = ux% - 1
muisti%(ylin%, 2) = uy%
viesti$ = "Lisätään pinoon vapaa ruutu " + nimet$(ux% - 1, uy%)
ELSEIF kartta%(ux%, uy% - 1) = 1 THEN
ylin% = ylin% + 1
muisti%(ylin%, 1) = ux%
muisti%(ylin%, 2) = uy% - 1
viesti$ = "Lisätään pinoon vapaa ruutu " + nimet$(ux%, uy% - 1)
ELSE
ylin% = ylin% - 1
poisto% = 1
viesti$ = "Poistetaan pinosta käsitelty ruutu " + nimet$(ux%, uy%)
END IF
IF poisto% = 0 THEN
LOCATE (ylin% - 1) MOD 20 + 2, 24 + ((ylin% - 1) \ 20) * 4
PRINT nimet$(muisti%(ylin%, 1), muisti%(ylin%, 2))
ELSE
LOCATE ylin% MOD 20 + 2, 24 + (ylin% \ 20) * 4
PRINT "xx"
END IF
GOSUB odota
LOOP
loppu:
SLEEP
SCREEN 0
END
odota:
LOCATE 23: PRINT LEFT$(viesti$ + SPACE$(40), 40)
IF piirto$ = "N" THEN
a! = TIMER
WHILE TIMER - a! < .2: WEND
ELSEIF piirto$ = "H" THEN
a! = TIMER
WHILE TIMER - a! < .8: WEND
ELSEIF piirto$ = "A" THEN
WHILE INKEY$ = "": WEND
END IF
RETURN
labya:
DATA "#########"
DATA "# #"
DATA "# ##### #"
DATA "#* # #"
DATA "### # # #"
DATA "# # # # #"
DATA "# # # ###"
DATA "# # "
DATA "#########"
labyb:
DATA "#########"
DATA "# #"
DATA "# ## ## #"
DATA "# ## ## #"
DATA "# * #"
DATA "# ## ## #"
DATA "# ## ## #"
DATA "# ## #"
DATA "####### #"
labyc:
DATA "#########"
DATA " * #"
DATA "####### #"
DATA "# #"
DATA "### ### #"
DATA "# # # # #"
DATA "# # # # #"
DATA "# # #"
DATA "#########"Kommentit
Saisiko EXE:ä? Basic:ini reistailee :( Sekoittaa kaiken sekavaksi...
Antti Laaksonen [02.09.2007 21:59:47]
Toki, ohjelman voi noutaa käännettynä osoitteesta:
http://koti.mbnet.fi/pllk/muut/LABY2.EXE
Varmaan kelpo vinkki, mutta en tiedä onko QBasic mukavin kieli algoritmien esittelemiseen.
Antti kirjoitti:
Labyrintin sisältä löytää ulos sekä leveyssuuntaisella että syvyyssuuntaisella haulla, mutta välillä erot algoritmien tehokkuudessa ja muistinkäytössä ovat suuria.
Luin jutun läpi ja odotin saavani tähän jotain tarkennusta. Äkkiseltään tuntuisi että keskimäärin kumpikin on yhtä tehokas. Eli olisi lähinnä tuurista kiinni kumpi on tehokkaampi. Onko tästä jotain tarkempaa tietoa?
Antti Laaksonen [07.09.2007 14:03:15]
Leveyshaun hyviä puolia ovat, että se löytää varmasti lyhimmän reitin (ja kaikki alireitit matkan varrella käsiteltyihin ruutuihin ovat myös lyhimpiä) eikä joudu koluamaan pitkiä umpikujia. Tosiaankin riippuu hyvin paljon labyrintin rakenteesta ja siitä, mihin suuntaan syvyyshaku sattuu kulloinkin menemään, kumpi algoritmi lopulta on yksittäisessä tapauksessa tehokkaampi.
Tämä labyrinttiesimerkki vääristää tilannetta muistinkäytön suhteen, koska labyrintti on jo valmiina muistissa ja molemmat algoritmit voivat tehdä siihen merkintöjä varaamatta lisää muistia. Mutta jos hakuverkkoa muodostetaan vasta ohjelman suorituksen aikana, leveyshaku tarvitsee paljon lisämuistia, koska se joutuu pitämään kirjaa kaikista solmuista, joissa on jo käyty. Syvyyshaun taas täytyy tallentaa muistiin vain yksi reitti kerrallaan. Toisaalta syvyyshaku voi joutua todella pahasti harhateille, jos se lähtee tutkimaan valtavaa verkkoa (joka ei edes ehkä kokonaisuudessaan mahdu muistiin) väärästä suunnasta.
Syvyyshaun vähäinen muistinkäyttö ja leveyshaun lyhimmän reitin löytäminen voidaan jotenkuten yhdistää suorittamalla peräkkäisiä syvyyshakuja, joissa reitin pituus on rajoitettu ja suurinta pituutta kasvatetaan hakujen välillä. Tällöin syvyyshaku saadaan pidettyä aisoissa, mutta muistia ei kulu sen enempää kuin tavallisessa syvyyshaussakaan. Tämä ratkaisu on selvästi leveyshakua hitaampi, koska syvyyshakuja tehdään yleensä useita, mutta näin vältetään leveyshaun muistinkulutusongelmat.
Tuossa syvyyshaun syvyyden rajoittamisessa tulee vaan ongelma, jos se oikea reitti on pidempi kuin sallittu maksimipituus. Tällöin jouduttaisiin epäonnistumisen jälkeen kasvattamaan maksimisyvyyttä ja tekemään kaikki alusta.
Antti Laaksonen [10.09.2007 19:08:34]
Niin siinä valitettavasti käy. Mutta jos tavallinen syvyyshaku tai leveyshaku ei löydä ratkaisua lainkaan, suurenkin aikalisän voi hyväksyä rajoitetussa syvyyshaussa.
No, wikipedian mukaan tuo rajoitetun haun aikalisä ei ole kovinkaan merkittävä leveyshakuun verrattuna. Mitä isompi verkon haarautumiskerroin on sitä vähemmän tuo asteittainen syventäminen vaikuttaa testattavien solmujen määränä suhteessa leveyshakuun.
http://en.wikipedia.org/wiki/IDA*
Lisäksi en olisi yhtään yllättynyt, vaikka IDA* olisi nopeampi kuin leveyshaku myös tilanteissa, joissa verkko ja leveyshaun rakenteet mahtuvat kokonaan muistiin. Yleensä nimittäin ohjelmien muistinkäsittelyssä kuluu eniten aikaa ja IDA* pienimuistinkulutus vastaa leveyshaun suuri, voivat hyvinkin kallistaa nopeusedun IDA*:n puolelle. Vaikka muistia ei ladattaisikaan dynaamisesti, tulee muistinkäytön nopeutee ottaa huomioon myös kuinka hyvin algoritmin rakenteet sopivat eri välimuisteihin, mistä syystä usein vähemmän muistia käyttävä algoritmi on nopeampi ellei muistinkäytöllä saavuteta algoritmille parempaa aikakompleksisuutta.