Оценка и рекорд: отбросить ветку, которая не побьёт лучшее найденное

Коротко

В задаче оптимизации ответ - число, и перебор можно отсекать сравнением с уже найденным РЕКОРДОМ: если оценка лучшего в ветке не лучше рекорда, ветку не раскрываем. Это метод ветвей и границ. Для целого рюкзака оценка берётся из дробного: добить остаток самым выгодным по удельной цене предметом, разрешив взять его часть. Замер на пятнадцати предметах: перебор с проверкой вместимости обходит 39 864 узла, ветви и границы - 23 узла. На тридцати предметах перебор не доходит до конца, а ветви и границы считают за 1677 шагов и 35 узлов.

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

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

В прошлой главе отсекать было легко: сумма превысила цель - ветка мертва, ответа «ровно 97» в ней уже не будет. Теперь задача другая: целый рюкзак. Тридцать предметов, вместимость 327, надо набрать МАКСИМУМ цены. Здесь ничего не «превышается»: любая ветка даёт какой-то ответ, просто одни лучше других.

Прежде чем читать дальше, подумай: что здесь может сыграть роль «цели», по которой отсекают? И откуда взять число, с которым сравнивать, если лучший ответ как раз и ищется?

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

Аукцион. Лучшая ставка на табло - 420, её видят все. Приходит новый участник и говорит: «Мой кошелёк - 400». Дальше слушать незачем: даже если он отдаст всё, он не перебьёт. Не потому что он плохо торгуется, а потому что потолок его возможностей ниже уже сделанной ставки.

Рекорд - это сделанная ставка. Оценка ветки - это кошелёк, потолок её возможностей. Если потолок не выше ставки, ветка не рассматривается.

Механизм: рекорд, оценка и одно сравнение

ВЕТВИ И ГРАНИЦЫ = поиск с возвратом + две вещи

РЕКОРД  - лучшее найденное решение (для максимума - наибольшая цена).
          Обновляется в каждом узле, где решение уже допустимо.

ОЦЕНКА  - потолок ветки: ЛУЧШЕЕ, что в ней вообще достижимо.
          Для максимума обязана быть НЕ МЕНЬШЕ реального лучшего в ветке.

ОТСЕЧЕНИЕ:  если оценка ≤ рекорд, ветку не раскрываем

Заметь асимметрию, которая делает приём правильным. Оценка обязана быть оптимистичной с запасом: ошибка в сторону «ветка лучше, чем на самом деле» делает отсечение более осторожным и ответ не портит. Ошибка в другую сторону - «ветка хуже, чем на самом деле» - отсекает ветку, в которой лежал оптимум, и программа тихо выдаёт ответ хуже настоящего. Поэтому оценку называют ДОПУСТИМОЙ, если она никогда не занижает потолок (для задачи на максимум) и никогда не завышает (для задачи на минимум).

Правило

Метод ветвей и границ - это поиск с возвратом, у которого есть рекорд (лучшее найденное решение) и оценка ветки (потолок достижимого в ней). Ветка отсекается, когда оценка не лучше рекорда. Оценка обязана быть ДОПУСТИМОЙ: для максимума - не меньше реального лучшего в ветке, для минимума - не больше. Чем оценка точнее, тем больше отсекается, но тем дороже её считать - это и есть главная развилка метода. Чем раньше найден хороший рекорд, тем раньше начинают работать отсечения, поэтому ветки обходят в порядке «сначала самая перспективная», а рекорд иногда заводят заранее приближённым решением.

Разбор: оценка для целого рюкзака из дробного

Целый рюкзак: предмет берут целиком или никак. Дробный: предмет можно разрезать. Дробный решается жадностью - брать по убыванию удельной цены цена / вес, последний предмет доливать частью, - и это мы разбирали в разделе про жадные алгоритмы.

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

def ocenka(i, v, c):
    svobodno = C - v
    j = i
    itog = c
    while j < len(ves):
        if ves[j] <= svobodno:          # влезает целиком - берём
            svobodno = svobodno - ves[j]
            itog = itog + cena[j]
        else:                           # не влезает - доливаем частью
            itog = itog + svobodno * cena[j] // ves[j]
            return itog
        j = j + 1
    return itog

Предметы отсортированы по убыванию удельной цены - без этого жадность не решает дробную задачу, и оценка перестаёт быть оценкой. Про деление нацело (//) два замечания. Первое: оно законно, хотя и уменьшает оценку. Цены целые, значит и настоящий лучший ответ ветки целый, а целое число, которое не больше дробной оценки, не больше и её целой части. Второе: порядок действий. Сначала умножение, потом деление - (svobodno * cena[j]) // ves[j]; если сначала поделить цену на вес нацело, оценка занизится и перестанет быть допустимой.

Сам перебор после этого выглядит так:

def rec(i, v, c):
    if c > rekord[0]:                   # решение допустимо - пробуем в рекорд
        rekord[0] = c
    if i == len(ves):
        return 0
    if ocenka(i, v, c) <= rekord[0]:    # потолок ветки не выше рекорда
        return 0
    if v + ves[i] <= C:
        rec(i + 1, v + ves[i], c + cena[i])
    rec(i + 1, v, c)
    return 0

rekord = [0]            # список из одного числа: функция меняет его содержимое
rec(0, 0, 0)
print(rekord[0])

Данные для замера - тридцать предметов:

ves  = [24, 23, 25, 10, 26, 27, 28, 22, 11, 31,  8, 26, 13, 32, 17,
        29,  9, 16, 34, 27, 18, 29, 21, 26, 22, 25, 25, 16, 17, 17]
cena = [38, 68, 58, 27, 69, 45, 38, 32, 28, 83, 15, 45, 22, 87, 31,
        39, 14, 32, 65, 39, 49, 46, 56, 31, 26, 44, 37, 28, 49, 17]

Набор «на n предметов» - это первые n из списка, отсортированные по убыванию cena / ves (оба списка переставляются вместе). Вместимость у каждого набора своя - половина его суммарного веса: 161, 219, 277 и 327. «Перебор» в левом столбце - тот же rec без строки с оценкой.

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

предметов   перебор (только вместимость)      ветви и границы
15          39 864 узла, 182 945 шагов        23 узла,    598 шагов
20          не уложился                       61 узел,  1 346 шагов
25          не уложился                       52 узла,  1 573 шага
30          не уложился                       35 узлов, 1 677 шагов

Узлы здесь посчитаны отдельным прогоном со счётчиком (он сам стоит по шагу на узел, поэтому шаги взяты из программы без него).

Двадцать три узла вместо сорока тысяч - это в 1733 раза меньше. И обрати внимание на правый столбец целиком: число узлов почти не растёт с размером задачи. Так и выглядит сильная оценка: она отсекает всё, кроме узкого коридора вокруг ответа.

Проверка правильности обязательна, и она есть: та же задача решается динамикой по вместимости из прошлого раздела, и ответы совпадают до единицы - 420, 532, 675, 783. Это и есть способ убедиться, что оценка допустима: сравнить с методом, который ничего не отсекает.

Разбор: жадный старт, который один раз сработал как магия

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

предметов   ВиГ с нуля          ВиГ с жадным стартом
15          23 узла,   598      23 узла,   654
20          61 узел, 1 346      61 узел, 1 420
25          52 узла, 1 573      52 узла, 1 665
30          35 узлов, 1 677     1 УЗЕЛ,    216

На тридцати предметах жадность сразу нашла оптимум - 783, и оценка в корне дерева оказалась ровно 783 тоже. Сравнение 783 <= 783 отсекло корень, и перебор закончился, не начавшись. На остальных трёх наборах жадный старт не дал ни одного сэкономленного узла и стоил лишних 56-92 шагов на сам жадный проход.

Почему он не дал ничего - объяснение полезнее самого замера. Обход в глубину с ветвью «берём предмет» ПЕРВОЙ спускается, забирая всё, что влезает, - то есть первый же путь до дна и ЕСТЬ жадное решение. Рекорд от жадности появляется сам на первом спуске, и жадный старт только приносит его чуть раньше. Сам спуск при этом не исчезает: в его узлах оценка выше жадного рекорда, отсекать их не за что. Замер подтверждает: на пятнадцати предметах жадность даёт 420, и перебор без всякого старта находит 420 на первом же пути - узлов 23 и там, и там. Выигрыш появляется только при редком совпадении: жадность попала точно в оптимум, И оценка в корне с ним сошлась.

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

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

Первое: недопустимая оценка. Если оценка занижает потолок ветки, отсечение убивает ветку с оптимумом. Проверим это на деле: заменим в ocenka долив по удельной цене ПЕРВОГО не влезающего предмета на долив по удельной цене последнего (самого невыгодного). Такая «оценка» иногда меньше настоящего потолка, и на двадцати пяти предметах программа печатает 670 вместо 675. На трёх других наборах из четырёх ответ остался верным. Ошибка, которая проявляется на одном наборе из четырёх, - худший вид ошибки.

Второе: забыть сортировку. Оценка из дробного рюкзака верна только на предметах, упорядоченных по убыванию удельной цены. Без сортировки она перестаёт быть оценкой сверху, и ответы ломаются сразу на всех размерах: 355 вместо 420, 518 вместо 532, 616 вместо 675, 700 вместо 783. Сортировка здесь - не оптимизация, а условие ПРАВИЛЬНОСТИ.

Третье: сравнивать строго. ocenka(...) < rekord[0] вместо <= оставляет ветки, которые могут только повторить рекорд, а не побить. Ответ останется верным, перебор подорожает. А вот в задаче «найти ВСЕ оптимальные решения» строгое сравнение как раз необходимо - там равенство рекорду ещё интересно.

Четвёртое: обновлять рекорд только на дне. В рюкзаке частичный набор - уже допустимое решение, и обновлять рекорд можно в каждом узле. Если делать это только при i == len(ves), рекорд будет расти позже, отсечения включатся позже, перебор подорожает.

Пятое: считать оценку дороже, чем она экономит. Наша ocenka стоит O(n) на узел. При 23 узлах это не важно, но бывает наоборот: через урок есть замер на коммивояжёре, где оценка, посчитанная в лоб, на шести городах сделала перебор втрое ДОРОЖЕ полного, а та же самая оценка, пересчитываемая при спуске за одно вычитание, на восьми городах оказалась в девять раз дешевле лобовой.

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

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

Второй - промышленные решатели. Любой решатель целочисленного линейного программирования (их используют в логистике, планировании, раскрое) внутри устроен как ветви и границы, где оценка - это ответ НЕПРЕРЫВНОЙ задачи (той же, но с разрешёнными дробными значениями), полученный симплекс-методом из раздела про линейное программирование. Отсюда и знакомое слово «релаксация»: ослабить требование целочисленности, получить оценку. Мы сделали то же самое руками на рюкзаке.

Третий - умение читать логи такого решателя. Строки вида «best bound 1043.5, best solution 1039, gap 0.4%» - это ровно оценка и рекорд из этого урока. Решатель остановится, когда они сойдутся, и «gap» - это то, что ещё не доказано.

Теперь сам

Задача на МИНИМУМ: разложить предметы по двум ящикам так, чтобы разница суммарных весов была наименьшей. Что здесь рекорд, что оценка, и в какую сторону оценка обязана ошибаться?

Ответ. Рекорд - наименьшая разница, найденная до сих пор (начать можно с «все предметы в первый ящик», то есть с суммы всех весов). Оценка здесь уже не потолок, а ПОЛ: наименьшая разница, на которую ветка может рассчитывать; она обязана быть НЕ БОЛЬШЕ реально достижимой, то есть снова оптимистичной - обещать ветке лучшее, чем та, возможно, даст.

Простая допустимая оценка: пусть в ветке уже разложены первые i предметов и разница текущих сумм равна d, а в хвосте осталось суммарно ostatok. Тогда лучшее, что может случиться, - это полностью закрыть разницу остатком:

если ostatok >= d:   оценка = 0, если сумма ВСЕХ весов чётная, иначе 1 - закрыть можно
иначе:               оценка = d − ostatok - остатка не хватит даже на выравнивание
отсекаем ветку, если оценка >= рекорд

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

Эта оценка груба (она почти всегда равна нулю или единице в начале перебора и потому ничего не отсекает), зато заведомо допустима. Заметь, откуда она взялась: это снова ослабление - мы разрешили делить остаток как угодно, будто это песок, а не предметы. Точнее её сделать можно тем же путём, что в рюкзаке: ослаблять задачу МЕНЬШЕ. Например, вспомнить про самый тяжёлый из оставшихся предметов: если он один тяжелее, чем d плюс все остальные, его не уравновесить ничем, и оценка сразу больше нуля.

Главное

Ветви и границы - это поиск с возвратом плюс рекорд плюс оценка. Рекорд - лучшее найденное решение, оценка - потолок достижимого в ветке, отсечение - одно сравнение между ними. Оценка обязана быть допустимой: для максимума не меньше реального лучшего в ветке, для минимума не больше; недопустимая оценка тихо выдаёт ответ хуже настоящего - 670 вместо 675 на одном наборе из четырёх. Оценка для целого рюкзака берётся из дробного (ослабить задачу - разрешить резать предметы), и она настолько сильна, что перебор тридцати предметов сходится за 35 узлов, тогда как перебор с одной проверкой вместимости на пятнадцати обходит 39 864 узла, а на двадцати уже не укладывается в предел. Сортировка по удельной цене здесь - условие правильности оценки, а не оптимизация: без неё ответы ломаются на всех размерах. И честно про жадный старт: на одном наборе он свёл дерево к одному узлу, на трёх других не дал ничего.