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 ${\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.

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.^[1]

• 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.^[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

Reference

1. Poole, David; Mackworth, Alan. „3.5 Uninformed Search Strategies‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition”. artint.info. Приступљено 7. 12. 2017.CS1 одржавање: Формат датума (веза)
2. Poole, David; Mackworth, Alan. „3.6 Heuristic Search‣ Chapter 3 Searching for Solutions ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition”. artint.info. Приступљено 7. 12. 2017.CS1 одржавање: Формат датума (веза)

Literatura

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