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

Lisaülesanne

(tulekul)