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

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

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

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

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

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

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

Пропускаем и или деревья

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

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

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