Pretraga prostora stanja

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 $S:\langle S,A,Action(s),Result(s,a),Cost(s,a)\rangle$, u kojem:

• $S$ je skup svih mogućih stanja;
• $A$ je skup mogućih radnji, koje se ne odnose na određeno stanje, već se odnose na ceo prostor stanja;
• $Akcija(s)$ {\displaistile Action(s)} je funkcija koja utvrđuje koju radnju je moguće izvršiti u određenom stanju;
• $Rezult(s,a)$ je funkcija koja vraća stanje postignuto izvođenjem radnje $a$ u stanju $s$
• $Cost(s,a)$ je cena izvođenja radnje $a$ u stanju $s$. 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

Literatura

• Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.