Е. И. Большакова , М. Г. Мальковский , В. Н. Пильщиков - Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие)

цели. Имеется также некоторое множество операций, или ходов, переводящих одну конфигурацию в другую. Именно из таких ходов состоит искомое решение задачи, которое можно в принципе получить методом проб и ошибок. Действительно, отправляясь от начальной ситуации, можно построить конфигурации, возникающие в результате выполнения возможных в этой ситуации ходов, затем построить множество конфигураций, получающихся после применения следующего хода, и так далее – пока не будет достигнута целевая конфигурация.
Введем теперь основные понятия, используемые при формализации задачи в пространстве состояний. Центральным из них является понятие состояния задачи. Например, для игры в пятнадцать (или в восемь) состояние – это просто некоторая конкретная конфигурация фишек.
Среди всех состояний задачи выделяются начальное состояние и целевое состояние, в совокупности определяющие задачу, которую надо решить  примеры их приведены на рис.1.
Другим важным понятием является понятие оператора, т.е. допустимого хода в задаче. Оператор преобразует одно состояние в другое, являясь по сути функцией, определенной на множестве состояний и принимающей значения из этого множества. Для игры в пятнадцать или в восемь удобнее выделить четыре оператора, соответствующие перемещениям пустой клетки (фишки-«пустышки») влево, вправо, вверх, вниз. В некоторых случаях оператор может оказаться неприменимым к какому-то состоянию: например, операторы сдвига вправо и вниз неприменимы, если пустая клетка расположена в правом нижнем углу. Значит, в общем случае оператор является частично определенной функцией отображения состояний.
В терминах состояний и операторов решение задачи есть определенная последовательность операторов, преобразующая начальное состояние в целевое. Решение задачи ищется в пространстве состояний – множестве всех состояний, достижимых из начального состояния при помощи заданных операторов. Например, в игре в пятнадцать или в восемь пространство состояний состоит из всех конфигураций фишек, которые могут быть образованы в результате возможных перемещений фишек.
Пространство состояний можно представить в виде направленного графа, вершины которого соответствуют состояниям, а дуги (ребра) – применяемым операторам. Указанные в виде стрелок направления соответствуют движению от вершины-аргумента применяемого оператора к результирующей вершине. Тогда решением задачи будет путь в этом графе, ведущий от начального состояния к целевому. На рис.2 показана часть пространства состояний для игры в пятнадцать: в каждой вершине помещена та конфигурация фишек, которую она представляет. Все дуги между вершинами являются двунаправленными, поскольку в этой головоломке для любого оператора есть обратный ему (точнее, множество операторов состоит из двух пар взаимно-обратных операторов: влево-вправо, вверх-вниз).






Рис. 2. Часть пространства состояний для игры в пятнадцать
Пространства состояний могут быть большими и даже бесконечными, но в любом случае предполагается счетность множества состояний.
Таким образом, в подходе к решению задачи с использованием пространства состояний задача рассматривается как тройка (S­I , O, SG) , где
SI – начальное состояние;
O – конечное множество операторов, действующих на не более чем счетном множестве состояний;
SG – целевое состояние.
Дальнейшая формализация решения задачи с использованием пространства состояний предполагает выбор некоторой конкретной формы описания состояний задачи. Для этого могут применяться любые подходящие структуры – строки, массивы, списки, деревья и т.п. Например, для игры в пятнадцать или восемь наиболее естественной формой описания состояния будет двумерный массив. Заметим, что от выбора формы описания состояния зависит в общем случае сложность задания операторов задачи, которые должны быть также определены при формализации задачи в пространстве состояний.
Если для игры в пятнадцать средством формализации выступает язык программирования Лисп или Паскаль, то операторы задачи могут быть описаны в виде четырех соответствующих функций языка. При использовании же продук­ционного языка, эти операторы задаются в виде правил продукций вида: «исход­ное состояние  результирующее состояние» (см. [Нильсон73, раздел 2.2]).
В рассмотренных на рис.1 примерах задач искомое целевое состояние задается явно, т.е. --">