Конспект: поиск с возвратом и отсечения

Понятия

Поиск с возвратом - перебор по дереву вариантов, в котором допустимость ЧАСТИЧНОГО решения проверяется на входе в ветку; недопустимая ветка не раскрывается.

Откат - восстановление состояния после возврата из рекурсии. Пара к занятию ресурса, как закрывающая скобка к открывающей.

Отсечение - условие, при котором ветка не раскрывается. Три вида: по допустимости, по оценке, по симметрии.

Допустимая оценка - оценка лучшего в ветке, которая никогда не обещает меньше, чем ветка способна дать: для максимума не меньше, для минимума не больше.

Встреча посередине - разрезать вход пополам, перебрать половины отдельно (2^(n/2) вариантов каждая) и склеить частичные результаты по одному соотношению.

Что унести

СХЕМА ОДНОГО УРОВНЯ (повторяется от задачи к задаче)
  для каждого кандидата:
      1. проверить совместимость с принятыми решениями   ← вся экономия здесь
      2. занять ресурс
      3. спуститься
      4. ОТКАТИТЬ занятое                                ← вся надёжность здесь

Отсечение на глубине k экономит всё поддерево продолжений - (n−k)! или nⁿ⁻ᵏ листьев. Поэтому проверять надо как можно раньше, а не как удобнее.

ТРИ ВИДА ОТСЕЧЕНИЙ
по допустимости   кандидат противоречит принятым решениям       надёжно, просто
по оценке         в ветке не может быть ответа лучше рекорда    сильнее всего
по симметрии      ветка - зеркало уже рассмотренной             постоянный множитель

ПОРЯДОК КАНДИДАТОВ отсечением не является, но решает, когда отсечения сработают

СУММА ПОДМНОЖЕСТВА, 20 чисел, цель 97 (ответ 179 во всех строках)
полное дерево                     2 097 151 узел   не уложился
+ превышение (summa > cel)           18 661 узел    73 126 шагов
+ остаток (summa + hvost[i] < cel)   15 017 узлов   62 684 шага
+ сортировка по УБЫВАНИЮ               6 047 узлов   25 996 шагов   в 347 раз меньше
сортировка по возрастанию            51 615 узлов  210 830 шагов   в 8 раз хуже

ВСТРЕЧА ПОСЕРЕДИНЕ - единственный приём, меняющий ПОКАЗАТЕЛЬ
2^n → 2^(n/2):  посильное n удваивается, с ~20 до ~40
суммы половины считать НАРАЩИВАНИЕМ (список удваивается на каждом элементе),
    а не перебором масок - разница в пять раз на замере
«ровно столько»  → словарь со счётчиком (множество занижает ответ)
«как можно ближе»→ сортировка + двоичный поиск или два указателя
плата - память 2^(n/2); она же и ставит границу приёма
делить ровно пополам: 8 и 16 вместо 12 и 12 - это 65 792 вместо 8192

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

Ловушки джокера

Забыл откат. Шесть ферзей дают ноль решений вместо четырёх, и программа не жалуется. Перебор при этом становится ДЕШЕВЛЕ (302 шага вместо 6176) - ложная занятость отсекает почти всё.

Заниженная оценка. Отсекает ветку, в которой был оптимум. Ответ есть, он просто хуже настоящего. Проверяется сравнением с полным перебором на малых данных.

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

Симметрия без точного счёта кратности. Девять ферзей: 298 (половина без центра × 2) или 406 (половина с центром × 2) вместо 352. Центральный столбец сам себе зеркало, его решения прибавляются один раз: 2 × 149 + 54 = 352. На чётном n ошибка не проявляется.

Отсечение, опирающееся на знак данных, без оговорки. summa > cel верно только для положительных чисел. Условие применимости писать рядом комментарием.

Остаток, посчитанный внутри рекурсии. Проверка станет стоить O(n) на узел и не окупится. Хвостовые суммы считаются один раз до перебора.

Разрезать задачу, в которой половины зависимы. Встреча посередине требует, чтобы частичный результат половины записывался одним числом, а склейка была равенством или сравнением. Для маршрута или порядка через все данные это не так.

Множество вместо словаря со счётчиком. Отвечает на «существует ли», а не на «сколько»: разные подмножества с равной суммой склеиваются в одно.

Ждать, что поиск с возвратом снимет экспоненту. Он сдвигает границу: десять ферзей - 2,1 миллиона шагов, одиннадцать - 10,9 миллиона.

Куда это ведёт

Отсечение по оценке мы пока применяли к ответу «да или нет»: сумма либо достижима, либо нет. В следующей главе та же идея переносится на задачи оптимизации, где ответ - число, которое надо минимизировать. Там оценка сравнивается с уже найденным РЕКОРДОМ, и появляется второе решение, которого здесь не было: в каком порядке обходить ветки, чтобы хороший рекорд нашёлся раньше. Это и есть метод ветвей и границ.