Конспект раздела: перебор и его сокращение

Карта раздела

ЧТО ПЕРЕБИРАЕМ                          СКОЛЬКО ЭТОГО
подмножества (берём / не берём)         2^n
перестановки (порядок всех)             n!
сочетания по k без порядка              C(n,k) = n!/(k!·(n−k)!)
сочетания с повторениями                C(n+k−1, k)
все последовательности длины k          n^k
расстановки с ограничениями             зависит от данных - только замер

КАК СОКРАЩАЕМ                           ЧТО ДАЁТ
отсечение по допустимости               поддерево продолжений кандидата
отсечение по оценке (рекорд)            всё, что не побьёт найденное
отсечение по симметрии                  постоянный множитель (2, 4, 8)
порядок кандидатов                      ничего сам, но решает, когда сработают отсечения
встреча посередине                      ПОКАЗАТЕЛЬ: 2^n → 2^(n/2)
альфа-бета (в играх)                    ПОКАЗАТЕЛЬ: b^d → b^(d/2) при хорошем порядке

Дерево решений: какой приём брать

Ответ - перечислить все объекты?
    └─ да → генерация: монотонный индекс (сочетания), обмен на месте
             (перестановки), счётчик по маске (подмножества)

Ответ - «существует ли объект с условием»?
    ├─ условие проверяется на ЧАСТИЧНОМ решении → поиск с возвратом
    └─ вход делится на независимые половины     → встреча посередине

Ответ - число (минимум или максимум)?
    ├─ подзадачи ПЕРЕКРЫВАЮТСЯ и состояний мало → динамика (раздел 15)
    ├─ есть дешёвая оценка потолка ветки        → ветви и границы
    └─ ни то, ни другое                         → перебор с отсечениями
                                                  + приближение (раздел 14)

Ход делает противник?
    └─ минимакс + альфа-бета; дерево не кончается → обрезка и оценка позиции

Главные замеры раздела

задача	без сокращения	с сокращением	во сколько
сочетания C(8,4)	фильтр по маске 9 036 шагов	монотонный индекс 1 583	5,7
перестановки, n=6	флаги 45 036 шагов	обмен на месте 16 889	2,7
восемь ферзей, узлов	перестановки 109 601	с возвратом 2 057	53
восемь ферзей, узлов	все клетки 19 173 961	с возвратом 2 057	9 322
сумма подмножества, n=20	2 097 151 узел	6 047 (отсечения + порядок)	347
сумма подмножества, n=16	отсечения 247 012 шагов	встреча посередине 4 894	50
рюкзак, 15 предметов	39 864 узла	ветви и границы 23 узла	1 733
коммивояжёр, 8 городов	13 700 узлов	ветви и границы 1 355	10
дерево игры b=3 d=6	минимакс 729 листьев	альфа-бета идеальная 53	14
крестики-нолики, узлов	минимакс 549 946	альфа-бета 18 297	30

Экспонента остаётся экспонентой. Все приёмы раздела, кроме двух, сдвигают границу посильного на единицы n и уменьшают константу. Показатель в этом разделе меняют встреча посередине (2^(n/2)) и альфа-бета при хорошем порядке ходов (b^(d/2)); ветвление из раздела 22 тоже уменьшает основание (1,618ⁿ) - и обе требуют условий: независимые половины в первом случае, хороший порядок ходов во втором.

Что проверять в своём коде

1. ОТКАТ. Состояние, изменённое перед спуском, восстановлено после возврата.
   Проверка: шесть ферзей дают 4 решения, а не 0.
2. ОТВЕТ НЕ ИЗМЕНИЛСЯ. Версия с отсечениями даёт то же, что полный перебор
   на маленьких данных. Любое расхождение = отсечение недопустимо.
3. ДОПУСТИМОСТЬ ОЦЕНКИ. Для максимума оценка не меньше достижимого, для
   минимума не больше. Сверять с динамикой или полным перебором.
4. СДЕЛКА ОКУПИЛАСЬ. Отсечение стоит шаг на каждом узле. Мерить на тех
   размерах, с которыми программа будет работать, и не на одном.
5. ПОРЯДОК КАНДИДАТОВ. Отсортировать по убыванию (или по оценке) стоит одну сортировку,
   а даёт до восьми раз.
6. СИММЕТРИЯ. Кратность посчитана точно: девять ферзей - 2×149 + 54, а не
   2×149 и не 2×203.

Объясни своими словами

Проверка на понимание: ответь, не подглядывая.

Почему монотонный индекс превращает перебор последовательностей в перебор сочетаний - и куда деваются лишние варианты?
Почему отсечение на глубине 2 экономит больше, чем на глубине n−1?
Чем отсечение по оценке отличается от отсечения по допустимости по требованиям к доказательству?
Почему заниженная оценка (для задачи на максимум) портит ответ, а завышенная только замедляет?
Как из «целый рюкзак» получить оценку, не решая целый рюкзак?
Почему лучший-первый обход раскрывает меньше узлов, но может не иметь ответа до самого конца?
Почему при идеальном порядке ходов альфа-бета смотрит именно b^(d/2) листьев?
Почему совпадение ответов обрезанного поиска на двух глубинах ничего не доказывает?

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

Перебор был последним способом получить ТОЧНЫЙ ответ на задачу, у которой нет быстрого алгоритма. Дальше раздел переключается с методов на предметные области: строки, числа, биты. Но тема «а что делать с задачей, у которой быстрого решения нет и, скорее всего, не будет» вернётся дважды - в разделе про то, что вообще вычислимо, и в разделе про то, как жить со сложной задачей. Там и выяснится, почему про коммивояжёра можно уверенно сказать «быстрого точного алгоритма не найдено», а приёмы этого раздела - ветви и границы, встреча посередине, отсечения - окажутся не костылями, а штатным инструментом работы с NP-трудными задачами.