В математической оптимизации , то алгоритм нажимных повторной расстановки меток ( в качестве альтернативы, предварительная подача нажатие алгоритма ) представляет собой алгоритм для вычисления максимума потоков в сети потока . Название «push – relabel» происходит от двух основных операций, используемых в алгоритме. На протяжении всего своего выполнения алгоритм поддерживает «предварительный поток» и постепенно преобразует его в максимальный поток, перемещая поток локально между соседними узлами с помощью операций push под руководством допустимой сети, поддерживаемой операциями переназначения . Для сравнения: алгоритм Форда – Фулкерсонавыполняет глобальные дополнения, которые направляют поток по пути от источника до приемника. [1]
Алгоритм push – relabel считается одним из наиболее эффективных алгоритмов максимального потока. Общий алгоритм имеет сильно полиномиальную временную сложность O ( V 2 E ) , которая асимптотически более эффективна, чем алгоритм Эдмондса – Карпа O ( VE 2 ) . [2] Конкретные варианты алгоритмов позволяют снизить временную сложность. Вариант, основанный на правиле выбора узла с наивысшей меткой, имеет временную сложность O ( V 2 √ E ) и обычно считается эталоном для алгоритмов максимального потока. [3] [4] Подкубическая временная сложность O ( VE log ( V 2 / E )) может быть достигнута с помощью динамических деревьев , хотя на практике это менее эффективно. [2]
Алгоритм push-relabel был расширен для вычисления потоков с минимальной стоимостью . [5] Идея меток расстояния привела к более эффективному алгоритму увеличения пути, который, в свою очередь, может быть снова включен в алгоритм push-relabel для создания варианта с еще более высокой эмпирической эффективностью. [4] [6]
История
Концепция предварительного потока была первоначально разработана Александром В. Карзановым и была опубликована в 1974 г. в Советском математическом Докладе 15. Этот алгоритм предварительного потока также использовал операцию выталкивания; однако вместо системы маркировки он использовал расстояния во вспомогательной сети, чтобы определить, куда направить поток. [2] [7]
Алгоритм push-relabel был разработан Эндрю В. Голдбергом и Робертом Тарьяном . Алгоритм был первоначально представлен в ноябре 1986 года в STOC '86: Proceedings восемнадцатого ежегодного симпозиума ACM по теории вычислений, а затем официально в октябре 1988 года в виде статьи в Journal of the ACM. В обеих документах подробно описывается общая форма алгоритма, заканчивающегося на O ( V 2 E ) вместе с последовательной реализацией O ( V 3 ), реализацией O ( VE log ( V 2 / E )) с использованием динамических деревьев и параллельной / распределенной реализацией. . [2] [8] A объяснил в [9] Голдберг-Тарджан ввел метки расстояния, включив их в параллельный алгоритм максимального потока Йоси Шилоаха и Узи Вишкина . [10]
Концепции
Определения и обозначения
Позволять:
- G = ( V , E ) - сеть с функцией пропускной способности c : V × V → ℝ ∞ ,
- F = ( G , C , ев , т ) сетевой поток , где S ∈ V и т ∈ V выбраны исходные и поглотителей вершины соответственно,
- F : V × V → ℝ обозначают предварительный поток в F ,
- x f : V → ℝ обозначает избыточную функцию по отношению к потоку f , определяемую формулой x f ( u ) = ∑ v ∈ V f ( v , u ) - ∑ v ∈ V f ( u , v ) ,
- c f : V × V → ℝ ∞ обозначает функцию остаточной пропускной способности по отношению к потоку f , определяемую формулой c f ( e ) = c ( e ) - f ( e ) ,
- E f ⊂ E - ребра, где f < c ,
а также
- G f ( V , E f ) обозначает остаточную сеть группы G относительно потока f .
Алгоритм push-relabel использует неотрицательную целочисленную допустимую функцию маркировки, которая использует метки расстояния или высоты на узлах, чтобы определить, какие дуги должны быть выбраны для операции push. Эта функция разметки обозначается 𝓁: V → ℕ . Эта функция должна удовлетворять следующим условиям, чтобы считаться действительной:
- Действующая маркировка :
- 𝓁 ( u ) ≤ 𝓁 ( v ) + 1 для всех ( u , v ) ∈ E f
- Состояние источника :
- 𝓁 ( s ) = | V |
- Консервация раковины :
- 𝓁 ( t ) = 0
В алгоритме значения меток s и t фиксированы. 𝓁 ( u ) - это нижняя граница невзвешенного расстояния от u до t в G f, если t достижимо из u . Если u был отключен от t , то 𝓁 ( u ) - | V | является нижней границей невзвешенного расстояния от u до s . В результате, если существует допустимая функция маркировки, в G f нет s - t путей, потому что ни один такой путь не может быть длиннее, чем | V | - 1 .
Дуга ( u , v ) ∈ E f называется допустимой, если 𝓁 ( u ) = 𝓁 ( v ) + 1 . Допустимая сеть G F ( V , Ē е ) состоит из множества дуг е ∈ E F , которые являются допустимыми. Допустимая сеть ациклична.
Операции
Инициализация
Алгоритм начинается с создания остаточного графа, инициализации значений предварительного потока равными нулю и выполнения набора насыщающих проталкивающих операций на остаточных дугах, выходящих из источника, ( s , v ), где v ∈ V \ { s } . Точно так же метки инициализируются таким образом, что метка в источнике представляет собой количество узлов в графе, 𝓁 ( s ) = | V | , а всем остальным узлам присваивается нулевое значение. После завершения инициализации алгоритм многократно выполняет операции push или переназначения активных узлов до тех пор, пока никакая применимая операция не может быть выполнена.
Толкать
Операция push применяется к допустимой внешней дуге ( u , v ) активного узла u в G f . Он перемещает min { x f ( u ), c f ( u , v )} единиц потока из u в v .
push (u, v): assert x f [u]> 0 и 𝓁 [u] == 𝓁 [v] + 1 Δ = min (x f [u], c [u] [v] - f [u] [v]) f [u] [v] + = Δ f [v] [u] - = Δ x f [u] - = Δ x f [v] + = Δ
Операция проталкивания, которая заставляет f ( u , v ) достичь c ( u , v ) , называется насыщающим проталкиванием, поскольку она использует всю доступную емкость остаточной дуги. В противном случае весь избыток в узле перемещается по остаточной дуге. Это называется ненасыщающим или ненасыщающим толчком .
Relabel
Операция переназначения применяется к активному узлу u без каких-либо допустимых выходных дуг в G f . Он изменяет 𝓁 ( u ) на минимальное значение, при котором создается допустимая выходная дуга. Обратите внимание, что это всегда увеличивает 𝓁 ( u ) и никогда не создает крутой дуги, которая является дугой ( u , v ) такой, что c f ( u , v )> 0 и 𝓁 ( u )> 𝓁 ( v ) + 1 .
relabel (u): утверждать x f [u]> 0 и 𝓁 [u] <= 𝓁 [v] для всех v таких, что c f [u] [v]> 0 𝓁 [u] = 1 + min (𝓁 [v] для всех v таких, что c f [u] [v]> 0)
Эффекты нажатия и повторной маркировки
После операции push или переназначения 𝓁 остается действующей функцией маркировки по отношению к f .
Для операции проталкивания на допустимой дуге ( u , v ) он может добавить дугу ( v , u ) к E f , где 𝓁 ( v ) = 𝓁 ( u ) - 1 ≤ ( u ) + 1 ; он также может удалить дугу ( u , v ) из E f , где эффективно снимает ограничение 𝓁 ( u ) ≤ 𝓁 ( v ) + 1 .
Чтобы увидеть, что операция изменения метки на узле u сохраняет действительность 𝓁 ( u ) , заметим, что это тривиально гарантируется по определению для выходных дуг u в G f . Для внутренних дуг u в G f увеличенная 𝓁 ( u ) может только менее строго удовлетворять ограничениям, но не нарушать их.
Общий алгоритм push – relabel
Общий алгоритм push – relabel используется только в качестве доказательства концепции и не содержит деталей реализации о том, как выбрать активный узел для операций push и повторной маркировки. Эта общая версия алгоритма завершится через O ( V 2 E ) .
Поскольку 𝓁 ( s ) = | V | , 𝓁 ( t ) = 0 , и путей длиннее | V | - 1 в G f , чтобы 𝓁 ( s ) удовлетворяли действительному условию маркировки, необходимо отсоединить s от t . При инициализации алгоритм выполняет это требование, создавая предварительный поток f, который насыщает все исходящие дуги s , после чего 𝓁 ( v ) = 0 тривиально выполняется для всех v ∈ V \ { s , t } . После инициализации алгоритм повторно выполняет соответствующую операцию push или переназначения до тех пор, пока такие операции не перестанут применяться, после чего предварительный поток будет преобразован в максимальный поток.
generic-push-relabel (G, c, s, t): создать предварительный поток f, который насыщает все выходящие дуги s пусть 𝓁 [s] = | V | пусть 𝓁 [v] = 0 для всех v ∈ V \ {s}, пока существует применимая операция push или переназначения do выполнить операцию
Правильность
Во время выполнения алгоритм поддерживает условие, что 𝓁 является допустимой меткой . Это можно доказать, исследуя влияние операций push и reabel на функцию label 𝓁 . Операция переназначения увеличивает значение метки на соответствующий минимум плюс один, который всегда будет удовлетворять ограничению 𝓁 ( u ) ≤ 𝓁 ( v ) + 1 . Операция push может отправить поток от u к v, если 𝓁 ( u ) = 𝓁 ( v ) + 1 . Это может добавить ( v , u ) к G f и может удалить ( u , v ) из G f . Добавление ( v , u ) к G f не повлияет на допустимую разметку, поскольку 𝓁 ( v ) = 𝓁 ( u ) - 1 . Удаление ( u , v ) из G f снимает соответствующее ограничение, поскольку допустимое свойство маркировки 𝓁 ( u ) ≤ 𝓁 ( v ) + 1 применяется только к остаточным дугам в G f . [8]
Если предпоток f и допустимая разметка 𝓁 для f существует, то в остаточном графе G f нет увеличивающего пути от s до t . Это может быть доказано противоречием, основанным на неравенствах, которые возникают в функции разметки при предположении, что дополняющий путь действительно существует. Если алгоритм завершается, все узлы в V \ { s , t } неактивны. Это означает, что все v ∈ V \ { s , t } не имеют избыточного потока, а при отсутствии превышения предварительный поток f подчиняется ограничению сохранения потока и может считаться нормальным потоком. Этот поток является максимальным потоком в соответствии с теоремой о максимальном потоке и минимальном отсечении, поскольку нет увеличивающего пути от s до t . [8]
Следовательно, алгоритм вернет максимальный поток по завершении.
Сложность времени
Чтобы ограничить временную сложность алгоритма, мы должны проанализировать количество операций push и переназначения, которые происходят в основном цикле. Количество операций смены метки, насыщения и ненасыщения анализируется отдельно.
В алгоритме операцию переназначения можно выполнить не более чем (2 | V | - 1) (| V | - 2) <2 | V | 2 раза. Это связано с тем, что значение метки 𝓁 ( u ) для любого узла u никогда не может уменьшиться, а максимальное значение метки не превышает 2 | V | - 1 для всех узлов. Это означает, что операция переназначения потенциально может быть выполнена 2 | V | - 1 раз для всех узлов V \ { s , t } (т.е. | V | - 2 ). Это приводит к ограничению O ( V 2 ) для операции переназначения.
Каждый насыщающий толчок допустимой дуге ( u , v ) удаляет дугу из G f . Для дуги с возможностью повторного введения G F для другого насыщающего толчка, v должен быть сначала перемаркированные, с последующим нажатием на дуге ( об , ¯u ) , то у должен быть перемаркированные. При этом 𝓁 ( u ) увеличивается как минимум на два. Следовательно, имеется O ( V ) толчков насыщения на ( u , v ) , и общее количество толчков насыщения не превышает 2 | V || E | . Это приводит к ограничению по времени O ( VE ) для операций насыщающей проталкивания.
Ограничить количество ненасыщающих толчков можно с помощью потенциального аргумента . Мы используем потенциальную функцию Φ = ∑ [ u ∈ V ∧ x f ( u )> 0] 𝓁 ( u ) (т.е. Φ - это сумма меток всех активных узлов). Очевидно, что изначально Φ равно 0 и остается неотрицательной на протяжении всего выполнения алгоритма. И повторная маркировка, и насыщающие толчки могут увеличивать Φ . Однако значение Φ должно быть равно 0 при завершении, поскольку в конце выполнения алгоритма не может быть никаких оставшихся активных узлов. Это означает, что во время выполнения алгоритма ненасыщающие нажатия должны компенсировать разницу между операциями переназначения и насыщения, чтобы Φ завершилась со значением 0. Операция переназначения может увеличить Φ не более чем на (2 | V). | - 1) (| V | - 2) . Насыщающий толчок на ( u , v ) активирует v, если он был неактивен до толчка, увеличивая Φ не более чем на 2 | V | - 1 . Следовательно, суммарный вклад всех насыщающих операций подталкивания в Φ не превосходит (2 | V | - 1) (2 | V || E |) . Ненасыщающий толчок ( u , v ) всегда дезактивирует u , но он также может активировать v, как в насыщающем толчке. В результате он уменьшает Φ как минимум на 𝓁 ( u ) - 𝓁 ( v ) = 1 . Поскольку изменение меток и насыщающие толчки увеличивают Φ , общее количество ненасыщающих толчков должно составлять разницу в (2 | V | - 1) (| V | - 2) + (2 | V | - 1) (2 | V || E |) ≤ 4 | V | 2 | E | . Это приводит к ограничению времени O ( V 2 E ) для ненасыщающих операций проталкивания.
В итоге алгоритм выполняет O ( V 2 ) повторных меток, O ( VE ) насыщающих толчков и O ( V 2 E ) ненасыщающих толчков . Структуры данных могут быть разработаны для выбора и выполнения соответствующей операции за время O (1) . Следовательно, временная сложность алгоритма составляет O ( V 2 E ) . [1] [8]
Пример
Ниже приведен пример выполнения общего алгоритма push-relabel, как определено выше, на следующей простой диаграмме сетевого потока.
В примере значения h и e обозначают метку 𝓁 и избыток x f , соответственно, узла во время выполнения алгоритма. Каждый остаточный граф в примере содержит только остаточные дуги с пропускной способностью больше нуля. Каждый остаточный граф может содержать несколько итераций цикла выполнения операции .
Алгоритм Операция (ы) | Остаточный график |
---|---|
Инициализируйте остаточный график, установив предварительный поток на значения 0 и инициализируя маркировку. | |
Начальный насыщающий толчок выполняется по всем дугам предварительного потока, выходящим из источника, s . | |
Узел a переименован, чтобы направить его избыточный поток к раковине t . Затем избыток в точке a перемещается в точку b, затем в точку d в двух последовательных толчках насыщения; которые до сих пор оставляет с некоторым избытком. | |
Еще раз, a меняют метку, чтобы протолкнуть его избыток вдоль последнего оставшегося положительного остатка (т. Е. Подтолкнуть избыток обратно к s ). Затем узел a удаляется из набора активных узлов. | |
Пометьте b, а затем переместите его избыток к t и c . | |
Пометьте c, а затем переместите его избыток на d . | |
Отметьте d, а затем переместите его избыток к t . | |
Это оставляет узел b в качестве единственного оставшегося активного узла, но он не может подтолкнуть свой избыточный поток к приемнику. Пометьте b, а затем протолкните его избыток к источнику s через узел a . | |
Нажмите на последний бит избыток в виде обратно к источнику, S . Нет оставшихся активных узлов. Алгоритм завершается и возвращает максимальный поток графика (как показано выше). | |
Пример (но с начальным потоком 0) можно запустить здесь в интерактивном режиме.
Практические реализации
В то время как общий алгоритм push-relabel имеет временную сложность O ( V 2 E ) , эффективные реализации достигают O ( V 3 ) или более низкой временной сложности, применяя соответствующие правила при выборе применимых операций push и reabel. Эмпирические характеристики могут быть дополнительно улучшены с помощью эвристики.
Структура данных "ток-дуга" и работа разряда
Структура данных «текущая дуга» - это механизм для посещения внутренних и внешних соседей узла в потоковой сети в статическом круговом порядке. Если для узла создается односвязный список соседей, структура данных может быть такой же простой, как указатель на список, который проходит по списку и перематывается к началу, когда он выходит из конца.
На основе структуры данных «ток-дуга» можно определить операцию разряда. Операция разгрузки применяется к активному узлу и многократно выталкивает поток из узла, пока он не станет неактивным, при необходимости меняя его метку, чтобы создать допустимые дуги в процессе.
разряд (u): в то время как x f [u]> 0 делать, если current-arc [u] побежал за пределы соседей [u], тогда переименовать (u) перемотка ток-дуга [u] иначе пусть (u, v) = current-arc [u], если (u, v) допустимо, то толкать (u, v) пусть current-arc [u] указывает на следующего соседа u
Правила выбора активного узла
Определение операции разряда сводит алгоритм push-relabel к многократному выбору активного узла для разряда. В зависимости от правила выбора алгоритм проявляет разную временную сложность. Для краткости мы игнорируем s и t при обращении к узлам в следующем обсуждении.
Правило выбора FIFO
Буфер FIFO нажимного алгоритм повторной расстановки меток [2] организует активные узлы в очередь. Начальные активные узлы можно вставлять в произвольном порядке. Алгоритм всегда удаляет узел в начале очереди для разгрузки. Когда неактивный узел становится активным, он добавляется в конец очереди.
Алгоритм имеет временную сложность O ( V 3 ) .
Правило выбора переназначения на передний план
Алгоритм переназначения на передний план push-переназначения [1] организует все узлы в связанный список и поддерживает инвариант, согласно которому список топологически отсортирован относительно допустимой сети. Алгоритм просматривает список спереди назад и выполняет операцию разгрузки на текущем узле, если он активен. Если узел помечается заново, он перемещается в начало списка, и сканирование запускается заново с начала.
Алгоритм также имеет временную сложность O ( V 3 ) .
Правило выбора наивысшей метки
Алгоритм push-relabel с наивысшей меткой [11] организует все узлы в сегменты, индексированные по их меткам. Алгоритм всегда выбирает активный узел с самой большой меткой для разгрузки.
Алгоритм имеет временную сложность O ( V 2 √ E ) . Если вместо этого используется правило выбора с наименьшей меткой, временная сложность становится O ( V 2 E ) . [3]
Методы реализации
Хотя в описании общего алгоритма push – relabel выше, ( u ) устанавливается равным нулю для каждого узла u, кроме s и t в начале, предпочтительнее выполнять обратный поиск в ширину от t для вычисления точного этикетки. [2]
Алгоритм обычно делится на две фазы. На первом этапе вычисляется максимальный предварительный поток, выгружая только активные узлы, метки которых меньше n . Вторая фаза преобразует максимальный предварительный поток в максимальный поток, возвращая избыточный поток, который не может достигнуть от t до s . Можно показать, что вторая фаза имеет временную сложность O ( VE ) независимо от порядка операций push и переназначения, и поэтому в ней преобладает первая фаза. В качестве альтернативы это может быть реализовано с использованием декомпозиции потока. [9]
Эвристика имеет решающее значение для улучшения эмпирической производительности алгоритма. [12] Две часто используемые эвристики - это эвристика пробелов и эвристика глобального переназначения. [2] [13] Эвристика пробелов обнаруживает пробелы в функции разметки. Если есть метка 0 <𝓁 ' <| V | для которых нет узла у таких , что 𝓁 ( у ) = 𝓁 'то любой узел U с 𝓁 ' <𝓁 ( у ) <| V | был отключен от t и может быть немедленно изменен на (| V | + 1) . Глобальная эвристика перемаркировки периодически выполняет обратный поиск в ширину от t в G f для вычисления точных меток узлов. Обе эвристики пропускают бесполезные операции перемаркировки, которые являются узким местом алгоритма и способствуют неэффективности динамических деревьев. [4]
Примеры реализации
#include #include #define NODES 6 #define MIN (X, Y) ((X) <(Y)? (X): (Y)) #define INFINITE 10000000void push ( const int * const * C , int ** F , int * превышение , int u , int v ) { int send = MIN ( превышение [ u ], C [ u ] [ v ] - F [ u ] [ v ]); F [ u ] [ v ] + = отправить ; F [ v ] [ u ] - = отправить ; избыток [ u ] - = отправить ; избыток [ v ] + = отправить ; }void relabel ( const int * const * C , const int * const * F , int * height , int u ) { int v ; int min_height = БЕСКОНЕЧНО ; for ( v = 0 ; v < NODES ; v ++ ) { if ( C [ u ] [ v ] - F [ u ] [ v ] > 0 ) { min_height = MIN ( min_height , height [ v ]) »; высота [ u ] = min_height + 1 ; } } };пустая разрядка ( const int * const * C , int ** F , int * превышение , int * высота , int * замечено , int u ) { while ( Excess [ u ] > 0 ) { if ( seen [ u ] < УЗЛЫ ) { int v = видел [ u ]; если (( C [ u ] [ v ] - F [ u ] [ v ] > 0 ) && ( высота [ u ] > height [ v ])) { push ( C , F , избыток , u , v ); } else { видел [ u ] + = 1 ; } } else { relabel ( C , F , высота , u ); видел [ u ] = 0 ; } } }void moveToFront ( int i , int * A ) { int temp = A [ я ]; int n ; для ( n = i ; n > 0 ; n - ) { A [ n ] = A [ n -1 ]; } A [ 0 ] = temp ; }int pushRelabel ( const int * const * C , int ** F , int источник , int приемник ) { int * избыток , * высота , * список , * видно , i , p ; избыток = ( int * ) calloc ( NODES , sizeof ( int )); высота = ( int * ) calloc ( УЗЛЫ , sizeof ( int )); замечено = ( int * ) calloc ( NODES , sizeof ( int )); список = ( int * ) calloc (( УЗЛЫ -2 ), sizeof ( int )); for ( i = 0 , p = 0 ; i < NODES ; i ++ ) { if (( i ! = источник ) && ( i ! = сток )) { list [ p ] = i ; p ++ ; } } высота [ источник ] = УЗЛЫ ; избыток [ источник ] = БЕСКОНЕЧНО ; for ( i = 0 ; i < NODES ; i ++ ) push ( C , F , избыток , источник , i ); р = 0 ; в то время как ( p < УЗЛЫ - 2 ) { int u = list [ p ]; int old_height = высота [ u ]; разряд ( C , F , превышение , высота , видно , u ); если ( высота [ u ] > old_height ) { moveToFront ( p , список ); р = 0 ; } else { p + = 1 ; } } int maxflow = 0 ; для ( я = 0 ; я < УЗЛЫ ; я ++ ) maxflow + = F [ источник ] [ я ]; бесплатно ( список ); бесплатно ( просмотрено ); свободный ( высота ); бесплатно ( франшиза ); return maxflow ; }void printMatrix ( const int * const * M ) { int я , j ; for ( i = 0 ; i < NODES ; i ++ ) { for ( j = 0 ; j < NODES ; j ++ ) printf ( "% d \ t " , M [ i ] [ j ]); printf ( " \ п " ); } }int main ( void ) { int ** поток , ** мощности , я ; flow = ( int ** ) calloc ( УЗЛЫ , sizeof ( int * )); capacity = ( int ** ) calloc ( NODES , sizeof ( int * )); для ( я = 0 ; я < УЗЛЫ ; я ++ ) { поток [ я ] = ( int * ) calloc ( NODES , sizeof ( int )); capacity [ i ] = ( int * ) calloc ( NODES , sizeof ( int )); } // Пример графического потенциала [ 0 ] [ 1 ] = 2 ; вместимость [ 0 ] [ 2 ] = 9 ; вместимость [ 1 ] [ 2 ] = 1 ; вместимость [ 1 ] [ 3 ] = 0 ; вместимость [ 1 ] [ 4 ] = 0 ; вместимость [ 2 ] [ 4 ] = 7 ; вместимость [ 3 ] [ 5 ] = 7 ; вместимость [ 4 ] [ 5 ] = 4 ; printf ( "Емкость: \ n " ); printMatrix ( емкости ); printf ( "Максимальный расход: \ n % d \ n " , pushRelabel ( емкости , расход , 0 , 5 )); printf ( "Потоки: \ п " ); printMatrix ( поток ); возврат 0 ; }
Защиту relabel_to_front ( C , источник : INT , раковина : INT ) -> INT : п = Len ( C ) # C матрица емкости F = [[ 0 ] * п для _ в интервале ( п )] # остаточная емкость от и к v - это C [u] [v] - F [u] [v] height = [ 0 ] * n # высота превышения узла = [ 0 ] * n # поток в узел минус поток от узла замечен = [ 0 ] * n # соседей, замеченных с момента последней перемаркировки # узла "queue" nodelist = [ i for i в диапазоне ( n ), если i ! = источник и i ! = сток ] def push ( u , v ): send = min ( превышение [ u ], C [ u ] [ v ] - F [ u ] [ v ]) F [ u ] [ v ] + = отправить F [ v ] [ u ] - = отправить лишнее [ u ] - = отправить лишнее [ v ] + = отправить def relabel ( u ): # Найти наименьшую новую высоту, делающую возможным толчок, # если такой толчок вообще возможен. min_height = ∞ для v в xrange ( n ): если C [ u ] [ v ] - F [ u ] [ v ] > 0 : min_height = min ( min_height , height [ v ]) height [ u ] = min_height + 1 def разрядка ( u ): в то время как превышение [ u ] > 0 : если видно [ u ] < n : # проверить следующего соседа v = видно [ u ], если C [ u ] [ v ] - F [ u ] [ v ] > 0 и height [ u ] > height [ v ]: push ( u , v ) else : seen [ u ] + = 1 else : # мы проверили всех соседей. необходимо изменить метку relabel ( u ) visible [ u ] = 0 height [ source ] = n # самый длинный путь от источника до приемника меньше n long превышение [ источник ] = ∞ # отправить как можно больше потока соседям источника для v в диапазоне ( n ): push ( source , v ) р = 0 , а р < LEN ( нодлиста ): U = нодлиста [ р ] old_height = высота [ U ] разряда ( U ) , если высота [ U ] > old_height : нодлиста . insert ( 0 , nodelist . pop ( p )) # перейти к началу списка p = 0 # начать с начала списка else : p + = 1 сумма возврата ( F [ источник ])
Рекомендации
- ^ a b c Кормен, TH ; Лейзерсон, CE ; Ривест, Р.Л . ; Стейн, К. (2001). «§26 Максимальный поток». Введение в алгоритмы (2-е изд.). MIT Press. стр. 643 -698. ISBN 978-0262032933.
- ^ Б с д е е г Гольдберг, А.В.; Tarjan, RE (1986). «Новый подход к проблеме максимального потока». Материалы восемнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '86 . п. 136. DOI : 10.1145 / 12130.12144 . ISBN 978-0897911931.
- ^ а б Ахуджа, Равиндра К .; Кодиалам, Мурали; Мишра, Аджай К .; Орлин, Джеймс Б. (1997). «Вычислительные исследования алгоритмов максимального потока». Европейский журнал операционных исследований . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . DOI : 10.1016 / S0377-2217 (96) 00269-X .
- ^ а б в Гольдберг, Эндрю В. (2008). «Частичный алгоритм дополнения – перемаркировки для задачи о максимальном потоке». Алгоритмы - ESA 2008 . Конспект лекций по информатике. 5193 . С. 466–477. CiteSeerX 10.1.1.150.5103 . DOI : 10.1007 / 978-3-540-87744-8_39 . ISBN 978-3-540-87743-1.
- ^ Гольдберг, Эндрю V (1997). «Эффективная реализация масштабируемого алгоритма потока минимальной стоимости». Журнал алгоритмов . 22 : 1–29. DOI : 10.1006 / jagm.1995.0805 .
- ^ Ахуджа, Равиндра К .; Орлин, Джеймс Б. (1991). «Направленные на расстояние алгоритмы увеличения траектории для задач максимального потока и параметрического максимального потока». Логистика военно-морских исследований . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . DOI : 10.1002 / 1520-6750 (199106) 38: 3 <413 :: АИД-NAV3220380310> 3.0.CO; 2-J .
- ^ Гольдберг, Эндрю В .; Тарджан, Роберт Э. (2014). «Эффективные алгоритмы максимального потока». Коммуникации ACM . 57 (8): 82. DOI : 10,1145 / 2628036 .
- ^ а б в г Гольдберг, Эндрю В .; Тарджан, Роберт Э. (1988). «Новый подход к проблеме максимального расхода». Журнал ACM . 35 (4): 921. DOI : 10.1145 / 48014.61051 .
- ^ а б Ахуджа, РК; Magnanti, TL; Орлин, Дж. Б. (1993). Сетевые потоки: теория, алгоритмы и приложения (1-е изд.). Прентис Холл. ISBN 978-0136175490.
- ^ Шилоах, Йосси; Вишкин, Узи (1982). «Параллельный алгоритм максимального потока O (n2log n)». Журнал алгоритмов . 3 (2): 128–146. DOI : 10.1016 / 0196-6774 (82) 90013-X .
- ^ Cheriyan, J .; Махешвари, С. Н. (1988). «Анализ алгоритмов проталкивания предпотока для максимального сетевого потока». Основы программных технологий и теоретической информатики . Конспект лекций по информатике. 338 . п. 30. DOI : 10.1007 / 3-540-50517-2_69 . ISBN 978-3-540-50517-4.
- ^ Черкасский, Борис В .; Гольдберг, Эндрю В. (1995). «О реализации метода push-relabel для задачи максимального потока». Целочисленное программирование и комбинаторная оптимизация . Конспект лекций по информатике. 920 . п. 157. CiteSeerX 10.1.1.150.3609 . DOI : 10.1007 / 3-540-59408-6_49 . ISBN 978-3-540-59408-6.
- ^ Derigs, U .; Мейер, В. (1989). «Реализация алгоритма максимального потока Голдберга? Вычислительное исследование». ZOR Zeitschrift für Методы исследования операций и модели исследования операций . 33 (6): 383. DOI : 10.1007 / BF01415937 .