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

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

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

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

Рис.6.1.

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

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

    Рис.6.2.

     

    Рис.6.4

6.3. Поиск в иерархии пространств

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

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

1. поиск в факторизованном пространстве;
2. поиск в фиксированном множестве пространств;
3. поиск в изменяющемся множестве пространств.

6.4. Поиск в альтернативных  пространствах

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

• все утверждения, описывающие состояние, являются истинными;
• применение оператора к некоторому состоянию формирует некоторое новое состояние, описание которого состоит только из истинных фактов.

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

6.5. Выбор метода решения  задач

    Выбор метода решения задачи зависит прежде всего от сложности задачи, которая  определяется особенностями проблемной области и требованиями, предъявляемыми пользователем к решению задачи. Для преодоления трудностей, вызванных большим пространством поиска, используются методы, основанные на введении иерархии пространств (конкретных, абстрактных и метапространств). Простейший из этих методов основывается на факторизуемости пространства решений, что позволяет производить раннее отсечение. Метод обеспечивает получение всех решений. Если пространство поиска не удается факторизовать, но при этом не требуется получать все решения или выбирать лучшее, то могут быть применены методы, использующие иерархию однородных абстрактных пространств. Если пространство поиска таково, что любая задача может быть сведена к известной заранее последовательности подзадач, то используется фиксированное абстрактное пространство.

 

Тема 7. Основы построения и использования механизмов логического вывода

    7.1. Основные понятия механизма логического вывода

    7.2. Механизм логического вывода в продукционных системах

    7.3. Понятие о механизме логического вывода в сетевых системах

    7.4. Понятие о механизме логического вывода во фреймовых системах

    7.5. Механизм логического вывода в диагностических системах байесовского типа

7.1. Основные понятия  механизма логического  вывода

    Механизм  логического вывода — неотъемлемая часть системы, основанной на знаниях (ЭС), реализующая функции вывода (формирования) умозаключений (новых суждений) на основе информации из базы знаний и рабочей памяти.

    Перед рассмотрением конкретных механизмов логического вывода отметим несколько важных моментов:

1. единого механизма логического вывода для произвольных систем, основанных на знаниях (ЭС), не существует;
2. механизм логического вывода полностью определяется моделью представления знаний, принятой в данной системе;
3. существующие механизмы логического вывода не являются строго фиксированными для каждого типа систем, основанных на знаниях (ЭС).

7.2. Механизм логического вывода в продукционных системах

    1. Сущность прямого логического вывода в продукционных ЭС состоит в построении цепочки выводов (продукций или правил), связывающих начальные факты с результатом вывода.

    В терминах «факты — правила» формирование цепочки вывода заключается в  многократном повторении элементарных шагов «сопоставить — выполнить».

    2. Механизм обратного вывода имеет совершенно иной алгоритм. Его идея заключается в проверке справедливости некоторой гипотезы (некоторого суждения, факта), которая выдвигается пользователем и проверяется ЭС. При этом осуществляется проверка истинности не левых, а правых частей продукций, а вопрос формулируется так: «Что нужно, чтобы правая часть данного правила была справедлива и есть ли необходимые суждения в рабочей памяти?».

7.3. Понятие о механизме логического вывода в сетевых системах

    Механизм  логического вывода в сетевых  системах основан на использовании  двух ведущих принципов:

    1. наследования свойств; 2. сопоставления по совпадению.

    Первый  принцип, в свою очередь, базируется на учете важнейших связей, отражаемых в семантической сети. К таким связям относятся:

    - связь «есть», «является» (англ. IS-A);

    - связи «имеет часть», «является частью» (англ. HAS-PART, PART-OF).

    Принцип сопоставления по совпадению основан на представлении вопроса к системе в виде фрагмента семантической сети с использованием тех же названий сущностей (узлов) и связей, что и в основной сети, и реализации процедуры «наложения» вопроса на сеть и поиска такого его положения, которое соответствует ответу на вопрос.

7.4. Понятие о механизме логического вывода во фреймовых системах

    Обычно фреймовая модель знаний имеет сложную иерархическую структуру, отражающую реальные объекты (понятия) и отношения (связи) некоторой предметной области. Механизм логического вывода в таких ЭС основан на обмене значениями между одноименными слотами различных фреймов и выполнении присоединенных процедур «если — добавлено», «если — удалено» и «если — нужно». Условная схема таких действий для простейшего варианта представлена на рис.7.4.

    

    

    Рис.7.4. Механизм вывода во фреймовой модели

7.5. Механизм логического вывода в диагностических системах байесовского типа

    Диагностические ЭС широко применяются в различных  областях человеческой деятельности (медицине, технике, экономике и др.). Как  правило, в них используются продукционные модели знаний о предметной области. Однако если имеется возможность использования в правилах статистических данных о понятиях и связях между ними, весьма целесообразно применить известную теорему Байеса для пересчета апостериорных вероятностей по результатам проверки наличия тех или иных симптомов.