русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Процессы поиска на графе

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

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

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

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

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

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

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

При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач. Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Подзадачи считается очевидной, если ее решение общеизвестно, или получено ранее. Процесс решения задачи разбиение на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ- графом. В графе выделяются два типа вершин: конъюнктивные вершины и дизъюнктивные вершины. Графическое представление вершин приведено далее на Рисунок 6.6.


 

Рисунок 4.2 Пространство состояний, построенное поиском в глубину (а) и поиском в ширину (б)


Пример графического представления разбиения на подзадачи, приведен на Рисунок 4.3.

 

Рисунок 4.3 Графическое представление разбиения на подзадачи

Цель процесса поиска в И/ИЛИ графе- показать, что начальная вершина разрешима, т.е. для этой вершины существует решающий граф. Определение разрешимой вершины в И/ИЛИ графе можно сформулировать рекурсивно следующим образом:

  1. Конечные (целевые) вершины разрешимы, так как их решение известно по исходному предположению.
  2. Вершина ИЛИ разрешима тогда, и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин.
  3. Вершина И разрешима тогда и только тогда, когда разрешима каждая из ее вершин.

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

Следующая программа иллюстрирует стратегию поиска в глубину и обратную цепочку рассуждений. Предположим, дерево (Рисунок 4.4) отражает транспортное сообщение между населенными пунктами.

Факты, означающие прямую связь между узлами графа (городами), могут выглядеть так:

dconnect(a,b)

dconnect(c,f)

dconnect(a,c)

dconnect(c,g)

dconnect(b,d)

dconnect(f,h)

dconnect(b,e)

dconnect(f,i)

 

Рисунок 4.4 Транспортное сообщение между населенными пунктами

Добавим косвенную связь connect(X,Y) для исключения зацикливания.

Правило на языке PROLOG, определяющее маршрут вниз по дереву, выглядит так:

connect(X,Y) if dconnect(X,Y).

Факт connect(X,Y)- истинна, если истина факт dconnect(X,Y).

Правило, проверяющее, есть ли связь между пунктами X и Y через промежуточный пункт Z:

connect(X,Y) if dconnect(X,Z), dconnect(Z,Y).

Простое правило всегда ставят первым - это уменьшит время поиска решения. Стратегию поиска в глубину применяют для решения проблемы, где все пути поиска от вершины дерева до его основания имеют одинаковую длину. При неодинаковой длине пригоден поиск в ширину. Текст программы, проверяющей есть ли связь между пунктами X и Y приведена в Приложении 1.

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

Просмотров:

Вернуться в оглавление:Экспертные системы



Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.