Реферат: Методы решения задач

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть задана тройка (S₀ , F, S_Т ), где S₀ - множество начальных состояний (условия задачи), F - множество операторов задачи, отображающих одни состояния в другие, S_Т - множество конечных (целевых) состояний (решений задачи).

Цель: определять такую последовательность операторов, которая преобразует начальные состояния в конечные.

Процесс решения в виде графа G=(Х, Y), где X={х₀ , х_1, ...} - множество (в общем случае бесконечное) вершин графа, состояний, а Y - множество, содержащее пары вершин (x_i , x_j ), (x_i , x_j )ÎX. Если каждая пара (x_i , x_j ) неупорядочена, то ее называют ребром, а граф - неориентированным. Если для каждой пары (x_i , x_j ) задан порядок (направление), то пару (x_i , x_j ) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (x_i , x_j ) называют концевыми точками ребра (дуги).

Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (x_i , x_j ) свидетельствует о существовании некоторого оператора f (fÎF), преобразующего состояние, соответствующее вершине x_i , в состояние x_j . Для некоторой вершины x_i выделяем множество всех направленных пар (x_i , x_j )ÎY, т.ь. множество дуг, исходящих из вершины х_i , (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины x_i , соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине х_i .

В множестве вершин X выделяют подмножество вершин Х₀ ÍХ, соответствующее множеству начальных состояний (S_o ),, и подмножество вершин Х_т ÍX, соответствующее множеству конечных (целевых) состояний (S_Т ). Множество Х_т может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.

Отметим, что граф С может быть задан явно и неявно. Неявное задание графа G стоит в определении множества Х₀ ÍХ (соответствующего множеству начальных состояний) и множества операторов, которые, будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--