Навигация
Главная
Поиск
Форум
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
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65418
ТЕХНОЛОГИИ ДОСТ... 62344
Имитационное мо... 58000
Реклама
Сейчас на сайте
Гостей: 16
На сайте нет зарегистрированных пользователей

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

Лабораторная работа по динамическим спискам на Turbo Pascal (перемещение...
Обратное размещение элементов ЭВС на Delphi + Пояснительная записка
Расчет обратной матрицы на Delphi + Пояснительная записка

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
Механизм возврата и процедурная семантика


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

меньше(X.Y) :-
XY, write(X),
write ('меньше, чем'),write(Y).
меньше(Х.У) :-
XY, write(Y),
write ('меньше, 4CM'),write(X).




Целевое утверждение

?- меньше (5, 2).




сопоставляется с головой первого утверждения при Х=5 и У=2. Однако не удается согласовать первый член конъюнкции в теле утверждения XПролог выдает сообщение “2 меньше, чем 5”. Запрос

?-меньше (2, 2).




сопоставляется с головой первого утверждения, но тело утверждения согласовать не удается. Затем происходит сопоставление с головой второго утверждения, но согласовать тело опять-таки оказывается невозможно. Поэтому попытка доказательства целевого утверждения меньше(2, 2) заканчивается неудачей.
Такой процесс согласования целевого утверждения путем прямого продвижения по программе называется прямой трассировкой (forward tracking). Даже если целевое утверждение согласовано, с помощью прямой трассировки мы можем попытаться получить другие варианты его доказательства, т.е. вновь согласовать целевое утверждение.
Пролог производит доказательство конъюнкции целевых утверждений слева направо. При этом может встретиться целевое утверждение, согласовать которое не удается. Если такое случается, то происходит смещение влево до тех пор, пока не будет найдено целевое утверждение, которое может быть вновь согласовано, или не будут исчерпаны все предшествующие целевые утверждения. Если слева нет целевых утверждений, то конъюнкцию целевых утверждений согласовать нельзя. Однако, если предшествующее целевое утверждение может быть согласовано вновь, Пролог возобновляет процесс доказательства целевых утверждений слева направо, начиная со следующего справа целевого утверждения. Описанный процесс смещения влево для повторного согласования целевого утверждения и возвращения вправо носит название механизма возврата.
В качестве примера использования механизма возврата напишем процедуру для поиска пути в лабиринте. Лабиринт представлен фактами вида:
стена(I, J) для позиции в I-м ряду и J-й колонке, где есть стена, отсутств_стена(I, J) для позиции в I-м ряду и J-й колонке, где нет стены, выход(I, J) для позиции в I-м ряду и J-й колонке, являющейся выходом
Рассмотрим небольшой лабиринт (рис. 2.4):

Лабиринт
Лабиринт
Рис. 2.4

Последний ряд лабиринта описывается фактами:

стена(4,1).
стена(4,3).
стена(4,4).
стена(4,5).
отсутств_стена(4,2).




Если задана исходная позиция, путь к выходу можно найти следующим образом.
Граничное условие:
Если исходная позиция является выходом, то путь найден.
Рекурсивные условия:
Ищем путь из исходной позиции в северном направлении. Если пути нет, идем на юг. Если пути нет, идем на запад. Если нельзя, идем на восток. Если соседняя позиция на севере (юге, западе, востоке) является стеной, то нет смысла искать путь из начальной позиции к выходу. Чтобы не ходить кругами, будем вести список позиций, в которых мы побывали.
Изложенному способу решения задачи соответствует процедура путь: она ищет путь (второй аргумент) к выходу из некоторой позиции (первый аргумент). Третьим аргументом является список позиций, где мы побывали.

% Терм a(I, J) представляет позицию в
% I-м ряду и J-й колонке.
% Нашли путь ?
путь(а(I, J),[а(I, J)], Были) :- выход(I, J).
% Пытаемся идти на север
путь(а(I, J),[а(I, J) | Р], Были) :-
К is I-1,
можем_идти(a (K, J), Были),
путь(а(I, J) ,Р, [a(K, J) | Были]).
% Пытаемся идти на юг
путь(а(I, J),[а(I, J) | Р], Были) :-
К is I+1,
можем_идти(a (K, J), Были),
путь(а(I, J) ,Р, [a(K, J) | Были]).
% Пытаемся идти на запад
путь(а (I, J), [a (I, J) | P], Были) :-
L is J-1,
можем_идти(а(I, L), Были),
путь(а(I, L), Р, [а(I, L)| Были]).
% Пытаемся идти на восток
путь(а (I, J), [a (I, J) | P], Были) :-
L is J+1,
можем_идти(а(I, L), Были),
путь(а(I, L), Р, [а(I, L)| Были]).
% в позицию a(I, J) можно попасть при
% условии, что там нет стены и мы
% не побывали в ней прежде
можем_идти(а(I, J)), Были) :-
отсутств_стена(I, J),
not (принадлежит (a (I, J), Были)).




Для того чтобы понять, каким образом процедура ищет путь к выходу, рассмотрим процесс согласования запроса с описанием лабиринта, описанного выше:

?-путь(а(4,2), Р, [а(4.2)]).




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

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).




Целевое утверждение не удается согласовать с первым утверждением

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)])




так как а (3,2) не является выходом. Во втором утверждении предпринимается попытка найти путь, двигаясь на север, т.е. согласовать целевое утверждение

путь(а(2,2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).




Ни одно из утверждений не может согласовать

путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).




Первое утверждение - потому, что а (2, 2) не является выходом, второе - потому, что северная позиция является стеной, третье утверждение - потому, что в южной позиции мы уже побывали, а четвертое и пятое утверждения - потому, что западная и восточная границы - это стены.
Неудача в согласовании

путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)])




заставляет Пролог-систему вернуться в ту точку, где было выбрано второе утверждение при попытке согласовать

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).




Решение пересматривается и выбирается третье утверждение.
В третьем утверждении осуществляется попытка найти путь, двигаясь на юг, но она оказывается неудачной, поскольку мы уже побывали в позиции а (4, 2). Тогда, чтобы согласовать

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]),




выбирается четвертое утверждение. Мы успешно находим путь, двигаясь в западном направлении к позиции а(3,1), которая и является выходом. Рекурсия сворачивается, и в результате получается путь

Р=[а(4, 2),а(3, 2), а(3,1)]




другие решения(да/нет)? да
Других решений нет
Альтернативный путь

[a(4,2), a(3,2), a(2,2), a(3,2), a(3,1)]




мы получить не можем, потому что не разрешается дважды бывать в одной и той же позиции.
Описанная процедура не обязательно находит кратчайший путь к выходу. Кратчайший путь можно найти, генерируя альтернативные пути с помощью вызова состояния неудачи и запоминая кратчайший из них.
Опубликовал Kest October 13 2010 17:05:39 · 0 Комментариев · 4647 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Microsoft SQL Ser...
DragMe [Исходник ...
Х. М. Дейтел, П. ...
Мод "проверочный ...
XPButtons
3D Тетрис [Исходн...
Конвертирование и...
3d Tank [Исходник...
База Allsubmitter...
Delphi. Учимся на...
Длинный заголовок...
WAP версия сайта
PHP 5 для "чайников"
Пример работы с ф...
Java 2. Наиболее ...
Правила программи...
Info
45 уроков по дельфи
IMtale
Размещение элемен...

Топ загрузок
Приложение Клие... 100471
Delphi 7 Enterp... 87462
Converter AMR<-... 20080
GPSS World Stud... 13086
Borland C++Buil... 11930
Borland Delphi ... 8632
Turbo Pascal fo... 7041
Visual Studio 2... 5000
Калькулятор [Ис... 4857
FreeSMS v1.3.1 3543
Случайные статьи
Операции над матри...
Когда количество э...
смарт-карты или ко...
Приемы эквивалентн...
Функции приведения
Доступ к аргумента...
Контроль ошибок
Полудуплексные про...
ВСТРОЕННЫЕ ПРЕДИКА...
Простое наследование
Табл. 3. Анализ те...
Яндекс учитывает с...
Параметр-шаблон
Сайты, посвященные...
Автопоилка для кошек
Полиморфизм
Настройка фотоаппа...
Взаимосвязь станда...
Интеллектуальные м...
Создание рабочей к...
Защита аутентифика...
Открытие существую...
ПРЕДИСЛОВИЕ К ПЕРВ...
Играть в Кекс на с...
Триггеры проверки
Статистика



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


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