Лекция: Поиск в пространстве состояний.

Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации.
Пусть задана тройка (S0, F, SТ), где S0 — множество начальных состояний (условия задачи), F — множество операторов задачи, отображающих одни состояния в другие, SТ — множество конечных (целевых) состояний (решений задачи).
Цель: определять такую последовательность операторов, которая преобразует начальные состояния в конечные.
Процесс решения в виде графа G=(Х, Y), где X={х0, х1,...} — множество (в общем случае бесконечное) вершин графа, состояний, а Y — множество, содержащее пары вершин (xi, xj), (xi, xj)?X. Если каждая пара (xi, xj) неупорядочена, то ее называют ребром, а граф — неориентированным. Если для каждой пары (xi, xj) задан порядок (направление), то пару (xi, xj) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (xi, xj) называют концевыми точками ребра (дуги).
Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (xi, xj) свидетельствует о существовании некоторого оператора f (f?F), преобразующего состояние, соответствующее вершине xi, в состояние xj. Для некоторой вершины xi выделяем множество всех направленных пар (xi, xj)?Y, т.е. множество дуг, исходящих из вершины хi, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины xi, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине хi.
В множестве вершин X выделяют подмножество вершин Х0 принадлежит Х, соответствующее множеству начальных состояний (So),, и подмножество вершин Хт?X, соответствующее множеству конечных (целевых) состояний (SТ). Множество Хт может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.
Отметим, что граф С может быть задан явно и неявно. Неявное задание графа G стоит в определении множества Х0? Х (соответствующего множеству начальных состояний) и множества операторов, которые, будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.
Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина х0? Х, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми, или терминальными (т.е. вершинами, к которым нельзя применить никаких операторов). В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти.
На практике требуется обеспечить полноту поиска, т.е. организовать поиск так, чтобы все целевые вершины были найдены, если они существуют. Надежным способом обеспечения полноты является полный перебор всех вершин. Для задания процесса перебора необходимо определить. порядок, в котором будут перебираться вершины графа. Обычно выделяют два основных способа поиска:

• поиск в глубину (сначала раскрывается та вершина, которая была построена самой последней). Рисунок 7.a.
• поиск в ширину. (вершины раскрываются в том же порядке, в котором они порождаются.) Рисунок 7.б.

Рисунок 7. Пространство состояний, построенное поиском в глубину (а) и поиском в ширину (б).

Целевые вершины помечены черными квадратами, а терминальные — белыми квадратами. При использовании каждого из способов могут быть найдены все решения. При переборе всего пространства оба метода будут анализировать одинаковое количество вершин, однако метод поиска в ширину будет требовать существенно больше памяти, так как он запоминает все пути поиска (а не один, как при поиске в глубину).