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ülesanne

(tulekul)