Поиск с возвратом: проверять на входе в ветку, а не на дне

Если ты пишешь поиск с возвратом не задумываясь и знаешь, почему проверка на входе в ветку сильнее проверки на дне, - листай до «Теперь сам».

Как думаешь, сколько расстановок придётся посмотреть

Восемь ферзей на доске 8×8 так, чтобы ни один не бил другого. Ферзь бьёт по строке, столбцу и обеим диагоналям.

Прежде чем читать дальше, прикинь три числа. Сколько всего способов поставить восемь ферзей, если в каждой строке ровно по одному (это уже разумное ограничение)? Сколько из них придётся проверить, если отбрасывать расстановку только когда она собрана целиком? И сколько - если отбрасывать её, как только второй ферзь встал под удар первого?

На что это похоже

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

Разница не в аккуратности, а в количестве работы. При первом подходе ты собираешь шкаф целиком даже тогда, когда ошибка была на второй детали. При втором - бракуешь всю ветку сборки на второй детали, и все варианты продолжений, которые из неё росли, не рассматриваются вовсе.

Механизм: поставил - спустился - откатил

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

Ключевое слово - «частичное решение». Проверка задаётся не на готовом ответе, а на недостроенном: три ферзя из восьми уже стоят, и если четвёртый встал под удар, то ВСЕ расстановки остальных четырёх можно не рассматривать. Их 8⁴ = 4096, если считать по клеткам, и ни одна не понадобится.

Правило

Поиск с возвратом - это перебор по дереву вариантов, в котором на каждом узле проверяется ДОПУСТИМОСТЬ частичного решения, и недопустимая ветка не раскрывается. Схема на каждом уровне: взять кандидата, проверить его совместимость с уже принятыми решениями, при успехе - занять ресурс, спуститься в рекурсию и обязательно ОТКАТИТЬ занятое после возврата. Сила приёма в том, что отсекается не вариант, а поддерево: проверка на глубине k экономит все продолжения, которых было бы (n−k)! или nⁿ⁻ᵏ. Проверка на дне (собрать решение целиком и потом посмотреть) даёт тот же ответ и обходит всё дерево: для восьми ферзей 109 601 узел против 2057.

Разбор: три версии ферзей, одинаковый ответ

Все три программы на одной и той же доске дают один и тот же ответ: 2 расстановки при n = 4, 10 при n = 5. Отличаются они только тем, где стоит проверка, - и тем, до какого n доходят. До восьми ферзей и ответа 92 на движке не доберётся ни одна из трёх: это сделает версия D из следующего разбора.

Версия A - перебор всех клеток: в каждой строке любой из n столбцов, проверка на дне. Версия B - перебор перестановок: столбцы заведомо различны, на дне проверяются только диагонали. Версия C - поиск с возвратом: кандидат проверяется перед спуском.

n   A (все клетки)             B (перестановки)            C (с возвратом)
4   5 973 шага, 341 узел       2 070 шагов, 65 узлов       877 шагов, 17 узлов
5   79 596 шагов, 3 906 узлов  13 293 шага, 326 узлов      3 793 шага, 54 узла
6   не уложился                99 522 шага, 1 957 узлов    17 537 шагов, 153 узла
7   не уложился                не уложился                 78 645 шагов, 552 узла

Узел - это вызов rec. У версии A их 1 + n + n² + ... + nⁿ, у версии B - 1 + n + n(n−1) + ..., как в уроке про перестановки, а у версии C формулы нет вовсе: сколько веток отсечётся, зависит от доски.

Вот код версии C - той самой, которая доходит дальше всех:

def rec(row, pos):
    if row == n:
        reshenij.append(1)
        return 0
    c = 0
    while c < n:
        mozhno = True
        i = 0
        while i < row:                      # сравниваем с уже поставленными
            if pos[i] == c or row - i == c - pos[i] or row - i == pos[i] - c:
                mozhno = False
            i = i + 1
        if mozhno:
            rec(row + 1, pos + [c])         # ветка раскрывается только годная
        c = c + 1
    return 0

reshenij = []
rec(0, [])
print(len(reshenij))

Условие row - i == c - pos[i] - это проверка диагонали: два ферзя стоят на одной диагонали ровно тогда, когда разность строк равна разности столбцов по модулю. Второе сравнение - для второй диагонали.

Обрати внимание, чего в этом коде НЕТ: шага «откатить». Он не нужен, потому что состояние передаётся параметром pos + [c] - новый список на каждом уровне. Это честный способ, и он стоит копии набора на каждом узле. В следующем разборе мы заменим его на общие массивы занятости, и вот там откат появится сразу.

Разбор: та же проверка за одну операцию вместо цикла

В версии C на каждого кандидата тратится цикл по уже поставленным ферзям - до n сравнений. Но «занятость» можно помнить: один массив на столбцы и два на диагонали. Номер диагонали считается из координат: для одной диагонали постоянна сумма row + c, для другой - разность row − c (к ней прибавляем n − 1, чтобы индекс был неотрицательным).

def rec(row):
    if row == n:
        reshenij.append(1)
        return 0
    c = 0
    while c < n:
        d1 = row + c
        d2 = row - c + n - 1
        if stolbec[c] == 0 and diag1[d1] == 0 and diag2[d2] == 0:
            stolbec[c] = 1
            diag1[d1] = 1
            diag2[d2] = 1
            rec(row + 1)                    # спускаемся
            stolbec[c] = 0                  # и откатываем всё занятое
            diag1[d1] = 0
            diag2[d2] = 0
        c = c + 1
    return 0

reshenij = []
stolbec = [0] * n
diag1 = [0] * (2 * n - 1)                   # диагоналей каждого вида 2n − 1,
diag2 = [0] * (2 * n - 1)                   # а не n: индекс доходит до 2n − 2
rec(0)
print(len(reshenij))

Замер той же задачи:

n    C (цикл проверки)      D (массивы занятости)   ответ
6    17 537 шагов           6 176 шагов             4
7    78 645 шагов           23 984 шага             40
8    не уложился            101 172 шага            92
9    не уложился            453 914 шагов *         352

Строка со звёздочкой снята с поднятым пределом: в обычные 300 000 шагов движка девять ферзей не влезают и у версии D, у себя ты увидишь «не уложилась».

Узлов дерева при этом СТОЛЬКО ЖЕ - 2057 при n = 8, их число не зависит от того, как мы проверяем. Подешевел один узел, а не дерево. И этого хватило, чтобы версия D прошла восемь ферзей в предел движка, а версия C нет.

Числа, кстати, можно сверить с известными: расстановок восьми ферзей 92, девяти - 352, десяти - 724, одиннадцати - 2680. Движок с поднятым пределом даёт ровно эти значения, и это хорошая проверка самой программы: если твой перебор даёт другое число, ошибка в нём, а не в доске.

Что ломается без этого

Первое и главное: забыл откат. Уберём в версии D две строки восстановления диагоналей - программа не упадёт, а напечатает 0 решений: при n = 6 вместо четырёх, потратив 302 шага, при n = 8 вместо 92, потратив 578. Диагонали, занятые в одной ветке, остаются занятыми в соседних, и свободных клеток быстро не остаётся ни одной. Это самый опасный класс ошибок в разделе: состояние, изменённое перед спуском, обязано быть восстановлено после возврата, и нарушение этого правила не вызывает ошибки - оно просто портит ответ.

Второе: проверять на дне, а потом удивляться цене. Версия B для n = 7 уже не укладывается в предел, хотя делает ровно то же. Отсечение на глубине 2 экономит 5! = 120 расстановок; на глубине 6 - только одну. Поэтому проверять надо как можно раньше, а не как можно удобнее.

Третье: проверять не всё. Если забыть одну из диагоналей, перебор выдаст больше решений, чем есть: программа найдёт расстановки, которые условию не удовлетворяют. Признак - число решений больше известного: 92 превращается в сотни.

Четвёртое: копировать состояние, когда этого можно не делать. Версия C с pos + [c] короче и понятнее, версия D с массивами и откатом втрое дешевле. На маленьких задачах выбирай первую, на границе возможного - вторую.

Пятое: считать, что поиск с возвратом снимает экспоненту. Не снимает. При n = 10 это 724 решения и 2,1 миллиона шагов; при n = 11 - 10,9 миллиона (оба замера - с поднятым пределом). Поиск с возвратом сдвигает границу посильного на несколько единиц n, и это много, но порядок роста остаётся экспоненциальным.

Зачем это в работе

Первый сюжет - расстановка ограничений. «Разложить двадцать сервисов по пяти машинам так, чтобы ни одна пара конфликтующих не попала на одну машину» - это ровно задача ферзей другими словами, и решается поиском с возвратом за десятки строк. Полный перебор там 5²⁰, то есть 10¹⁴; с проверкой на входе в ветку задача считается за секунды, потому что конфликт обнаруживается на третьем-четвёртом сервисе.

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

Третий, самый практичный: откат как привычка. Эта схема повторяется далеко за пределами перебора - транзакция в базе, снимок состояния перед миграцией, стек отмен в редакторе. Правило «изменил перед спуском - восстанови после» одно и то же, и ошибка в нём выглядит одинаково: всё работает, только результат не тот.

Теперь сам

В версии D перебор восьми ферзей обходит 2057 узлов. Сколько узлов обойдёт перебор, если проверять расстановку только на дне - и почему это число не зависит от того, сколько решений у задачи?

уровень k:  8!/(8−k)! узлов
0:      1        4:   1 680
1:      8        5:   6 720
2:     56        6:  20 160
3:    336        7:  40 320
                 8:  40 320
итого: 109 601 узел