Виды баз знаний1. ему обязательно должен быть указан график 2. ему не обязательно должен быть указан график 3. в плане видов расчета, связанном с регистром расчета должен быть установлен признак "использует период действия" 4. верны 1 и 3 утверждения Вопрос 48 Каково соотношение планов видов расчета и регистров рас- чета? 1. Один план видов расчета соответствует одному регистру расчета 2. Несколько регистров расчета могут быть привязаны к одному плану видов расчета 3. Несколько планов видов расчета могут быть привязаны к одному регистру расчета 4. Регистр расчета может быть привязан к нескольким планам видов расчета, а план видов расчета к нескольким регистрам расчета. Виды баз знаний Существуют динамические и статические базы знаний. Динамические базы знаний не зависят от состояния окружающие среды. Новые факты в таких базах появляются по результатам выводов существующих правил и фактов. Статические базы знаний – это системы с монотонным выводом, и знания в них не изменяются в процессе решения задач. В этих системах возможно только изменение и удаление фактов.
9. Подсистема вывода ЭС
Подсистема логического вывода Подиситема вывода – это программный компонент ЭС, который реализует процесс рассуждения на основе рабочего множества базы знаний. Этот механизм обладает двумя основными фукнциями: 1. просмотр и анализ существующих правил и добавление новых 2. выделение этого порядка и просмотр Таким образом, эта подсистема управляет процессом консультации, сохраняя для пользователя полученное заключение, а также, в случае необходимости, запрашивает у него информацию в случае ее недостатка. Эта подсистема служит для достижения цели ЭС. Целью любой ЭС является некое целевое утверждение, которое либо выводится, либо опровергается. Существует 2 варианта – либо целевое утверждение заложено сразу в ЭС, либо выводится вместе с пользователем. В процессе работы системы при переборе последовательности шагов определяются некоторые правила, применяемые к рабочему множеству. Это и есть процесс логического вывода.
Компонент вывода – действие этого компонента основано на правиле вывода модус поненс. Суть этого правила состоит в том, что если выражение A истинно, то при записи «если А то B» B – тоже истинно. Компонент вывода должен продолжать поиск решения при любых условиях (нехватка информации, ее двусмысленность и т.д.)
10. Прямой и обратный порядок вывода в ЭС
Существует 2 процесса логического вывода: - прямой – происходит от фактов рабочего множества к заключению. Если такое заключение существует, то оно заносится в рабочее множество. Пример: А1 – кашель; А2 – насморк => свиной грипп. - обратный порядок – предусматривает движение от гипотезы к фактам. Если в процессе обратного вывода найдены или получены от пользователя факты, подтверждающие гипотезу, то гипотеза становится истиной. Если гипотеза подтвердилась, то выдвигаются следующие гипотезы, детализирующие первое, затем ищутся факты, подтверждающие детализирующую гипотезу и т д, пока мы не придем к целевой..
11. Поиск в "глубину" и "ширину" в ЭС
У каждого порядка существует 2 вида стратегии: 1) поиск в ширину 2) поиск в глубину Стратегии поиска: А) прямой в глубину – движение от фактов к гипотезе через уровни. Б) прямой в ширину – движение от фактов как через уровни, так и внутри одного уровня к гипотезе; В) обратный в глубину – движение от гипотезы к фактам через уровни; Г) обратный в ширину – движение от гипотезы к фактам одного уровня с возвратом гипотезы.
12. Функции управляющего компонента ЭС
Управляющий компонент Этот компонент определяет порядок применения фактов и правил, а также перебирает те факты, которые необходимо применить в процессе работы. Этот компонент определяет 4 основные функции: 1. сопоставление. На первом этапе происходит сопоставление образцов правил с имеющимися факторами. 2. вывод. Если при работе первого этапа происходит отбор нескольких правил, то выбирается одно наиболее подходящее. Этот процесс называется процессом разрешения конфликта. Чаще всего выбирается правило с наивысшим приоритетом. 3. срабатывание. Если после первых этапов происходит совпадение фактов правил, то происходит срабатывание правил. 4. действие. Это процесс, когда рабочее множество подвергается изменению путем добавления в него активизированного правила. 5. Далее удаляется список сработавших правил.
13. Цикл работы интерпретатора ЭС
Цикл работы интерпретатора вывода Информация из рабочего множества (РМ) сопоставляется с информацией из базы правил (БП). Происходит сопоставление. Оно переходит в конфликтное множество. По какому-то критерию выбора происходит разрешение конфликта. Если конфликт разрешился, то срабатывает выбранное правило. На основании срабатывания правила происходит действие. Цикл закончен, но после срабатывания цикла на основе выбранного правила происходит коррекция критериев выбора и добавление элементов в рабочее множество и базу знаний.
14. Системы управления выводом Стратегии управления выводом Вопрос выбора стратегии очень важен, так как от этого зависит порядок работы правил и найдет ли система решение вообще. При выборе стратегии необходимо ответить на 2 вопроса: 1) какую точку пространства состояния считать исходной (система определяет прямой или обратный порядок перехода); 2) как повысить эффективность поиска решений.
Стратегии управления выводом Выбор стратегии очень важен, т к от этого зависит порядок работы правил, найдет ли система решение вообще. При выборе стратегии нужно ответить на 2 вопроса: 1. какую точку в пространстве состояний считать исходной (система определяет прямой или обратный порядок перехода). 2. как повысить эффективность поиска.
15. Методы повышения эффективности поиска В некоторых ЭС количество правил и фактов может достигать сотен тысяч и более. В рамках ограниченности временных технических человеческих ресурсов, вопрос повышения эффективности становится крайне актуален. Существует 3 способа повысить эффективность: 1) Сопоставление поиска в глубину и ширину (комбинирование); 2) α и β алгоритм; 3) Разбиение на подзадачи. 1. Суть поиска в глубину состоит в том, что при выборе очередной подцели пространства состояний, система отдает предпочтение правилам, которые следуют за более общим правилом, то есть идет от общего к частному. При поиске в ширину, система анализирует все правила, находящиеся на одном уровне, а потом переходит на более детальный уровень и перебирает правила там. На практике преобладает, как правило, поиск в глубину, так как он анализирует только те признаки, которые соответствуют гипотезе. Но существуют задачи, которые возможно решить, используя комбинацию этих двух методов (двигаясь в глубину к гипотезе или к начальной точке, частично смещать движение по нескольким уровням). 2. Суть этого метода заключается в сокращении пространства состояния путем удаления ветвей, для поиска успешного решения. Рассматриваются только те ветки, в которые можно попасть в результате следующего шага. 3. Суть заключается в выделении в исходной задаче задач, более низкого уровня, решение которых будет рассматриваться как начальные условия для решений исходной задачи, если получается правильно определить структуру задачи и разбить на подзадачи, то путь к решению минимален. Чисто для решения задач требуется проведение логического анализа. После его проведения, поиск решения либо упрощается, либо анализ показывает, что решения нет.
Методы повышения эффективности поиска В некоторых системах количество правильных фактов может достигать сотен тысяч и более. В рамках ограниченности временных ресурсов, технических и человеческих ресурсов вопрос повышения эффективности становится крайне актуальным. Существует 3 способа повышения эффективности: 1. сопоставление поиска в глубину (к очередной цели мы идем через уровни) и ширину (система анализирует все правила, находящиеся на одном уровне). На практике лучше применять комбинации этих методов, т к система сможет проанализировать все правила, удовлетворяющие гипотезе. 2. альфа и бета алгоритм. Суть этого метода заключается в том, что сокращается путь пространства состояния путем удаления ненужных идей, которые не нужны для поиска решения. Рассматриваются только те пути, которые приводят к решению. 3. разбиение на подзадачи. Суть заключается в том, что в исходной задаче выделяются задачи более низкого уровня, решение которых будет рассматриваться как исходные данные решения общих задач. Если получается правильно разбить исходную задачу, то решение будет минимальным. Чаще всего эти используется в задачах планирования. 4. неосновной метод повышения эффективности – использование формальной логики. Часто для решения задач необходимо провести логический анализ. Решение задач существенно упрощается, если анализ показывает отсутствие решения.
16. Процесс объяснения, диалог с ЭС
Диалог с ЭС. Процесс объяснения Поскольку ЭС реализуются на компьютере, то входная информация системы должна быть на языке, понятном машине. Чтобы пользователь мог работать в системе, требуется реализовать диалог на языке, понятном пользователям. Как правило, инициатива диалога принадлежит системе, но в отличие от эксперта система не комментирует свои действия. Чтобы адекватно оценить «разумность ЭС», пользователю нужно обратиться к подсистеме объяснений. Процесс же объяснения в ЭС принято представлять в виде схемы, которая называется «дерево выводов».
Пр. Мира 19а, ОАО Омскнефтехимпроект, 22 октября, 15.00.
17. Альфа-бета алгоритм поиска
Задача сводится к уменьшению пространства состояний путем удаления в нем ветвей, не перспективных для поиска успешного решения. Поэтому просматриваются только те вершины, в которые можно попасть в результате следующего шага, после чего неперспективные направления исключаются из дальнейшего рассмотрения. Например, если цвет предмета, который мы ищем, не красный, то его бессмысленно искать среди красных предметов. Альфа- бета алгоритм нашел широкое применение в основном в системах, ориентированных на различные игры, например в шахматных программах.
18. Поиск путем разбиения на подзадачи
При такой стратегии в исходной задаче выделяются подзадачи, решение которых рассматривается как достижение промежуточных целей на пути к конечной цели. Если удается правильно понять сущность задачи и оптимально разбить ее на систему иерархически связанных целей- подцелей, то можно добиться того, что путь к ее решению в пространстве поиска будет минимален. Однако если задача является плохо структурированной, то сделать это невозможно. При сведении задачи к подзадачам производится исследовании исходной задачи с целью выделения такого множества подзадач, чтобы решение некоторого определенного подмножества этих подзадач содержало в себе решение исходной задачи. Рассмотрим, например, задачу о проезде на автомобиле из Пало-Альто (штат Калифорния) в Кембридж (штат Массачусетс). Эта задача может быть сведена, скажем, к следующим подзадачам: Подзадача 1. Проехать из Пало-Альто в Сан-Франциско. Подзадача 2. Проехать из Сан-Франциско в Чикаго. Подзадача 3. Проехать из Чикаго в Олбани. Подзадача 4. Проехать из Олбани в Кембридж. Здесь решение всех четырех подзадач обеспечило бы некоторое решение первоначальной задачи. Каждая из подзадач может быть решена с применением какого-либо метода. К ним могут быть применены методы, использующие пространство состояний, или же их можно проанализировать с целью выделения для каждой своих подзадач и т.д. Если продолжить процесс разбиения возникающих подзадач на еще более мелкие, то в конце концов мы придем к некоторым элементарным задачам, решение которых может считаться тривиальным. На каждом из этапов может возникнуть несколько альтернативных множеств подзадач, к которым может быть сведена данная задача. Т.к. некоторые из этих множеств в конечном итоге, возможно, не приведут к окончательному решению задачи, то, как правило, для решения первоначальной задачи необходим поиск в пространстве множеств подзадач
19. Запись данных в пространстве состояний в виде графа Представление задач в пространстве состояний Чтобы построить корректное описание задач, очень важен выбор некоторой формы описания состояний, для этого могут быть использованы строки символов, векторы, двумерные массивы, деревья состояний и списки. Часто запись задач выполняется в форме, которая имеет некоторое сходство с физическим свойством решаемой задачи. Для описания пространства состояний для поиска решений задач, иногда вводят понятие оператор (преобразует состояние от начального к целевому, тем самым находя решение (некое подобие подпрограммы)).
Запись состояний в виде графов Граф состоит из конечного множества вершин, соединенных с помощью дуг. Если эти дуги направлены от одной вершины к другой, то такие графы называются направленными. Если дуга от вершины Ni к вершине ni, то считается, что ni является дочерней вершиной Ni, а Ni является родительской вершиной.
Если дуга между вершинами имеет двустороннее направление, то вершины являются дочерними друг к другу. Переход i называется ребром графа. В случае, когда граф используется для записи состояний, то его вершины записывают состояние, ребра – операторы. Оператор (правило) – это совокупность условий действий для перехода из одного состояния в другое. Последовательность вершин С1-Сn называется путем длины n. Если в общем графе такой путь существует, то С1 – предок, а Сn – потомок.
Граф состоит из множества (не обязательно конечного) вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направленных графов. Если некоторая дуга направлена от вершины ni к вершине nj, то говорят, что вершина nj является дочерней для вершины ni, а вершина ni является родительской вершиной для nj. Может оказаться, что наши две вершины будут дочерними друг для друга; в этом случае пара направленных дуг называется иногда ребром графа. В случае, когда граф используется для представления пространства состояний, с его вершинами связывают описание состояний, а с его дугами- операторы. Последовательность вершин ni1,ni2,...,nik., в которой каждая вершина nij дочерняя для ni,j-1, j=2,k, называется путем длины k от вершины ni1, к вершине nik. Если существует путь, ведущий от вершины ni к вершине nj, то вершину nj называют достижимой из вершины ni или потомком вершины ni . В этом случае вершина ni называется также предком для вершины nj. Видно, что проблема нахождения последовательности операторов, преобразующих одно состояние в другое, эквивалентна задаче поиска пути на графе
20. Полный перебор при поиске на графе
Процессы поиска на графе Пусть исходное состояние мы заносим в начальную вершину графа. Пусть существуют некоторые операторы, которые строят все последующие вершины с указанием связей до целевой вершины. Этот процесс называется раскрытие целевой вершины. Процесс, обратный этому, называется решающая последовательность.
полный перебор
В методе полного перебора вершины раскрываются в том порядке, в котором они строятся. Простой алгоритм полного перебора на дереве состоит из следующей последовательности шагов: 1) Поместить вершину в список, называемый ОТКРЫТ. 2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу. 3) Взять первую вершину из списка ОТКРЫТ и перенести ее в список ЗАКРЫТ; назовем эту вершину n. 4) Раскрыть вершину n, образовав все вершины, непосредственно следующие за n. Если непосредственно следующих вершин нет, то переходить сразу же к шагу (2). Поместить имеющиеся непосредственно следующие за n вершины в конец списка ОТКРЫТ и построить указатели, ведущие от них назад к вершине n. 5) Если какие-нибудь из этих непосредственно следующих за n вершин являются целевыми вершинами, то на выход выдать решение, получающееся просмотром вдоль указателей; в противном случае переходить к шагу (2). В этом алгоритме предполагается, что начальная вершина не удовлетворяет поставленной цели, хотя нетрудно ввести этап проверки такой возможности. Блок- схема алгоритма показана на рис.6. Вершины и указатели, построенные в процессе перебора, образуют поддерево всего неявно определенного дерева пространства состояний. Мы будем называть такое поддерево деревом перебора. В методе полного перебора непременно будет найден самый короткий путь к целевой вершине при условии, что такой путь вообще существует. (Если такого пути нет, то в указанном методе будет объявлено о неуспехе в случае конечных графов, а в случае бесконечных графов алгоритм никогда не кончит свою работу.)
Рисунок 6 – Блок-схема программы алгоритма полного перебора для дерева.
21. Метод равных цен при поиске на графе метод равных цен Суть метода состоит в том. Что каждому переходу по состоянию присваивается стоимость, и перебирая вершины по этому методу, мы должны обеспечить путь с минимальной суммарной стоимостью
Могут встретится задачи, в которых решению предъявляются какие-то иные требования, отличные от требования получения наикратчайшей последовательности операторов. Присваивание дугам деревьев определенных цен (с последующим нахождением решающего пути, имеющего минимальную стоимость) соответствует многим из таких обещанных критериев. Более общий вариант метода полного перебора, называемый методом равных цен, позволяет во всех случаях найти некоторый путь от начальной вершины к целевой, стоимость которого минимальна. В то время как в выше описанном алгоритме распространяются линии равной длины пути от начальной вершины, в более общем алгоритме, который будет описан ниже, распространяются линии равной стоимости пути. Предполагается, что нам задана функция стоимости c(ni,nj), дающая стоимость перехода от вершины ni к некоторой следующей за ней вершине nj. В методе равных цен для каждой вершины n в дереве перебора нам нужно помнить стоимость пути, построенного от начальной вершины s к вершине n. Пусть g(n)- стоимость от вершины s к вершине n в дереве перебора. В случае деревьев перебора мы можем быть уверены, что g(n) является к тому же стоимостью того пути, который имеет минимальную стоимость (т.к. этот путь единственный). В методе равных цен вершины раскрываются в порядке возрастания стоимости g(n). Этот метод характеризуется такой последовательностью шагов: 1) Поместить начальную вершину s в список, называемый ОТКРЫТ. Положить g(s)=0. 2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу. 3) Взять из списка ОТКРЫТ ту вершину, для которой величина g имеет наименьшее значение, и поместить ее в список ЗАКРЫТ. Дать этой вершине название n. (В случае совпадения значений выбирать вершину с минимальными g произвольно, но всегда отдавая предпочтение целевой вершине.) 4) Если n есть целевая вершина, то на выход выдать решающий путь, получаемый путем просмотра назад в соответствии с указателями; в противном случае переходить к следующему шагу. 5) Раскрыть вершину n, построив все непосредственно следующие за ней вершины. (Если таковых нет переходить к шагу (2).) Для каждой из такой непосредственно следующей (дочерней) вершины ni вычислить стоимость g(n), положив g(ni)=g(n)+c(n,ni). Поместить эти вершины вместе с соответствующими им только что найденными значениями g в список ОТКРЫТ и построить указатели, идущие назад к n. 6) Перейти к шагу (2). Блок- схема этого алгоритма показана на рис.7. Проверка того, является ли некоторая вершина целевой, включена в эту схему так, что гарантируется обнаружение путей минимальной стоимости. Алгоритм, работающий по методу равных цен, может быть также использован для поиска путей минимальной длины, если просто положить стоимость каждого ребра равной единице. Если имеется несколько начальных вершин, о алгоритм просто модифицируется: на шаге (1) все начальные вершины помещаются в список ОТКРЫТ. Если состояния, отвечающие поставленной цели, могут быть описаны явно, то процесс перебора можно пустить в обратном направлении, приняв целевые вершины в качестве начальных и используя обращение оператора Г.
Рисунок 7 – Блок-схема программы алгоритма равных цен для деревьев
22. Использование эвристической информации (оценочные функции)
В граф вводят оценочную функцию, которая обеспечивает возможность ранжирования (расстановки приоритетов) вершин, которые с наибольшей вероятностью соответствуют цели
|
