Поток наименьшей стоимости
Также: Minimum-cost flow · min-cost flow · MCMF · транспортная задача · transportation problem · задача Монжа — Канторовича · последовательные кратчайшие пути · successive shortest paths · отмена отрицательных циклов · cycle cancelling · потенциалы · алгоритм Суурбалле · Suurballe
Как провезти груз по сети так, чтобы суммарная стоимость была наименьшей. У отмены перевозки отрицательная цена, и план наилучший, когда в остаточной сети нет круга отрицательной стоимости; доказывают это «цены» вершин — потенциалы, а строят план кратчайшими путями.
В 1930 году А. Н. Толстой напечатал статью «Методы нахождения наименьшего суммарного километража при планировании перевозок в пространстве». В ней была задача: десять источников груза, шестьдесят восемь станций, сто пятьдесят пять железнодорожных путей с известными расстояниями. Нужно развезти 543 тысячи тонн так, чтобы сумма «тонны × километры» была наименьшей. Толстой решил её вручную и проверил решение, перебирая круги из нескольких перевозок. Ниже его таблица целиком и решение на компьютере.
Сначала план, который нашёл обычный поток: всё вывезено, все станции снабжены, но о расстояниях этот план ничего не знал — 398 548 тысяч тонно-километров. Потом 30 кругов. Каждый круг — это перевозки, которые можно поменять разом, не нарушив ни одного запаса и ни одной потребности: здесь везти больше, там меньше. Если сумма расстояний со знаками отрицательна, перемена выгодна. Самый выгодный круг экономит 1224 тысячи тонно-километров: Артёмовск начинает возить в Москву, Балахониха вместо Москвы — в Самару, Илецк вместо Самары — в Ташкент, а Артёмовск, наоборот, больше не возит в Ташкент за 3051 километр.
Когда кругов не осталось, план стоит 395 052 тысячи тонно-километров — ровно столько, сколько у плана Толстого. Совпадает и деталь, которую Толстой выписал в статье: из Дзержинска — 25 тысяч тонн в Нижний Новгород, 35 в Москву, 15 в Ликино, 10 в Берендеево, 6 в Иваново, 5 в Нерехту, 4 в Александров. В 2002 году Александр Схрейвер проверил его план программой линейного программирования: наилучший. В конце сцены — цены, которые доказывают это без всякой программы.
Идея
У каждой дуги сети, кроме пропускной способности, есть стоимость — цена провоза единицы по ней: километры, тенге, минуты. Стоимость потока — сумма по дугам «поток × стоимость». Задача о потоке наименьшей стоимости: провезти заданное количество — или развезти заданные запасы по заданным потребностям — как можно дешевле. Транспортная задача Толстого — её частный случай: источники, станции, пути между ними без ограничения пропускной способности.
Как и в задаче о наибольшем потоке, ключевой инструмент — остаточная сеть: у дуги остаётся то, что можно добавить, а у обратной — то, что можно отменить. Новое одно: обратная дуга стоит минус стоимость прямой. Отменить перевозку на 400 километров значит сэкономить 400 километров на тонну. В остаточной сети появляются дуги отрицательной стоимости, и с ними — круги отрицательной стоимости.
Поток наилучший, когда в остаточной сети нет круга отрицательной стоимости. Улучшать можно двумя способами: брать любой поток и пускать единицы по отрицательным кругам, пока они есть, или растить поток с нуля, каждый раз по самому дешёвому пути остаточной сети.
Первый способ — в сцене выше, второй — в коде ниже. Оба приходят к одному ответу, и для обоих важно одно и то же свойство.
Почему план наилучший
Поток с заданными запасами и потребностями имеет наименьшую стоимость тогда и только тогда, когда в его остаточной сети нет круга отрицательной стоимости.
Если отрицательный круг есть, пустим по нему столько, сколько позволяет его самая узкая дуга. В каждую вершину круга войдёт столько же, сколько выйдет, — запасы и потребности не изменятся, ёмкости не нарушатся, а стоимость уменьшится. Значит, поток не был наилучшим.
Пусть отрицательных кругов нет, и f* — любой другой поток с теми же запасами и потребностями. Разность f* − f читается как поток в остаточной сети: где f* везёт по дуге больше, разница занимает её остаток, где меньше — обратную дугу. В каждой вершине у этой разности втекает столько же, сколько вытекает, ведь у обоих потоков одинаковые запасы и потребности. Такой поток раскладывается на круги: начнём с любой дуги, где что-то течёт, и пойдём дальше по дугам с течением — из вершины, куда втекло, обязательно что-то вытекает, — пока не придём в уже пройденную вершину. Получился круг; вычтем из него наименьшее течение на нём и повторим. Все круги лежат в остаточной сети и стоят не меньше нуля, поэтому стоимость f* − f не меньше нуля, то есть f* не дешевле f.
Толстой, по-видимому, первым заметил, что в наилучшем плане таких кругов нет, и проверял свой план по кругам. Только перебрать все круги вручную невозможно, а несколько найденных ничего не гарантируют. Схрейвер подсчитал: план, в котором нет ни одного отрицательного круга из четырёх перевозок и ни одного из семи более длинных кругов, которые проверял Толстой, может стоить до 397 226 — на 2174 дороже наилучшего. Нужно свидетельство, которое проверяется одним проходом. Его дают потенциалы.
В остаточной сети нет круга отрицательной стоимости тогда и только тогда, когда вершинам можно приписать числа π(v) так, что у каждой дуги остаточной сети приведённая стоимость c(u, v) + π(u) − π(v) не меньше нуля.
Если такие числа есть, возьмём любой круг: у каждой его вершины π один раз прибавляется и один раз вычитается, так что стоимость круга равна сумме приведённых стоимостей его дуг, а она не меньше нуля. Обратно: добавим вершину, из которой во все остальные ведут дуги нулевой стоимости, и посчитаем кратчайшие расстояния d(v) от неё, например Беллманом — Фордом. Без отрицательных кругов они конечны, а для любой дуги выполнено неравенство треугольника d(v) ≤ d(u) + c(u, v). Положим π = d.
В транспортной задаче потенциалы читаются как цены. Цена тонны в источнике π(i), цена на станции π(j). У пути из i в j в остаточной сети всегда есть прямая дуга, и условие для неё: цена на станции не больше цены в источнике плюс провоз, π(j) − π(i) ≤ cij. Если по пути идёт груз, есть и обратная дуга со стоимостью −cij, и условие для неё превращает неравенство в равенство. Получается: план наилучший, если найдутся цены, при которых ни одна перевозка не дешевле разницы цен, а там, где груз идёт, разница цен равна провозу. Проверить это — один проход по 155 путям. В конце сцены это и сделано: на всех 76 путях, где идёт груз, равенство, на остальных — неравенство. Такие цены Леонид Канторович в 1939 году назвал «разрешающими множителями», позже — «объективно обусловленными оценками».
Кратчайшие пути по очереди
Отменять круги можно долго, да и найти первый план надо отдельно. Обычно поступают иначе: начинают с пустого потока, в котором отрицательных кругов нет, и добавляют поток по самому дешёвому пути от истока к стоку в остаточной сети. Оказывается, свойство «нет отрицательных кругов» при этом сохраняется, а значит, после каждого шага поток наилучший для своей величины.
Пусть у потока f нет отрицательных кругов, а π — потенциалы с неотрицательными приведёнными стоимостями. Найдём кратчайшие по приведённым стоимостям расстояния d от истока и пустим поток по кратчайшему пути до стока. Тогда с потенциалами π + d у всех дуг новой остаточной сети приведённые стоимости тоже не меньше нуля.
Рассуждаем о вершинах, достижимых из истока: в остальные поток не попадает ни сейчас, ни потом, потому что новые дуги появляются только вдоль найденного пути. Для дуги u → v старой остаточной сети d(v) ≤ d(u) + cπ(u, v), поэтому новая приведённая стоимость cπ(u, v) + d(u) − d(v) не меньше нуля. На дугах кратчайшего пути неравенство обращается в равенство, их новая приведённая стоимость — ноль. Пуская поток, мы добавляем только обратные к ним дуги, и у них приведённая стоимость тоже ноль. Остальные дуги новой сети были и в старой.
Отсюда два следствия. Раз приведённые стоимости неотрицательны, кратчайший путь можно искать Дейкстрой, хотя в сети есть отрицательные дуги, — это заметили Н. Томидзава в 1971 году и Эдмондс с Карпом в 1972-м, тем же приёмом, что в алгоритме Джонсона. И цена каждой следующей единицы не меньше предыдущей: в новой сети любой путь от истока к стоку стоит не меньше π(t) − π(s) + d(t), а это цена только что найденного пути. В задаче Толстого 89 путей, и их цена за единицу растёт от 0 километров — груз из Мурома в Касимов идёт по воде — до 2643: последние тонны всегда самые дорогие.
Обратные дуги здесь не украшение. Вот задача попроще: основной и запасной маршрут по городу без общих перекрёстков, чтобы перекрытие одного не задело второй, и вместе как можно короче. Это поток из двух единиц, где у каждого перекрёстка ёмкость 1, а стоимость улицы — её длина. Напрашивается жадный способ: кратчайший маршрут, потом кратчайший в обход его перекрёстков.
От Зелёного базара до парка 28 панфиловцев кратчайший маршрут — 496 метров, а второй в обход него — 932, вместе 1428. Поток из двух единиц находит пару за 1000 метров. Его второй путь проходит 223 метра по первому маршруту навстречу ему, и эти улицы первый маршрут отдаёт: отмены сокращаются, остаются два маршрута без общих перекрёстков. А от пожарной части СПЧ-7 до MEGA кратчайший маршрут перерезает все дороги, и второго в обход него нет вовсе, хотя пара есть — 14 663 метра. Отказаться от кратчайшего ради пары и есть то, что делает обратная дуга.
Код
Сеть хранится, как в статье о наибольшем потоке: дуги парами, пара дуги a — a ^ 1, и у обратной дуги стоимость со знаком минус. Поиск пути — Дейкстра по приведённым стоимостям, после каждого поиска расстояния прибавляются к потенциалам. Стоимости в задаче Толстого неотрицательны, поэтому начальные потенциалы — нули; если в сети есть отрицательные стоимости, их сначала считает Беллман — Форд.
Последняя строка — круг из статьи Толстого: если отдать Дзержинску Ростов, Ярославлю — Ленинград, Артёмовску — Москву, то по кругу выходит +65 километров на тонну. Перемена невыгодна, и Толстой оставил Ростов Ярославлю. Тот же ответ дают круги, как в сцене. Самый дешёвый по средней стоимости дуги круг ищет алгоритм Карпа: таблица «самый дешёвый путь ровно из k дуг, кончающийся в v» и минимум по вершинам из максимума по k. Так советуют выбирать круг Эндрю Голдберг и Роберт Тарьян: тогда число отмен не зависит от чисел в задаче.
И основной с запасным маршрутом по улицам Алматы. Каждый перекрёсток разрезан на въезд и выезд с ёмкостью 1, как аэропорты в статье об алгоритме Диница, только у улиц ещё есть длина.
От Центрального стадиона до Esentai Mall жадный способ случайно угадал: второй путь потока ничего не отменяет. На остальных парах пара потока короче жадной на 3,5–30 процентов, а у пожарной части жадный способ вообще не находит запасного маршрута.
Сколько это стоит
| Алгоритм | Время | Замечания |
|---|---|---|
| Последовательные кратчайшие пути с потенциалами | O(F · E log V) | F — сколько единиц везём; каждый путь добавляет хотя бы одну |
| Они же с масштабированием ёмкостей | O(E log U · (E + V log V)) | сначала крупными порциями, потом мельче; U — наибольшая ёмкость |
| Отмена кругов с наименьшим средним | полиномиально от V и E | Голдберг и Тарьян, 1989: число отмен не зависит от чисел |
| Сетевой симплекс | зависит от правила выбора дуги | на практике один из самых быстрых; так работает networkx |
Замер на сетях, устроенных как у Толстого: d станций и d/8 источников, каждая станция связана с тремя ближайшими источниками. Три способа: кратчайшие пути с потенциалами и Дейкстрой; кратчайшие пути без потенциалов, тогда в сети отрицательные дуги, и каждый путь ищет Беллман — Форд с очередью; и отмена кругов, найденных Беллманом — Фордом, от плана обычного потока.
Отмена кругов на 128 станциях медленнее кратчайших путей в 26 раз на Python и в 8 раз на Go и растёт круче. А Беллман — Форд с очередью здесь быстрее Дейкстры — в полтора раза на Python и в пять на Go. Это не опечатка: в такой сети почти нет кругов, вершина встаёт в очередь в среднем полтора раза за поиск, а куча Дейкстры платит логарифм за каждый шаг. Потенциалы покупают не скорость на удобной сети, а гарантию: Дейкстра тратит O(E log V) на путь на любой сети, а очередь Беллмана — Форда на неудачной сети разгоняется до O(V E).
Где легко ошибиться
- Дейкстра без потенциалов. После первого пути в остаточной сети появляются дуги отрицательной стоимости, и Дейкстра по исходным стоимостям может вернуть не кратчайший путь. Ответ тогда просто неверный, без всякой ошибки выполнения.
- Потенциалы недостижимых вершин. До вершины, которую поиск не нашёл, расстояние бесконечно, и прибавлять его к потенциалу нельзя: потенциал оставляют как есть. Это безопасно, потому что из таких вершин поток больше не пройдёт.
- Жадно, без обратных дуг. Найти самый дешёвый путь, закрыть его и искать следующий — ошибка из сцены с маршрутами. Без обратных дуг поток не умеет отказаться от сделанного выбора.
- Переполнение. Стоимость — произведение количества на цену, сложенное по всем дугам. В задаче Толстого это 3,95 миллиона в сотнях тонн на километр, но на больших сетях 32 бит не хватает.
- Не всё развезено. Если сток стал недостижим раньше, чем вывезены все запасы, задача невыполнима — нужно сравнить итоговый поток с суммой потребностей, а не молча вернуть стоимость частичного плана.
Где работает
Транспортные задачи — склады и магазины, заводы и станции, — и задачи о назначениях с ёмкостями. Венгерский алгоритм — это последовательные кратчайшие пути с потенциалами на сети из двух долей. Основной и запасной пути без общих узлов ищут в сетях связи алгоритмом Суурбалле (1974) — это тот же поток из двух единиц, устроенный так, чтобы хватило двух поисков. Расстояние между двумя распределениями — сколько «земли» нужно перевезти, чтобы одна гистограмма стала другой, — Йоси Рубнер, Карло Томази и Леонидас Гибас в 1998 году назвали Earth Mover's Distance и сравнивали так изображения по цветам. В библиотеках: min_cost_flow в networkx (сетевой симплекс), SimpleMinCostFlow в OR-Tools, несколько алгоритмов в LEMON.
История
Задачу о перевозке с наименьшей работой поставил Гаспар Монж в 1781 году в «Мемуаре о теории выемок и насыпей»: как перенести грунт из выемок в насыпи, чтобы сумма «объём × расстояние» была наименьшей. Дискретную задачу с источниками и станциями решал Толстой в 1930 году. Он, по-видимому, первым заметил, что в наилучшем плане нет отрицательных кругов, хотя и не доказал, что их отсутствия достаточно.
Леонид Канторович в 1939 году в книге «Математические методы организации и планирования производства» ввёл разрешающие множители — те самые цены, — а в 1942 году в заметке «О перемещении масс» вернулся к задаче Монжа. Фрэнк Хичкок сформулировал транспортную задачу в 1941 году, Тьяллинг Купманс изучал её в 1948-м, а Джордж Данциг в 1951 году решил её симплекс-методом. В 1975 году Канторович и Купманс получили премию по экономике памяти Нобеля за вклад в теорию оптимального распределения ресурсов.
Отмену отрицательных кругов как алгоритм описал Мортон Клейн в 1967 году. Последовательные кратчайшие пути появились у Уильяма Джуэлла (1958), Масао Ири (1960) и у Роберта Бусакера и Пола Гоуэна (1961), а потенциалы, с которыми хватает Дейкстры, — у Томидзавы (1971) и у Эдмондса и Карпа (1972). Голдберг и Тарьян в 1989 году показали, что отмена кругов с наименьшим средним делает полиномиальное число шагов, не зависящее от чисел, а Джеймс Орлин в 1988 году дал первый быстрый такой алгоритм. В 2022 году алгоритм почти линейного времени, о котором рассказывает глава курса, решил задачу наименьшей стоимости вместе с задачей о наибольшем потоке.
Задачи
В первой задаче нужно развезти груз по таблице, где среди тестов есть и таблица Толстого, а жадный план без отмен застревает. Во второй — найти основной и запасной маршрут по улицам Алматы, и кратчайший маршрут для этого не годится.
План перевозок Запасной маршрутДанные: Задача А. Н. Толстого (1930): таблица из статьи А. Схрейвера «On the history of the transportation and maximum flow problems» (2002) Дороги Алматы © участники OpenStreetMap, ODbL Пожарные части Алматы © участники OpenStreetMap, ODbL (выгрузка 17.10.2026)