Iti0210lab3

Heuristiline otsing

Sissejuhatus

Jätkame eelmise harjutustunni tegevust ja muudame oma otsingu heuristiliseks - see tähendab, et kasutame mingit meetodit et umbkaudu hinnata, mis tee kiiremini lahenduseni viib.

Meeldetuletuseks, otsing toimub ASCII-art formaadis kaardil. Tuleb leida tee kaardil alguspunktist "s" teemandini "D". Seejuures ei tohi tee läbida kohti, kus on laava (tähistus "*").

Implementeerime ahne otsingu ja A*-i ning katsetame neid etteantud kaartidel (paremklõps ja Save as vms):

• Fail:300x300.txt
• Fail:600x600.txt
• Fail:900x900.txt

Vabatahtlikus lisaülesandes analüüsime heuristikute käitumist.

Ettevalmistus

Enne kasutamist tuleb kaart failist laadida. Et saada samas formaadis kaart, nagu eelmises ülesandes, võib järgmist koodi kasutada:

with open("300x300.txt") as f:
    map_data = [l.strip() for l in f.readlines() if len(l)>1]

Loomulikult võib teha andmetega soovi korral edasisi teisendusi, kui selline esitus mugav ei tundu.

Lisa ka kood, mis otsib kaardilt üles "D" koordinaadid. Seda on vaja heuristilise väärtuse arvutamise jaoks.

Ahne otsing

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

Katseta A*-i ja ahnet otsingut kõikidel kaartidel. Lisa ajavõtmine ning võrdle leitud teekonna pikkusi ja funktsiooni töö aega.

Lisaülesanne

(tulekul)