Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В области искусственного интеллекта и компьютерного программирования , планирования пространства состояний это процесс , используемый при разработке программ для поиска данных или решения проблем. В компьютерном алгоритме, который ищет в структуре данных фрагмент данных, например, в программе, которая ищет слово в компьютерном словаре, пространство состояний является собирательным термином для всех данных, подлежащих поиску. Точно так же программы искусственного интеллекта часто используют процесс поиска в конечном множестве возможных процедур для достижения цели, чтобы найти процедуру или лучшую процедуру для достижения цели. Вселенная возможных решений для поиска называется пространством состояний. Государственная планировка пространства это процесс принятия решения, в каких частях пространства состояний программа будет искать и в каком порядке.

Определение [ править ]

Простейшие классические алгоритмы планирования (см. Автоматическое планирование ) - это алгоритмы поиска в пространстве состояний. Это алгоритмы поиска, в которых пространство поиска является подмножеством пространства состояний: каждый узел соответствует состоянию мира, каждая дуга соответствует переходу между состояниями, а текущий план соответствует текущему пути в пространстве поиска.Прямой поиск и обратный поиск - два основных примера планирования пространства состояний .

Прямой поиск [ править ]

Поиск вперед - это алгоритм, который выполняет поиск вперед от начального состояния мира, чтобы попытаться найти состояние, удовлетворяющее формуле цели.

Поиск вперед (O, s 0 , g)

s = s 0 P = пустой план петля если s удовлетворяет g, то верните P применимо = {a | a является основным экземпляром оператора в O, а precond (a) истинно в s} если применимо = ∅, то вернуть отказ  недетерминированно выбрать действие a из применимых s = γ (s, а) P = Па

Обратный поиск [ править ]

Обратный поиск - это алгоритм, который начинается с состояния цели и возвращается к исходному состоянию. Этот метод иногда называют «обратным распространением».

Обратный поиск (O, s 0 , g)

s = s 0 P = пустой план петля если s удовлетворяет g, то верните P релевантный = {a | a - основной экземпляр оператора в O, который имеет отношение к g} если уместно = ∅, то вернуть отказ  недетерминированно выбрать действие a из релевантных P = aP  s = γ −1 (s, а)

См. Также [ править ]

Ссылки [ править ]