Навигация
Главная
Поиск
Форум
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
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Имитационное мо... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Реклама
Сейчас на сайте
Гостей: 9
На сайте нет зарегистрированных пользователей

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

Моделирование работы участка термической обработки шестерен на GPSS + По...
Двунаправленный динамический список на Delphi + Блок схемы
Калькулятор на Delphi с переводом в другую систему исчисления + Блок схемы

7.2. Поиск в лабиринте


Стоит темная грозовая ночь. Когда вы ехали по пустынной сельской дороге, ваша машина сломалась и вы оказались перед входом сказочного дворца. Вы подошли к двери, обнаружили, что она открыта, и стали искать телефон. Как нужно осматривать дворец, чтобы не заблудиться и быть уверенным, что вы осмотрели каждую комнату? И каков кратчайший путь к телефону? Именно для таких крайних обстоятельств и разработаны методы поиска в лабиринте.
Во многих программах для ЭВМ, подобных программам поиска в лабиринте, полезно вести информационные списки и просматривать нужный список, когда впоследствии понадобится некоторая информация. Например, если мы решили найти во дворце телефон, нам может понадобиться список уже осмотренных комнат. Чтобы не плутать, снова и снова заходя в те же самые комнаты, нам нужно просто записывать на листке бумаги номера комнат, где мы уже побывали. Перед тем, как войти в комнату, мы проверяем, нет ли ее номера на нашем листке. Если он есть, мы пропускаем эту комнату, потому что уже должны были побывать там раньше. Если номера этой комнаты нет на листке, то мы записываем ее номер и входим в комнату, и так до тех пор, пока не найдем телефон.
Этот метод нуждается в некоторых уточнениях, но мы сделаем их позднее, при обсуждении проблем поиска на графе. А сначала давайте запишем по порядку наши шаги, чтобы знать, какие задачи предстоит решать:
1. Подойти к двери какой-либо комнаты. Если номер комнаты есть в нашем списке, то перейти к шагу 1.
2. Если в поле зрения нет ни одной комнаты, то «вернуться назад» через ту комнату, через которую мы прошли сюда, и посмотреть, нет ли возле нее каких-либо других комнат.
3. Иначе дописать номер комнаты к нашему списку.
4. Поискать телефон в этой комнате.
5. Если телефона нет, то перейти к шагу 1. Иначе мы останавливаемся, и наш список содержит путь, который мы прошли, чтобы попасть в нужную комнату.
Будем считать, что номера комнат являются константами (безразлично целыми числами или атомами). Сначала мы можем решить, как просматривать номера комнат, записанные на листке бумаги. Для этого можно использовать предикат принадлежит , определенный в разд. 3.3, полагая, что содержимое листка бумаги представлено в виде списка. Теперь мы можем продвинуться в решении задачи поиска в лабиринте. Рассмотрим небольшой пример, где задан план дома, комнаты которого помечены буквами (см. рис. 7.2). Заметим, что просветы в стенах обозначают двери и что комната а – это просто представление пространства вне дома. Имеются двери, ведущие из а в b , из с в d , из f в е , и так далее. Сведения о том, где имеются двери, могут быть представлены в виде фактов Пролога:
д(а,b).
д(b,е).
д(b,с).
д(d,c).
д(c,d).
д(e,f).
д(g,e).




Заметим, что информация о наличии дверей не избыточна. Например, мы сказали, что имеется дверь, ведущая из комнаты  g в комнату е , но не сказали, что имеется дверь, ведущая из комнаты е в комнату g , т. е. мы не зафиксировали утверждение д(e,g) . Чтобы обойти эту проблему представления двухсторонних дверей, мы могли бы повторно записать д-факт для каждой двери с перестановкой аргументов. Или мы могли бы устроить программу таким образом, чтобы она понимала, что каждая дверь фактически может рассматриваться как двухсторонняя. Этот вариант мы и выбрали в нижеследующей программе.
Чтобы перейти из одной комнаты в другую, мы должны распознать один из следующих случаев:
• мы находимся в той комнате, которая нам нужна, или
• мы должны войти в дверь и распознать эти случаи снова (рекурсивно).
Рассмотрим целевое утверждение переход(X,Y,T) , которое доказуемо (согласуется с базой данных), если можно перейти из комнаты X в комнату Y . Третий аргумент Т – это наш листок бумаги, который мы носим с собой и на котором записан перечень номеров комнат, в которых мы побывали до сего момента.
Граничное условие перехода из комнаты X в комнату Y состоит в том, что, возможно, мы уже находимся в комнате Y (т. е., возможно, X есть Y ). Это условие представлено в виде утверждения:
переход(Х,Х,Т).



В противном случае мы выбираем некоторую смежную комнату, назовем ее Z , и смотрим, были ли мы в ней раньше. Если нет, то «переходим» из Z в Y , дописывая Z в наш список. Все это выражается в виде следующего утверждения:
переход(Х, Y,T,):- Д(Х,Z),not(принадлежит(Z,Т)), переход(Z,Y,[Z|T]).



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



Или, используя предикат ';' (обозначающий дизъюнкцию), можно записать:
переход(Х,Х,Т).
переход(Х,Y,T):- (д(Х,Z); д(Z,Х)), not(принадлежит (Z,T)),пepexод(Z,Y,[Z|T]).



Теперь о том, как найти телефон. Рассмотрим целевое утверждение есть_телефон(X) , которое согласуется с базой данных, если в комнате X есть телефон. Если мы хотим сказать, что в комнате g есть телефон, то мы просто записываем в нашу базу данных факт есть_телефон(g) . Предположим, мы начали поиск с комнаты а . Один из способов узнать дорогу к телефону – это задать вопрос:
?- переход(а,Х,[]), есть_телефон(X).
Это – вопрос типа «создать и проверить», который находит достижимые комнаты и затем проверяет наличие в них телефона. Другой способ – это найти сопоставление сначала для предиката есть_телефон(Х) , а затем попробовать перейти из комнаты а в X :
?- есть_телефон(Х), переход(а,Х,[]).



Последний метод более эффективен, однако он подразумевает что мы «знаем», где телефон, еще до того, как начали поиск.
Начальная установка третьего аргумента пустым списком означает, что мы начинаем поиск, имея чистый лист бумаги. Изменяя эту начальную установку, можно получить разные варианты поиска. Вопрос «найти телефону не заходя в комнаты d и f » можно выразить на Прологе так:
?- есть_телефон(X), переход (a,X,[d,f]).



В разд. 7.9 мы рассмотрим некоторые общие процедуры поиска по графу, в том числе программу, находящую кратчайший путь.
Упражнение 7.2. Допишите вышеприведенную программу так, чтобы она печатала такие сообщения, как «входим в комнату X » и «телефон найден в комнате Y », подставляя в них соответствующие номера комнат.
Упражнение 7.3. Может ли эта программа находить альтернативные пути? Если да, то где нужно «отсечь» , чтобы избежать нахождения более чем одного пути?
Упражнение 7.4. Чем определяется порядок, в котором просматриваются комнаты?

Опубликовал Kest July 09 2009 21:10:26 · 0 Комментариев · 9399 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Delphi 6/7 базы д...
Tetris 2002
Plasma
IPAddresseEdit
Панель "ссылки"
Delphi. Разработк...
Dreamsoft Progres...
База данных фильм...
FreeNet
3d Tank [Исходник...
EMS QuickExport S...
WinAmp
Модифицированная ...
Программа предназ...
Пользовательская...
Использование Lis...
Основы Delphi
Encrypt Decrypt
Win-Prolog 3.618
Создание отчетов ...

Топ загрузок
Приложение Клие... 100771
Delphi 7 Enterp... 97787
Converter AMR<-... 20259
GPSS World Stud... 17014
Borland C++Buil... 14186
Borland Delphi ... 10267
Turbo Pascal fo... 7372
Калькулятор [Ис... 5968
Visual Studio 2... 5205
Microsoft SQL S... 3661
Случайные статьи
Обработка ошибок
Маршрутизатор обра...
Топовые игровые ав...
Удаленные клиенты ...
Процедура SetActiv...
Онлайн-казино
Введение в Турбо П...
Онлайновая инфогра...
2000 Professional(...
К головоломке
Идентификация объе...
Яндекс учитывает м...
14.1. Структура да...
Тестирование файлов
Фотоаппарат: настр...
Условия коллектива
RETURN (ВЕРНУТЬ)
Специальные встрое...
Другие разделы полей
Манчестерское коди...
8.7. Задачи
Программа Stufflt ...
Игровые автоматы к...
Популярно о PageRank
ВВОД ИНФОРМАЦИИ С...
Статистика



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


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