Algoritmi pretraživanja u ekspertskim sistemima

Pretraživanje se odnosi na nalaženje nekog podatka u skupu podataka organizovanih na određeni način, a na osnovu određene karakteristike tog podatka.

Takvo pretraživanje je određeno sledećim parametrima:

  • organizacijom i vrstom pristupa podacima,
  • karakteristikom podatka koji se traži,
  • strategijom pretraživanja

Pretraživanje kao metoda rešavanja problema

уреди

Pretraživanje u ekspertskim sistemima ima drugačiji smisao. Ono se sastoji u nalaženju rešenja nekog problema do koga se inače teško može doći na opšti način primenom metoda klasičnog programiranja.

  • Primer 1 - putovanje iz jednog mesta u drugo. Od jednog mesta do drugog može postojati više puteva različitih dužina i oni se mogu prikazati u vidu stabla. Ako bi se računaru dostavio opis ove putne mreže, njegov zadatak bi bio da izabere onaj put od jednog mesta do drugog koji je najkraći. Problem bi se mogao postaviti u složenijoj formi, ako bi uključili kriterijum izbora kvaliteta puta i njegove opterećenosti. Može i u vidu mreže, koja se dalje može prevesti u oblik stabla. Ova transformacija mora biti ekvivalentna sa tačke gledišta pretraživanja, to znači, da važi za svako C { i = 1, 2, ...}, gde je C cilj, a { i = 1, 2, ...} skup rešenja. Model pretraživanja zasnovan na strukturi stabla je jednostavniji od mrežnog modela, međutim transformacija mrežnog modela u model stabla nije uvek jednostavna.
  • Primer 2 - dve posude od 4 i 3 litra bez mernih oznaka. Kako se posuda od 4 litra može napuniti tačno do polovine svoje zapremine?
  • Primer 3 - igranje šaha. Cilj bi se mogao definisati kao ostvarivanje pozicije na šahovskoj tabli u kome protivnik nema na raspolaganju dozvoljen potez i njegov kralj je napadnut. Definisati precizno problem, odrediti njegove početne pozicije koje čine prihvatljivo rešenje problema Analizirati problem u cilju otkrivanja njegovih bitnih svojstava koje mogu da budu odlučujuće u izboru metode za njegovo rešavanje. Odabrati najbolju metodu i primeniti je u rešavanju problema.

Podela strategija pretraživanja ekspretskih sistema

уреди
Za pronalaženje neke putanje
  • po dubini
  • po širini
  • generišii testiraj
  • planinarenje
  • prvo najbolji
  • Grananje i ograničavanje
Za pronalaženje optimalne putanje
  • A
  • AO
  • Zadovoljavanje ograničenja
  • Metoda sukcesivnih aproksimacija
  • Britanski muzej
  • Skoči i ograniči
Igre
  • Minimaks
  • Alfa-beta podešavanje
  • Progresivno proširivanje
  • Heurističko podešavanje
  • Heurističko nastavljanje

Literatura

уреди

Vidi još

уреди