Это 15-й день моего участия в августовском испытании обновлений. Узнайте подробности события:Испытание августовского обновления
Задача о максимальном потоке относится к категории теории графов.В задаче о максимальном потоке мы изучаем графНаправленный и привилегированный граф, то есть ребра имеют направления и веса. В графе много узлов.
- Начальный узел обозначается s (источник).
- Конечная точка представлена t (цель)
Задачу о максимальном расходе можно понять визуально, то есть мы хотим транспортировать воду из начальной точки s в конечную точку t для объяснения задачи о максимальном расходе Ребра (трубы), соединенные промежуточными узлами, имеют определенную пропускную способность Вот такое понятие вместимости (мощности). Под пропускной способностью или пропускной способностью трубопровода можно понимать количество воды, которое может пройти по трубопроводу в секунду, на рисунке тем меньше кубометров воды можно транспортировать от начальной точки до конечной. Это задача максимального потока. Итак, для задачи о максимальном потоке какая информация нам нужна и что эта информация означает?
Во-первых, нам нужно иметь ориентированный взвешенный граф, состоящий из узлов и ребер между узлами, а затем нам нужно поддерживать начальную и конечную точки наибольшего потока в графе.Что нам нужно сделать, так это найти некоторые разумные пути чтобы сделать единицу времени от начальной точки до конечной точки максимальным потоком. То есть при действующей сети максимальное количество воды, которое можно транспортировать от источника до пункта назначения.
Как показано на рисунке выше, вес ребра можно понимать как пропускную способность водопроводной трубы.Здесь вес ребра, соединяющего v1 и v3, равен 2, что означает, что пропускная способность водопроводной трубы равна 2. Прежде чем мы начнем, нам нужно ввести понятие остатка, который представляет собой пропускную способность, которую несет труба, пропускная способность за вычетом фактического расхода, то есть, какая часть пропускной способности водопроводной трубы все еще бесполезна. В начале, когда нет трафика, проходящего через сеть, когда на картинке нет трафика, холостая мощность равна пропускной способности водопровода. Следующие две картинки перечислены для всеобщего обозрения. это исходное изображение, а справа показана свободная водопроводная труба.
Как показано на рисунке ниже, следующая серия операций представляет операции над остаточным графом. Сначала находим простой путь из начальной точки в конечную.Так называемый простой путь означает, что в пути не может быть петель. Есть много способов найти простой путь, среди них мы сначала рассматриваем граф как невзвешенный граф, а затем находим кратчайший путь как простой путь графа. Далее мы нашли путь, а затем путь с эталоном цветовой линии такой, как показано на рисунке ниже (слева). Этот путь проходит от начальной точки s через v2, v4 до конечной точки. Веса на пути равны 2, 2 и 3 соответственно, из которых минимальный вес равен 2. Из-за эффекта короткой доски весь этот путь может пройти не более 2 частей воды. Мы пропускаем через него 2 части воды. путь, поэтому путь становится свободным. будет вычтено на 2 и станет 0, 0 и 1, как показано на правом рисунке ниже. Теперь мы обновили карту количества простоев один раз.
Наблюдая, я обнаружил, что два ребра между s до v2 и v2 до v4 имеют свободное пространство 0, что означает, что они уже содержат воду и не позволяют воде вытекать из этих двух труб, поэтому мы можем удалить эти два ребра из свободного графа, как показано слева. На этом заканчивается первый раунд цикла. Следующим шагом является повторение вышеописанных шагов и поиск в простом графе другого простого пути s v1 v3 t. Поскольку минимальный вес на этом пути равен 2, все свободные количества вычитаются на 2, и оказывается, что вычитаются величины бездействия от v1 до v3. После 2 оно становится 0, затем ребра между ними удаляются, так что граф бездействия становится нижним правым графом после второй итерации.
Продолжайте входить в следующий цикл.Я не буду объяснять в этот раз.Я думаю каждый сможет понять как получаются эти картинки глядя на картинки.Если вы до сих пор не понимаете как появились эти две картинки,то можете оставить мне сообщение в область комментариев.
Теперь мы получаем нижнюю правую картинку после просмотра последнего цикла, на этой картинке мы не можем найти путь, по которому вода течет от начала до конца. Когда путь от начальной точки до конечной точки не может быть найден в графе бездействия, мы можем выйти из цикла.
Теперь у нас есть цикл для получения графика бездействия (остаточного графа), мы можем рассчитать поток в сети, когда поток равен пропускной способности минус объем простоя Поток = пропускная способность - остаток
По этой формуле мы можем вычислить цифру слева, где 2/2 означает расход/производительность, то есть пропускная способность равна 2 трубам, проходящим через 2 потока, а количество простоя равно 0.
Из приведенного выше рисунка слева нетрудно увидеть, что общий сетевой трафик равен 5, поэтому как рассчитать сетевой трафик здесь равен 5, трафик, проходящий из начальной точки 3, равен 2 + 3, поэтому максимальный сетевой трафик равен 5. .
Но тогда давайте посмотрим на проблему этого алгоритма. Проблема этого алгоритма в том, что нет гарантии, что решение является максимальным потоком. Для объяснения этой проблемы используется пример. Мы все еще анализируем приведенный выше пример. Способность алгоритма находить максимальный поток зависит от порядка поиска путей. Если он найден за один цикл, то найден путь s v1 v4 t, и обновленный график свободного количества получается с использованием уже представленного алгоритма, как показано на нижнем правом рисунке.
Затем продолжаем получать на нем граф простоя, находим другой путь s v1 v3 t и затем продолжаем обновлять граф количества простоя, чтобы получить нижний правый график, а затем снова наблюдаем граф простоя, и отправляем этот граф простоя ( нижний правый график) уже нельзя найти из Пути от начальной точки до конечной точки и полученного из нее графика простоя.
Что ж, мы вычитаем емкость исходного изображения, чтобы получить количество простоя в простое изображение, чтобы получить изображение слева.Рассчитывая исходящий поток из начальной точки, обнаруживается, что максимальный поток изображения, полученный через выше расчет равен 4, что меньше предыдущего на 5, то результат явно не максимальный расход на этой картинке.
На приведенном выше примере мы объясним, что с помощью этого простого метода сетевой поток может не быть максимальным сетевым потоком из-за различного порядка выбора путей. Это не максимальный поток.На самом деле блок-схема на рисунке выше носит название блокирующего потока.Почему он называется блокирующим потоком?На самом деле это означает,что при таком потоке сеть больше не может течь из отправной точки до конечной точки. Конечно, максимальный поток также является блокирующим потоком, очевидно, что при достижении максимального потока сеть не может пропустить больше трафика.
- На вход алгоритма подается взвешенный ориентированный граф, в котором необходимо указать начальную точку s и конечную точку t.
- Цель состоит в том, чтобы найти несколько путей, которые позволяют как можно большему количеству воды течь из начальной точки в конечную точку.
- Ограничения, каждое ребро имеет вес, указывающий пропускную способность водопроводной трубы, поэтому расход водопроводной трубы не может превышать пропускную способность
алгоритм
- Постройте остаточный граф, начальный простой граф является исходным графом
- Затем выполните цикл, найдите простой путь, а затем найдите ребро с наименьшим весом пути, которое является узким местом пути, затем вычтите узкое место из всех весов ребер на пути, затем обновите граф простоя и затем обратите внимание, что количество бездействия в графе бездействия равно 0. Удалено из графа бездействия.