Навигация
Главная
Поиск
Форум
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
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

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

Игра Sokoban на Delphi + Блок схемы
Моделирование работы аэропорта на GPSS + Пояснительная записка
Расчет обратной матрицы на Delphi + Пояснительная записка

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
7.9. Поиск по графу


Граф – это сеть, состоящая из узлов, соединенных дугами. Например, географическую карту можно рассматривать как граф, где узлами являются населенные пункты, а дугами, соединяющие их дороги. Если вы хотите найти кратчайший маршрут между двумя населенными пунктами, вам предстоит решить задачу нахождения кратчайшего пути между двумя узлами графа.
Проще всего описать граф в базе данных с помощью фактов, представляющих дуги между узлами графа. На рис, 7.3 приведен пример графа и его представления с помощью фактов. Чтобы пройти от узла g к узлу а , мы можем пойти по пути g , d , e , а или по одному из многих других возможных путей. Если мы представляем ориентированный граф, то предикат а следует понимать так, что а(Х, Y) означает, что существует дуга из X в Y , но из этого не следует существование дуги из Y в X . В данном разделе мы будем иметь дело только с неориентированными графами, у которых все дуги двунаправленные. Это допущение совпадает с тем, которое мы делаем в разд. 7.2 при поиске в лабиринте.
Простейшая программа поиска по графу, представленному так, как указано выше, выглядит следующим образом:
переход(Х,X).
переход(Х,Y):- (a(X,Z);a(Z,X)), переход(Z,Y).



К сожалению, эта программа может зацикливаться. Поэтому, как и раньше, мы используем список Т для хранения перечня тех узлов, в которых мы уже побывали в какой-либо рекурсии предиката.
переход(Х,Х,Т).
переход(Х,Y,T):- (a(X,Z);a(Z,X)), not (принадлежит(Z, Т)),переход(Z, Y,[Z|T]).



Эта программа, разработанная в разд. 7.2, осуществляет так называемый поиск «вглубь», поскольку вначале рассматривается только один из соседей узла по графу, Другие же соседи игнорируются до тех пор, пока неудачные попытки согласовать цели в рекурсивных вызовах не возвратят Пролог к рассмотрению данного узла.
Теперь давайте рассмотрим такой поиск по графу, который мог бы быть полезен на практике. Как быть, если мы должны спланировать маршрут поездки из одного города Северной Англии в другой? Для этого потребуется база данных с информацией о дорогах между городами в Северной Англии и их протяженности:
а(ньюкасл,карлайл,58).
а(карлайл,пенрит,23).
а(дарлингтон,ньюкасл,40).
а(пенрит, дарлингтон,52).
а(уэркингтон,карлайл,33).
а(уэркингтон,пенрит,39).



На некоторое время мы можем забыть о расстояниях и определить новый предикат:
a(X,Y):- a(X,Y,Z).



С помощью этого определения предиката а уже имеющаяся программа поиска по графу ( переход ) будет находить пути, по которым можно переезжать из одного места на графе в любое другое. Однако программа переход имеет недостаток: когда она успешно завершается, мы не знаем, какой путь она нашла. По меньшей мере мы вправе ожидать от программы переход выдачи нам в нужном порядке списка мест, которые придется посетить. Тем более, что в программе имеется перечень этих мест, правда, в порядке, обратном тому, какой нам нужен. Чтобы получить правильный список, мы можем воспользоваться программой обр , определенной в разд. 7.5. Тогда мы получим новое определение программы переход , которая возвращает найденный маршрут через свой третий аргумент:
переход(Старт,Цель,Путь):- переход0(Старт,Цель,[],R),обр(R, Путь).
переход0(Х,Х,Т,[Х|Т]).
переход0(Место,Y,Т,R):-следузел(Место,Т,Сосед),переход0(Сосед,Y,[Место|T],R).
следузел(Х,Бывали,Y):- (a(X,Y); a(Y,X)),not (принадлежит(Y,Бывали)).



Заметим, что предикат следузел позволяет получать для узла X «правильный» узел Y , т. е. такой, к которому можно непосредственно перейти от узла X . Ниже приводится пример работы этой программы при поиске маршрута из Дарлингтона в Уэркингтон:
?- переход(дарлингтон,уэркингтон,Х)
Х=[дарлингтон,ньюкасл,карлайл,пенрит,уэркингтон]



Это не самый лучший маршрут, однако, программа найдет другие маршруты если мы инициируем процесс возврата.
У этой программы много недостатков. Она совершенно не управляет выбором следующего участка пути, поскольку у нее нет доступа к полному набору возможных вариантов, а те выборы, которые у программы имеются, не представлены явно в виде структуры, которая может анализироваться программой, а неявно предопределены схемой работы механизма возврата.
Ниже приведен переработанный вариант программы, который отличается большей универсальностью. В дальнейшем мы увидим, как с помощью простых изменений в этой программе можно получить разнообразные методы поиска.
переход(Старт,Цель,Путь):- переход1([[Старт]],Цель,R),обр(R, Путь).
переход1([Первый|Ост],Цель,Первый):- Первый =[Цель|_].
переход1([[Послед|Бывали]|Прочие],Цель,Путь):-найтивсе([Z, Послед|Бывали], следузел(Послед, Бывали,Z), Список), присоединить(Список, Прочие, НовПути), переход1(НовПути,Цель,Путь).



Предикат следузел остается прежним. Предикату переход1 передается список рассматриваемых путей вместе с конечным пунктом, и в последнем аргументе он возвращает удачный путь. Список рассматриваемых путей – это просто все дороги, начинающиеся в начальной точке, которые мы уже рассмотрели. Мы надеемся, что одна из них при продлении даст путь, который приведет нас в конечный пункт. Все пути представлены в виде обратных списков населенных пунктов, так что они могут также выполнять функции перечня мест, где мы уже бывали.
В самом начале имеется только один возможный путь, который можно пытаться продлить. Это просто путь, который начинается в исходном пункте и никуда не ведет. Если мы стартуем из Дарлингтона, то это будет [дарлингтон]. Если теперь исследовать пути ведущие из Дарлингтона в соседние города, то можно обнаружить, что имеются два возможных пути [ньюкасл, дарлингтон] и [пенрит, дарлингтон]. Поскольку Уэркингтон не встречается ни на одном из этих путей, необходимо решить, какой из этих путей следует продолжить. Если принято решение продлить первый путь, то мы обнаружим, что существует всего один доступный узел – последний город на этом пути. Итак, кроме пути Дарлингтон – Пенрит у нас есть новый путь: [карлайл, ньюкасл, дарлингтон].
Наш «изыскатель», переход1 ведет полный список путей, по которым, может быть, стоит двигаться. Как же он решает какой из путей следует рассмотреть первым? Он просто выбирает первый попавшийся. Затем он ищет все возможные способы продления этого пути до следующего населенного пункта (используя найтивсе для построения списка всех таких продленных путей) и помещает получившиеся пути в начало списка для рассмотрения их на следующем уровне рекурсии.
В результате, переход1 ведет себя таким образом, что он попробует все возможные способы продления первого пути прежде чем будет рассматривать альтернативные пути. Такая стратегия поиска является одним из вариантов поиска вглубь. Между прочим, переход1 рассматривает пути совершенно в том же порядке, что и переход0. Быть может вам будет интересно выяснить, почему это так.
Если нас интересует кратчайший путь от Дарлингтона до Уэркингтона, то имеющаяся программа для этого не подходит. Первое найденное ею решение – это не кратчайший путь, а наоборот, самый длинный (в данном случае). Нам нужно изменить программу таким образом, чтобы она строила пути в порядке возрастания их длины. Если мы изменим ее так, чтобы она всегда продлевала более короткие пути, прежде чем рассматривать более длинные, то она будет вынуждена находить вначале кратчайшие пути (если измерять длину пути числом городов на нем). Полученная программа будет осуществлять поиск вширь. Единственное, что нужно сделать для этого – это вставлять новые альтернативы в конец всего списка возможностей, а не в начало, как в последнем примере. Мы просто исправим второе утверждение в определении переход1 , чтобы он выглядел следующим образом:
переход1([[Послед|Бывали]|Прочие],Цель,Путь):-найтивсе([Z,Послед|Бывали], следузел(Послед, Бывали,Z),Список), присоединить(Прочие,Список,НовПути), переход1(НовПути,Цель, Путь).



Теперь исправленная программа находит возможные пути из Дарлингтона в Уэркингтон в следующем порядке:
[дарлингтон,пенрит,уэркингтон]
[дарлингтон,ньюкасл, карлайл,уэркингтон]
[дарлингтон,пенрит,карлайл,уэркингтон]
[дарлингтон,ньюкасл,карлайл,пенрит,уэркингтон]



Мы можем значительно упростить эту программу, если уверены, что ответ на вопрос всегда существует и если нам нужно только первое решение. В этом случае отпадает необходимость в проверке на зацикливание. Попробуйте самостоятельно выяснить, почему это так.
К сожалению, путь через наименьшее число городов не обязательно будет самым кратчайшим по километражу. До сих пор мы не принимали во внимание информацию о расстояниях, имеющуюся в нашем графе. Если же мы добавим к нашему графу несколько фиктивных городов, чтобы получить:
а(ньюкасл,карлайл,58).
а(карлайл,пенрит,23).
а(городБ,городаА,15).
а(пенрит, дарлингтон,52).
а(городБ,городВ,10).
а(уэркингтон, карлайл, 33).
а(уэркингтон,городВ,5).
а(уэркингтон,пенрит,39).
а(дарлингтон,городА,25).



то путь, кратчайший по километражу, фактически будет построен последним, поскольку он проходит через большое число городов. С каждым путем, который может быть продолжен, нам нужно связать и поддерживать в процессе работы программы указатель текущей длины этого пути. Тогда программа будет всегда продлевать путь с наименьшим километражем. Такая стратегия называется поиском по критерию первый-лучший. Будем теперь представлять путь в списке альтернативных путей в виде структуры г(М, П) , где М – общая длина пути в километрах, а П – список мест, где мы уже побывали. Модифицированный предикат переходЗ находит кратчайший путь в списке альтернатив. Предикат кратчайший выделяет кратчайший путь в отдельный список, а остальные пути – в другой список. Предикат продлить находит все допустимые продолжения текущего кратчайшего пути и добавляет их к списку. Это в свою очередь требует новой версии предиката следузел , которая прибавляет расстояние до следующего города к уже вычисленному расстоянию. В целом программа выглядит так:
переходЗ (Пути,Цель,Путь):-кратчайший (Пути,Кратчайший,ОстПути), продлить(Кратчайший,Цель,ОстПути,Путь).
продлить(г(Расст,Путь),Цель,_,Путь):- Путь = [Цель|_].
продлить(г(Расст,[Послед| Бывали]),Цель,Пути,Путь):-найтивсе(г(D1,[Z,Послед|Бывали]),следузел(Послед,Бывали,Z,Расст,D1),Список), присоединить(Список,Пути,НовПути), переходЗ(НовПути,Цель,Пути).
кратчайший([Путь[Пути],Кратчайший,[ПутьЮст]):-кратчайший(Пути,Кратчайший,Ост), короче(Кратчайший,Путь),!.
кратчайший(Путь|Ост],Путь,Ост). короче(г(М1,_),г(М2, _):- M1 ‹ М2.
следузел(Х,Бывали,Y,Расст,НовРасст):-(a(X,Y,Z); a(Y,X,Z)),not(принадлежит(Y,Бывали)),НовРасст is Расст+Z.



Чтобы использовать эту программу, необходимо задать вопрос, содержащий предикат переход, определенный следующим образом:
переход (Старт,Цель,Путь):-переход3([г(0,[Старт])],Цель,R), обр(R,Путь).
Эта новая программа успешно строит возможные пути в по-рядке возрастания их фактической протяженности. Может быть, вам захочется изменить ее так, чтобы вместе с ответами она печатала длины различных путей.
Мы лишь затронули вопрос о возможных способах организации поиска по графу. Сведения о том, как осуществлять поиск по графу с использованием более эффективных критериев, чем «первый лучший», можно найти в литературе по искусственному интеллекту. Например: Nilsson N. Principles of Artificial Intelligence, Springer-Verlag, 1982 [10] и Winstone P. Artificial Intelligence, (second edition), Addison-Wesley, 1984. [11]

Опубликовал Kest July 10 2009 01:18:58 · 0 Комментариев · 11709 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Пример создания W...
Программа рисует ...
C# в кратком изло...
C++ для начинающих
TelBook
Игра змейка
Мониторинг сервер...
С. Г. Горнаков - ...
Библия хакера 2. ...
Реализация ЭЦП по...
Plasma
Интерактивный инт...
Анекдоты с ostrie.ru
AID антивирус
RAS
Создание меню на ...
EditButton
iChat v.7.0 Final...
Battle.Net - мони...
Error mod

Топ загрузок
Приложение Клие... 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
Случайные статьи
Программа выводит ...
Получение XML-схем...
Планирование справ...
WTABLE (ВЗВЕШЕННАЯ...
5.4.2. Чтение файлов
Элементы управлени...
Изготовление метал...
Компиляция - Проло...
Разработка
Таймер - компонент...
Программа TidyGUI
Задание правил сох...
CGI+SSI - пример с...
Оптимизация QueryI...
Чем занимаются СРО?
МНОГОКАНАЛЬНЫЕ УСТ...
Ремонт телефонов П...
ЛюбойЛюбой2
Где купить итальян...
Управляющая логика
Категории компонентов
Функции ввода для ...
Инсталляция библио...
Компромиссы
Используя функции ...
Статистика



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


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