Отличие
ЭС от других
программных
продуктов
Области
применения
экспертных
систем
Проблемы,
возникающие
при созданииЭС.
Перспективы
разработки
Критерий
пользователя
ЭС
Подсистема
вывода
Компонент
вывода
Диалог
с ЭС. Объяснение
Разработка
стратегии
Представление
задач в пространстве
состояний
Запись
в виде графа
Метод
равных цен
Изменение
при переборе
на произвольных
графах
Использование
других эвристик
Навигация
Запись в виде графа
Экспертные системы. Классификация экспертных систем. Разработка простейшей экспертной системы
102315
знаков
3
таблицы
0
изображений
3.4.3. Запись в виде графа.
Граф состоит из множества (не обязательно конечного) вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направленных графов. Если некоторая дуга направлена от вершины 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. Видно, что проблема нахождения последовательности операторов, преобразующих одно состояние в другое, эквивалентна задаче поиска пути на графе.
Глава 4. Методы поиска в пространстве состояний
4.1. Процессы поиска на графе
Граф определяется как множество вершин вместе с множеством ребер, причем каждое ребро задается парой вершин. Если ребра направлены, то их также называют дугами. Дуги задаются упорядоченными парами. Такие графы называются направленными. Ребрам можно приписывать стоимости, имена или метки произвольного вида, в зависимости от конкретного приложения.
При формулировке задачи решение получается в результате применения операторов к описаниям состояний до тех пор, пока не будет получено выражение, описывающее состояние, которое соответствует достижению цели. Все методы перебора, которые мы будем обсуждать, могут быть смоделированы с помощью следующего теоретико- графового процесса:
Начальная вершина соответствует описанию начального состояния. Вершины, непосредственно следующие за данной, получаются в результате использования операторов, которые применимы к описанию состояния. Пусть Г- некоторый специальный оператор, который строит все вершины, непосредственно следующие за данной. Мы будем называть процесс применения оператора Г к вершине раскрытием вершины.
От каждой такой последующей вершины к породившей ее идут указатели. Эти указатели позволяют найти путь назад к начальной вершине, уже после того как обнаружена целевая вершина.
Для вершин, следующих за данной, делается проверка, не являются ли они целевыми вершинами. Если целевая вершина еще не найдена, то продолжается процесс раскрытия вершин (и установки указателей). Когда же целевая вершина найдена, эти указатели просматриваются в обратном направлении- от цели к началу, в результате чего выявляется путь решения. Тогда операторы над описаниями состояний, связанные с дугами этого пути, образуют решающую последовательность.
Этапы, указанные выше, описывают просто основные элементы процесса перебора. При полном описании процесса перебора нужно еще задать порядок, в котором следует раскрывать вершины. Если вершины раскрываются в том же порядке, в котором они порождаются, то получается процесс, который называется полным перебором, Если же сначала раскрывается всегда та вершина, которая была построена самой последней, то получается процесс перебора в глубину. Процессы полного перебора в глубину можно назвать также процедурами слепого перебора, поскольку расположение цели не влияет на порядок, в котором раскрываются вершины.
Возможно, однако, что у нас имеется некоторая эвристическая информация о глобальном характере графа и общем расположении цели поиска. Такого рода информация часто может быть использована для того, чтобы “подтолкнуть” поиск в сторону цели, раскрывая в первую очередь наиболее перспективные вершины.
Рассмотрим более подробно методы слепого перебора. Деревом называется граф, каждая вершина которого имеет ровно одну непосредственно предшествующую ей (родительскую) вершину, за исключением выделенной вершины, называемой корнем дерева, которая вовсе не имеет предшествующих ей вершин. Таким образом, корень дерева служит начальной вершиной. Для перебора деревья проще графов прежде всего потому, что при построении новой вершины мы можем быть уверены, что она никогда раньше не строилась и никогда не будет построена вновь. Таким образом, путь от корня до данной вершины единственен.
4.2. Методы перебора
4.2.1. Методы полного перебора
В методе полного перебора вершины раскрываются в том порядке, в котором они строятся. Простой алгоритм полного перебора на дереве состоит из следующей последовательности шагов:
1) Поместить вершину в список, называемый ОТКРЫТ.
2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу.
3) Взять первую вершину из списка ОТКРЫТ и перенести ее в
список ЗАКРЫТ; назовем эту вершину n.
4) Раскрыть вершину n, образовав все вершины, непосредственно следующие за n. Если непосредственно следующих вершин нет, то переходить сразу же к шагу (2). Поместить имеющиеся непосредственно следующие за n вершины в конец списка ОТКРЫТ и построить указатели, ведущие от них назад к вершине n.
5) Если какие- нибудь из этих непосредственно следующих за n вершин являются целевыми вершинами, то на выход выдать решение, получающееся просмотром вдоль указателей; в противном случае переходить к шагу (2).
В этом алгоритме предполагается, что начальная вершина не удовлетворяет поставленной цели, хотя нетрудно ввести этап проверки такой возможности. Блок- схема алгоритма показана на рис.6. Вершины и указатели, построенные в процессе перебора, образуют поддерево всего неявно определенного дерева пространства состояний. Мы будем называть такое поддерево деревом перебора.
В методе полного перебора непременно будет найден самый короткий путь к целевой вершине при условии, что такой путь вообще существует. (Если такого пути нет, то в указанном методе будет объявлено о неуспехе в случае конечных графов, а в случае бесконечных графов алгоритм никогда не кончит свою работу.)
Пуск
Поместить S в список
ОТКРЫТ
нет да
Пуст ли список Неудача
ОТКРЫТ?
Взять первую вершину из списка ОТКРЫТ
и поместить ее в список ЗАКРЫТ.
Обозначить эту вершину через n
Раскрыть n. Поместить дочерние
вершины в конец списка ОТКРЫТ.
Провести от них к n указателю.
нет Являются ли да
какие-либо из Успех
дочерних вершин
целевыми?
рис.6 Блок- схема программы алгоритма полного перебора
для дерева.
Похожие работы
... охватывало бы вопросы воспитания, взаимодействия учителей с родителями учеников и самими учениками, вопросы самоподготовки желающих учиться учеников, помощи отстающим и т.п. 5. РАЗРАБОТКА ШКОЛЬНОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ (ШИС) НА ОСНОВЕ IT-ТЕХНОЛОГИЙ ДЛЯ МОУ СОШ № 97 Поставленные в предыдущем разделе задачи могут быть решены путем организации широчайшего (относительно родителей, учеников и ...
... основании вышеуказанных протоколов проводится окончательная оценка соответствия средства размещения определенной категории. Средства размещения определенной категории должны соответствовать: гостиницы, мотели и пр. с количеством номеров более 50: - требованиям, определенным в таблицах приложения к системе классификации; - критериям балльной оценки (табл. 2) с учетом следующего суммарного ...
... профессиональных знаний из экспертов и проектирование базы знаний экспертной системы и ее архитектуры. Программист необходим при разработке специализированного для данной экспертной системы программного обеспечения, когда подходящего стандартного (например, оболочки для создания экспертных систем) не существует или его возможностей не достаточно и требуются дополнительные модули. В процессе ...
... системы управления (АСУ); автоматизированные системы информационного обеспечения (АСИО). Рассмотрим каждый из перечисленных в классификации типов АИС подробнее. Под автоматизированной информационно-справочной системой (АИСС) в области права будем понимать автоматизированную информационную систему, предназначенную для сбора, систематизации, хранения и поиска правовой информации по запросам ...
0 комментариев