МЕТОДЫ ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ

Методы решения задач, основанные на сведении 'их к поиску, зависят от особенностей предметной области, в которой решается задача, и от требований, предъявляемых пользователем к решению. Особенности предметной области:

· объем пространства, в котором предстоит искать решение;

· степень изменяемости области во времени и пространстве (статические и динамические области);

· полнота модели, описывающей область, если модель не полна, то для описания области используют несколько моделей, дополняющих друг друга;

· определенность данных о решаемой задаче, степень точности (ошибочности) и полноты (неполноты) данных.

Требования пользователя к результату задачи, решаемой с помощью поиска, можно характеризовать

1) количеством решений : одно решение, несколько решений, все решения.

2) свойствами результата: ограничения, которым должен удовлетворять полученный результат

3) и (или) способом его получения.

Существующие методы решения задач, используемые в экспертных системах, можно классифицировать следующим образом:

· методы поиска в одном пространстве - методы, предназначенные для использования в следующих условиях: области небольшой размерности, полнота модели, точные и полные данные;

· методы поиска в иерархических пространствах - методы, предназначенные для работы в областях большой размерности;

· методы поиска при неточных и неполных данных ;

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

Предполагается, что перечисленные методам при необходимости должны объединяться для того, чтобы позволить решать задачи, сложность которых возрастает одновременно по нескольким параметрам.

3.1. ПОИСК РЕШЕНИЙ В ОДНОМ ПРОСТРАНСТВЕ

Методы поиска решений в одном пространстве обычно делятся на:

1) поиск в пространстве состояний (рассмотрим подробно),

2) поиск методом редукции,

3) эвристический поиск

4) поиск методом "генерация-проверка".

3.1.1. Поиск в пространстве состояний

Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации.

Пусть задана тройка (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ÍХ, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми, или терминальными (т.е. вершинами, к которым нельзя применить никаких операторов). В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти.

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

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

поиск в ширину. (вершины раскрываются в том же порядке, в котором они порождаются.) Рис.3.1.б.

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

Рис.3.1.

3.1.2. Поиск методом редукции

При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач. Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ-графом; Каждой вершине этого графа ставитсяв соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины.