Бэктрекинг: поиск с возвратом

Урок о главном механизме Prolog: автоматическом переборе вариантов с откатом назад при неудаче.

Бэктрекинг (поиск с возвратом) — стратегия, при которой Prolog пробует решения по очереди сверху вниз, а упёршись в тупик, откатывается к последней точке выбора и берёт следующий вариант.

Зачем это нужно

В обычных языках вы сами пишете циклы: «перебери всех сотрудников, для каждого проверь условие». В Prolog перебор встроен в сам движок. Вы описываете факты и правила, задаёте вопрос — а интерпретатор сам обходит все возможности и выдаёт каждое подходящее решение. Бэктрекинг — это и есть тот невидимый цикл, который делает Prolog декларативным: вы говорите что ищете, а как перебирать берёт на себя система.

Понимать бэктрекинг важно по двум причинам. Во-первых, без него непонятно, откуда берутся «следующие» ответы на запрос. Во-вторых, именно неконтролируемый бэктрекинг — источник самых частых ошибок: лишних дублей, неожиданных решений и зависаний.

База фактов и первый перебор

Возьмём маленькую семью. Запишем, кто чей родитель:

parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

Спросим, у кого Tom родитель. Переменная X с заглавной буквы — это «дырка», которую Prolog попытается заполнить:

?- parent(tom, X).

Интерпретатор идёт по фактам сверху вниз. Первый факт parent(tom, bob) подходит — он отвечает и ставит точку выбора: «здесь остались ещё непроверенные факты». Вывод:

Вывод:

X = bob

Точка с запятой — «дай следующее»

Один ответ нас не устроил. Нажимаем ; (точка с запятой читается как «ИЛИ», «следующее решение»). Prolog возвращается к точке выбора и продолжает перебор фактов:

?- parent(tom, X).
X = bob ;
X = liz ;
false.

После liz непроверенных фактов про Tom не осталось, и финальный ; даёт false — решений больше нет. Если бы мы вместо ; нажали Enter (или точку), Prolog остановился бы на первом ответе и закрыл все точки выбора.

Точки выбора (choice points)

Точка выбора — место, где у Prolog осталась альтернатива: ещё один подходящий факт или ещё одно правило, которое можно попробовать позже.

Точки выбора возникают, когда заголовку запроса соответствует больше одного предложения (clause). Если факт ровно один — выбора нет, перебор сразу заканчивается. Каждая точка выбора — это «закладка», к которой движок умеет вернуться.

Откат при неудаче

Самое интересное начинается, когда в запросе несколько условий через запятую (запятая читается как «И»). Найдём внуков Tom: нужен кто-то Y, чей родитель Tom, и затем Z, чей родитель уже Y.

?- parent(tom, Y), parent(Y, Z).

Prolog решает условия слева направо. Сначала parent(tom, Y) даёт Y = bob (точка выбора: ещё есть liz). Идём вправо: parent(bob, Z) — есть ann. Первое решение готово: Y = bob, Z = ann.

Просим ещё через ;. Правое условие parent(bob, Z) имеет свою точку выбора — берём pat. Решение: Y = bob, Z = pat. Просим дальше — у bob детей больше нет, правое условие проваливается. Тут и срабатывает откат: Prolog возвращается к левой точке выбора и берёт Y = liz. Но у liz детей нет — снова провал, откатываться больше некуда:

Вывод:

Y = bob, Z = ann ;
Y = bob, Z = pat ;
false.

Как работает под капотом

Внутри Prolog хранит стек точек выбора. При неудаче он не сдаётся, а «отматывает» вычисление к вершине этого стека: освобождает (развязывает) переменные, связанные после той закладки, и пробует следующую альтернативу. Этот откат с развязыванием переменных называется backtracking.

Удобно представлять перебор как обход дерева поиска в глубину. Корень — запрос, ветви — альтернативные предложения, листья — успех или провал. Prolog спускается влево-вниз, а наткнувшись на провальный лист, поднимается к ближайшей развилке и идёт по следующей ветви.

Дерево для parent(tom, Y), parent(Y, Z) (стрелки рисуем чёрточками, без угловых скобок):

            parent(tom, Y)
               /        \
          Y=bob          Y=liz
            |               |
      parent(bob,Z)    parent(liz,Z)
        /      \            |
    Z=ann     Z=pat       (детей нет)
      |         |             |
   успех     успех         провал

Слева находятся два успешных листа (ann и pat), справа — тупик. Prolog обходит дерево слева направо, сверху вниз, и каждый успешный лист — это один ответ, выдаваемый по ;.

Порядок предложений = порядок ответов

Поскольку перебор идёт сверху вниз, порядок фактов в базе определяет порядок решений. Если поменять местами parent(tom, bob) и parent(tom, liz), первым ответом станет liz. На множество решений это не влияет, но на их последовательность — да.

Частые ошибки

• Думать, что Prolog вернёт сразу все ответы. Он выдаёт по одному; остальные нужно запрашивать через ; или собирать предикатом findall/3.
• Путать запятую и точку с запятой. Запятая , — это «И» (оба условия должны выполниться), точка с запятой ; — «ИЛИ» (в запросе ещё и команда «дай следующее решение»).
• Ожидать, что переменная «запомнит» прежнее значение. При откате Prolog развязывает переменные, связанные после точки выбора. Y перестаёт быть bob и заново станет liz.
• Дубли решений. Если один и тот же факт записан дважды, бэктрекинг честно выдаст ответ дважды — база фактов должна быть без повторов.

Итог

• Бэктрекинг — встроенный перебор: Prolog пробует предложения сверху вниз и откатывается при неудаче.
• Точка выбора возникает там, где запросу подходит больше одного факта или правила.
• ; запрашивает следующее решение; false означает, что альтернатив больше нет.
• Перебор удобно представлять обходом дерева поиска в глубину слева направо.
• Порядок фактов задаёт порядок (но не состав) решений.