2) Pretraživanje prostora stanja Flashcards
Opisati formalnu definiciju problema pretražvanja prostora stanja i dati primjere
Problem pretraživanja stanja sastoji se od trenutnog stanja, funkcije sljedbenika i predikata koji je točan samo u ciljnom stanju. Primjeri su sudoku, hanojski tornjevi, rubikova kocka
Razlikovati izmedu prostora stanja i stabla pretraživanja
Prostor stanja je skup mogućih stanja s vezama. Stablo pretraživanja se gradi prolaskom kroz usmjereni graf tako da proširujemo čvorove. Stablo se sastoji od zatvorenih čvorova i otvorenih čvorova tj fronte
Definirati i objasniti opći algoritam pretraživanja
Na početku se u open listi nalazi samo inicijalni čvor.
U petlji dok god lista open nije prazna :
trenutni čvor je prvi čvor iz liste open. Ako je trenutni čvor također ciljni, algoritam se zaustavlja. Inače u listu open dodajemo čvorove koji slijede trenutnom čvoru.
Definirati osnovna svojstva problema pretraživanja prostora stanja i dati primjere
|S| – broj stanja
b – faktor grananja stabla pretraživanja
d – dubina optimalnog rješenja u stablu pretraživanja
m – maksimalna dubina stabla pretraživanja (moguće ∞)
Analizirati dani problem pretraživanja prema njegovim osnovnim svojstvima
Odrediti broj stanja, faktor grananja, dubinu optimalnog rješenja i
maksimalnu dubinu stabla
Definirati osnovna svojstva algoritama pretraživanja prostora stanja
Potpunost (engl. completeness) – algoritam je potpun akko pronalazi
rješenje uvijek kada ono postoji
2 Optimalnost (engl. optimality, admissibility) – algoritam je optimalan
akko pronalazi optimalno rješenje (ono s najmanjom cijenom)
3 Vremenska složenost (broj generiranih čvorova)
4 Prostorna složenost (broj pohranjenih čvorova)
Definirati i objasniti algoritam pretraživanja u širinu i njegova svojstva
Jednostavno slijepo pretraživanje, pretražujemo razinu po razinu
Na početku se u open listi nalazi samo inicijalni čvor.
U petlji dok god lista open nije prazna:
trenutni čvor je prvi čvor iz liste open. Ako je trenutni čvor također ciljni, algoritam se zaustavlja. Inače u listu open NA KRAJ dodajemo čvorove koji slijede trenutnom čvoru.
LIsta open je QUEUE (Red)
Svojstva:
Optimalnost: da
Potpunost: da
Vremenska složenost: O(b^(d+1))
Prostorna složenost: O(b^(d+1))
Definirati i objasniti algoritam pretraživanja s jednolikom cijenom i njegova svojstva
Jednostavni slijepi algoritam poput pretraživanja u širinu, ali uzimamo u obzir udaljenost između čvorova.
Na početku se u open listi nalazi samo inicijalni čvor.
U petlji dok god lista open nije prazna:
trenutni čvor je prvi čvor iz liste open. Ako je trenutni čvor također ciljni, algoritam se zaustavlja. Inače u listu open NA KRAJ SORTIRANO dodajemo čvorove koji slijede trenutnom čvoru.
Lista open je priority queue
Svojstva:
Optimalnost: da
Potpunost: da
Vremenska složenost: O(b^(d+[C/E]))
Prostorna složenost: O(b^(d+[C/E]))
Definirati i objasniti algoritam pretraživanja u dubinu i njegova svojstva
Na početku se u open listi nalazi samo inicijalni čvor.
U petlji dok god lista open nije prazna:
trenutni čvor je prvi čvor iz liste open. Ako je trenutni čvor također ciljni, algoritam se zaustavlja. Inače u listu open NA POČETAK dodajemo čvorove koji slijede trenutnom čvoru.
Lista open je stog
Svojstva:
Optimalnost: ne (ide razinu po razinu)
Potpunost: ne (može zapeti u petlji)
Vremenska složenost: O(bm) (ako ne pamtimo open nego samo sljedeći, onda je samo O(m)
Prostorna složenost: O(b^m)
Definirati i objasniti algoritam iterativnog pretraživanja u dubinu i njegova svojstva
Kao pretraživanje u dubinu ali ograničimo na neku dubinu.
Svojstva:
Optimalnost: ne (ide razinu po razinu)
Potpunost: ne (može biti d >k)
Vremenska složenost: O(bk)
Prostorna složenost: O(b^k)
Primijeniti algoritme slijepog pretraživanja na jednostavne probleme
pravilno gradi stablo
Vrednovati algoritme slijepog pretraživanja po njihovim osnovnim svojstvima
sastavi tablicu
