3) Heurističko pretraživanje

Question 1

Razlikovati izmedu algoritama slijepog i heurističkog pretraživanja prostora stanja

Answer 1

U slijepom pretraživanju za sljedeće trenutno stanje uzimamo ono koje po redu dolazi u listi open, a u nju se sprema ili po redu ili sortirano po udaljenosti između čvorova. U algoritmima slijepog pretraživanja sljedeći trenutni čvor biramo pomoću heurističkih pravila koja poboljšavaju učinkovitost problema.

Question 2

Definirati i objasniti heurističku funkciju i dati primjere

Answer 2

iskustvena pravila koja pretraživanje brže usmjere prema cilju.
Heuristička funkcija pridjeljuje svakom stanju s iz prostora stanja procjenu udaljenosti od ciljnog stanja.
Npr. broj kvadrata udaljenosti od ciljnog mjesta u premetaljki ili rubokovoj kocki ili zračna odaljenost od naselja do naselja.

Question 3

Definirati i objasniti pohlepno pretraživanje najbolji prvi i njegova svojstva

Answer 3

Proširuje se čvor s najmanjom heurističkom vrijednosti. Pohlepan je jer ovisi samo o heuristici koja ne mora biti dobar pokazatelj.
Optimalnost: ne
Potpunost: ne (osim ako se koristi lista posjećenih stanja)
Vremenska složenost:O(b^m)
Prostorna složenost: O(b^m)

Question 4

Definirati i objasniti pretraživanje usponom na vrh i njegova svojstva

Answer 4

Kao najbolji prvi ali se posjećeni čvorovi ne pohranjuju u memoriji. Lako zaglavi u lokalnim optimumima pa se zato koristi tehnika slučajnog ponovnog restarta.
Optimalnost: ne
Potpunost: ne
Vremenska složenost:O(b)
Prostorna složenost: O(1)

Question 5

Definirati i objasniti algoritam A* i njegova svojstva

Answer 5

U obzir osim heuristik euzima i cijenu pređenog puta tj. u listu otvroenih čvorova čvorove dodaje sortirano po sumi ostvarenog puta i heuristike za taj čvor. Ako se isti čvor ponovo pronađe na upitu za ubavanje u listu open a u njoj se već nalazi ili je već obiđen, u listu open se dodaje samo ako je boljih karakteristika od onog koji je već unutra.
Optimalan: da ako je heuristika optimistična
Potpun: da
Vremenska složenost: O(min(b^(d+1), b|S|)
Prostorna složenost: O(isto)

Question 6

Definirati optimističnost heuristike i dati primjere

Answer 6

Heuristika je optimistična ako ne precjenjuje tj. nije veća od prave cijene do cilja.
h(s) <= *h(s) za svaki s. *h je prava cijena do cilja.
primjer: zračna udaljenost, hipotenuza.

Question 7

Definirati i objasniti konzistentnost heuristike i njezin utjecaj na algoritam A*

Answer 7

Heuristika je konzistentna ili monotona ako svaki čvor koji prvi ispitamo za neko stanje će biti čvor s najmanjom cijenom za to stanje, tj. za svaka dva stanja s1 i s2, heuristika od s1 će biti manja ili jednaka zbroju heuristike za stanje 2 i cijene prijelaza od stanja s1 do stanja s2.
Ako je heuristika konzistentna, to nam osigurava da ne moramo ponovo prolaziti kroz listu otvorenih čvorova popravljati jer je čvor koji prvi obiđemo onaj s najmanjom cijenom.

Question 8

Odrediti je li heuristika za dani problem optimistična i/ili konzistentna

Answer 8

Optimističnost: heuristika mora biti manja od stvarne cijene do cilja za svako stanje

Konzistentnost: heuristika svakog roditelja mora biti manja ili jednaka heuristici djeteta + cijena prijelaza od roditelja do djeteta

Question 9

Objasniti i primijeniti oblikovanje heuristike metodom relaksacije problema

Answer 9

Heuristiku oblikujemo kada želimo ubrzati algoristam smanjenjem broja generiranih čvorova. Relaksacija problema znači da stvaramo optimističniju heuristiku uklanjanjem prepreka. - Nađi bolje objašnjenje

Question 10

Primijeniti algoritme heurističkog pretraživanja na jednostavne probleme

Answer 10

prođi algoritme

Question 11

Vrednovati algoritme heurističkog pretraživanja po njihovim osnovnim svojstvima

Answer 11

nauči svojstva pojedinih algoritama