Понятие бектрекинг

Бектрекинг - механизм возврата, который работает следующим образом: если не произошло согласование текущего предиката-цели с базой данных (т. е. механизм унификации сработал как fail), то происходит вызов на согласование с базой данных предиката, который до этого выступал как целевой. Если предикат был объявлен несколько раз, то осуществляется переход к следующему (по порядку записи) определению этого предиката.

Сложное целевое выражение вида:

GOAL G:- G1,G2,...,GN.

обрабатывается слева направо, а соответствующие выражения для этих предикатов-подцелей Gi при этом просматриваются сверху вниз. При этом Турбо-Пролог поочередно пытается согласовать каждую подцель. Если обнаружен факт который сопоставим с i -ой подцелью, то Турбо-Пролог ставит в этом месте программы i -ый маркер, при этом некоторые свободные переменные могут быть конкретизированы. Если некоторая свободная переменная X – конкретизируется, то конкретизируются и все ее вхождения в последующие подцели.

Далее Турбо-Пролог пытается согласовать i+1 -ую подцель. Для каждой новой подцели просмотр описаний предикатов начинается заново. Если согласование всех подцелей закончилось успехом, система выдает полученное решение

В противном случае каждый раз, когда целевое утверждение не выполняется (в программе нет фактов сопоставимых с целью), Турбо-Пролог запускает механизм обратного просмотра – " бeктрекинг ", т.е. возвращается на шаг назад и пытается найти новое согласование для i-1- ой подцели, начиная поиск с помеченного i-1 -ым маркером определения предиката. При этом все конкретизированные ранее (при предыдущем согласовании i-1 -ой подцели) переменные вновь становятся свободными.

Может случиться, что в процессе поиска решения Турбо-Пролог будет вынужден все время сдвигаться влево по целевому выражению и, наконец, исчерпает свои возможности: попытается выйти за левую границу целевого утверждения. Это означает, что данная задача не имеет решений, т.е. нет фактов, удовлетворяющих цели, и система ответит: No solution. (Решения нет).

Большинство функций, которые организованы в виде циклически замкнутых процедур (циклов), можно описать или с использованием механизма рекурсии, или с использованием механизма возврата (бектрекинга).