Resavanje problema koriscenjem pretrage

Question 1

Gde se najcesce koristi vestacka iteligencija ?

Answer 1

Vestacka iteligencije se prvesnstveno koristi pri resavanju problema kod kojih se pojavljuje kombinatorna eksplozija .

Question 2

Faze resavanja problema koriscenjem pretrage

Answer 2

1.Modelovanje problema
2.resavanje problema opisanog u matematickim terminima
3.interpretacija i analiza resenja

Question 3

Modelovanje problema

Answer 3

Modelovanje problema predstavlja formulisanje problema precizno,u matematickim terminima,koriscenjem pogodnih matematickih struktura.
Takva formulacija obicno ima sledece elemente:

Skup mogucih stanja:U nekim algoritmima potrebno je poznavati samo stanja koja su neposredno dostupna,dok je u nekim algoritmima potrebno poznavanje svih stanja unapred

Polazno stanje:

Test cilja:Problem je resen ako dodje do ciljnog stanja .Potrebno je da postoji raspoloziv efektivan test koji proverava da li se doslo do ciljnog stanja

Skup mogucih akcija:
U svakom koraku pretrage moze se preduzeti neki korak,neka akcija.Skup akcija moze biti isti u svakom trenutku ili se moze razlikovati od stanja do stanja

Funkcija prelaska:
Ova funkcija preslikava par stanje-akcija u novo stanje,dobijeno izborom neke akcije u nekom stanju.Stanja koja su neposredno dostupna iz nekog stanja zovemo i susedna stanja.

Funkcija cene:
Ova funkcija preslikava par stanje-akcija u numericku vrednost

Question 4

Graf prostora stanja

Answer 4

Opisuje skup mogucih stanja i mogucih akcija i svakom grafu pridruzeno je jedno stanje, a svakoj grani jedna akcija.

Question 5

Sta se desi ako funkcija prelaska nije poznata

Answer 5

Nije poznato ni u koje ce se stanje dospeti posle preduzimanja odredjene akcije i proces odlucivanja postaje kompleksniji

Question 6

Sta se desava u fazi resavanja problema?

Answer 6

U fazi resavanja problema cesto je u grafu prostora stanja potrebno pronaci cvor sa nekim svojstvima ili najkraci put do nekog cvora.
Pretrazivanjem grafa nastaje stablo pretrazivanje ili stablo pretrage.To stablo ne mora nuzno da se kreira eksplicitno,kao struktura u memoriji racunara,vec moze da se kreira samo implicitno ,procesom obilaska cvorova

Question 7

Interpretiranje i analiza resenja

Answer 7

Dobijeno resenje matematicki formulisanog problema potrebno je formulisati u terminima pocetnog problema i potreno je razumeti njegova svojstva

Question 8

Koja su najvaznija opsta svojstva algoritma pretrage?

Answer 8

Potpunost,Optimalnost,Vremenska i prostorna slozenost

Question 9

Potpunost

Answer 9

Potpunost je svojstvo koje garantuje da ce algoritam naci neko resenje problema ako resenja uopste postoje.Ovo svojstvo je pozeljno ali u nekim slucajevima nije neophodno .

Question 10

Optimalnost

Answer 10

Optimalnost je svojstvo koje garantuje nalazenje resenja sa najmanjom cenom.Optimalno resenje je resenje sa najmanjom cenom i ono ne mora biti jedinstveno .Moguce je da algoritam koji nema svojstvo optimalnosti cesto pronalazi resenja bliska optimalnom ali u znacajno kracem vremenu.

Question 11

Vremenska i prostorna slozenost

Answer 11

Vremenska i prostorna slozenost govore o tome koliko vremena i memorijskog prostora potrebno za sprovodjenje procesa pretrage .Obicno se razmatra slozenost najgoreg i prosecnog slucaja