Отсечения

Студия записывает аудиокнигу «Войны и мира». Первую часть эпилога — шестнадцать глав — читают четверо, одновременно, и часть готова, когда закончит самый занятой. Кому какие главы? Способов раздать — 4¹⁶, больше четырёх миллиардов, а дерево перебора, где на каждом уровне решается судьба одной главы, — почти шесть миллиардов узлов. Ниже — этот перебор на настоящих главах романа. Лесенка вверху сцены добавляет отсечения одно за другим и считает узлы, которые перебору пришлось открыть. Под ней — переключатели: уберите любое отсечение или добавьте опасное.

Перебор, который не даёт чтецу больше лучшего найденного времени, не укладывается и в три миллиона узлов. Если раздавать сначала длинные главы, узлов 2 503 341, если не различать чтецов с равной нагрузкой — 20 355. Ещё одна проверка — хватит ли чтецам запаса на оставшиеся главы — и узел остаётся один: корень. Перебору не пришлось ничего перебирать, потому что жадный способ сразу нашёл раскладку по 33 минуты, а лучше 33 минут не бывает — это видно, ещё не начав. Переключите минуты на слова, и картина станет другой. Об этом — ниже.

Идея

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

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

• Рекорд. Лучшее найденное решение — рекорд — служит планкой: ветку, где лучше рекорда не выйти, не открываем.
• Хороший рекорд пораньше. Чем ниже планка с самого начала, тем больше она отсекает. Её даёт быстрый приближённый способ — например, жадный.
• Порядок. Сам по себе порядок ничего не отсекает, но решает, насколько рано сработают остальные проверки.
• Симметрия. Если два выбора дают зеркальные поддеревья, достаточно обойти одно.
• Оценка снизу. Если даже при самом удачном продолжении лучше рекорда не выйти, ветка не нужна. А если рекорд сравнялся с оценкой для всей задачи, перебор можно остановить совсем.

Шесть отсечений по очереди

Возьмём часть поменьше, чтобы перебор без хитростей тоже закончился: четвёртую часть второго тома, тринадцать глав, три чтеца. Глава весит столько минут, сколько её читать при скорости 150 слов в минуту: от 4 до 17 минут, всего 120. Полное дерево — 1 + 3 + 3² + … + 3¹³ = 2 391 484 узла. Числа ниже напечатал листинг из раздела о коде; в сцене, если выбрать эту часть и трёх чтецов, получатся те же.

1. Не давать чтецу больше рекорда: 32 957 узлов. Самый занятой чтец читает не меньше, чем любой другой уже набрал. Если глава поднимает нагрузку чтеца до рекорда или выше, лучше рекорда в этой ветке не будет. Пока рекорда нет, отсекать нечего, но первое же законченное решение даёт планку, и дерево сразу худеет в семьдесят раз.

2. Рекорд жадного с самого начала: 32 346. Жадный способ — главы по убыванию, каждую самому свободному чтецу — даёт 42 минуты. Рональд Грэм доказал в 1969 году, что он ошибается не больше чем в 4/3 − 1/(3k) раза, и это хорошая стартовая планка. Здесь она помогла мало: перебор и сам за несколько сотен узлов находил раскладку не хуже.

3. Сначала длинные главы: 11 483. Длинная глава, поставленная последней, раздувает нагрузку внизу дерева, когда большая часть работы уже сделана. Поставленная первой, она сразу показывает, что ветка безнадёжна. Тот же принцип в переборе с возвратом называют «сначала самое трудное».

4. Равные нагрузки — один чтец: 1814. В начале все три чтеца свободны, и отдать первую главу первому, второму или третьему — одно и то же с точностью до имён. Без этой проверки перебор обходит каждое решение 3! = 6 раз, под каждой перестановкой чтецов, — и узлов действительно стало в 6,3 раза меньше. Проверка общая: если у двух чтецов сейчас одинаковая нагрузка, их поддеревья совпадают с точностью до перестановки, и достаточно одного.

5. Оставшееся должно влезть: 43. Самая сильная проверка. Если рекорд — 42 минуты, а мы ищем лучше, каждый чтец может набрать не больше 41 минуты, то есть взять ещё не больше 41 − нагрузка. Сложим этот запас по всем чтецам. Если он меньше длины оставшихся глав, раздать их, не побив рекорда, нельзя, и всю ветку можно закрыть. Это оценка ослаблением: мы разрешили главам дробиться на куски и спросили, хватит ли места хотя бы так. Если не хватает даже для дробных глав, для целых не хватит тем более.

6. Стоп на нижней оценке: 38. Для всей задачи с самого начала известно: самый занятой чтец читает не меньше самой длинной главы и не меньше ⌈120 / 3⌉ = 40 минут. Как только рекорд дошёл до сорока, перебор останавливается: лучше не бывает. Без этой проверки он доказывал бы оптимальность, обходя остаток дерева, — здесь, правда, остаток уже почти пуст, и разница всего пять узлов.

От 2,4 миллиона узлов до 38 — в шестьдесят тысяч раз. А в сцене на эпилоге и четырёх чтецах — от шести миллиардов до одного.

Почему ничего не теряется

Каждое отсечение выбрасывает ветки вслепую, не глядя, что в них. Почему ответ остаётся лучшим? Сформулируем, каким отсечение должно быть, чтобы это гарантировать.

Отсюда правило: отсекать можно по доказанной оценке снизу или по доказанной равносильности. Все шесть проверок чтецов такие. Нагрузка чтеца — оценка снизу для любой раскладки в поддереве, потому что нагрузки только растут. Запас — оценка ослаблением. Чтецы с равной нагрузкой — равносильность: переставьте их имена во всех решениях одного поддерева и получите решения другого той же стоимости. А «сначала длинные главы» и «рекорд жадного» не отсекают сами — они лишь делают условие (а) выполнимым раньше.

Код

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

prunings                                nodes  busiest
cut a reader at the record              32957       40
+ the greedy record at the start        32346       40
+ the longest chapters first            11483       40
+ equal loads are the same reader        1814       40
+ the room left must fit the rest          43       40
+ stop at the lower bound                  38       40

Сцена делает то же самое, только перебор в ней записан циклом с явным стеком, а не рекурсией, — чтобы между порциями узлов браузер успевал рисовать. Порядок ходов и проверок тот же, и узлы сходятся с листингом до единицы.

Минуты, секунды, слова

Последние строки листинга — та же часть в секундах и в словах, со всеми шестью отсечениями.

in seconds: 3252 nodes, the busiest reader 2393, the lower bound 2390
in words: 3237 nodes, the busiest reader 5982, the lower bound 5975

Было 38 узлов, стало больше трёх тысяч — в восемьдесят пять раз. Главы те же, отсечения те же, изменилась только точность чисел. В минутах раскладок, где все трое читают ровно по 40, много, и первые же ветки находят одну из них, после чего оценка останавливает перебор. В секундах нижняя оценка — 2390 — недостижима: лучшее, что есть, — 2393. Чтобы это доказать, перебору приходится обойти всё, что не отсекли оценки. Переключите в сцене минуты на слова для третьей части первого тома и четырёх чтецов — счёт пойдёт на миллионы.

Для деления чисел на две равные кучи это явление изучено точно. Иэн Гент и Тоби Уолш в 1996 году заметили, а Стефан Мертенс в 1998-м объяснил методами статистической физики, что у задачи есть порог: если бит в каждом числе заметно меньше, чем самих чисел, точных разбиений много и найти одно легко; если бит больше, точное разбиение, скорее всего, одно или ни одного, и доказывать оптимальность приходится перебором. Свой обзор об этом Мертенс назвал «Самая лёгкая трудная задача». В минутах на главу приходится несколько бит, в словах — двенадцать-тринадцать: мы пересекли этот порог, не меняя ничего, кроме единиц измерения.

Сколько это стоит

В худшем случае отсечения не помогают: задача о чтецах трудная — к ней сводится разбиение чисел на две равные кучи, — и найдутся входы, где отсечь почти нечего. Оценка остаётся O(kⁿ). Памяти перебор берёт O(n): путь от корня и нагрузки.

Время — это число узлов, умноженное на работу в узле, и проверки не бесплатны. Проверка запаса стоит O(k) на узел, а простое сравнение с рекордом — O(1). Сделка выгодна, если проверка отрезает больше, чем стоит: здесь одна она сократила дерево в сорок раз. Ниже — замер на первых n главах второй части третьего тома, четыре чтеца, минуты: перебор, отсекающий только по рекорду, и перебор со всеми отсечениями. Ось времени логарифмическая.

Перебор с одним рекордом растёт ровной экспонентой: каждая новая глава умножает время в три-шесть раз, и на 17 главах Go тратит полсекунды. Перебор со всеми отсечениями на большинстве n заканчивается за микросекунды, но не на всех. На 22 и 23 главах его время в Go подскакивает в десять тысяч раз по сравнению с соседями; в Python эти точки шли бы секунды, и их из замера убрали. А на 29 главах перебор не закончился и за много секунд ни на одном языке, и эту точку убрали из обоих замеров. Это не ошибка в программе, а свойство перебора, которое называют тяжёлыми хвостами. Карла Гомес, Барт Селман и их соавторы в 2000 году показали, что у перебора с возвратом на похожих входах редкие очень долгие прогоны встречаются куда чаще, чем подсказывает интуиция. Помогают перезапуски со случайным порядком выбора: из десяти коротких попыток одна часто проскакивает мимо ловушки, в которой застряла бы одна длинная.

Опасные отсечения

Самая соблазнительная ошибка — отсекать по тому, что «скорее всего». Например, по средней нагрузке: зачем давать кому-то больше ⌈сумма / k⌉, если в хорошей раскладке все читают поровну? Включите в сцене опасное отсечение, выберите третью часть первого тома, четырёх чтецов и слова вместо минут. Перебор обойдёт восемь с половиной миллионов узлов и ответит: 9397 слов, лучше нельзя. Это ответ жадного способа, с которого перебор начинал, и он далёк от лучшего: нижняя оценка здесь 9023 слова, она недостижима, а лучшая раскладка даёт 9024. Опасное отсечение выбросило все ветки, где кто-то читает больше 9023, то есть все решения лучше жадного, и перебор «доказал» оптимальность ответа, которого не проверял. Без стартового рекорда он ответил бы, что раскладки нет вовсе. В минутах то же отсечение «работает»: там оценка достижима. Поэтому такие ошибки проходят тесты и живут долго.

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

Ещё две похожие ловушки. Симметрия должна быть настоящей: чтецы с равной нагрузкой взаимозаменяемы, а чтецы с равным числом глав — нет. И оценка должна оценивать то, что нужно: в A* подсказка, которая завышает расстояние, отсекает кратчайший путь точно так же, как средняя нагрузка отсекла лучшую раскладку.

Где работает

• Целочисленное программирование. Ветви и границы — это перебор с отсечением по оценке, где оценку даёт задача с ослабленными ограничениями: целым переменным разрешают быть дробными и решают линейную программу. Эйлса Лэнд и Элисон Дойг описали этот метод в 1960 году, и на нём стоят решатели задач о расписаниях, перевозках и раскрое.
• SAT-решатели. Перебор значений переменных, где каждое назначение тут же выводит следствия, а каждый тупик превращается в новое ограничение, которое отсекает целый класс будущих тупиков. Об этом — в главе курса о трудных задачах.
• Игры. Альфа-бета-отсечение в шахматных программах не открывает ходы, про которые уже ясно, что соперник их не допустит. При удачном порядке ходов оно смотрит примерно на корень из числа позиций, которые смотрит полный минимакс; это доказали Дональд Кнут и Рональд Мур в 1975 году. Разбор на крестиках-ноликах — в главе курса об играх.
• Базы данных. Таблица, разбитая на секции по датам, не читает секции, которые не могут попасть под условие запроса, а форматы хранения вроде Parquet держат для каждого куска столбца минимум и максимум и по ним пропускают куски целиком. Это отсечение по оценке, только ветки — мегабайты на диске.
• Геометрия. Поиск ближайшей точки в k-d дереве не заглядывает за плоскость деления, если до неё дальше, чем до лучшей найденной точки.

История

Общий метод для задач на оптимум — ветви и границы — опубликовали в 1960 году Эйлса Лэнд и Элисон Дойг для целочисленного программирования. В 1969 году Рональд Грэм оценил жадную раскладку работ по машинам — ту самую, что даёт перебору чтецов стартовый рекорд, — и доказал, что она хуже лучшей не больше чем в 4/3 − 1/(3k) раза. В 1975 году Кнут и Мур разобрали, сколько позиций экономит альфа-бета-отсечение. А Ричард Корф в 1998 году построил для деления чисел на части перебор, который сначала выдаёт ответ разностного метода Кармаркара и Карпа, а потом улучшает его, пока не докажет оптимальность: и рекорд пораньше, и порядок, и оценки — всё в одном.

Задачи

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