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

Рассмотрим бэктрекинг на конкретном примере.

Пусть необходимо организовать вывод на экран таблицы истинности логической функции "И". Задачу решим опираясь на встроенный предикат Пролога bitand.

В базе знаний будут размещаться два факта f(0) и f(1), задающие возможные значения аргументов логической функции. Пролог должен будет совершить полный перебор всех входных наборов для логической двухаргументной функции. Очевидно, что всего таких варианта 4, а именно: 00, 01, 10, 11.

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

Программа выглядит следующим образом.

Зададим в окне диалога вопрос этой программе: f(A),f(B),bitand(A,B,X).

Получим ответ:

A=0, B=0, X=0

A=0, B=1, X=0

A=1, B=0, X=0

A=1, B=1, X=1

4 Solutions

Процесс унификации проходил следующим образом.

Цель сложная, имеет три подцели. Первая f(A) запускает процесс унификации и Пролог, просматривая базу знаний сверху-вниз, останавливается уже на первом же факте f(0). Так как в вопросе переменная ничем не означена, то сопоставление заканчивается присвоением переменной A значения "0". Однако этот факт не единственно возможный для реализации унификации. Есть ещё и f(1), поэтому Пролог оставляет себе информацию об альтернативном варианте унификации (точку возврата №1).

Вторая подцель вопроса f(B) принуждает Пролог начать процесс унификации опять с самого начала, то есть просматривать все наличествующие факты сверху-вниз, начиная с первого. И первый же факт имеет тот же идентификатор f и необходимое количество аргументов (один). Таким образом сопоставление возможно. Так как переменная B ничем не означена, то сопоставление заканчивается присвоением ей значения "0". Однако этот факт не единственно возможный для реализации унификации. Есть ещё и f(1), поэтому Пролог оставляет себе информацию об альтернативном варианте унификации (точку возврата №2).

Третья подцель - стандартный предикат Пролога. Используя значения A и B как входные переменные, а X как выходную переменную - bitand выдает соответствующий ответ. А достигнутая исходная цель, состоящая из трех подцелей, позволяет Прологу вывести общий ответ.

И тут начинается самое интересное. Без дополнительных усилий со стороны программиста Пролог самостоятельно принимает решение о необходимости проверки альтернативных вариантов. Пролог возвращается к ближайшей точке возврата - к точке №2. И берет за основу следующий, не исследованный ранее альтернативный вариант, а именно - унификация подцели f(B) возможна не только на первом факте f(0), но и на втором факте f(1). То есть в данном случае, после сопоставления со вторым фактом, переменная B означивается "1".

После этого комбинация переменных A=0 и B=1 передается на вход bitand и производится вывод соответствующего ответа.

Ну а что же далее, ведь альтернативы для второй подцели исчерпаны. А далее Пролог припоминает, что есть ещё и точка возврата №1, где были ещё нерассмотренные альтернативы и делает отступ в своих размышлениях до этой точки. То есть как бы забывает, что уже рассматривал когда-либо вторую подцель. Можно рассматривать это так, как если бы Пролог, приступив к унификации исходной цели и начав с первой подцели, сразу выбрал для неё второй из двух альтернативных вариантов - факт f(1). Сопоставление завершается присвоением переменной A значения "1".

После этого, то есть после унификации первой подцели Пролог переключается на вторую, так как если бы ранее этого еще не делал.

Вторая подцель вопроса f(B) принуждает Пролог начать процесс унификации опять с самого начала, то есть просматривать все наличествующие факты сверху-вниз, начиная с первого. И первый же факт имеет тот же идентификатор f и необходимое количество аргументов (один). Таким образом сопоставление возможно. Так как переменная B ничем не означена, то сопоставление заканчивается присвоением ей значения "0". Однако этот факт не единственно возможный для реализации унификации. Есть ещё и f(1), поэтому Пролог оставляет себе информацию об альтернативном варианте унификации (точку возврата №3).

После этого комбинация переменных A=1 и B=0 передается на вход bitand и производится вывод соответствующего ответа.

После этого Пролог возвращается к ближайшей точке возврата - к точке №3. И берет за основу следующий, не исследованный ранее альтернативный вариант, а именно - унификация подцели f(B) возможна не только на первом факте f(0), но и на втором факте f(1). То есть в данном случае, после сопоставления со вторым фактом, переменная B означивается "1".

Далее комбинация переменных A=1 и B=1 передается на вход bitand и производится вывод соответствующего ответа.