Iti0210lab23
Sisukord
Tee leidmine kaardil
Sissejuhatus
Lahendame ülesannet, kus tuleb leida teekond kaardil alguspunktist soovitud sihtkohta. Ülesanne koosneb järgmistest osadest:
- laiutiotsing (väike kaart)
- otsing suuremal kaardil
- heuristiline otsing
Kasutame mitut erinevat algoritmi. Uurime, kui efektiivselt nad lahenduse leiavad ja kas see on parim lahendus.
Esimene katsetus otsinguga
Antud on kaks kaarti. Kaardi formaat on ASCII-art - ebakonventsionaalne, aga harjutusülesandeks kõlbab küll. Tuleb leida tee kaardil alguspunktist "s" teemandini "D". Seejuures ei tohi tee läbida kohti, kus on laava (tähistus "*"). Liikuda tohib ainult neljas suunas: üles, alla, vasakule ja paremale (mitte diagonaalis).
Kaart 1:
lava_map1 = [
" ** ** ",
" *** D *** ",
" *** ",
" ***** ",
" **** ******** ",
" *** *******",
" ** ******",
"***** **** *** ",
"***** ** ",
"*** ",
" ** ******",
"** *** *******",
"*** ***** ",
" ",
" s ",
]
start_row=14
start_col=16
Kaart 2:
lava_map2 = [
" ********************** ",
" ******* D ********** ",
" ******* ",
" **************** **********",
"*********** ******** ",
" *******************",
" ******** ******************",
"******** ****",
"***** ************ ",
"*** ********* ",
"* ****** ************",
"***************** *******",
"*** **** ***** ",
" ",
" s ",
]
start_row=14
start_col=16
Seda kaarti võib vaadata kui ruudustikku, kus iga ruutu tähistab tema x ja y koordinaat. Tee leidmiseks kasutame laiutiotsingut (breadth first search, BFS). Laiutiotsingu tööpõhimõtte animatsioone vaata siit lehelt. Sel viisil otsides laava vältimine on tegelikult lihtne - tuleb lihtsalt laavaga ruute käsitleda, nagu läbimatut seina. Kui algoritm on tee leidnud, siis uurime ka, kuidas tema leitud tulemust tõlgendada ja visualiseerida.
Enne, kui otsingut saab alustada, tuleb kindlaks määrata alguspunkt. Seega otsusta, mida tähistad x ja y koordinaatidena (üks peaks olema read, teine veerud). Mõlemal kaardil on alguspunkt 14. reas, 16. veerus, kusjuures Pythoni indeksite nummerdamine hakkab 0-st.
Samuti tee kindlaks kaardi suurus x ja y suunas. Otsingu implementeerimisel tuleb paratamatult kontrollida, kas mingi koordinaadipaar on kaardil või sellest väljas.
Laiutiotsing
Kasutame kooditükki siit.
frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
Antud kood alustab otsimist start punktist ning leiab tegelikult teed kõikidesse punktidesse graafil graph. Seejuures saab leitud teid rekonstrueerida selle alusel, et kui came_from[A] == B siis tee punktist A alguspunkti läheb läbi B - see tähendab, et tee tuleb rekonstrueerida tagurpidi sihtpunktist alguspunkti.
Kuna meie ülesanne on pisut erinev, siis peame koodi pisut kohandama. Lisaks realiseerime selle funktsioonina, nii et oleks mugav erinevaid kaarte ette anda.
from queue import Queue
def minu_otsing(kaart, start):
# start (algolek) on näiteks tuple kujul (x, y)
frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None
while not frontier.empty():
current = frontier.get()
# meid ei huvita kõik teed, seega peaks kontrollima, kas current on teemant.
# Kui on, siis katkestame otsingu
# (ja loomulikult jätame teemandi koordinaadid meelde)
for next in graph.neighbors(current): # see osa tuleb suht palju ümber teha.
# tuleb leida sobivad naaberruudud kaardilt
# nagu ta meile ette on antud (ülal, all,
# paremal ja vasakul olev ruut)
if next not in came_from:
frontier.put(next)
came_from[next] = current
# Kui teemant on leitud, tuleb ka teekond rekonstrueerida
# mis andmestruktuurina teekonda esitada, pole oluline,
# aga loomulik viis oleks list
return path
Suuremad kaardid
Proovi nüüd otsingut kaartidel suuruses 300x300 kuni 900x900 (paremklõps ja Save as vms):
Enne kaardi kasutamist tuleb see failist laadida. Et saada samas formaadis kaart, nagu eelmises ülesandes, võib järgmist koodi kasutada:
with open("cave300x300") as f:
map_data = [l.strip() for l in f.readlines() if len(l)>1]
Alguspunktide ja teemandi asukohtade koordinaadid:
| kaart | rida | veerg | |
|---|---|---|---|
| 300x300 | start | 2 | 2 |
| goal | 295 | 257 | |
| 600x600 | start | 2 | 2 |
| goal | 598 | 595 | |
| 900x900 | start | 2 | 2 |
| goal | 898 | 895 |
Ahne otsing
Lisame nüüd heuristilise otsingu - see tähendab, et kasutame mingit meetodit et umbkaudu hinnata, mis tee kiiremini lahenduseni viib.
Inspiratsiooni heuristilise otsingu tegemiseks saame jälle siit tutorialist. Samast leiad ka animatsioone ja selgitusi nende algoritmide käitumise kohta.
Ahne otsingu ja laiutiotsingu peamine erinevus on, et ahne otsing üritab liikuda eelistatult eesmärgi suunas. Selleks valitakse alati selline järgmine punkt, mis on eesmärgile kõige lähemal. Leitud punktide automaatseks järjestamiseks kasutame PriorityQueue-t.
from queue import Queue, PriorityQueue
Tee uus greedy funktsioon, mis on koopia laiutiotsingust ja millel on lisaks parameeter goal (seda on vaja heuristiku jaoks). Muuda seda järgmiselt:
frontier on alati sorteeritud elemendi väärtuse järgi (mitte lisamise järjekorras)
frontier = PriorityQueue()
frontier.put((0, start))
Uued ruudud lisatakse koos heuristilise väärtusega, mis aitab õigesti sorteerida.
priority = h(next, goal)
frontier.put((priority, next))
Kuna järjekorra formaat muutus, siis tuleb ka sealt asju teistmoodi välja võtta:
_, current = frontier.get()
Lõpuks on meil vaja ka heuristilist funktsiooni ennast. Kuna meil on tegu ruudustikul nelja ilmakaare suunas liikumisega, siis Manhattan distance on selleks väga sobiv.
def h(node, goal):
# implementeeri ise
A*
Ahne otsingu ja A* vahel on ainult üks erinevus: esimesel juhul leitakse heuristiline väärtus f(n) = h(n), teisel juhul f(n) = g(n) + h(n). See tähendab, et ka senini läbitud teepikkus mängib järgmise punkti valimisel rolli. Sel viisil välditakse olukordi, kus konstrueeritud teekond suundub otse eesmärgi suunas, kuni kohtab takistust ning peab siis tagasi pöörduma.
Tee uus funktsioon astar, mis on ahne otsingu koopia.
Kõigepealt on vaja g(n) väärtusi meelde jätta.
cost_so_far = {}
cost_so_far[start] = 0
Heuristilise väärtuse arvutamisel tuleb senine teekond sisse arvestada. Järgmisse ruutu liikumise maksumus on alati 1. Lisaks tuleb muuta kohta, kus kontrollitakse, kas next on juba nähtud. Nimelt on võimalik, et me saabume uuesti samasse kohta lühemat teed mööda ning meid huvitab eelkõige see uus, lühem tee.
new_cost = cost_so_far[current] + 1
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + h(next, goal) # g(n) + h(n)
frontier.put((priority, next))
came_from[next] = current
Tulemused
Katseta laiutiotsingut, A*-i ja ahnet otsingut kõikidel kaartidel alates 300x300 suurusest.
Mõõda neid asju:
- lahenduse leidmiseks kulunud aeg (piisab kui on iteratsioonide arv, aga võib lisada ka aja sekundites)
- lahenduse pikkus sammudes
Nendest katsetuste tulemustest võiks kaitsmisel rääkida. Pane lühike kokkuvõte ka README faili.
Optimaalsed tulemused
Erinevate strateegiate käitumine 300x300 kaardil. Roheline tähistab otsingu läbitud ala, punane leitud teed.
Optimaalsed teepikkused
300x300 554 600x600 1247 900x900 1843
Lisaülesanded
Järgmised tegevused pole kohustuslikud, aga aitavad otsingust ja heuristikutest paremini aru saada.
Visualiseerimine
Kirjuta kood, mis leitud teekonna väljastab sellisel ASCII-art kujul (kujutatud tee on suvaline näide):
** **
*** D.... ***
*** .
. *****
**** . ********
*** . *******
** . ******
***** .**** ***
***** . **
*** .
** . ******
** ***. *******
*** .. *****
.
s
Heuristikute käitumine
Implementeeri teine heuristiline funktsioon:
def h2(node, goal):
return max(abs(node[0]-goal[0]), abs(node[1]-goal[1])) # suurim koordinaadi nihe
Võrdle A* ja ahne otsingu käitumist mõlema heuristikuga kõigil kaartidel.
Seejärel muuda otsingut nii, et lubataks diagonaalis liikumisi. Mis mõju on sellel heuristikute efektiivsusele, eriti A* puhul?
