Пространство состояний, дерево решений. Основные виды поиска решения.

Задача, предъявленная для решения ЭС по своему заданию определяет круг объектов, действий, законов и т.п. необходимых для ее решения.

Все, что необходимо знать для решения задачи составляет предметную область, которую формализуют в виде модели предметной области (МПО) следующим образом:

МПО: <X, C, R, G>,

где X – множество имен(объектов), с которыми имеем дело при решении задачи; C- множество имен свойств (состояний) объектов; R – множество имен отношений, в которые могут вступать объекты моделируемой предметной области; G – множество имен операций (действий), которые допустимы с этими объектами через изменение их свойств и отношений между ними.

Множества X, C, R, G задают концептуальную модель предметной области, они определяют ее статическую структуру. Для перехода к модели предметной области необходимо задать пространство состояний.

Задача поиска решений в ЭС заключается в том, чтобы перевести предметную область из состояния (начального) в некоторое заданное, определяемое как целевое.

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

Методом представления пространства состояний и поиска решений задачи является метод, графической моделью которого стал граф или так называемое дерево решений.

Если отождествить состояние Sн с корнем или начальной вершиной графа-дерева, то, применяя к Sн какой-либо оператор g1 G, мы порождаем новое состояние S₁, образуя тем самым следующую вершину графа (рис. 1).

Sн

g1 g2

S₁ S₂

g3 g4

S ₃ S₄

g6 g5

 

S₆ S₅

g7 g8

S₇ Sц

 

Рис. 1. Граф решения задачи

Эта новая вершина может быть промежуточной или целевой. Если вершина промежуточная, то процесс порождения новых вершин (с помощью операторов gi) будет продолжен, пока не найдется целевая.

Общая процедура построения дерева решений в пространстве состояний при этом выглядит следующим образом.

1). К корню дерева (Sн) применяются операторы gi из множества G (их может быть несколько). Полученные при этом вершины образуют первый уровень новых вершин.

2). Каждая из вновь полученных вершин проверяется, не является ли она целевой. Если нет, то процесс продолжается по отношению к каждой из них. Образуется второй уровень вершин. Если к какой-либо вершине никакой оператор из G не применим, то эта вершина становится терминальной (конечной). Как видим, на каждом шаге проводятся две операции: порождение новой вершины и проверка, не является ли новая вершина целевой, т.е. совпадающей с целевым состоянием.

3). Когда целевая вершина найдена, в обратном направлении (от цели к началу) просматриваются указатели дуг и выделяется путь решения. Практически этот путь удобнее отображать посредством операторов, связанных с этими дугами (см. рис. 1).

В общем случае количество вершин может быть большим. Их последовательное раскрытие, анализ и пометка пути осложняют задачу. Возникает проблема перебора вершин: в каком порядке они будут порождаться и анализироваться. Здесь возможны следующие варианты:

1) вершины раскрываются в том же порядке, в котором они порождаются, то такой перебор называется полным перебором в ширину;

2) на каждом шаге первой раскрывается вершина, которая была построена последней, такой процесс называется полным перебором в глубину.

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

3) если есть некоторая дополнительная (эвристическая) информация о предметной области, которая позволяет делать суждения о характере графа пространства состояний и расположения цели, то такой метод построения графа называется эвристическим ("эвристический" означает "служащий открытию"). Эвристическая информация, опирающаяся, как правило, на предыдущий опыт, позволяет выполнять поиск в наиболее перспективных направлениях.

Говоря о графе, будем рассматривать только один наиболее простой его тип - граф типа "дерево". Как известно, деревом называется граф, каждая вершина которого имеет только одну вершину, непосредственно предшествующую ей (родительскую), за исключением вершины-корня, которая предшествующих вершин не имеет.