Методы поиска решений в экспертных системах

  • 14 окт. 2010 г.
  • 2198 Слова
МЕТОДЫ ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ

Методы решения задач, основанные на сведении 'их к поиску, зависят от особенностей предметной области, в которой решается задача, и от требований, предъявляемых пользователем к решению. Особенности предметной области:
0 объем пространства, в котором предстоит искать решение;
1 степень изменяемости области во времени и пространстве(статические и динамические области);
2 полнота модели, описывающей область, если модель не полна, то для описания области используют несколько моделей, дополняющих друг друга;
3 определенность данных о решаемой задаче, степень точности (ошибочности) и полноты (неполноты) данных.

Требования пользователя к результату задачи, решаемой с помощью поиска, можно характеризовать
1) количеством решений : однорешение, несколько решений, все решения.
2) свойствами результата: ограничения, которым должен удовлетворять полученный результат
3) и (или) способом его получения.
Существующие методы решения задач, используемые в экспертных системах, можно классифицировать следующим образом:
4 методы поиска в одном пространстве - методы, предназначенные для использования в следующих условиях:области небольшой размерности, полнота модели, точные и полные данные;
5 методы поиска в иерархических пространствах - методы, предназначенные для работы в областях большой размерности;
6 методы поиска при неточных и неполных данных ;
7 методы поиска, использующие несколько моделей, предназначенные для работы с областями, для адекватного описания которых одной модели недостаточно.Предполагается, что перечисленные методам при необходимости должны объединяться для того, чтобы позволить решать задачи, сложность которых возрастает одновременно по нескольким параметрам.

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 (fF), преобразующего состояние,соответствующее вершине xi, в состояние xj. Для некоторой вершины xi выделяем множество всех направленных пар (xi, xj)Y, т.ь. множество дуг, исходящих из вершины хi, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины xi, соответствует множеству операторов, которые могут быть применены к состоянию,соответствующему вершине хi.
В множестве вершин X выделяют подмножество вершин Х0Х, соответствующее множеству начальных состояний (So),, и подмножество вершин ХтX, соответствующее множеству конечных (целевых) состояний (SТ). Множество Хт может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.
Отметим, что граф С...
tracking img