Računalništvo

Hevristično programiranje

Ogledali si bomo primer premičnice (ang. sliding puzzle). Premičnica je igra oz. uganka, v kateri lahko premikamo ploščice po vnaprej določenih "tirih". V našem primeru se bomo osredotočili na premičnice spodnje oblike:

$$ \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & \square \end{matrix} $$

$$ \begin{matrix} 1 & 2 & 3 & 4\\ 5 & 6 & 7 & 8\\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & \square \end{matrix} $$

Zgoraj sta prikazani uganki dimenzije 3, kjer najdemo števila do vključno 8, in dimenzije 4, kjer najdemo števila do 15. Znak $\square$ predstavlja prazno mesto, torej mesto na katerega lahko premaknemo sosednje ploščice.

Uganka je rešena, ko so številke urejene od najmanjše do največje po vrsticah in stolpcih in vrsticah, kot prikazujeta zgornja diagrama.

Naloga 1

Stanje uganke bomo predstavili z matriko, t.j., standardno s seznamom seznamov. Na mesto na katerem trenutno ni ploščice, torej na mesto brez številke, bomo postavili vrednost None.

Sestavite funkcijo resitev(n), ki sestavi matriko, ki predstavlja rešeno uganko dimenzije $n$.

Naloga 2

Naložite in preglejte kodo v datoteki uganka.py. Čemu je namenjen razred Stanje? Kolikšna je cena premika ploščice?

Naložite si še datoteko preiskovanje.py, ki vsebuje razred za preiskovanje Preisci, ki ga je profesor predstavil na predavanjih.

Nato z uporabo razreda Stanje sestavite razred Uganka, ki naj ustreza zahtevam razreda Preisci. Poleg metod zacetno, resitev, razvejaj ne pozabite še na konstruktor __init__, ki naj sprejme in nastavi začetno stanje uganke.

Naloga 3

Na spodnji uganki (uganka1 v uganka.py) poženite preiskovanje s strategijo najprej najboljši. Koliko različnih stanj razveja?

$$ \begin{matrix} 4 & \square & 1\\ 7 & 2 & 3\\ 5 & 8 & 6\\ \end{matrix} $$

Naloga 4

Razredu Uganka dodajte hevristiko h. Ta naj prešteje koliko ploščic (tu $\square$ štejemo kot ploščico) je na napačnem mestu. Na primer, v stanju iz naloge 3, so na napačnih mestih 4, $\square$, 1, 7, 2, 3 5 in 6, torej bo vrednost hevristike 8.

Zgornjo uganko preiščite še s strategijo A*. Kako se ta preiskava primerja s tisto iz naloge 3?

Naloga 5

Ogledali si bomo še drugačno hevristiko. Namesto, da bi opazovali koliko ploščic je na napačnih mestih, bomo izračunali koliko so oddaljene od svoje prave pozicije.

Po hitrem premisleku lahko ugotovimo, da so prave koordinate za vrednost v, t.j., tiste ki jo v zavzame v rešeni uganki, natanko ((v - 1) // n, (v - 1) % n). Če se na koordinatah (i, j) nahaja vrednost v, je odstopanje na teh koordinatah enako natanko

abs(i - (v - 1) // n) + abs(j - (v - 1) % n)

razen, če je v ravno None; v tem primeru je odstopanje za koordinate (i, j) enako

abs(i - (n - 1)) + abs(j - (n - 1))

Primer: v zgornji uganki je na koordinatah (0, 0) vrednost 4. Prave koordinate vrednosti 4 so (1, 0), torej je odstopanje za koordinate (0, 0) enako 1. Takemu odstopanju pravimo tudi Manhattanska razdalja med dvema koordinatama.

Hevristiko tedaj definiramo kot vsoto odstopanj preko vseh možnih koordinat. Da bomo lahko hevristiki primerjali ne da bi si pokvarili razred Uganka, bomo sestavili razred Uganka2, ki bo vse dedoval od razreda Uganka. Metodo za hevristiko h bomo nato ponovno definirali kot spodaj:

class Uganka2(Uganka):
    def h(self, s):
        pass

Razredu Uganka2 ustrezno popravite metodo h tako, da bo računala novo hevristiko.

Naloga 6

Primerjajte preiskovanje z obema hevristikama na spodnjih ugankah (uganka2, uganka3 in uganka4 v uganka.py).

$$ \begin{matrix} 2 & 7 & 3\\ 5 & 1 & 6\\ 4 & 8 & \square\\ \end{matrix} $$ $$ \begin{matrix} 7 & 1 & 3\\ 2 & 4 & \square\\ 5 & 8 & 6\\ \end{matrix} $$ $$ \begin{matrix} 2 & 5 & 3\\ 1 & 7 & 6\\ \square& 4 & 8\\ \end{matrix} $$

Naloga 7 (premislek)

Premislite ali oz. zakaj sta predlagani hevristiki sprejemljivi.