 |
II . Унификация и поиск с возвратом
|
|
|
|
Сопоставление и унификация
Рассмотрим программу ch04e01.pro (рис.1) с точки зрения того, как утилита Test Goal будет отыскивать все решения следующей цели written_by(X, Y).
domains
title, author = symbol
pages= unsigned
predicates
book(title, pages)
written_by(author, title)
long_novel (title)
clauses
written_by(fleming, "DR NO").
written_by(melville, "MOBY DICK").
book("MOBY DICK", 250).
book("DR NO", 310).
long_novel (Title):-
written_by(_, Title),
book(Title, Length),
Length > 300.
Рис. 1. Листинг программы ch04e01.pro
Пытаясь выполнить целевое утверждение written_by(X, Y), Visual Prolog должен проверить каждое предложение written_by(X, Y) в программе. Сопоставляя аргументы X и Y с аргументами каждого предложения written_by, Visual Prolog выполняет поиск от начала программы до ее конца. Обнаружив предложение, соответствующее целевому утверждению, Visual Prolog присваивает значения свободным переменным таким образом, что целевое утверждение и предложение становятся идентичными. Говорят, что целевое утверждение унифицируется с предложением. Такая операция сопоставления называется унификацией.
Поскольку X и Y являются свободными переменными в целевом утверждении, а свободная переменная может быть унифицирована с любым другим аргументом (и даже с другой свободной переменной), то целевое утверждение может быть унифицировано с первым предложением written_by в программе, как показано ниже:
written_by (X,Y).
¯¯
written_by(fleming,"DR NO").
Visual Prolog устанавливает соответствие, X становится связанным с fleming, a Y – “dr no”. В этот момент Visual Prolog напечатает:
X=fleming, Y="DR NO"
Поскольку Test Goal ищет все решения для заданной цели, целевое утверждение также будет унифицировано и со вторым предложением written_by:
written_by(melville, "MOBY DICK").
Test Goal печатает второе решение:
X=melville, Y="MOBY DICK"
|
|
|
2 Solutions
Рассмотрим, как Visual Prolog выполнит следующее целевое утверждение:
long_novel(X).
Когда Visual Prolog пытается выполнить целевое утверждение, он проверяет, действительно ли обращение может соответствовать факту или заголовку правила. В нашем случае устанавливается соответствие с
long_novel(Title)
Visual Prolog проверяет предложение для long_novel, пытаясь завершить сопоставление унификацией аргументов. Поскольку в целевом утверждении X - свободная переменная, то она может быть унифицирована с любым другим аргументом. Title также не является связанным в заголовке предложения long_novel. Целевое утверждение соответствует заголовку правила, и унификация выполняется. Впоследствии Visual Prolog будет пытаться согласовывать подцели с правилом
long_novel(Title):-
written_by(_, Title), book(Title, Length), Length>300.
Пытаясь выполнить согласование тела правила, Visual Prolog обратится к первой подцели в теле правила — written_by(_, Title). Поскольку авторство книги является несущественным, на месте аргумента author появляется анонимная переменная (_). Обращение written_by (_, Title) становится текущей подцелью, и Пролог ищет решение для этого обращения.
Пролог ищет соответствие с данной подцелью от вершины и до конца программы. В результате достигается унификация с первым фактом для written_by, а именно:
written_by(_, Title),
¯¯
written_by (fleming, "DR NO").
Переменная Title связывается с "dr no", и к следующей подцели book (Title, Length) обращение выполняется уже с этим значением переменной. Далее Visual Prolog начинает очередной процесс поиска, пытаясь найти соответствие с обращением к book. Так как Title связан с "dr no", фактическое обращение выглядит как book("DR NO", Length). Процесс поиска опять начинается с вершины программы. Заметим, что первая попытка сопоставления с предложением book(“MOBY DICK", 250) завершится неудачно, и Visual Prolog перейдет ко второму предложению book в поиске соответствия. Здесь заголовок книги соответствует подцели, и Visual Prolog связывает переменную Length с величиной 310.
|
|
|
Теперь третье предложение в теле long_novel становится текущей подцелью:
length > 300.
Visual Prolog выполняет сравнение, завершающееся успешно: 310 больше, чем 300. В этот момент все подцели в теле правила выполнены, и, следовательно, обращение long_novel(X) успешно. Так как X в обращении был унифицирован с переменной Title в правиле, то значение, с которым связывается Title при подтверждении правила, возвращается и унифицируется с переменной X. Переменная Title в случае подтверждения правила имеет значение "dr no", поэтому Visual Prolog выведет:
X="DR NO"
1 Solution.
Поиск с возвратом
Часто при решении реальной задачи мы придерживаемся определенного пути для ее логического завершения. Если полученный результат не дает искомого ответа, мы должны выбрать другой путь.
Так, вам, возможно, приходилось играть в лабиринт. Один из верных способов найти конец лабиринта — это поворачивать налево на каждой развилке лабиринта до тех пор, пока вы не попадете в тупик. Тогда следует вернуться к последней развилке и попробовать свернуть вправо, после чего опять поворачивать налево на каждом встречающемся распутье. Путем методичного перебора всех возможных путей вы, в конце концов, найдете выход.
Visual Prolog при поиске решения задачи использует именно такой метод проб и возвращений назад; этот метод называется поиск с возвратом. Если, начиная поиск решения задачи (или целевого утверждения), Visual Prolog должен выбрать между альтернативными путями, то он ставит маркер у места ветвления (называемого точкой отката) и выбирает первую подцель, которую и станет проверять. Если данная подцель не выполнится, Visual Prolog вернется к точке отката и попробует проверить другую подцель.
predicates
likes(symbol,symbol)
tastes(symbol, symbol)
food(symbol)
clauses
likes(bill,X):-
food(X), tastes(X,good).
tastes(pizza,good).
tastes(brussels_sprouts,bad).
food(brussels_sprouts).
food(pizza).
Рис. 2. Программа ch04e02.pro
Эта маленькая программа составлена из двух множеств фактов и одного правила. Правило, представленное отношением likes, утверждает, что Билл любит вкусную пищу.
Чтобы увидеть, как работает поиск с возвратом, дадим программе для решения следующее целевое утверждение:
likes(bill, What).
Когда Пролог пытается произвести согласование целевого утверждения, он начинает поиск с вершины программы.
|
|
|
В данном случае Пролог будет искать решение, производя с вершины программы поиск соответствия с подцелью likes (bill, what).
Он обнаруживает соответствие с первым предложением в программе и переменная What унифицируется с переменной X. Сопоставление с заголовком правила заставляет Visual Prolog попытаться удовлетворить это правило. Производя это, он двигается по телу правила и обращается к первой находящейся здесь подцели: food(X).
Если выполняется новое обращение, поиск соответствия для этого обращения вновь начинается с вершины программы.
Пытаясь согласовать первую подцель, Visual Prolog (начиная с вершины) производит сопоставление с каждым фактом или заголовком правила, встреченным в программе.
Он обнаруживает соответствие с запросом у первого же факта, представляющего отношение food. Таким образом, переменная X связывается со значением brussels_sprouts. Поскольку существует более чем один возможный ответ на обращение food(X), Visual Prolog ставит точку возврата (маркер) возле факта food(brussels_sprouts). Эта точка поиска с возвратом указывает на то место, откуда Пролог начнет поиск следующего возможного соответствия для food(X).
Когда установление соответствия обращения завершается успешно, говорят, что обращение возвращается, и может быть испытана очередная подцель.
Поскольку переменная X связана с brussels_sprouts, следующее обращение будет выполняться так:
tastes(brussels_sprouts, good)
и Visual Prolog вновь начнет поиск с вершины программы, пытаясь согласовать это вращение. Поскольку соответствующих предложений не обнаруживается, обращение завершается неудачно, и теперь Visual Prolog запускает механизм возврата. Начиная поиск с возвратом, Пролог отступает к последней позиции, где была уставлена точка отката. В данном случае Пролог возвращается к факту
food(brussels_sprouts).
Единственным способом освободить переменную, однажды связанную в предложении, является откат при поиске с возвратом.
Когда Пролог отступает к точке поиска с возвратом, он освобождает все переменные, связанные после этой точки, и будет искать другое решение для исходного обращения.
|
|
|
Обращение было food(X), так что связанность brussels_sprouts с X отменена. Теперь Пролог пытается заново произвести решение для этого обращения. Он обнаруживает соответствие с фактом food (pizza); на этот раз переменная X связывается со значением pizza.
Пролог переходит к следующей подцели в правиле, имея при этом новую связанную переменную. Производится новое обращение, tastes (pizza, good), и начинается поиск (опять от вершины программы). На этот раз соответствие найдено, и целевое утверждение успешно выполняется.
Поскольку переменная what в целевом утверждении унифицирована с переменной X в правиле likes, а переменная X связана со значением pizza, переменная What отныне связана со значением pizza и Visual Prolog сообщает решение:
What=pizza
1 Solution
|
|
|
