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.

U pretraživanju prostora stanja, prostor stanja je formalno predstavljen kao skup ${\displaystyle S:\langle S,A,Action(s),Result(s,a),Cost(s,a)\rangle }$, u kojem:

• ${\displaystyle S}$ je skup svih mogućih stanja;
• ${\displaystyle A}$ je skup mogućih radnji, koje se ne odnose na određeno stanje, već se odnose na ceo prostor stanja;
• ${\displaystyle Akcija(s)}$ {\displaistile Action(s)} je funkcija koja utvrđuje koju radnju je moguće izvršiti u određenom stanju;
• ${\displaystyle Rezult(s,a)}$ je funkcija koja vraća stanje postignuto izvođenjem radnje ${\displaystyle a}$ u stanju ${\displaystyle s}$
• ${\displaystyle Cost(s,a)}$ je cena izvođenja radnje ${\displaystyle a}$ u stanju ${\displaystyle s}$. U mnogim prostorima stanja a je konstanta, ali to nije uvek tačno.

Prema Pulu i Makvortu, sledeće su neinformisane metode pretrage u prostoru stanja, što znači da nemaju nikakve prethodne informacije o lokaciji cilja.^[1]

• Tradicionalna pretraga u dubinu
• Pretraga u širinu
• Iterativno produbljivanje
• Pretraga po najnižim troškovima / Pretraga po uniformnog ceni (UCS)

Ove metode uzimaju lokaciju cilja u obliku heurističke funkcije.^[2] Pul i Makvort navode sledeće primere kao algoritme za informisane pretrage:

• Informisana/heuristička pretraga u dubinu
• Pohlepna najbolje-prvo pretraga
• A* Potraga