- •Алгоритм а
- •Структуры управления в mycin
- •Математическое определение нечетких множеств. Определение уиниверсума. Примеры.
- •Сценарий посещения ресторана
- •Структуры данных в языке lisp
- •Обработка списков
- •Сопоставление с образцом
- •Определение функции принадлежности. Виды и примеры функций принадлежности. Примеры.
- •Классический период: игры и доказательство теорем Поиск в пространстве состояний
- •Графы, деревья и сети
- •Представление неопределенности знаний и данных
- •Источники неопределенности
- •Определение ядра, высоты и границ нечеткого множества. Пример.
- •Машина логического вывода и база знаний. Представление знаний: принципы и методы. Представление знаний: принципы и методы
- •Системы, основанные на знаниях
- •Канонические системы
- •Объектно-ориентированный анализ и конструирование экспертных систем
- •Нормальное нечеткое множество (определение). Равенство и доминирование нечетких множеств. Пример.
- •Планировщик strips
- •Представление типовых объектов и ситуаций
- •Основные понятия концепции фреймов
- •Фреймы и графы
- •Объектно-ориентированный анализ и конструирование экспертных систем
- •Операции пересечения, объединения и разности нечетких множеств. Примеры.
Классический период: игры и доказательство теорем Поиск в пространстве состояний
Множество проблем можно сформулировать в терминах трех важнейших ингредиентов:
исходное состояние проблемы, например исходное состояние головоломки;
тест завершения — проверка, достигнуто ли требуемое конечное состояние или найдено решение проблемы (примером может послужить правило определения, собрана ли головоломка);
множество операций, которые можно использовать для изменения текущего состояния проблемы, например шаги или перемещения фигур при сборке головоломки.
Один из способов представления такого концептуального пространства состояний — граф, в котором состояниям соответствуют узлы, а операциям — дуги.
Графы, деревья и сети
Все определения сформулированы в предположении, что существуют два вида примитивов — узлы и связи. Узлы представляют собой исходящие и целевые пункты для связей и обычно каким-либо образом промаркированы. Связи также могут быть промаркированы, но это не обязательно. Все зависит от того, имеем ли мы дело со связями одного вида или разных. В общепринятой терминологии теории графов узлы называются "вершинами", а связи — "ребрами графа", или "дугами".
Если N— множество узлов, то любое подмножество NxN является обобщенным графом G. Если в парах подмножества NxN имеет значение порядок, то граф G является ориентированным.
Граф не обязательно должен быть связным. Если задаться условием, что петли не допускаются, т.е. в каждой паре должны присутствовать разные узлы, то такой граф называется обыкновенным. Если на графе не допускаются не только петли, но и циклы (т.е. последовательность связей, в которой начальный и конечный узлы совпадают), то такой граф называется лесом.
Если G— обыкновенный граф, в котором имеется п узлов и п-1 связей и отсутствуют циклы, то такой граф является деревом.
Иными словами, дерево — это связный лес. Обычно один из узлов дерева является его корнем.
Остальные узлы образуют ветвящуюся структуру "наследников" корневого узла, в которой отсутствуют циклы. Узлы, не имеющие наследников, являются терминальными, или "листьями" дерева, а остальные узлы называются промежуточными (нетерминальными).
В теории графов сетью называется взвешенный ориентированный граф, т.е. граф, в котором каждой связи сопоставлено определенное число.
Если L — это множество взвешенных связей, a N, как и ранее, множество узлов, то сеть — это любое подмножество NxLxN, в котором имеет значение порядок в триадах.
Связи в сети практически всегда являются ориентированными, поскольку отношения, представленные взвешенными связями, не должны быть симметричными.
Обыкновенные графы используются для представления взаимоотношений между объектами в пространстве или во времени. Можно использовать их и для представления более абстрактных причинно-следственных связей. Для представления иерархических классификаций и сетей применяются деревья.
Семантические сети используются в качестве структуры, пригодной для представления информации общего вида, — узлы представляют некоторые концепты (понятия), а связи — отношения между концептами.
Аппарат ассоциативных сетей все шире используется для моделирования объектов и их взаимосвязей в конкретных предметных областях, что необходимо для построения экспертных систем.