Претрага простора стања

Претрага простора стања је процес који се користи у области рачунарства, укључујући вештачку интелигенцију (VI), у коме се разматрају узастопне конфигурације или стања инстанце, са намером да се пронађе циљно стање са жељеним својством.

Проблеми се често моделују као простор стања, скуп стања у којима проблем може бити. Скуп стања формира граф где су два стања повезана ако постоји операција која се може извести да се прво стање трансформише у друго.

Претраживање простора стања се често разликује од традиционалних метода претраживања рачунарских наука јер је простор стања имплицитан: типичан граф простора стања је превелик за генерисање и складиштење у меморији. Уместо тога, чворови се генеришу док се истражују и обично се након тога одбацују. Решење за инстанцу комбинаторне претраге може се састојати од самог циљног стања, или од пута од неког почетног стања до циљног стања.

Репрезентација

У претраживању простора стања, простор стања је формално представљен као скуп $S:\langle S,A,Action(s),Result(s,a),Cost(s,a)\rangle$ , у којем:

$S$ је скуп свих могућих стања;
$A$ је скуп могућих радњи, које се не односе на одређено стање, већ се односе на цео простор стања;
$Akcija(s)$ {\дисплаистиле Ацтион(с)} је функција која утврђује коју радњу је могуће извршити у одређеном стању;
$Rezult(s,a)$ је функција која враћа стање постигнуто извођењем радње $a$ у стању $s$
$Cost(s,a)$ је цена извођења радње $a$ у стању $s$ . У многим просторима стања а је константа, али то није увек тачно.

Примери алгоритама претраживања у простору стања

Неинформирана потрага

Према Пулу и Макворту, следеће су неинформисане методе претраге у простору стања, што значи да немају никакве претходне информације о локацији циља.^[1]

Информирана потрага

Ове методе узимају локацију циља у облику хеуристичке функције.^[2] Пул и Макворт наводе следеће примере као алгоритме за информисане претраге:

Информисана/хеуристичка претрага у дубину
Похлепна најбоље-прво претрага
А* Потрага

Референце

^ Пооле, Давид; Мацкwортх, Алан. „3.5 Унинформед Сеарцх Стратегиес‣ Цхаптер 3 Сеарцхинг фор Солутионс ‣ Артифициал Интеллигенце: Фоундатионс оф Цомпутатионал Агентс, 2нд Едитион”. артинт.инфо. Приступљено 7. 12. 2017.
^ Пооле, Давид; Мацкwортх, Алан. „3.6 Хеуристиц Сеарцх‣ Цхаптер 3 Сеарцхинг фор Солутионс ‣ Артифициал Интеллигенце: Фоундатионс оф Цомпутатионал Агентс, 2нд Едитион”. артинт.инфо. Приступљено 7. 12. 2017.

Литература

Стуарт Ј. Русселл анд Петер Норвиг (1995). Артифициал Интеллигенце: А Модерн Аппроацх. Прентице Халл.

[1] Пооле, Давид; Мацкwортх, Алан. „3.5 Унинформед Сеарцх Стратегиес‣ Цхаптер 3 Сеарцхинг фор Солутионс ‣ Артифициал Интеллигенце: Фоундатионс оф Цомпутатионал Агентс, 2нд Едитион”. артинт.инфо. Приступљено 7. 12. 2017.

[2] Пооле, Давид; Мацкwортх, Алан. „3.6 Хеуристиц Сеарцх‣ Цхаптер 3 Сеарцхинг фор Солутионс ‣ Артифициал Интеллигенце: Фоундатионс оф Цомпутатионал Агентс, 2нд Едитион”. артинт.инфо. Приступљено 7. 12. 2017.

[1]

[2]