Введение в проблему искусственного интеллекта


Продукционная модель (ПМ) знаний и ее использование в ЭС. - часть 5


множ. X

Если каждая пара (Xi;Xj) не упорядочена, то ее называют ребром графа, а граф неориентированным.

Если для каждой пары (Xi;Xj) задан порядок, то ее называют дугой, а граф ориентированным.

Наиболее часто метод используется для ориентированного графа.

В этом случае решение задачи представляет собой путь на ориентированном графе, где пары (Xij-1;Xij) принадлежат Y, который приводит из начального состояния к целевому. На практике дугам графа приписывают весовые характеристики, которые отображают их приоритетность в процессе обработки запроса. В этом случае выбор пути сводится к минимизации или максимизации суммы весовых характеристик дуг, образующих этот путь. Таким образом граф j задает пространство возможных состояний предметной области. Построение пространства осуществляется с помощью следующей процедуры: берется некоторая вершина из множества начальных состояний и к ней применяются все возможные операторы, порождающие дочерние вершины. Этот процесс иначе называется “раскрытием вершин”. Он продолжается до тех пор, пока не будет найдена вершина, соответствующая одному из целевых состояний.

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

Метод II - редукция.

При поиске методом редукции решение задачи сводится к решению образующих ее подзадач. Процесс повторяется для каждой следующей подзадачи до тех пор, пока не будет найдено очевидное решение для всей их совокупности. Процесс разбиения задач на подзадачи представляется в виде ориентированного графа j, который называется “и/или-граф”. Каждая вершина “и/или-графа” представляет собой задачу или подзадачу и может быть конъюнктивной (“и”-вершиной) или дизъюнктивной (“или”-вершиной).


Начало  Назад  Вперед