На этом шаге мы рассмотрим поиск с возвратом.
Часто при решении реальной задачи мы придерживаемся определенного пути для ее логического завершения. Если полученный результат не дает искомого ответа, мы должны выбрать другой путь. Так, вам, возможно, приходилось играть в лабиринт. Один из верных способов найти конец лабиринта - это поворачивать налево на каждой развилке лабиринта до тех пор, пока вы не попадете в тупик. Тогда следует вернуться к последней развилке и попробовать свернуть вправо, после чего опять поворачивать налево на каждом встречающемся распутье. Путем методичного перебора всех возможных путей вы, в конце концов, найдете выход.
Пролог при поиске решения задачи использует именно такой метод проб и возвращений назад; этот метод называется поиск с возвратом. Если, начиная поиск решения задачи (или целевого утверждения), Пролог должен выбрать между альтернативными путями, то он ставит маркер у места ветвления (называемого точкой отката) и выбирает первую подцель, которую и станет проверять. Если данная подцель не выполнится (что эквивалентно достижению тупика в лабиринте), Пролог вернется к точке отката и попробует проверить другую подцель.
Рассмотрим простой пример pro29_1.pro.
predicates
likes(symbol,symbol)
tastes(symbol,symboI)
food(symbol)
clauses
likes (bill,X):-
food(X),
tastes(X,good).
tastes(pizza,good).
tastes(brussels_sprouts,bad).
food(brussels_sprouts).
food(pizza).
Эта маленькая программа составлена из двух множеств фактов и одного правила. Правило, представленное отношением likes, утверждает, что Билл любит вкусную пищу.
Чтобы увидеть, как работает поиск с возвратом, дадим программе для решения следующее целевое утверждение:
likes(bill,What).
Замечание. Когда Пролог пытается произвести согласование целевого утверждения, он начинает поиск с вершины программы.
В данном случае Пролог будет искать решение, производя с вершины программы поиск соответствия с подцелью
likes (bill,What).
Он обнаруживает соответствие с первым предложением в программе и переменная what унифицируется с переменной X. Сопоставление с заголовком правила заставляет Пролог попытаться удовлетворить это правило. Производя это, он двигается по телу правила и обращается к первой находящейся здесь подцели: food(X).
Замечание. Если выполняется новое обращение, поиск соответствия для этого обращения вновь начинается с вершины программы.
Пытаясь согласовать первую подцель, Пролог (начиная с вершины) производит сопоставление с каждым фактом или заголовком правила, встреченным в программе.
Он обнаруживает соответствие с запросом у первого же факта, представляющего отношение food. Таким образом, переменная X связывается со значением brussels_sprouts. Поскольку существует более чем один возможный ответ на обращение food(X), Пролог ставит точку возврата (маркер) возле факта food(brussels_sprouts). Эта точка поиска с возвратом указывает на то место, откуда Пролог начнет поиск следующего возможного соответствия для food(X).
Замечание. Когда установление соответствия обращения завершается успешно, говорят, что обращение возвращается, и может быть испытана очередная подцель.
Поскольку переменная X связана с brussels_sprouts, следующее обращение будет выполняться так:
tastes: (brussels_sprouts,good)
и Пролог вновь начнет поиск с вершины программы, пытаясь согласовать это обращение. Поскольку соответствующих предложений не обнаруживается, обращение завершается неудачно, и теперь Пролог запускает механизм возврата. Начиная поиск с возвратом, Пролог отступает к последней позиции, где была поставлена точка отката. В данном случае Пролог возвращается к факту food(brussels_sprouts).
Замечание. Единственным способом освободить переменную, однажды связанную в предложении, является откат при поиске с возвратом.
Когда Пролог отступает к точке поиска с возвратом, он освобождает все переменные, связанные после этой точки, и будет искать другое решение для исходного обращения.
Обращение было food(X), так что связанность brussels_sprouts с X отменена. Теперь Пролог пытается заново произвести решение для этого обращения. Он обнаруживает соответствие с фактом food (pizza); на этот раз переменная X связывается со значением pizza.
Пролог переходит к следующей подцели в правиле, имея при этом новую связанную переменную. Производится новое обращение, tastes (pizza, good), и начинается поиск (опять от вершины программы). На этот раз соответствие найдено, и целевое утверждение успешно выполняется. Поскольку переменная What в целевом утверждении унифицирована с переменной X в правиле likes, а переменная X связана со значением pizza, переменная What отныне связана со значением pizza и Пролог сообщает решение:
What=pizza
На следующем шаге мы рассмотрим управление поиском решений.
