В теории оптимизации , максимальные задачи потока вовлекают найти посильную поток через сеть потока , который получает максимально возможную скорость потока.
Задачу максимального потока можно рассматривать как частный случай более сложных проблем сетевого потока, таких как проблема циркуляции . Максимальное значение st-потока (т. Е. Потока от источника s к приемнику t) равно минимальной пропускной способности st-отрезка (т. Е. Отрезка s, отделяющего s от t) в сети, как указано в max-flow min- теорема сокращения .
Задача о максимальном потоке была впервые сформулирована в 1954 году Т.Е. Харрисом и Ф.С. Россом как упрощенная модель советского железнодорожного движения. [1] [2] [3]
В 1955 году Лестер Р. Форд-младший и Делберт Р. Фулкерсон создали первый известный алгоритм - алгоритм Форда – Фулкерсона . [4] [5] В своей статье 1955 года [4] Форд и Фулкерсон написали, что проблема Харриса и Росса формулируется следующим образом (см. [1] с. 5):
Рассмотрим сеть железных дорог, соединяющую два города посредством ряда промежуточных городов, где каждому звену сети присвоен номер, обозначающий его пропускную способность. Предполагая установившееся состояние, найдите максимальный поток из одного заданного города в другой.
В их книге потоков в сети , [5] в 1962 году, Ford и Фулкерсон писал:
Она была поставлена авторам весной 1955 года Т. Е. Харрисом, который вместе с генералом Ф. С. Россом (в отставке) сформулировал упрощенную модель движения железнодорожного транспорта и определил эту конкретную проблему как центральную, предложенную в модель [11].
где [11] относится к секретному отчету 1955 года « Основы метода оценки пропускной способности железнодорожной сети » Харриса и Росс [3] (см. [1] стр. 5).
За прошедшие годы были обнаружены различные улучшенные решения проблемы максимального потока, в частности алгоритм кратчайшего увеличивающегося пути Эдмондса и Карпа и независимо Диница; алгоритм блокировки потока Диница; нажимной алгоритм повторной расстановки меток из Голдберг и Tarjan ; и алгоритм двоичного блокирующего потока Голдберга и Рао. Алгоритмы Шермана [6] и Келнера, Ли, Ореккья и Сидфорда [7] [8] соответственно находят приблизительно оптимальный максимальный поток, но работают только в неориентированных графах.
В 2013 году Джеймс Б. Орлин опубликовал статью с описанием алгоритма. [9]
Сначала введем некоторые обозначения:
Определение. Емкость ребра максимального количество потоков , которые могут проходить через край. Формально это карта
Определение. Поток представляет собой карту , которая удовлетворяет следующему:
Замечание . Потоки кососимметричны: для всех
Определение. Величина потока является количеством проходящего от источника к раковине потока. Формально для потока это:
Определение. Задача максимального потока состоит в том, чтобы направить как можно больше потока из источника в сток, другими словами, найти поток с максимальным значением.
Обратите внимание, что может существовать несколько максимальных потоков, и если разрешены произвольные действительные (или даже произвольные рациональные) значения потока (а не только целые числа), существует либо ровно один максимальный поток, либо бесконечно много, поскольку существует бесконечно много линейных комбинаций базовые максимальные потоки. Другими словами, если мы отправляем единицы потока на краю в одном максимальном потоке и единицы потока на другом максимальном потоке, то для каждого мы можем отправить блоки и направить поток по оставшимся краям соответственно, чтобы получить другой максимальный поток. Если значения расхода могут быть любыми действительными или рациональными числами, то таких значений для каждой пары бесконечно много .
В следующей таблице перечислены алгоритмы решения задачи максимального расхода.
Метод | Сложность | Описание |
---|---|---|
Линейное программирование | Ограничения, заданные определением юридического потока . Смотрите линейную программу здесь. | |
Алгоритм Форда – Фулкерсона | Пока существует открытый путь через остаточный граф, отправьте минимум остаточных мощностей на пути. Алгоритм гарантированно завершится, только если все веса рациональны , и в этом случае сумма, добавляемая к потоку на каждом шаге, является, по крайней мере, наибольшим общим делителем весов. В противном случае возможно, что алгоритм не сойдется к максимальному значению. Однако, если алгоритм завершается, гарантируется нахождение максимального значения. | |
Алгоритм Эдмондса – Карпа | Специализация Форда – Фулкерсона, поиск дополнительных путей с помощью поиска в ширину . | |
Алгоритм диника | На каждом этапе алгоритмы строят многоуровневый граф с поиском в ширину на остаточном графе . Максимальный расход на многоуровневом графике можно рассчитать по времени, а максимальное количество фаз равно . В сетях с единичной мощностью алгоритм Диника завершается во времени. [ необходима цитата ] | |
Алгоритм MKM (Малхотра, Кумар, Махешвари) [10] | Модификация алгоритма Динича с другим подходом к построению блокирующих потоков. Обратитесь к исходной бумаге . | |
Алгоритм Динича с динамическими деревьями | Структура данных динамических деревьев ускоряет вычисление максимального потока в многоуровневом графе до . | |
Общий алгоритм push – relabel [11] | Алгоритм push relabel поддерживает предварительный поток, то есть функцию потока с возможностью избытка в вершинах. Алгоритм выполняется, пока есть вершина с положительным избытком, т.е. активная вершина в графе. Операция проталкивания увеличивает поток на остаточном ребре, а функция высоты на вершинах управляет тем, через какие остаточные ребра могут протекать потоки. Функция высоты изменяется операцией переназначения. Правильное определение этих операций гарантирует, что результирующая функция потока будет максимальным потоком. | |
Алгоритм push – reabel с правилом выбора вершин FIFO [11] | Вариант алгоритма push-relabel, который всегда выбирает самую последнюю активную вершину и выполняет операции push, пока избыток положительный и есть допустимые остаточные ребра из этой вершины. | |
Алгоритм push – relabel с правилом выбора вершин на максимальном расстоянии [12] | Вариант алгоритма push-reabel, который всегда выбирает самую удаленную вершину из или (т.е. вершину самой высокой метки), но в остальном действует как алгоритм FIFO. | |
Алгоритм push-relabel с динамическими деревьями [11] | Алгоритм строит деревья ограниченного размера на остаточном графе относительно функции высоты. Эти деревья обеспечивают многоуровневые операции проталкивания, т. Е. Проталкивание по всей траектории насыщения вместо одного края. | |
Алгоритм KRT (King, Rao, Tarjan) [13] | ||
Алгоритм двоичного блокирующего потока [14] | Значение U соответствует максимальной пропускной способности сети. | |
Алгоритм Джеймса Б. Орлина + KRT (Кинг, Рао, Тарджан) [9] | Алгоритм Орлина решает максимальный поток за время, пока KRT решает его за . | |
Алгоритм Катурии-Лю-Сидфорда [15] | Методы внутренней точки и усиление ребер с использованием нормальных потоков. Основан на более раннем алгоритме Мадри, который обеспечивает время выполнения . [16] | |
Алгоритм BLNPSSSW / BLLSSSW [17] [18] | Методы внутренней точки и динамическое поддержание электрических потоков с детандерными разложениями. | |
Алгоритм Гао-Лю-Пэна [19] | Алгоритм Гао, Лю и Пэна вращается вокруг динамического поддержания дополнительных электрических потоков в основе алгоритма, основанного на методе внутренней точки из [Mądry JACM '16]. Это влечет за собой разработку структур данных, которые в ограниченных настройках возвращают края с большой электрической энергией в график, претерпевающий обновления сопротивления. |
Дополнительные алгоритмы см. В Goldberg & Tarjan (1988) .
Теорема об интегральном потоке утверждает, что
Утверждение состоит не только в том, что значение потока является целым числом, что непосредственно следует из теоремы о максимальном потоке и минимальном разрезе , но и в том, что поток на каждом ребре является целым. Это имеет решающее значение для многих комбинаторных приложений (см. Ниже), где поток через ребро может кодировать, должен ли элемент, соответствующий этому ребру, быть включен в искомый набор или нет.
Учитывая сеть с набором источников и набором приемников, а не только один источник и один приемник, мы должны найти максимальный поток через . Мы можем преобразовать несколько источников проблемы мульти-раковину в максимальные проблемы потока путем добавления консолидированного источника при подключении к каждой вершине в и сводной раковине , соединенный каждой вершина (также известной как supersource и supersink ) с бесконечной мощностью на каждое ребре ( См. Рис. 4.1.1.).
Учитывая двудольный граф , мы должны найти соответствие максимальной мощности в , то есть соответствие , которое содержит наибольшее возможное число ребер. Эту задачу можно преобразовать в задачу о максимальном потоке, построив сеть , где
Тогда значение максимального потока в равно размеру максимального сопоставления в , и сопоставление максимальной мощности можно найти, взяв те ребра, которые имеют поток в интегральном максимальном потоке.
Для ориентированного ациклического графа мы должны найти минимальное количество вершинно-непересекающихся путей, чтобы покрыть каждую вершину в . Мы можем построить двудольный граф из , где
Тогда можно показать, что соответствие размера есть тогда и только тогда, когда оно имеет непересекающееся вершинно-непересекающееся покрытие пути, содержащее ребра и пути, где - количество вершин в . Следовательно, проблема может быть решена путем поиска соответствия максимальной мощности в .
Интуитивно понятно, что если две вершины совпадают , то ребро содержится в . Очевидно, что количество ребер в нем равно . Чтобы увидеть, что это вершина-непересекающаяся, рассмотрим следующее:
Таким образом, ни одна вершина не имеет двух входящих или двух исходящих ребер , что означает, что все пути в вершине не пересекаются.
Чтобы показать, что крышка имеет размер , мы начинаем с пустой крышки и постепенно наращиваем ее. Чтобы добавить вершину к покрытию, мы можем либо добавить ее к существующему пути, либо создать новый путь нулевой длины, начинающийся с этой вершины. Первый случай применим, если любой путь в укрытии начинается в , или и заканчивается в . Последний случай применим всегда. В первом случае общее количество ребер в крышке увеличивается на 1, а количество путей остается прежним; в последнем случае количество путей увеличивается, а количество ребер остается прежним. Теперь ясно, что после покрытия всех вершин сумма количества путей и ребер в покрытии равна. Следовательно, если количество ребер в покрытии равно , то количество путей равно .
Пусть будет сеть. Предположим, что в каждом узле есть пропускная способность в дополнение к пропускной способности ребра, то есть такое отображение , что поток должен удовлетворять не только ограничению пропускной способности и сохранению потоков, но также ограничению пропускной способности вершин.
Другими словами, количество потока, проходящего через вершину, не может превышать ее пропускную способность. Чтобы найти максимальный поток , мы можем преобразовать задачу в задачу максимального потока в исходном смысле, расширив ее . Сначала каждый заменяется на и , где соединяется ребрами, входящими внутрь и соединяется с ребрами, выходящими из , затем присваивает емкость ребру, соединяющему и (см. Рис. 4.4.1). В этой расширенной сети снято ограничение на пропускную способность вершин, и поэтому проблему можно рассматривать как исходную задачу о максимальном потоке.
Для ориентированного графа и двух вершин и необходимо найти максимальное количество путей от до . У этой проблемы есть несколько вариантов:
1. Пути не должны пересекаться по ребрам. Эту проблему можно преобразовать в задачу максимального потока, построив сеть из , с и, являясь источником и приемником соответственно, и присвоив каждому ребру пропускную способность . В этой сети максимальный поток равен тогда и только тогда, когда существуют пути, не пересекающиеся по ребрам.
2. Пути должны быть независимыми, т. Е. Вершинно-непересекающимися (кроме и ). Мы можем построить сеть из вершинных мощностей, где мощность всех вершин и все ребра . Тогда значение максимального потока равно максимальному количеству независимых путей от до .
3. В дополнение к тому, что пути не пересекаются по ребрам и / или не пересекаются по вершинам, они также имеют ограничение на длину: мы считаем только пути, длина которых равна точной или максимальной длине . Большинство вариантов этой задачи являются NP-полными, за исключением небольших значений . [20]
Замыкание ориентированного графа представляет собой набор вершин C , таким образом, что нет края не оставить C . Проблема закрытия - это задача нахождения замыкания с максимальным или минимальным весом в ориентированном графе, взвешенном по вершинам. Ее можно решить за полиномиальное время, используя задачу сведения к максимальному потоку.
В задаче на выбывание по бейсболу в лиге соревнуются n команд. На определенном этапе сезона лиги w i - это количество побед, r i - количество игр, оставшихся до игры для команды i, а r ij - количество игр, оставшихся против команды j . Команда выбывает, если у нее нет шансов закончить сезон на первом месте. Задача задачи выбывания бейсбола состоит в том, чтобы определить, какие команды выбывают в каждой точке в течение сезона. Шварц [21] предложил метод, который сводит эту проблему к максимальному потоку в сети. В этом методе создается сеть, чтобы определить,k исключается.
Пусть G = ( V , E ) - сеть, где s , t ∈ V - источник и сток соответственно. Один добавляет игровой узел { i , j } с i < j к V и соединяет каждый из них из s ребром с емкостью r ij, которое представляет количество игр между этими двумя командами. Мы также добавляем командный узел для каждой команды и соединяем каждый игровой узел { i , j } с двумя командными узлами i и j.чтобы обеспечить победу одного из них. На этих краях нет необходимости ограничивать величину потока. Наконец, от узла команды i к узлу приемника t делаются ребра, а емкость w k + r k - w i устанавливается так, чтобы не дать команде i выиграть больше, чем w k + r k . Пусть S будет набором всех команд, участвующих в лиге, и пусть . В этом методе утверждается, что команда k не удаляется тогда и только тогда, когда в сети существует значение потока размера r ( S - { k }).G . В указанной статье доказано, что это значение расхода является максимальным значением расхода от s до t .
В авиационной отрасли серьезной проблемой является планирование работы летных экипажей. Задачу планирования авиалиний можно рассматривать как приложение расширенного максимального сетевого потока. Входными данными этой задачи является набор рейсов F, который содержит информацию о том, где и когда каждый рейс отправляется и прибывает. В одной из версий расписания авиакомпаний цель состоит в том, чтобы составить реальное расписание с максимум k экипажами.
Для решения этой проблемы используется разновидность задачи циркуляции, называемая ограниченной циркуляцией, которая является обобщением задач сетевого потока с добавленным ограничением нижней границы для граничных потоков.
Пусть G = ( V , E ) - сеть с s , t ∈ V в качестве узлов источника и приемника. Для источника и пункта назначения каждого рейса i к V добавляются два узла : узел s i как источник и узел d i как узел назначения рейса i . Также к E добавляются следующие ребра :
В упомянутом методе заявлено и доказано, что нахождение значения потока k в G между s и t равносильно нахождению допустимого расписания для полетного набора F с не более чем k экипажами. [22]
Другой вариант расписания авиакомпаний - поиск минимально необходимого экипажа для выполнения всех полетов. Для того , чтобы найти ответ на этот вопрос, двудольный граф G» = ( ∪ B , E ) создаются , где каждый полет имеет копию в множестве A и множество B . Если же плоскость может выполнять полет J после полета я , я ∈ A соединен с J ∈ B . Паросочетание в G ' индуцирует расписание для Fи, очевидно, максимальное двустороннее соответствие на этом графике дает расписание авиалиний с минимальным количеством экипажей. [22] Как упоминается в разделе «Приложение» этой статьи, двустороннее сопоставление с максимальной мощностью является приложением задачи о максимальном потоке.
Есть несколько фабрик, которые производят товары, и несколько деревень, куда товары нужно доставить. Они связаны сетью дорог, каждая из которых имеет пропускную способность c для максимального количества товаров, которые могут проходить по ней. Проблема в том, чтобы определить, есть ли тираж, удовлетворяющий спрос. Эта проблема может быть преобразована в задачу о максимальном расходе.
Пусть G = ( V , E ) - эта новая сеть. Существует тираж, удовлетворяющий спрос тогда и только тогда, когда:
Если существует циркуляция, рассмотрение решения с максимальным потоком даст ответ о том, сколько товаров должно быть отправлено по определенной дороге для удовлетворения потребностей.
Задачу можно расширить, добавив нижнюю границу потока на некоторых ребрах. [23]
В своей книге Клейнберг и Тардос представляют алгоритм сегментации изображения. [25] Они представляют алгоритм для поиска фона и переднего плана в изображении. Точнее, алгоритм принимает растровое изображение в качестве входных данных, смоделированных следующим образом: a i ≥ 0 - вероятность того, что пиксель i принадлежит переднему плану, b i ≥ 0 - вероятность того, что пиксель i принадлежит фону, а p ij - это вероятность того, что пиксель i принадлежит фону. штраф, если два соседних пикселя i и j размещаются один на переднем плане, а другой - на заднем. Цель - найти раздел ( A , B) набора пикселей, которые максимизируют следующее количество
Действительно, для пикселей в A (рассматривается как на переднем плане), мы получаем в I ; для всех пикселей в B (рассматриваемых как фон) мы получаем b i . На границе между двумя соседними пикселями i и j мы теряем p ij . Это эквивалентно минимизации количества
потому что
Теперь мы строим сеть, узлами которой являются пиксель, а также источник и приемник, см. Рисунок справа. Подключаем источник к пикселю i ребром веса a i . Подключаем пиксель i к раковине ребром веса b i . Мы соединяем пиксель i с пикселем j с весом p ij . Теперь осталось вычислить минимальный разрез в этой сети (или, что эквивалентно, максимальный поток). На последнем рисунке показан минимальный срез.
1. В задаче потока с минимальными затратами каждое ребро ( u , v) также имеет коэффициент затрат a uv в дополнение к своей пропускной способности. Если поток через край является F уф , то общая стоимость ув е ув . Требуется найти поток заданного размера d с наименьшими затратами. В большинстве вариантов коэффициенты затрат могут быть как положительными, так и отрицательными. Для этой задачи существуют различные полиномиальные алгоритмы.
2. Проблема максимального потока может быть дополнена дизъюнктивными ограничениями : отрицательное дизъюнктивное ограничение говорит, что определенная пара ребер не может одновременно иметь ненулевой поток; а положительное дизъюнктивное ограничение говорит , что в некоторых парах ребер, по меньшей мере , один должна иметь ненулевой поток. При отрицательных ограничениях задача становится NP-трудной даже для простых сетей. При положительных ограничениях проблема является полиномиальной, если разрешены дробные потоки, но может быть сильно NP-трудной, когда потоки должны быть целыми. [26]