Эвристические методы поиска в пространстве состояний

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

Для реальных случаев чаще всего используется дополнительная - эвристическая информация, основанная на предыдущем опыте или полученная на основании теоретических выводов.

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

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

Возможно также использование комбинированных стратегий поиска методами и в ширину, и в глубину: перебор этапами, ограничение числа дочерних вершин, двунаправленный перебор от Sн к Sц и обратно, методы ветвей и границ и динамическое программирование, применяемые в исследовании операций.

14. Основные модели представления знаний в экспертной системе: логическая, продукционная, фреймовая. Сетевые модели представления знаний экспертной системе. Семантическая сеть.

Модель представления знаний - совокупность структур представления знаний и механизма вывода на их основе содержащихся либо новых знаний.

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

Логические модели. Все предметы, взаимосвязи, события и процессы, составляющие основу необходимой для решения задачи информации, называют предметной областью. Для представления математического знания пользуются формальными логическими языками – исчислением высказываний и исчислением предикатов 1-го порядка. Эти языки имеют ясную формальную семантику, и для них разработаны формальные методы логического вывода.

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

Логические модели представления знаний в ЭС являются формальными логическими моделями, основанными на классической теории исчисления предикатов 1-го порядка, когда предметная область описывается в виде набора аксиом.

Создание формальной логической модели, основывается на формальной теории S, образованной четырьмя множествами:

S = {B,F,A,P},

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

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

А – выделенное множество наперед заданных правильных конструкций (априорно истинных формул), именуемых аксиомами. Декларируется, что имеется процедура установления принадлежности к аксиомам ряда создаваемых правильных выражений или объектов.

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

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

Продукционная модель. Продукционная модель представления знаний называется моделью, основанной на правилах – продукциях.

Правило-продукция имеет вид выражения:

«Если А<условие>, то В<действие>, постусловие С».

В качестве «условия» выступает предложение – образец, по которому осуществляется поиск в базе знаний, а под «действием» - действия, выполняемые при успешном исходе поиска.

Любое продукционное правило, содержащееся в базе знаний, состоит из двух частей: антецедента и консеквента.

Правило продукции представимо в виде p_i: s_i → d_i,

где p_i - правило продукции; s_i - антецедент – представляет условие применения правила p_i и состоит из элементарного предложения; d_i - консеквент - включает одно или несколько предложений, соединенных логическими связками И, ИЛИ (определяет результат применения правила p_i).

Примеры продукционных правил

ЕСЛИ «идет дождь», ТО «надо взять зонт».

ЕСЛИ «небо покрыто тучами» И «идет дождь», ТО «надо взять зонт».

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

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

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

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

Фреймовая модель представления знаний в ЭС. Фреймы – это фрагменты знания, предназначенные для представления стандартных ситуаций.

Фрейм имеет иерархическую структуру: на верхнем уровне располагаются фиксированные характеристики ситуации, на последующих уровнях (в так называемых «слотах»-отсеках) – уточняющая и конкретизирующая информация. Часто структуру фрейма либо сеть фреймов изображают соответственно подсетью и сетью ориентированных графов. В первом случае вершина графа-составляющая фрейма, а дуги(ребра)-отношения, фиксируемые между его составляющими. Во втором случае в вершине графа размещается фрейм, а дуги между вершинами отражают отношения, устанавливаемые между фреймами.

Указатели наследования показывают, какую информацию об атрибутах слотов из верхнего уровня наследуют слоты с одинаковыми именами в данном фрейме.

С фреймами через слоты связываются внешние и внутренние процедуры.

Во фреймовых экспертных системах различают два типа присоединенных процедур: процедуры-демоны и процедуры-слуги.

Программная реализация фреймов и фреймовых сетей возможна как посредством универсальных объектно-ориентированных и компонентных языков программирования, так и языков фреймовых систем.

Сетевые модели представления знаний в экспертных системах. Семантическая сеть.

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

Семантическая сеть – это ориентированный граф, вершины которого – понятия (объекты предметной области), а дуги – отношении между ними.

Используются три основных типа объектов: понятия, события и свойства; понятия - объекты предметной области, события - действия, свойства-характеристики объектов или событий.

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

· множество-подмножество;

· отношений «сходства-различий»;

· пространственных отношений;

· временных отношений;

· количественных отношений;

· функциональных связей;

· атрибутивных связей;

· логических связей.

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