Программирование на языке Турбо-Пролог 2.0. Николаев В.Г - 16 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

- 16 -
1.7. Бектрекинг
БЕКТРЕКИНГ - механизм возврата, который работает следующим
образом: если не произошло согласование текущего предиката-цели с
базой данных (т. е. механизм унификации сработал как fail), то
происходит вызов на согласование с базой данных предиката, кото-
рый до этого выступал как целевой. Если предикат был объявлен
несколько раз, то осуществляется переход к следующему (по порядку
записи) определению этого предиката.
Сложное целевое выражение вида: GOAL G:-G1,G2,...,GN.
обрабатывается слева направо, а соответствующие выражения для
этих предикатов-подцелей Gi при этом просматриваются сверху вниз.
При этом Турбо-Пролог поочередно пытается согласовать каждую
подцель. Если обнаружен факт который сопоставим с i-ой подцелью,
то Турбо-Пролог ставит в этом месте программы i-ый маркер, при
этом некоторые свободные переменные могут быть конкретизированы.
Если некоторая свободная переменная X - конкретизируется, то
конкретизируются и все ее вхождения в последующие подцели.
Далее Турбо-Пролог пытается согласовать i+1-ую подцель. Для
каждой новой подцели просмотр описаний предикатов начинается за-
ново. Если согласование всех подцелей закончилось успехом, систе-
ма выдает полученное решение.
В противном случае, каждый раз, когда целевое утверждение не
выполняется (в программе нет фактов сопоставимых с целью), Тур-
боПролог запускает механизм обратного поиска -"бeктрекинг", т.е.
возвращается на шаг назад и пытается найти новое согласование для
(i-1)-ой подцели, начиная поиск с помеченного (i-1)-ым маркером
определения предиката. При этом все конкретизированные ранее (при
предыдущем согласовании (i-1)-ой подцели) переменные вновь стано-
вятся свободными.
Может случится, что в процессе поиска решения Турбо-Пролог
будет вынужден все время сдвигаться влево по целевому выражению
и, наконец, исчерпает свои возможности: попытается выйти за левую
границу целевого утверждения. Это означает, что данная задача не
имеет решений ( нет фактов удовлетворяющих цели) и система отве-
тит: No solution. (Решения нет).

Страницы