Отсечения: по оценке, по симметрии и по порядку переменных

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

Как думаешь, какое отсечение сильнее

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

Прежде чем читать дальше, выбери, что добавить первым. Вариант один: не раскрывать ветку, если накопленная сумма уже больше 97. Вариант два: не раскрывать, если даже со всем оставшимся хвостом до 97 не дотянуть. Вариант три: отсортировать числа по убыванию и ничего больше не менять. Какой из трёх даст самый большой выигрыш?

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

Отсечение - это как закрытая дверь в коридоре с комнатами. Можно войти в каждую комнату и убедиться, что выхода нет. А можно прочитать табличку на входе в коридор: «тупик» - и не входить вовсе. Табличка не делает коридор короче; она избавляет от необходимости его проходить.

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

Механизм: три вида и что каждый требует

ПО ДОПУСТИМОСТИ
условие: кандидат противоречит уже принятым решениям
пример:  ферзь под ударом; цвет совпал с соседним; ресурс занят
требует: уметь проверить ЧАСТИЧНОЕ решение
даёт:    всё поддерево продолжений этого кандидата

ПО ОЦЕНКЕ
условие: даже в самом лучшем случае ветка не даст ответа лучше найденного
пример:  сумма уже больше цели; остатка не хватит; оценка хуже лучшего найденного
требует: оценку, которая НЕ ЗАНИЖАЕТ возможности ветки
даёт:    тем больше, чем раньше оценка становится безнадёжной

ПО СИММЕТРИИ
условие: ветка повторяет уже рассмотренную с точностью до преобразования
пример:  зеркальная половина доски; равные элементы; поворот фигуры
требует: ТОЧНОГО счёта, сколько ветвей склеивается в одну
даёт:    постоянный множитель (вдвое, в восемь раз - сколько симметрий)

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

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

Правило

Отсечение по оценке требует ДОПУСТИМОЙ оценки: она обязана быть не хуже (для минимума - не больше, для максимума - не меньше) любого реально достижимого в этой ветке результата. Такая оценка обещает ветке не меньше, чем та способна дать, - она оптимистична, и это правильно. Опасна обратная ошибка: оценка, которая ЗАНИЖАЕТ возможности ветки, отсекает ветку, в которой был ответ, и ошибку не видно - программа просто выдаёт не оптимум. Отсечение по симметрии требует точного счёта кратности: при чётном n у ферзей зеркало даёт ровно двойку, при нечётном - двойку для всех столбцов кроме центрального и единицу для центрального, и забытая единица теряет 54 решения из 352. Порядок кандидатов меняет цену перебора в разы, не меняя ответа: на сумме подмножества сортировка по убыванию даёт 25 996 шагов, по возрастанию - 210 830. И общее правило всего раздела: выигрыш отсечения ЗАМЕРЯЕТСЯ, а не предполагается, потому что проверка стоит шаг на каждом узле.

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

Данные: двадцать чисел 41, 32, 27, 19, 55, 12, 38, 7, 24, 61, 16, 45, 9, 33, 28, 51, 14, 22, 36, 5, цель 97. Правильный ответ - 179 подмножеств.

Начинаем с полного перебора «берём - не берём», он нам уже знаком:

def rec(i, summa):
    if i == len(a):
        if summa == cel:
            nashli.append(1)
        return 0
    rec(i + 1, summa + a[i])
    rec(i + 1, summa)
    return 0

Первое отсечение - по превышению. Все числа положительны, значит сумма только растёт: если она уже больше цели, дальше смысла нет.

    if summa > cel:
        return 0

Второе - по остатку. Заранее посчитаем хвостовые суммы: hvost[i] - сумма всех элементов от i до конца. Если даже забрать весь хвост целиком, до цели не дотянуть - ветка мертва. Обе проверки ставятся первыми строками функции, до проверки дна, и программа целиком выглядит так:

hvost = [0] * (len(a) + 1)
i = len(a) - 1
while i >= 0:
    hvost[i] = hvost[i + 1] + a[i]
    i = i - 1

def rec(i, summa):
    if summa > cel:
        return 0                      # превышение: сумма назад не вернётся
    if summa + hvost[i] < cel:
        return 0                      # остаток: даже со всем хвостом не дотянуть
    if i == len(a):
        if summa == cel:
            nashli.append(1)
        return 0
    rec(i + 1, summa + a[i])
    rec(i + 1, summa)
    return 0

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

Замер. Узлы - это вызовы rec, то есть размер фактически обойдённого дерева:

вариант                              узлов      шагов       ответ
полное дерево (без отсечений)     2 097 151   не уложился     -
+ отсечение по превышению            18 661     73 126       179
+ отсечение по остатку               15 017     62 684       179
+ сортировка по убыванию              6 047     25 996       179
те же два отсечения, но сортировка
по ВОЗРАСТАНИЮ                       51 615    210 830       179

Строки с плюсом накапливаются: каждая добавляет своё к предыдущей. Последняя строка - отдельный опыт: оба отсечения на месте, а числа отсортированы в обратную сторону.

Ответ везде один и тот же - это обязательное свойство отсечения, и именно его проверяют тестами. А цена между удачным и неудачным порядком отличается в восемь с половиной раз (51 615 узлов против 6047), и в 347 раз между лучшей строкой и полным деревом.

Теперь ответ на вопрос из начала урока, и он с подвохом. Самый большой шаг - первое отсечение: с двух миллионов узлов до 18 661, в 112 раз. Остаток добавил ещё 1,24 раза, сортировка по убыванию - ещё 2,5. А вариант три в чистом виде, «отсортировать и ничего больше не менять», не даёт НИЧЕГО: без отсечений дерево полное при любом порядке. Сортировка не отбрасывает ни одной ветки сама - она делает так, чтобы сумма превышала цель как можно раньше, и тогда раньше срабатывает отсечение по превышению. Зато неудачный порядок способен съесть заработанное: исходный, случайный порядок дал 15 017 узлов, порядок по возрастанию - 51 615, втрое хуже, потому что мелкие числа в начале долго не дают сумме дорасти до цели. Порядок кандидатов - бесплатная оптимизация, которую чаще всего забывают.

Разбор: отсечение по остатку, которое сначала проиграло

Вот деталь, которую легко не заметить. Отсечение по остатку на двадцати числах сократило узлы с 18 661 до 15 017 и шаги с 73 126 до 62 684 - польза очевидна. А на первых двенадцати числах того же списка вышло так:

n = 12, цель 97            узлов    шагов
+ превышение                1 525    5 929
+ превышение и остаток      1 417    5 982   узлов МЕНЬШЕ, шагов БОЛЬШЕ

Узлов стало меньше на 108, а шагов - больше на 53. Вторая проверка выполняется на каждом из 1417 оставшихся узлов, а экономит только 108 отсечённых - и на коротком списке не окупилась. На первых шестнадцати числах то же самое: 5947 узлов вместо 6077, а шагов 24 799 вместо 23 105. В плюс она выходит только на двадцати.

Отсюда правило, которое стоит унести: отсечение - это сделка. Левая часть сделки - стоимость проверки, умноженная на число узлов; правая - сэкономленные поддеревья. На маленьких данных левая часть побеждает, на больших правая, и переломная точка зависит от задачи. Проверять надо на тех данных, на которых программа будет работать, и не по одному размеру, а по нескольким.

Разбор: симметрия, которая молча теряет решения

Доска ферзей зеркально симметрична: любому решению соответствует отражённое. Значит можно ставить первого ферзя только в левую половину строки, а найденные решения удвоить. Замер на восьми ферзях подтверждает: 52 577 шагов вместо 101 172 и 1029 узлов вместо 2057, то есть почти вдвое, ответ 92.

Теперь то же самое на девяти ферзях. Правильный ответ - 352. Два естественных способа применить симметрию дают:

первая строка, столбцы 0..3 (половина без центра), ответ × 2   →  298
первая строка, столбцы 0..4 (половина с центром),  ответ × 2   →  406
правильно:  2 × 149 (столбцы 0..3)  +  54 (столбец 4)          →  352

Ни один из первых двух не верен, и оба выглядят правдоподобно. Причина в том, что центральный столбец сам себе зеркало: решения с первым ферзём в центре при отражении переходят В СЕБЯ, и удваивать их нельзя. При чётном n центрального столбца нет, поэтому там работает простое удвоение - и именно поэтому ошибку так легко не заметить: на восьми ферзях всё верно, на девяти уже нет.

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

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

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

Второе: отсечение, зависящее от знака данных. if summa > cel: return 0 верно только потому, что все числа положительны. Появись в списке отрицательные - отсечение станет неверным, и часть ответов потеряется. Условие применимости надо писать рядом в комментарии, иначе через полгода его никто не вспомнит.

Третье: проверка остатка без заранее посчитанных хвостов. Если считать остаток циклом внутри rec, то проверка стоит O(n) на узел, и отсечение почти наверняка не окупится. Хвостовые суммы считаются один раз за O(n) до перебора.

Четвёртое: удвоить решения и не проверить на маленьком случае. Разобранная выше потеря 54 решений из 352 - типичная цена.

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

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

Первый сюжет - подбор под ограничения. «Собрать заказ из позиций склада ровно на нужную сумму», «набрать группу серверов с суммарной памятью не меньше N и ценой не больше M» - это сумма подмножества с двумя отсечениями, и разница между наивным кодом и кодом с отсечениями - это разница между «не досчитало» и «ответ за секунду».

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

Третий - разговор о цене. «Добавим проверку, станет быстрее» - утверждение, которое надо мерить. Замер из этого урока (n = 12: узлов меньше, шагов больше) - готовый аргумент в таком разговоре.

Теперь сам

Задача: найти в списке положительных чисел подмножество с МАКСИМАЛЬНОЙ суммой, не превышающей C. Какое отсечение по оценке здесь допустимо, а какое нет?

if summa + hvost[i] <= rekord:
    return 0            # даже забрав весь хвост, рекорд не побить
if summa > C:
    return 0            # допустимость: за границу вылезли