МЕТОДЫ ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ
    
    Методы решения задач, основанные на сведении их к поиску, зависят от особенностей предметной области, в которой решается задача, и от требований, предъявляемых пользователем к решению. Особенности предметной области: * объем пространства, в котором предстоит искать решение; * степень изменяемости области во времени и пространстве (статические и динамические области); * полнота модели, описывающей область, если модель не полна, то для описания области используют несколько моделей, дополняющих друг друга; * определенность данных о решаемой задаче, степень точности (ошибочности) и полноты (неполноты) данных.
    
    Требования пользователя к результату задачи, решаемой с помощью поиска, можно характеризовать: * количеством решений : одно решение, несколько решений, все решения. * свойствами результата: ограничения, которым должен удовлетворять полученный результат и (или) способом его получения.
    Существующие методы решения задач, используемые в экспертных системах, можно классифицировать следующим образом: * методы поиска в одном пространстве - методы, предназначенные для использования в следующих условиях: области небольшой размерности, полнота модели, точные и полные данные; * методы поиска в иерархических пространствах - методы, предназначенные для работы в областях большой размерности; * методы поиска при неточных и неполных данных ; * методы поиска, использующие несколько моделей, предназначенные для работы с областями, для адекватного описания которых одной модели недостаточно.
    
    Предполагается, что перечисленные методам при необходимости должны объединяться для того, чтобы позволить решать задачи, сложность которых возрастает одновременно по нескольким параметрам.
    
    3.1. ПОИСК РЕШЕНИЙ В ОДНОМ ПРОСТРАНСТВЕ
    
    Методы поиска решений в одном пространстве обычно делятся на: * поиск в пространстве состояний (рассмотрим подробно), * поиск методом редукции, * эвристический поиск * поиск методом "генерация-проверка".
    
    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. ............