Откуда берётся граница: ослабить задачу

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

Как думаешь, откуда взялась оценка для рюкзака

В прошлых уроках оценка для рюкзака появилась как фокус: «решим дробную задачу - получим потолок для целой». Фокус работает, но сам приём остался необъяснённым.

Прежде чем читать дальше, попробуй повторить его на другой задаче. Коммивояжёр: обойти все города и вернуться, минимизируя длину. Какое требование здесь можно УБРАТЬ, чтобы задача стала простой, но ответ остался не больше настоящего?

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

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

Это и есть ослабление: выбросить часть ограничений («мастер один и не может быть в двух местах»), сосчитать упрощённую задачу и получить гарантированную границу.

Механизм: убрать требование - получить границу

РЕЛАКСАЦИЯ: убери ограничение → задача становится проще → её ответ
            не хуже ответа исходной задачи → это и есть оценка

целый рюкзак      убрать «предмет целиком»      → дробный рюкзак (жадность)
коммивояжёр       оставить «из города есть выход» → сумма минимальных рёбер
коммивояжёр       убрать «каждая степень 2»     → остовное дерево (МОД)
целые переменные  убрать целочисленность        → непрерывная задача (симплекс)
расписание        убрать «машина одна»          → каждая задача на своей машине

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

Почему ответ ослабленной задачи - именно граница, а не что-то другое: мы РАСШИРИЛИ множество допустимых решений. Все настоящие решения остались допустимыми, добавились новые. Значит минимум по расширенному множеству не больше минимума по исходному, а максимум - не меньше. Отсюда и направление: для задачи на минимум ослабление даёт оценку СНИЗУ, для задачи на максимум - СВЕРХУ. Ровно то, что требуется для допустимого отсечения.

Правило

Граница получается ослаблением: убери одно или несколько требований задачи, реши оставшееся, и ответ будет оценкой - снизу для минимума, сверху для максимума. Это законно потому, что ослабление РАСШИРЯЕТ множество допустимых решений. Чем меньше убрано, тем точнее оценка и тем дороже её счёт, поэтому выбор оценки - это точка на оси между «ничего не отсекает» и «стоит как вся задача». Оценку надо считать ИНКРЕМЕНТНО: передавать в рекурсию уже накопленную часть и менять её на одну величину, а не пересчитывать с нуля на каждом узле. Замер: та же оценка коммивояжёра, пересчитываемая целиком, стоит в девять раз дороже предпосчитанной, а на малых n делает перебор дороже полного.

Разбор: граница для коммивояжёра из «самых дешёвых рёбер»

Что убрать. В настоящем маршруте из каждого непосещённого города выходит ровно одно ребро дальше по маршруту - и из текущего города тоже. Оставим от маршрута только это, а остальное уберём: и то, что рёбра складываются в один СВЯЗНЫЙ путь, и то, что в каждый город входит ровно одно ребро. Каждому городу разрешим выбрать себе самое дешёвое ребро независимо от остальных.

Тогда остаток маршрута не может стоить меньше, чем сумма этих минимумов:

оценка = пройденная длина
       + минимальное ребро из ТЕКУЩЕГО города
       + минимальное ребро из каждого НЕПОСЕЩЁННОГО города

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

Считать её можно двумя способами, и разница огромна. Способ в лоб: на каждом узле пройти по всем непосещённым городам и для каждого найти минимум - это O(n²) на узел. Способ лучше: посчитать минимальное ребро каждого города ОДИН раз до перебора, а сумму минимумов непосещённых передавать параметром, вычитая из неё минимум того города, в который заходим:

n = len(d)
minr = [0] * n                      # minr[v] - самое дешёвое ребро из города v
v = 0
while v < n:
    m = 100000
    u = 0
    while u < n:
        if u != v and d[v][u] < m:  # u != v: на диагонали нули, их пропускаем
            m = d[v][u]
        u = u + 1
    minr[v] = m
    v = v + 1

def rec(tek, posesheno, dlina, ostatok):
    if posesheno == n:
        itog = dlina + d[tek][0]
        if itog < rekord[0]:
            rekord[0] = itog
        return 0
    if dlina + ostatok + minr[tek] >= rekord[0]:
        return 0                               # граница не лучше рекорда
    v = 1
    while v < n:
        if byl[v] == 0:
            byl[v] = 1
            rec(v, posesheno + 1, dlina + d[tek][v], ostatok - minr[v])
            byl[v] = 0
        v = v + 1
    return 0

byl = [0] * n
byl[0] = 1
rekord = [100000]                   # заведомо больше любого маршрута
summa = 0
v = 1
while v < n:
    summa = summa + minr[v]         # в корне не посещены все города, кроме нулевого
    v = v + 1
rec(0, 1, 0, summa)
print(rekord[0])

Замер. У каждого n своя матрица расстояний, поэтому ответы не обязаны расти вместе с числом городов (матрицы на шесть и восемь городов - в задаче этой главы). «Не уложился» значит не уложился в 300 000 шагов движка. Ответы ветвей и границ сверены с полным перебором: на шести-восьми городах прямо на движке, на девяти и десяти - прогоном перебора с поднятым пределом (он стоит 2,4 и 23,7 миллиона шагов).

городов   полный перебор               ветви и границы            ответ
6           326 узлов,   5 387 шагов     170 узлов,   2 599 шагов   262
7         1 957 узлов,  35 982 шага      354 узла,    5 207 шагов   219
8        13 700 узлов, 277 780 шагов   1 355 узлов,  20 349 шагов   225
9         не уложился                  4 577 узлов,  73 122 шага    228
10        не уложился                  6 742 узла,  105 526 шагов   205
11        не уложился                   не уложился                  -

Узлы посчитаны отдельным прогоном со счётчиком, шаги - программой без него.

Выигрыш скромнее, чем в рюкзаке (там было 23 узла вместо 39 864), и это не случайность: граница из минимальных рёбер - слабая. Она не учитывает, что рёбра должны складываться в путь, и потому сильно недооценивает остаток. Более точная граница - минимальное остовное дерево на непосещённых городах, то же МОД из раздела 11: оно учитывает связность и даёт оценку выше, но стоит O(n²) на узел вместо O(1). Это ровно та развилка с картинки выше, и решается она замером.

Разбор: оценка, которая не окупилась

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

def ocenka(tek):
    summa = 0
    v = 0
    while v < n:
        if v == tek or byl[v] == 0:
            m = 100000
            u = 0
            while u < n:
                if u != v and d[v][u] < m:
                    m = d[v][u]
                u = u + 1
            summa = summa + m
        v = v + 1
    return summa
# ...в rec:  if dlina + ocenka(tek) >= rekord[0]: return 0

Число получается то же самое, поэтому и отсекается ровно то же: узлов 170, 354 и 1355, как у предпосчитанной версии. Отличается только цена узла:

городов   полный перебор    оценка в лоб (O(n²))   оценка предпосчитанная
6           5 387 шагов      15 264 шага             2 599 шагов
7          35 982 шага       41 746 шагов            5 207 шагов
8         277 780 шагов     186 770 шагов           20 349 шагов
9         не уложился       не уложился             73 122 шага

Два факта из этой таблицы. Первый: на шести и семи городах версия с оценкой в лоб ДОРОЖЕ полного перебора - 15 264 против 5387 и 41 746 против 35 982. Отсечение сработало (узлов стало вдвое-впятеро меньше), но каждый узел подорожал настолько, что сделка оказалась убыточной. Второй: та же оценка, посчитанная предподсчётом и переданная параметром, дешевле варианта в лоб в девять раз на восьми городах - и вот она окупается при любом n.

Есть и третий вариант, и он показывает ось с картинки целиком. Если искать минимум не по всем рёбрам города, а только по рёбрам в ещё не посещённые города (и в нулевой, куда надо вернуться), граница станет СИЛЬНЕЕ: ребро в уже пройденный город в маршруте всё равно не понадобится. Узлов от этого меньше, но предпосчитать такую оценку нельзя - она зависит от того, что посещено. На восьми городах она стоит 74 396 шагов: лучше лобовой, но в три с половиной раза хуже слабой и дешёвой.

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

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

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

Второе: ослабить не то. Если убрать из коммивояжёра требование «посетить все города», ослабленная задача станет тривиальной (ноль), оценка - нулевой, и отсечение перестанет работать вовсе. Ослаблять надо то, что МЕШАЕТ считать, оставляя то, что даёт величину.

Третье: путать направление. Для задачи на минимум нужна оценка СНИЗУ, и ослабление её и даёт. Если случайно посчитать оценку сверху (например, длину какого-то конкретного маршрута), отсечение оценка >= рекорд станет неверным и отбросит оптимум.

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

Пятое: забыть, что рекорд надо чем-то инициализировать. В коммивояжёре начальный рекорд 100000 - это «заведомо больше любого маршрута». Если поставить туда ноль, отсечётся всё и ответ будет неверным; если поставить слишком маленькое число - то же самое. Надёжнее начинать с длины ЛЮБОГО настоящего маршрута, например жадного.

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

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

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

Третий - понимание, почему решатель «почти решил». Пара «оценка и рекорд» даёт не только ответ, но и гарантию: если в задаче на максимум рекорд 1039, а лучшая оценка по всем открытым веткам 1043, то оптимум где-то между, и дальше можно не считать - разница меньше процента. Это и есть то, чем живёт прикладная оптимизация: не «точный ответ», а «ответ с доказанной границей ошибки».

Теперь сам

Задача: разложить n задач по трём машинам, минимизируя время окончания последней (длительности известны). Какое ослабление даёт хорошую оценку снизу?

оценка = max( сумма всех длительностей / 3 ,  самая длинная задача )