Поиск с возвратом.

Часто при решении реальной задачи необходимо придерживаться некото-

рого пути для ее логического завершения. Если полученный результат не да-

ет искомого ответа, вы должны выбрать другой путь. Так, в детстве вам,

возможно, приходилось играть в лабиринт. Один из верных способов найти

конец лабиринта - это поворачивать налево на каждой развилке лабиринта до

тех пор, пока вы не попадете в тупик. Тогда вам следует вернуться к пос-

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

вать налево на каждом встречающемся распутье. Путем методичного перебора

всевозможных путей вы в конце концов найдете верный путь.

Турбо Пролог при поиске решения задачи использует именно такой метод

проб и возвращений назад; этот метод называется "поиск с возвратом". На-

чиная поиск решения задачи (или целевого утверждения), Турбо Пролог, воз-

можно, должен выбрать между двумя альтернативными путями. Тогда он ставит

маркер у места ветвления (называемый точкой отката) и выбирает первую

подцель, которой и станет придерживаться. Если данная подцель не выпол-

нится (что эквивалентно достижению тупика в лабиринте), Турбо Пролог вер-

нется к точке отката и попробует другую подцель.

Вот простой пример:

/* Program CH05EX02.PRO */

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_spouts).

food(pizza).

Эта маленькая программа составлена из двух множеств фактов и одного

правила. Это правило, представленное отношением likes, просто утверждает,

что Билл любит вкусную пищу.

Чтобы увидеть, как работает поиск с возвратом, дадим программе для

решения внешнее целевое утверждение. Используя главное меню, загрузим

программу и скомпилируем ее в память. По подсказке "Goal:" введите

likes(bill,What).

-----------------------------------------------------------

Когда Пролог пытается произвести согласование целевого

утверждения, он начинает поиск с вершины программы.

-----------------------------------------------------------

В данном случае он начнет поиск решения, производя с вершины прог-

раммы поиск соответствия с подцелью likes(bill, What).

Он обнаруживает соответствие с первым предложением в программе, и

переменная What унифицируется с переменной X. Сопоставление с заголовком

правила заставляет Турбо Пролог попытаться удовлетворить это правило.

Производя это, он двигается по телу правила и обращается к первой находя-

щейся здесь подцели: food(X).

-------------------------------------------------------------

Kогда выполняется новое обращение, поиск соответствия для

этого обращения вновь начинается с вершины программы.

-------------------------------------------------------------

Пытаясь согласовать первую подцель, Турбо Пролог начинает с вершины,

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

ным в процессе прохождения через программу.

Oн обнаруживает соответствие с запросом у первого же факта, предс-

тавляющего отношение food. Таким образом, переменная X связывается со

значением brussels_sprouts. Поскольку существует более, чем один возмож-

ный ответ на обращение food(X), Турбо Пролог помещает точку возвратаа

(маркер) возле факта food(brussels_sprouts). Эта точка поиска с возвратом

указывает на то место, откуда Пролог начнет поиск следующего возможного

соответствия для food(X).

--------------------------------------------------------------

Kогда установление соответствия обращения завершается успеш-

но, говорят, что обращение возвращается, и очередная подцель

может быть испытана.

--------------------------------------------------------------

Имея X, связанным с brussels_sprouts, следующее обращение будет вы-

полняется как

tastes(brussels_sprouts, good)

и Турбо Пролог начнет поиск, пытаясь согласовать это обращение, - вновь с

вершины программы. Так как соответствующих предложений не обнаруживается,

обращение завершается неудачно, и Турбо Пролог запускает свой автомати-

ческий возвратный механизм. Начиная поиск в возвратом, Пролог отступает к

последней позиции, где была поставлена точка отката. В данном случае Про-

лог возвращается к факту food(brussels _sprouts).

---------------------------------------------------------

Единственным способом освободить переменную, однажды

связанную в предложении, является поиск в возвратом.

---------------------------------------------------------

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

все переменные, расположенные после этой точки, и намеревается найти дру-

гое решение для исходного обращения.

Обращение было food(X), так что связанность brussels_sprouts с Х от-

менена. Теперь Пролог пытается заново произвести решение для этого обра-

щения, начиная с того места, где оно было брошено. Он обнаруживает соот-

ветствие с фактом food(pizza) и производит возврат; на этот раз перемен-

ная X связывается со значением pizza.

Теперь Пролог переходит к следующей подцели в правиле, имея при этом

новую связанную переменную. Производится новое обращение, tastes(pizza,

good), и начинается поиск с вершины программы. На этот раз соответствие

найдено и целевое утверждение успешно возвращается.

Поскольку переменная What в целевом утверждении унифицирована с пе-

ременной X в правиле likes, а переменная X связана со значением pizza,

переменная What отныне связана со значением pizza и Турбо Пролог сообщает

решение:

What=pizza

1 Solution