Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Рассмотрим следующее предложение:
p:- p.
В нем говорится: "p истинно, если p истинно". С точки зрения декларативного смысла это совершенно корректно, однако в процедурном смысле оно бесполезно. Более того, для пролог-системы такое предложение может породить серьезную проблему. Рассмотрим вопрос:
?- p.
При использовании вышеприведенного предложения цель p будет заменена на ту же самую цель p; она в свою очередь будет заменена снова на p и т.д. В этом случае система войдет в бесконечный цикл, не замечая, что никакого продвижения в вычислениях не происходит.
Данный пример демонстрирует простой способ ввести пролог-систему в бесконечный цикл. Однако подобное зацикливание могло встретиться и в некоторых наших предыдущих программах, если бы мы изменили порядок предложений, или же порядок целей в них. Будет полезно рассмотреть несколько примеров.
В программе об обезьяне и банане предложения, касающиеся отношения ход, были упорядочены следующим образом: схватить, залезть, подвинуть, перейти (возможно, для полноты следует добавить еще "слезть"). В этих предложениях говорится, что можно схватить, можно залезть и т.д. В соответствии с процедурной семантикой Пролога порядок предложений указывает на то, что обезьяна предпочитает схватывание залезанию, залезание — передвиганию и т.д. Такой порядок предпочтений на самом деле помогает обезьяне решить задачу. Но что могло случиться. если бы этот порядок был другим? Предположим, что предложение с "перейти" оказалось бы первым. Процесс вычисления нашей исходной цели из предыдущего раздела
?- можетзавладеть(состояние(удвери, наполу, уокна, неимеет)).
протекал бы на этот раз так. Первые четыре списка целей (с соответствующим образом переименованными переменными) остались бы такими же, как и раньше:
(1) можетзавладеть(состояние(удвери, наполу, уокна, неимеет)).
Применение второго предложения из можетзавладеть ("может2") породило бы
(2) ход(состояние(удвери, наполу, уокна, неимеет), М', S2'),
можетзавладеть(S2')
С помощью хода перейти(уокна, Р2') получилось бы
(3) можетзавладеть(состояние(Р2', наполу, уокна, неимеет))
Повторное использование предложения "может2" превратило бы список целей в
(4) ход(состояние(Р2', наполу, уокна, неимеет), М'', S2''),
можетзавладеть(S2'')
С этого момента начались бы отличия. Первым предложением, голова которого сопоставима с первой целью из этого списка, было бы теперь "перейти" (а не "залезть", как раньше). Конкретизация стала бы следующей:
S2'' = состояние(Р2'', наполу, уокна, неимеет).
Поэтому список целей стал бы таким:
(5) можетзавладеть(состояние(Р2'', наполу, уокна, неимеет))
Применение предложения "может2" дало бы
(6) ход(cocтояниe(P2'', наполу, yoкнa, неимeeт), M''', S2'''),
можетзавладеть(S2''')
Снова первый было бы попробовано "перейти" и получилось бы
(7) можетзавладеть(состояние(Р2''', наполу, уокна, неимеет))
Сравним теперь цели (3), (5) и (7). Они похожи и отличаются лишь одной переменной, которая по очереди имела имена Р', Р'' и P'''. Как мы знаем, успешность цели не зависит от конкретных имен переменных в ней. Это означает, что, начиная со списка целей (3), процесс вычислений никуда не продвинулся. Фактически мы замечаем, что по очереди многократно используются одни и те же два предложения: "может2" и "перейти". Обезьяна перемещается, даже не пытаясь воспользоваться ящиком. Поскольку продвижения нет, такая ситуация продолжалась бы (теоретически) бесконечно: пролог-система не сумела бы осознать, что работать в этой направлении нет смысла.
Данный пример показывает, как пролог-система может пытаться решить задачу таким способом, при котором решение никогда не будет достигнуто, хотя оно существует. Такая ситуация не является редкостью при программировании на Прологе. Да и при программировании на других языках бесконечные циклы не такая уж редкость. Что действительно необычно при сравнении Пролога с другими языками, так это то, что декларативная семантика пролог-программы может быть правильной, но в то же самое время ее процедурная семантика может быть ошибочной в том смысле, что с помощью такой программы нельзя получить правильный ответ на вопрос. В таких случаях система не способна достичь цели потому, что она пытается добраться до ответа, но выбирает при этом неверный путь.
Теперь уместно спросить: "Не можем ли мы внести какое-либо более существенное изменение в нашу программу, так чтобы полностью исключить опасность зацикливания? Или же нам всегда придется рассчитывать на удачный порядок предложений и целей?" Как оказывается, программы, в особенности большие, были бы чересчур ненадежными, если бы можно было рассчитывать лишь на некоторый удачный порядок. Существует несколько других методов, позволяющих избежать зацикливания и являющихся более общими и надежными, чем сам по себе метод упорядочивания. Такие методы будут систематически использоваться дальше в книге, в особенности в тех главах, в которых пойдет речь о нахождении путей (в графах), о решения интеллектуальных задач и о переборе.
Варианты программы, полученые путем переупорядочивания предложений и целей
Уже в примерах программ гл. 1 существовала скрытая опасность зацикливания. Определение отношения предок в этой главе было таким:
предок(X, Z):-
родитель(X, Z).
предок(X, Z):-
родитель(X, Y),
предок(Y, Z).
Проанализируем некоторые варианты этой программы. Ясно, что все варианты будут иметь одинаковую декларативную семантику, но разные процедурные семантики.
В соответствии с декларативной семантикой Пролога мы можем, не меняя декларативного смысла, изменить
(1) порядок предложений в программе и
(2) порядок целей в телах предложений.
Процедура предок состоит из двух предложений, и одно из них содержит в своем теле две цели. Возможны, поэтому, четыре варианта данной программы, все с одинаковым декларативным смыслом. Эти четыре варианта можно получить, если
(1) поменять местами оба предложения и
(2) поменять местами цели в каждом из этих двух последовательностей предложений.
Соответствующие процедуры, названные пред1, пред2, пред3 и пред4, показаны на рис. 2.16.
Есть существенная разница в поведении этих четырех декларативно эквивалентных процедур. Чтобы это продемонстрировать, будем считать, отношение родитель определенным так, как показано на рис. 1.1 гл. 1. и посмотрим, что произойдет, если мы спросим, является ли Том предком Пат, используя все четыре варианта отношения предок:
?- пред1(том, пат).
да
?- пред2(том, пат).
да
?- пред3(том, пат).
да
?- пред4(том, пат).
% Четыре версии программы предок
% Исходная версия
пред1(X, Z):-
родитель(X, Z).
пред1(X, Z):-
родитель(X, Y),
пред1(Y, Z).
% Вариант а: изменение порядка предложений в исходной версии
пред2(X, Z):-
родитель(X, Y),
пред2(Y, Z).
пред2(X, Z):-
родитель(X, Z).
% Вариант b: изменение порядка целей во втором предложении
% исходной версии
пред3(X, Z):-
родитель(X, Z).
пред3(X, Z):-
пред3(X, Y),
родитель(Y, Z).
% Вариант с: изменение порядка предложений и целей в исходной
% версии
пред4(X, Z):-
пред4(X, Y),
родитель(Y, Z).
пред4(X, Z):-
родитель(X, Z).
Рис. 2.16. Четыре версии программы предок.
В последнем случае пролог-система не сможет найти ответа. И выведет на терминал сообщение: "Не хватает памяти".
На рис. 1.11 гл. 1 были показаны все шаги вычислений по пред1 (в главе 1 она называлась предок), предпринятые для ответа на этот вопрос. На рис 2.17 показаны соответствующие вычисления по пред2, пред3 и пред4. На рис. 2.17 (с) ясно видно, что работа пред4 — бесперспективна, а рис. 2.17(а) показывает, что пред2 довольно неэффективна по сравнению с пред1: пред2 производит значительно больший перебор и делает больше возвратов по фамильному дереву.
Такое сравнение должно напомнить нам об общем практическом правиле при решении задач: обычно бывает полезным прежде всего попробовать самое простое соображение. В нашем случае все версии отношения предок основаны на двух соображениях:
• более простое — нужно проверить, не удовлетворяют ли два аргумента отношения предок отношению родитель;
• более сложное — найти кого-либо "между" этими двумя людьми (кого-либо, кто связан с ними отношениями родитель и предок).
Из всех четырех вариантов отношения предок, пред1 использует наиболее простое соображение в первую очередь. В противоположность этому пред4 всегда сначала пробует использовать самое сложное. Пред2 и пред3 находятся между этими двумя крайностями. Даже без детального изучения процессов вычислений ясно, что пред1 следует предпочесть просто на основании правила "самое простое пробуй в первую очередь".
Наши четыре варианта процедуры предок можно далее сравнить, рассмотрев вопрос: "На какие типы вопросов может отвечать тот или иной конкретный вариант и на какие не может?" Оказывается, пред1 и пред2 оба способны найти ответ на любой вид вопроса относительно предков; пред4 никогда не находит ответа, а пред3 иногда может найти, иногда нет. Вот пример вопроса, на который пред4 ответить не может:
?- пред3(лиз, джим).
Такой вопрос тоже вводит систему в бесконечную рекурсию. Следовательно и пред3 нельзя признать верным с точки зрения процедурного смысла.
Рис. 2.17. Поведение трех вариантов формулировки отношения предок при ответе на вопрос, является ли Том предком Пат?
Дата публикования: 2015-10-09; Прочитано: 243 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!