Масштабирование выпуклого потока и доказательство оценки

Если можешь объяснить ремонт при смене масштаба, переходи к «Теперь сам».

Крючок: можно ли просто делить блок пополам

Как думаешь, сохранит ли решение с неотрицательными приведёнными ценами это свойство после уменьшения блока? Для квадрата при x=4 средняя цена блока длины четыре равна (64-16)/4=12. Средняя цена блока два равна (36-16)/2=10. Если поправка потенциалов равна одиннадцати, первая приведённая цена равна одному, вторая - минус одному. Сам поток не изменился, но допустимое улучшение стало мельче и дешевле. Поэтому переход между фазами требует ремонта.

На что это похоже: сначала палеты, затем коробки

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

Механизм: сеть блоковых перемещений

Для x+Δ≤u прямая остаточная дуга получает ёмкость Δ и цену [C(x+Δ)-C(x)]/Δ. Для x≥Δ обратная получает ёмкость Δ и цену [C(x-Δ)-C(x)]/Δ. Деление на Δ переводит полное изменение стоимости блока в цену единицы. Сравнение путей остаётся верным, потому что каждый перенос в фазе имеет одинаковый размер Δ.

Здесь выводим вариант для сети, в которой все ёмкости конечны и целы, балансы целы и суммируются в ноль. Полагаем U=max(1, max|b(i)|, max u). Начинаем с наибольшей степени двойки Δ≤U. Все потоки сначала нулевые. Поскольку u≤U<2Δ, на дуге помещается не больше одного полного блока. Если его цена отрицательна, отправляем блок; иначе оставляем ноль. Если блок не помещается, оставляем ноль. При нулевых потенциалах все доступные блоковые цены неотрицательны: после отправления прямой дуги уже нет, а обратная возвращает отрицательную цену со знаком плюс. Получаем псевдопоток, пока без гарантии балансов.

Обозначим e(i)=b(i)-(исходящий поток минус входящий). На фазе S содержит e≥Δ, T содержит e≤-Δ. Ищем кратчайший путь из любого S в любой T в блоковой сети. Если путь есть, обновляем потенциалы и переносим Δ. Если нет пути ни между какой такой парой, заканчиваем только текущую фазу и делим Δ пополам. В отличие от варианта с доступными неограниченными путями, оба множества могут оставаться непустыми. Остановку всей задачи разрешает последний масштаб Δ=1.

Для расстояний удобно соединить все S с временным источником нулевыми дугами. Пусть d - кратчайшие приведённые расстояния, D - расстояние до ближайшего достижимого T. Обновляем π(i)←π(i)-h(i), где h(i)=min(d(i),D); для недостижимой вершины h(i)=D. Таким образом не вычитаем бесконечность. Для любой дуги с неотрицательной длиной a выполняется h(j)≤h(i)+a: усечение сверху сохраняет неравенство кратчайшего пути. Если i недостижима, h(i)=D и h(j)≤D≤D+a; если i достижима и есть дуга i→j, то j тоже достижима. Новая приведённая цена a+h(i)-h(j) неотрицательна. На выбранном пути h=d и равенства дают нулевые цены; обратные дуги после дополнения не нарушают инвариант.

Правило: ремонт до поиска пути

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

Разбор: ремонт квадратичной дуги

Берём C(x)=x², x=4, старый масштаб четыре, новый два. Пусть π(i)-π(j)=11. При масштабе четыре прямая приведённая цена 12-11=1, обратная (0-16)/4+11=7. Обе неотрицательны. После перехода к двум прямая 10-11=-1, обратная (4-16)/2+11=5. Увеличиваем поток до шести.

Теперь прямая блоковая цена равна (64-36)/2-11=3, обратная (16-36)/2+11=1. Ремонт сработал. В начале i отдал дополнительно две единицы, j получил две: узловые дисбалансы изменились, поэтому восстановление потоковой допустимости нельзя пропустить.

Почему достаточно одного сдвига? Сначала пусть x+2Δ≤u, то есть старый прямой блок существует. Обозначим полные приведённые приращения двух соседних малых блоков A и B. По старому инварианту A+B≥0. После уменьшения масштаба обнаружили A<0. Значит, B≥-A>0. После сдвига вперёд новая прямая цена B/Δ≥0, а новая обратная -A/Δ>0.

Отдельно рассмотрим границу x+Δ≤u0. Поэтому требуемые знаки снова восстановлены. Например, x=4,u=7,Δ=2, C=x² и разность потенциалов11: новая прямая цена -1, сдвигаем x до6, дальше блок до8 запрещён, обратная цена1. Для уменьшения потока рассуждение симметрично: если x-2Δ<0, после сдвига назад следующая обратная дуга исчезает, а прямая получает положительную цену. Именно проверка существования дуг разрешает граничный случай.

# scaling_repair.py
x = 4
delta = 2
potential_difference = 11

def reduced_forward(x, delta):
    change = (x+delta)**2 - x*x
    return change / delta - potential_difference

def reduced_backward(x, delta):
    change = (x-delta)**2 - x*x
    return change / delta + potential_difference

print(reduced_forward(x, 4))
print(reduced_backward(x, 4))
print(reduced_forward(x, delta))
print(reduced_backward(x, delta))
if reduced_forward(x, delta) < 0:
    x = x + delta
print(x)
print(reduced_forward(x, delta))
print(reduced_backward(x, delta))
# 1.0
# 7.0
# -1.0
# 5.0
# 6
# 3.0
# 1.0

Разбор: грубый масштаб ещё не обязан пропускать поток

Две параллельные дуги s→t имеют ёмкости по одной и цену C(x)=x². Нужно перевезти две единицы: b(s)=2,b(t)=-2. При U=2 стартуем с Δ=2. Ни одна блоковая дуга не существует, S={s}, T={t}, и пути нет. Это завершает фазу, но не доказывает недопустимость. При Δ=1 обе дуги доступны с ценой один; два дополнения дают потоки один и один, полный расход два и нулевые дисбалансы. Значит, правило «нет пути - задача невыполнима» до последнего масштаба было бы ошибочным.

Механизм: число дополнений через конечный разрез

Обоснуем границу для допустимой исходной задачи. В конце фазы возьмём R - все вершины, достижимые из S в Δ-сети. В R нет вершин T. Сравним псевдопоток x с любым допустимым потоком x*. Разность должна иметь чистый выход e(R) из R. Но через разрез нет остаточных дуг ёмкости хотя бы Δ: для исходящей дуги u-x<Δ, для входящей x<Δ. Поэтому возможный дополнительный чистый выход не превосходит суммы этих остатков, и e(R)≤mΔ.

Внутри R каждый отрицательный дисбаланс по модулю меньше Δ, поэтому их сумма меньше nΔ. Снаружи R каждый положительный дисбаланс меньше Δ, иначе вершина сама была бы в S и R. Общий положительный дисбаланс внутри R равен e(R) плюс модуль отрицательных внутри, то есть меньше (m+n)Δ. Добавив положительные снаружи, получим меньше (m+2n)Δ. Этот довод работает и при непустых S,T, разделённых недостаточно ёмким разрезом.

При переходе от 2Δ к Δ ремонт m дуг добавляет не больше mΔ к общей положительной невязке. Итого в начале новой фазы она меньше (3m+4n)Δ. Каждое дополнение уменьшает её на Δ, значит, дополнений O(m+n). В первой фазе отдельная граница: начальные запасы дают не больше nU, а включение блоков не больше mΔ; поскольку U<2Δ, снова получаем O((m+n)Δ). После удаления изолированных вершин каждая оставшаяся касается дуги, поэтому n≤2m и оценка становится O(m) дополнений. Изолированная вершина с b≠0 сразу доказывает недопустимость; с b=0 её можно убрать.

Фаз 1+⌊log₂U⌋, то есть O(log(U+1)). Если S(n,m) - время одного поиска кратчайшего пути с неотрицательными длинами, вся работа на допустимом входе занимает O((m+n)log(U+1)·S(n,m)); после указанного удаления вершин это O(m log(U+1)·S). Потенциалы и ремонт обходят сеть за линейное время. Зависимость от U означает, что алгоритм не является сильно полиномиальным.

При Δ=1 и целых данных отсутствие пути уже завершает проверку допустимости. У R нет отрицательных e, вне R нет положительных. Остатки разреза меньше единицы равны нулю, поэтому для допустимой задачи e(R)≤0 и все дисбалансы нулевые. Если положительный e всё же остался, исходящие дуги R насыщены, входящие нулевые, и b(R)>Σu(R→внеR). Это проверяемый сертификат невозможности исходных балансов, а не эвристический отказ поиска.

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

Что ломается на границах

При x+Δ>u прямой блоковой дуги нет: нельзя считать её цену и потом округлять поток до ёмкости. При x<Δ отсутствует обратная. Остаток ёмкости, меньший текущего блока, станет доступен на следующих фазах. При дробных балансах остановка на Δ=1 уже не означает точного нуля дисбалансов. Нужно заранее выбрать сетку и масштабировать входные данные либо решать непрерывную задачу отдельным методом.

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

Дуги без конечной ёмкости: сначала докажи ограничение

В предыдущем варианте нельзя просто пропустить u=∞ при определении U. Контрпример: на неограниченной дуге C(x)=(x-3)², формально U=1 и Δ=1. После отправки первого блока следующая прямая цена C(2)-C(1)=-3, поэтому стартовый инвариант ещё не достигнут. В модели книги встречаются неограниченные пути; наш довод одного стартового блока относится к явно конечному варианту. Для применения его к ∞ нужна дополнительная обоснованная граница, а не произвольная замена знакомого U.

Один достаточный способ получить такую границу использует известный допустимый целый план x⁰ с ценой K и нижние оценки Lₐ≤Cₐ(x) на каждой дуге. Любой план не дороже K обязан удовлетворять Cₐ(xₐ)≤K-Σ других L. Если цена каждой неограниченной дуги растёт до бесконечности при x→∞ и известна точка начала её неубывания, можно найти конечный Bₐ, за которым это неравенство уже нарушено. Удваиваем проверяемый аргумент до превышения уровня, затем при желании уточняем границу двоичным поиском. Все лучшие планы лежат в полученной конечной коробке, поэтому замена ∞ на эти B сохраняет оптимум; новое U включает B. Стоимость получения границ учитывается отдельно.

Для C(x)=(x-3)² нижняя оценка ноль, а допустимый уровень K=4 ограничивает x интервалом[1,5], так что B=5 достаточно. Для постоянной цены такая проверка границы не даёт, хотя иная структура сети может дать её; для цены -x возможен неограниченный снизу цикл. Без доказанной ограниченности подходящего уровня или другого аргумента этот конечный вариант алгоритма нельзя объявить решателем произвольных неограниченных выпуклых сетей.

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

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

Теперь сам

На квадрате при x=6,Δ=2 выбери разность потенциалов 9. Найди две приведённые цены и нужный ремонт. Ответ: вперёд (64-36)/2-9=5, назад (16-36)/2+9=-1. Уменьшаем x до четырёх. Затем вперёд 10-9=1, назад -6+9=3. Проверь, что прежний блок длины четыре до ремонта имел неотрицательные приведённые цены: вперёд 16-9=7, назад -8+9=1.