Pretraga prostora stanja je proces koji se koristi u oblasti računarstva, uključujući veštačku inteligenciju (VI), u kome se razmatraju uzastopne konfiguracije ili stanja instance, sa namerom da se pronađe ciljno stanje sa željenim svojstvom.
Problemi se često modeluju kao prostor stanja, skup stanja u kojima problem može biti. Skup stanja formira graf gde su dva stanja povezana ako postoji operacija koja se može izvesti da se prvo stanje transformiše u drugo.
Pretraživanje prostora stanja se često razlikuje od tradicionalnih metoda pretraživanja računarskih nauka jer je prostor stanja implicitan: tipičan graf prostora stanja je prevelik za generisanje i skladištenje u memoriji. Umesto toga, čvorovi se generišu dok se istražuju i obično se nakon toga odbacuju. Rešenje za instancu kombinatorne pretrage može se sastojati od samog ciljnog stanja, ili od puta od nekog početnog stanja do ciljnog stanja.
Reprezentacija
U pretraživanju prostora stanja, prostor stanja je formalno predstavljen kao skup , u kojem: je skup svih mogućih stanja; je skup mogućih radnji, koje se ne odnose na određeno stanje, već se odnose na ceo prostor stanja; {\displaistile Action(s)} je funkcija koja utvrđuje koju radnju je moguće izvršiti u određenom stanju; je funkcija koja vraća stanje postignuto izvođenjem radnje u stanju je cena izvođenja radnje u stanju . U mnogim prostorima stanja a je konstanta, ali to nije uvek tačno.
Primeri algoritama pretraživanja u prostoru stanja Neinformirana potraga
Prema Pulu i Makvortu, sledeće su neinformisane metode pretrage u prostoru stanja, što znači da nemaju nikakve prethodne informacije o lokaciji cilja. Tradicionalna pretraga u dubinu Pretraga u širinu Iterativno produbljivanje Pretraga po najnižim troškovima / Pretraga po uniformnog ceni (UCS)
Informirana potraga
Ove metode uzimaju lokaciju cilja u obliku heurističke funkcije. Pul i Makvort navode sledeće primere kao algoritme za informisane pretrage: Informisana/heuristička pretraga u dubinu Pohlepna najbolje-prvo pretraga A* Potraga
Reference
Literatura
Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.
Категорија:Алгоритми претраживања