Максимальный поток

Матч на Центральном стадионе Алматы кончился, и тысячи машин одновременно хотят уехать подальше. Сколько потоков машин могут разъезжаться разом, если по каждой полосе идёт один поток? Ответ не в том, сколько улиц у стадиона, а в том, сколько их на самом узком кольце вокруг него — и это кольцо надо ещё найти. Ниже настоящие улицы из OpenStreetMap с числом полос в каждую сторону, и по ним алгоритм ищет путь за путём, пока путей не останется. Двигайте радиусы, перенесите исток касанием карты, разрешите всем улицам двустороннее движение.

От перекрёстков в 400 метрах от стадиона до всего, что дальше трёх километров, ведут 20 полос. Не больше: красные улицы в конце — двенадцать кусков улиц, в которых вместе ровно 20 полос, и все они заняты целиком. Перекройте их, и до кольца не доехать. Узкое место лежит совсем рядом: куски разреза начинаются в 276–754 метрах от стадиона, а не на дальних магистралях. Если бы все улицы были двусторонними, полос было бы 27: одностороннее движение отнимает у разъезда семь.

Переключите поиск. В ширину алгоритм нашёл 17 путей, и каждый следующий не короче предыдущего: от 17 до 30 кусков улиц. В глубину путей 20, и они петляют по всему центру — от 40 до 302 кусков. Ответ тот же: 20 полос. Почему так и почему длина путей вообще имеет значение, разберём ниже.

Идея

Сеть — ориентированный граф с двумя выделенными вершинами, истоком s и стоком t, и с пропускной способностью c(u, v) ≥ 0 у каждого ребра. Поток назначает каждому ребру число от нуля до его пропускной способности, и в каждую вершину, кроме s и t, втекает столько же, сколько вытекает. Величина потока — сколько вытекает из истока. У нас вершины — перекрёстки, ребро — направление движения по куску улицы, пропускная способность — число полос в эту сторону. Много истоков и стоков сводятся к одному: добавим общий исток с рёбрами бесконечной ёмкости ко всем перекрёсткам у стадиона и общий сток — от всех дальних.

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

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

Третий путь идёт из C в A по пунктиру — против потока, пущенного первым путём. Ни одна машина не едет назад: меняется план. Одна полоса машин из A, которая шла через C, теперь идёт через D, а освободившееся место на C → T занимают машины из B. Без этой отмены поток остановился бы на трёх.

Почему поток наибольший

Разделим вершины на две части: S, где лежит исток, и T, где сток. Это разрез, а его ёмкость c(S, T) — сумма пропускных способностей рёбер, ведущих из S в T. Любой поток не больше ёмкости любого разреза: всё, что вытекло из истока, должно хоть раз пересечь границу из S в T, и чистый поток через границу равен величине потока. Значит, если найдены поток и разрез одной величины, оба оптимальны.

Доказательство даёт и рецепт узкого места: когда пути кончились, обойдите остаточную сеть из истока, как в сцене, — синие улицы, — и рёбра на границе будут минимальным разрезом. И ещё одно следствие: если все пропускные способности целые, каждый путь добавляет целое число, и найдётся наибольший поток с целым числом на каждом ребре. На этом держатся все сведения к потоку с ответом «да или нет»: пары, маршруты, назначения.

Подробнее с историей и учебной картой — в главе курса «Потоки и пары».

Код

Сеть хранится списком дуг, и каждая дуга добавляется парой: прямая с номером 2i и обратная с номером 2i + 1 и нулевой ёмкостью. Тогда пара дуги a — это a ^ 1, и «пустить x по дуге» — две строки: уменьшить cap[a] и увеличить cap[a ^ 1]. Остаточная сеть и есть массив cap, отдельной структуры не нужно. Поиск пути — в ширину или в глубину, остальное общее.

Из двенадцати кусков разреза пять — улицы второго класса (secondary в OpenStreetMap), на них 12 полос из 20; ещё пять — дворовые, на них 6. Со стороны стадиона остаётся 50 перекрёстков. Почему поиску в глубину понадобилось меньше просмотров дуг, хотя пути у него длиннее: он ныряет и доходит до далёкого кольца стока быстро, а поиск в ширину перед каждым путём обходит весь круг радиусом до этого кольца. На маленьких целых числах простой Форд — Фалкерсон работает неплохо. Плохо становится, когда числа растут.

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

Каждый увеличивающий путь находится за O(E) и прибавляет к потоку хотя бы единицу, если пропускные способности целые. Значит, Форд — Фалкерсон с любым способом поиска делает не больше |f| путей, где |f| — величина наибольшего потока, и работает за O(E · |f|). Оценка зависит от чисел на рёбрах, а не только от размера сети. Сколько путей понадобится на решётке 15 × 15, если пропускные способности случайны в пределах от единицы до всё больших чисел:

up to 1      flow     15: BFS   15 paths, DFS   15 paths
up to 100    flow    496: BFS   86 paths, DFS  301 paths
up to 10000  flow  40976: BFS  111 paths, DFS 1121 paths

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

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

При пропускных способностях до десяти тысяч поиск в глубину медленнее в 22 раза и на Python, и на Go, и чем крупнее числа, тем больше путей нужно поиску в глубину, пока их число не перестаёт расти. На практике и Эдмондса — Карпа обгоняют: алгоритм Диница строит слоистую сеть и за один проход пускает много путей одной длины, а алгоритмы проталкивания предпотока вообще не ищут путей целиком. В теории в 2022 году нашли алгоритм почти линейного времени — об этом в главе курса.

Что ещё оказывается потоком

Много истоков и стоков. Общий исток и общий сток с рёбрами бесконечной ёмкости — так устроена сцена: исток — все перекрёстки у стадиона, сток — все за кольцом.

Пропускная способность у вершин. Если предел у перекрёстка, а не у улицы, вершину v разрезают на вход v_in и выход v_out с ребром между ними нужной ёмкости: все входящие рёбра ведут во вход, все исходящие — из выхода.

Непересекающиеся пути. Дайте каждому ребру ёмкость 1, и наибольший поток — это наибольшее число путей из s в t без общих рёбер: по целочисленности поток раскладывается на пути по единице. Разрез же — наименьшее число рёбер, без которых s отрезан от t. Их равенство — теорема Менгера 1927 года, старше всех алгоритмов статьи. Разрезав вершины, как выше, получим пути без общих вершин — это вторая задача статьи.

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

Разрезы как ответ. Иногда нужен не поток, а сам разрез: разделить пиксели снимка на объект и фон, выбрать выгодный набор проектов, когда одни проекты требуют других. Это статья о минимальном разрезе.

Где модель врёт

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

Данные тоже упрощены. У трети кусков улиц число полос указано в OpenStreetMap прямо, у главных улиц — почти всегда, у дворовых — почти никогда. Где числа нет, мы считали по классу улицы: две полосы в каждую сторону на магистралях и одна на остальных.

История

Задачу поставили военные: в 1955 году Тед Харрис и Фрэнк Росс в секретном докладе корпорации RAND оценивали пропускную способность железных дорог и искали их узкое место — эта история рассказана в главе курса. Харрис рассказал о задаче коллегам, Лестеру Форду и Делберту Фалкерсону, и в 1956 году вышла их статья «Maximal flow through a network» с теоремой о потоке и разрезе. В том же году теорему независимо доказали Питер Элайес, Амиэль Файнстейн и Клод Шеннон. Выбор кратчайших путей и оценку O(V E²) опубликовали Джек Эдмондс и Ричард Карп в 1972 году; двумя годами раньше Ефим Диниц напечатал алгоритм, который пускает по слоистой сети сразу много кратчайших путей.

Задачи

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