Главная Обратная связь Поможем написать вашу работу!

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Рассмотрим структуру продукционных систем



Продукционные систем состоят из продукционных правил и стратегий управления выводом, которая формально может быть записана в виде набора M=<M1,M2,M2>. М1 – процедура формирования множества продукционных правил, для которых выполнимо условие их применения. М2 – процедура выбора из сформированного подмножества, которое называют конфликтным одного правила, которое и будет выполняться на данном шаге. М3 – процедура, которая вносит изменения в базу знаний на основании того, как было реализовано правило. Возможны 2 основных варианта, которые приводят к выполнению правил:

1) после выполнения в базу знаний вносятся новые факты.

2) Взаимодействие с пользователем.

Возможны дополнительные варианты. Интерпретация правил выполняется специальным интерпретатором, который проводит их означивание, определяет выполнится или нет. Часто условие применимости правила Р и проверку выполнимости предпосылки правила А комбинируют, например в начале определяют множество правил, для которых выполнена предпосылка, а затем определяют какой приоритет у того или иного правила.

Рассмотрим функциональную структура систем. Она состоит из 3-х основных частей:

1) рабочая память (рабочая часть базы знаний)

2) база правил (постоянная часть базы знаний)

3) блок управления выводом (машина вывода)

 

Прямой вывод

Будем рассматривать монотонный вывод. 1) прямой вывод, последовательность которого идет от известных фактов, на каждом шаге к этим фактам применяются всевозможные правила, которые порождают новые факты. Так до тех пор пока в рабочей памяти не появится факт цель или процесс вывода просто не сможет быть продолженным. 2) Обратный вывод – вывод от поставленной цели или гипотезы. Если целевой факт согласуется с заключением правила, то его условия принимаются за подцель, для которой процесс рекурсивно повторяется до тех пор пока не будет получено совпадение подцели с известными фактами или не получено ее опровержение. Проиллюстрируем:

Структуру системы можно представить в виде графа, вершины которого соответствуют фактам кружок, правило – квадратик. Если из кружка в квадрат, то предпосылка правила, если наоборот – заключение правила.



Пусть в качестве целевого факта задан факт 9. Рассмотрим прямой вывод. Нас интересует выполнится ли 9 при истинности фактов 1, 2, 3, 4, 5. Последовательность прямого вывода зависит от процедуры разрешения конфликтов. На первом шаге видим, что у нас работают правила 1, 2, 3. Рассмотрим 2 стратегии:

1) поиск в ширину (выбор первого подходящего правила). В соответствии с ней в начале работает правило 1, добавится факт 6. Затем 2, в память 7. Потом правило 3 и в память добавляется факт 9. При такой последовательности в память добавили факт ., который не относился к фактору вывода 9.

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

Срабатывает 2, в базу добавляется 7, срабатывает 1, добавляется 6, срабатывает 3, получаем 9.Для это конфигурации выигрыша нет, но если бы нумерация была бы такова, что срабатывала бы вначале правило 2, потом 3 и получили 9.

Обратный вывод

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



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

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

 

Вывод в ширину и в глубину

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

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



 

Пропускаем И ИЛИ деревья

Есть вершина, корень, которая достижима через и или от других вершин, которые цепляются за вершины 3-го яруса и т.д.. Соответственно можно изображать как угодно но корректнее связки изображают с помощью промежуточных вершин. В итоге, такую конструкцию можно представить в виде следующей, которая будет содержать вершины только 2 типов: типа «и» и «или». Если трактовать каждую вершину как некоторую задачу, то «и» «или» дерево указывает на зависимости между этими задачами.

 
 

 
 

 
 

               
 
   
   
 
 
 
   


 
 
           
   
   

 

 


Для решения задачи 1 требуется решение хотя бы 1 из задач. Введем формально задачу 1.1 или задачу 4. Задача 1 выполняется при выполнении 2 и 3. Соответственно 2 и 3 зависят от задач самого низкого уровня, о выполнимости которых можем судить непосредственно. Для выполнения 4, требуется 10, т.к. они непосредственно вытекают друг из друга и задача 4 не учитывает никаких дополнительных подзадач, эти вершины отождествляются. Пусть теперь располагаем некоторым перечнем средств, решающем некоторый список исходных задач низкого уровня. Нас интересует, сработает ли корневая задача. Пусть например список решает задачи 8, 9, 11, 12.

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


Просмотров 354

Эта страница нарушает авторские права




allrefrs.ru - 2021 год. Все права принадлежат их авторам!