Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 59630
Реклама
Сейчас на сайте
Гостей: 7
На сайте нет зарегистрированных пользователей

Пользователей: 13,110
новичок: kostya001001
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

База данных - рабочее место кассира на Delphi + бд Access
Медиа плейер на Delphi + Пояснительная записка
Моделирование автовокзала + Отчет + Блок схема

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Представление задач в виде И/ИЛИ – графов


Представление в виде И/ИЛИ - графов наиболее хорошо приспособлено для задач, которые естественным образом разбиваются на взаимно независимые подзадачи. Примерами таких задач могут служить поиск маршрута, игровые задачи, доказательство теорем и т.п.
Для некоторых категорий задач представление в форме И/ИЛИ-графа является более естественным. Такое представление основано на разбиении задач на подзадачи. Разбиение на подзадачи дает преимущества в том случае, когда подзадачи взаимно независимы, а, следовательно, и решать их можно независимо друг от друга.
Проиллюстрируем это на примере. Рассмотрим задачу отыскания на карте дорог маршрута между двумя заданными городами, как показано на рис. 3.4. Не будем пока учитывать длину путей. Разумеется, эту задачу можно сформулировать как поиск пути в пространстве состояний. Соответствующее пространство состояний выглядело бы в точности, как карта рис. 3.4: вершины соответствуют городам, дуги - непосредственным связям между городами. Тем не менее давайте построим другое представление, основанное на естественном разбиении этой задачи на подзадачи.

Поиск маршрута из а в z на карте дорог
Представление задач в виде И/ИЛИ – графов
Рис. 3.4.

На карте рис. 3.4 мы видим также реку. Допустим, что переправиться через нее можно только по двум мостам: один расположен в городе f, другой -в городе g. Очевидно, что искомый маршрут обязательно должен проходить через один из мостов, а значит, он должен пройти либо через f, либо через g. Таким образом, мы имеем две главных альтернативы:
Для того, чтобы найти путь из а в г, необходимо найти одно из двух:
(1) путь из а в г, проходящий через f, или
(2) путь из а в г, проходящий через g.
И/ИЛИ-представление задачи поиска маршрута
И/ИЛИ-представление задачи поиска маршрута
Рис. 3.5.

Теперь каждую из этих двух альтернативных задач можно, в свою очередь, разбить следующим образом:
(1) Для того, чтобы найти путь из а в г через f, необходимо:
1.1 найти путь из а в f и
1.2 найти путь из f в z.
(2) Для того, чтобы найти путь из a в z через g, необходимо:
2.1 найти путь из а в g и
2.2 найти путь из g в z.
Для того,  чтобы  найти путь из a в z через g
Рис. 3.6.

Итак, мы имеем две главных альтернативы для решения исходной задачи: (1) путь через f или (2) путь через g. Далее, каждую из этих альтернатив можно разбить на подзадачи (1.1 и 1.2 или 2.1 и 2.2 соответственно). Здесь важно то обстоятельство, что каждую из подзадач в обоих альтернативах можно решать независимо от другой. Полученное разбиение исходной задачи можно изобразить в форме И/ИЛИ-графа (рис. 3.5). Обратите внимание на полукруглые дуги, которые указывают на отношение И между соответствующими подзадачами. Граф, показанный на рис. 3.5 - это всего лишь верхняя часть всего И/ИЛИ-дерева. Дальнейшее разбиение подзадач можно было бы строить на основе введения дополнительных промежуточных городов.
Какие вершины И/ИЛИ-графа являются целевыми? Целевые вершины - это тривиальные, или «примитивные» задачи. В нашем примере такой подзадачей можно было бы считать подзадачу «найти путь из а в с», поскольку между городами а и с на карте имеется непосредственная связь.
Рассматривая наш пример, мы ввели ряд важных понятий. И/ИЛИ-граф - это направленный граф, вершины которого соответствуют задачам, а дуги отношениям между задачами. Между дугами также существуют свои отношения. Это отношения И и ИЛИ, в зависимости от того, должны ли мы решить только одну из задач-преемников или же несколько из них (см. рис. 3.6). В принципе из вершины могут выходить дуги, находящиеся в отношении И вместе с дугами, находящимися в отношении ИЛИ. Тем не менее, мы будем предполагать, что каждая вершина имеет либо только И-преемников, либо только ИЛИ-преемников; дело в том, что в такую форму можно преобразовать любой И/ИЛИ-граф, вводя в него при необходимости вспомогательные ИЛИ-вершины. Вершину, из которой выходят только И-дуги, называют И-вершиной; вершину, из которой выходят только ИЛИ-дуги, - ИЛИ-вершиной.
Что же является решением в случае И/ИЛИ-представления? Решение должно, конечно, включать в себя все подзадачи И-вершины. Следовательно, это уже не путь, а дерево. Такое решающее дерево Т определяется следующим образом:
• исходная задача Р - это корень дерева Т;
• если Р является ИЛИ-вершиной, то в Т содержится только один из ее преемников (из И/ИЛИ-графа) вместе со своим собственным решающим деревом;
• если Р - это И-вершина, то все ее преемники (из И/ИЛИ-графа) вместе со своими решающими деревьями содержатся в Т.

Такое решающее дерево Т определяется следующим образом
Рис. 3.7
Иллюстрацией к этому определению может служить рис. 3.7. Используя стоимости, мы можем формулировать критерии оптимальности решения. Например, можно определить стоимость решающего графа как сумму стоимостей всех входящих в него дуг. Тогда, поскольку обычно мы заинтересованы в минимизации стоимости, мы отдадим предпочтение решающему графу, изображенному на рис. 3.7(с).
Для задачи отыскания кратчайшего маршрута (рис. 3.4) И/ИЛИ-граф вместе с функцией стоимости можно определить следующим образом:
• ИЛИ-вершины представляются в форме X-Z, что означает: найти кратчайший путь из X в Z.
• И-вершины имеют вид X-Z через Y , что означает: найти кратчайший путь из X в Z, проходящий через Y.
• Вершина X-Z является целевой вершиной (примитивной задачей), если на карте существует непосредственная связь между X и Z.
• Стоимость каждой целевой вершины X-Z равна расстоянию, которое необходимо преодолеть по дороге, соединяющей X с Z.
• Стоимость всех остальных (нетерминальных) вершин равна 0.
В этом разделе нас будет интересовать какое-нибудь решение задачи независимо от его стоимости, поэтому проигнорируем пока стоимости связей или вершин И/ИЛИ-графа. Простейший способ организовать поиск в И/ИЛИ-графах средствами Пролога - это использовать переборный механизм, заложенный в самой пролог-системе. Оказывается, что это очень просто сделать, потому что процедурный смысл Пролога это и есть не что иное, как поиск в И/ИЛИ-графе. Например, И/ИЛИ-граф рис. 3.7 (без учета стоимостей дуг) можно описать при помощи следующих предложений:
a :- b. % а - ИЛИ-вершина с двумя преемниками
a :- c. % b и с
b :- d, е. % b - И-вершина с двумя преемниками d и е
c :- h.
c :- f, g.
f :- h, i.
d. g. h. % d, g и h - целевые вершины




Для того, чтобы узнать, имеет ли эта задача решение, нужно просто спросить:
?- а.



Получив этот вопрос, пролог - система произведет поиск в глубину в дереве рис. 3.7 и после того, как пройдет через все вершины подграфа, соответствующего решающему дереву рис. 3.7(b), ответит «да».
Опубликовал Kest October 16 2010 20:57:23 · 0 Комментариев · 10222 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Info
Анекдоты с ostrie.ru
Факториал [Исходн...
Интерактивный инт...
PDJ Scrollers
NotePad Pro [Исхо...
Berg
Java 2 - Эффектив...
Базы данных в Инт...
RSS Feeds
PHP: Полезные приемы
Еext Editor
PHP: настольная к...
Adapter (пример D...
Geo-Whois
Разработка распре...
Моделирование дви...
Print Grid
45 уроков по дельфи
Удаление своего EXE

Топ загрузок
Приложение Клие... 100515
Delphi 7 Enterp... 90501
Converter AMR<-... 20093
GPSS World Stud... 15031
Borland C++Buil... 12762
Borland Delphi ... 8973
Turbo Pascal fo... 7097
Калькулятор [Ис... 5142
Visual Studio 2... 5020
FreeSMS v1.3.1 3555
Случайные статьи
4.1. Порождение ...
Блок TABULATE
LINK (ВВЕСТИ В СПИ...
Отправка и получен...
Вот что происходит...
Максимальная разни...
Малая вирусная энц...
О стандартах прогр...
Однокоренная иерархия
Обработка щелчков ...
Управления ipl
Предварительная по...
Эконом мебель
Таблицы имеют след...
Игровые автоматы. ...
КРАТКОЕ ОПИСАНИЕ G...
Метод Чёрчмена-Акофа
ПРИЛОЖЕНИЕ 5. Карт...
Создание заставок ...
Этап опытной экспл...
Задача о шахматах....
Встроенные массивы...
Unit file format e...
Microsoft Internet...
На какие на какие ...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?