Показать меню

Алгоритм Форда — Фалкерсона

08.12.2020
102

Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f ( u , v ) = 0 {displaystyle f(u,v)=0} для всех u , v ∈ V {displaystyle u,vin V} . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Алгоритм

Неформальное описание

  • Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
  • В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
  • Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
  • На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью c min {displaystyle c_{min }} .
  • Для каждого ребра на найденном пути увеличиваем поток на c min {displaystyle c_{min }} , а в противоположном ему — уменьшаем на c min {displaystyle c_{min }} .
  • Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
  • Возвращаемся на шаг 2.
  • Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению (см. пример ниже).

    Если искать не любой путь, а кратчайший, получится алгоритм Эдмондса — Карпа или алгоритм Диница. Эти алгоритмы сходятся для любых вещественных весов за время O ( | V | | E | 2 ) {displaystyle O(|V||E|^{2})} и O ( | V | 2 | E | ) {displaystyle O(|V|^{2}|E|)} соответственно.

    Формальное описание

    Дан граф G ( V , E ) {displaystyle G(V,E)} с пропускной способностью c ( u , v ) {displaystyle c(u,v)} и потоком f ( u , v ) = 0 {displaystyle f(u,v)=0} для рёбер из u в v. Необходимо найти максимальный поток из источника s в сток t. На каждом шаге алгоритма действуют те же условия, что и для всех потоков:

    •   f ( u , v ) ⩽ c ( u , v ) {displaystyle f(u,v)leqslant c(u,v)} . Поток из u {displaystyle u} в v {displaystyle v} не превосходит пропускной способности.
    •   f ( u , v ) = − f ( v , u ) {displaystyle f(u,v)=-f(v,u)} .
    •   ∑ v f ( u , v ) = 0 ⟺ f i n ( u ) = f o u t ( u ) {displaystyle sum _{v}f(u,v)=0Longleftrightarrow f_{in}(u)=f_{out}(u)} для всех узлов u {displaystyle u} , кроме s {displaystyle s} и t {displaystyle t} . Поток не изменяется при прохождении через узел.

    Остаточная сеть G f ( V , E f ) {displaystyle G_{f}(V,E_{f})} — сеть с пропускной способностью c f ( u , v ) = c ( u , v ) − f ( u , v ) {displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} и без потока.

    Вход Граф G {displaystyle G} с пропускной способностью c {displaystyle c} , источник s {displaystyle s} и сток t {displaystyle t}
    Выход Максимальный поток f {displaystyle f} из s {displaystyle s} в t {displaystyle t}

  • f ( u , v ) := 0 {displaystyle f(u,v):=0} для всех рёбер ( u , v ) {displaystyle (u,v)}
  • Пока есть путь p {displaystyle p} из s {displaystyle s} в t {displaystyle t} в G f {displaystyle G_{f}} , такой что c f ( u , v ) > 0 {displaystyle c_{f}(u,v)>0} для всех рёбер ( u , v ) ∈ p {displaystyle (u,v)in p} :
  • Найти c f ( p ) = min { c f ( u , v ) | ( u , v ) ∈ p } {displaystyle c_{f}(p)=min{c_{f}(u,v);|;(u,v)in p}}
  • Для каждого ребра ( u , v ) ∈ p {displaystyle (u,v)in p}
  • f ( u , v ) := f ( u , v ) + c f ( p ) {displaystyle f(u,v):=f(u,v)+c_{f}(p)}
  • f ( v , u ) := f ( v , u ) − c f ( p ) {displaystyle f(v,u):=f(v,u)-c_{f}(p)}
  • Путь может быть найден, например, поиском в ширину (алгоритм Эдмондса — Карпа) или поиском в глубину в G f ( V , E f ) {displaystyle G_{f}(V,E_{f})} .

    Сложность

    На каждом шаге алгоритм добавляет поток увеличивающего пути к уже имеющемуся потоку. Если пропускные способности всех рёбер — целые числа, легко доказать по индукции, что и потоки через все рёбра всегда будут целыми. Следовательно, на каждом шаге алгоритм увеличивает поток по крайней мере на единицу, следовательно, он сойдётся не более чем за O(f) шагов, где f — максимальный поток в графе. Можно выполнить каждый шаг за время O(E), где E — число рёбер в графе, тогда общее время работы алгоритма ограничено O(Ef).

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

    Пример не сходящегося алгоритма

    Рассмотрим приведённую справа сеть, с источником   s {displaystyle s} , стоком   t {displaystyle t} , пропускными способностями рёбер   e 1 {displaystyle e_{1}} =   1 {displaystyle 1} ,   e 2 {displaystyle e_{2}} = r = ( 5 − 1 ) / 2 {displaystyle r=({sqrt {5}}-1)/2} ,   e 3 {displaystyle e_{3}} =   1 {displaystyle 1} и пропускной способностью всех остальных рёбер, равной целому числу M ≥ 2 {displaystyle Mgeq 2} . Константа   r {displaystyle r} выбрана так, что   r 2 = 1 − r {displaystyle r^{2}=1-r} . Мы используем пути из остаточного графа, приведённые в таблице, причём   p 1 = { s , v 4 , v 3 , v 2 , v 1 , t } {displaystyle p_{1}={s,v_{4},v_{3},v_{2},v_{1},t}} ,   p 2 = { s , v 2 , v 3 , v 4 , t } {displaystyle p_{2}={s,v_{2},v_{3},v_{4},t}} и   p 3 = { s , v 1 , v 2 , v 3 , t } {displaystyle p_{3}={s,v_{1},v_{2},v_{3},t}} .

    Заметим, что после шага 1, как и после шага 5, остаточные способности рёбер e 1 {displaystyle e_{1}} , e 2 {displaystyle e_{2}} и e 3 {displaystyle e_{3}} имеют форму r n {displaystyle r^{n}} , r n + 1 {displaystyle r^{n+1}} и 0 {displaystyle 0} , соответственно, для какого-то натурального n {displaystyle n} . Это значит, что мы можем использовать увеличивающие пути p 1 {displaystyle p_{1}} , p 2 {displaystyle p_{2}} , p 1 {displaystyle p_{1}} и p 3 {displaystyle p_{3}} бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага 5 равен 1 + 2 ( r 1 + r 2 ) {displaystyle 1+2(r^{1}+r^{2})} . За бесконечное время полный поток сойдётся к 1 + 2 ∑ i = 1 ∞ r i = 3 + 2 r {displaystyle extstyle 1+2sum _{i=1}^{infty }r^{i}=3+2r} , тогда как максимальный поток равен 2 M + 1 {displaystyle 2M+1} . Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.

    Пример

    Следующий пример показывает первые шаги алгоритма Форда — Фалкерсона в транспортной сети с четырьмя узлами, источником A и стоком D. Этот пример показывает худший случай. При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага.

    Еще по этой теме:
    Вязкостное решение
    04:18, 06 декабрь
    Вязкостное решение
    Вязкостное решение — определённый тип слабого решения дифференциального уравнения в частных производных, а точнее вырожденного эллиптического уравнения. Определения Вырожденное эллиптическое
    Матрица Коши (линейная алгебра)
    14:45, 04 декабрь
    Матрица Коши (линейная алгебра)
    В математике матрица Коши (названа в честь Огюстена Луи Коши) — это матрица размера m × n с элементами вида a i j
    Максимальный тор
    12:52, 03 декабрь
    Максимальный тор
    Максимальный тор связной вещественной группы Ли G {displaystyle G} — связная компактная коммутативная подгруппа Ли T
    Вариационный ряд
    08:23, 03 декабрь
    Вариационный ряд
    Вариационный ряд (упорядоченная выборка) — последовательность X ( 1 ) ⩽
    APX
    08:20, 02 декабрь
    APX
    APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом
    Обратный элемент
    23:38, 01 декабрь
    Обратный элемент
    Обратный элемент — термин в общей алгебре, обобщающий понятия обратного числа (для умножения) и противоположного числа (для сложения). Определения Пусть ( M
    Комментарии:
    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent