Алгоритмы - построение и анализ (1021735), страница 154
Текст из файла (страница 154)
° Базовый алгоритм Форда-Фалкерсоиа При выполнении каждой итерации метода Форда-Фалкерсона мы находим некоторый увеличивающий путь р, и поток у вдоль каждого ребра данного пути увеличивается на величину остаточной пропускной способности су (р). Приведенная далее реализация данного метода вычисляет максимальный поток в графе С = (К Е) путем обновления потока у [и,п] между каждой парой вершин и и и, соединенных ребром'. Если вершины и и и не связаны ребром ни в одном направлении, неявно предполагается, что Г" [и, и] = О. Предполагается, что значения пропускных способностей задаются вместе с графом и с(и, и) = О, если (и, н) ф Е.
Остаточная пропускная способность су (и, и) вычисляется по формуле (26.5). В коде процедуры су (р) в действительности является просто временной переменной, в которой хранится остаточная пропускная способность пути р. 'Квадратные скобки используются, когда идентификатор (в данном случае г) трактуется вак изменяемое поле, а когда зто функпня — используются круглые скобки. Часть Ч1.
Алгоритмы для работы с графами 750 РО80 Вл.кензо(С> я, т) 1 1ог (для) каждого ребра (и, и) Е Е1С] 2 По Ди, и] +- О У[о, и] О 4 и'И!е существует путь р из и в 1 в остаточной сети Су 5 я1о су(р) +- пйп (су(и, и): (и, и) принадлежит р) б 1ог (для) каждого ребра (и, и) ш р 7 Йо 7" '1и, и] - Ди, и] + су(р) 8 Л.л] --Лъ,.] Приведенный псевдокод алгоритма Рокп Рзл.кбкбом является расширением приведенного ранее псевдокода Ропп Рпькекзон Мнтноп. На рис. 26.5 показаны результаты каждой итерации при тестовом выполнении. Строки 1-3 инициализируют поток 7" значением О. В цикле зчЬПе в строках 4-8 выполняется неоднократный поиск увеличивающего пути р в Су„и поток 7" вдоль пути р увеличивается на остаточную пропускную способность су (р).
Когда увеличивающих путей больше нет, поток 7" является максимальным. Остаточная сеть на рис. 26.5а — это исходная сеть С; поток 1', показанный на рис. 26.5д, является максимальным потоком. Анализ метода Форда-Фалкерсона Время выполнения процедуры РОкп РтзькбкзОи зависит от того, как именно выполняется поиск увеличивающего пути р в строке 4. При неудачном методе поиска алгоритм может даже не завершиться: величина потока будет последовательно увеличиваться, но она не обязательно сходится к максимальному значению потоказ.
Если увеличивающий путь выбирается с использованием поиска в ширину (который мы рассматривали в разделе 22.2), алгоритм выполняется за полиномиальное время. Прежде чем доказать этот результат, получим простую границу времени выполнения для случая, когда увеличивающий пуп выбирается произвольным образом, а все значения пропускных способностей являются целыми числами. На практике задача поиска максимального потока чаще всего возникает в целочисленной постановке. Если пропускные способности — рациональные числа, можно использовать соответствующее масштабирование, которое сделает их целыми.
В таком предположении непосредственная реализация процедуры РОкп РОз кинзой имеет время работы О (е ] г" ]), где 7"* — максимальный поток, найденный данным алгоритмом. Анализ проводится следующим образом. Выполнение строк 1-3 занимает время 9 (Е). Цикл ткЬПе в строках 4-8 выполняется не бо- Метод Форда-Фалкерсона может работать бесконечно, только если значения пропускной способности ребер яаляются иррациональными числами.
Глава 26. Задача о максимальном потоке 751 1// ( и Рис. 26.5. Работа базового алгоритма Форда-Фалкерсона (послеловательные итерации цикла чгвйе). В левой части кажлого рисунка показана остаточная сеть С/ с выделенным увеличивающим путем р; в правой части показан новый поток у, который получается в результате прибавления ~р к ~ лес ~~'~ раз, поскольку величина потока за каждую итерацию увеличивается по крайней мере на одну единицу.
Работа внутри цикла зтЫ1е зависит от того, насколько эффективно организовано управление структурой данных, используемой для реализации сети С = (У, Е). Предположим, что мы поддерживаем структуру данных, соответствующую ориентированному графу С' = (К, Е"), где Е' = ((и, о): (и, о) б Е или (о, и) б Е). Часть Ч1. Алгоритмы для работы с графами 752 ф~э ъд, Ж ~'йд„ .-!п~Р„о а) б) в) Рис.
26.6. Транспортная сеть, лля которой выполнение процедуры Ровп Р~л.кнкзом мо- жет занимать время тт(Е (~'(), (,1'*) = 2000000 Алгоритм Эдмоидса-Карпа Указанный недостаток метода Форда-Фалкерсона можно преодолеть, если реализовать вычисление увеличивающего пути р в строке 4 как поиск в ширину, т.е. если в качестве увеличивающего пути выбирается кратчаймшй путь из з Ребра сети С являются также ребрами графа С', поэтому в этой структуре данных можно довольно легко хранить пропускные способности и потоки.
Для данного потока г" в С, ребра остаточной сети Сг состоят из всех ребер (и, ц) графа С', таких что с (и, о) — г" 1и, и1 ф О. Таким образом, время поиска пути в остаточной сети составляет 0 (У+ Е') = 0 (Е), если используется только поиск в глубину или поиск в ширину. Каждая итерация цикла ттп11е занимает время О (Е), так что в результате общее время выполнения процедуры Рокп Ри.кнкзглч составляет О (Е 1,г"' ~). Когда значения пропускных способностей являются целыми числами и оптимальное значение потока ~~" ~ невелико, время выполнения алгоритма ФордаФалкерсона достаточно неплохое. Но на рис. 26.6а показан пример того, что может произойти в простой транспортной сети, с большим значением ~ Г" 1 Величина максимального потока в данной сети равна 2 000 000: 1 000 000 единиц потока идет по пути з -+ и -+ 1, а другие 1 000 000 единиц идут по пути з -~ ц -+ т.
Если первым увеличивающим путем, найденным процедурой Роищ Ргл.кнкзом, является путь з и с -> 1, как показано на рис. 26.6а, поток после первой итерации имеет значение 1. Полученная остаточная сеть показана на рис. 26.66. Если в ходе выполнения второй итерации найден увеличивающий путь з — о -+ и -> т, как показано на рис. 26. 66, поток станет равным 2. На рис. 26.6в показана соответствующая остаточная сеть. Можно продолжать процедуру, выбирая увеличивающий пуп з и — + ц — 8 для итераций с нечетным номером а -~ и и г для итераций с четным номером.
В таком случае нам придется выполнить 2000000 увеличений, при этом величина потока на каждом шаге увеличивается всего на 1 единицу. Глава 26. Задача о максимальном потоке 753 в ~ в остаточной сети, где каждое ребро имеет единичную длину (вес). Такая реализация метода Форда-Фалкерсона называется алгоритмом Эдмондса-Карпа (ЫшоиЬ-Кагр а18опйип). Докажем, что время выполнения алгоритма ЭдмондсаКарпа составляет О (г' Ез). Анализ зависит от расстояний между вершинами остаточной сети Су. В следующей лемме длина кратчайшего пути из вершины и в и в остаточной сети Су, где каждое ребро имеет единичную длину, обозначена как бу (и, и). Лемма 26.8.
Если для некоторой транспортной сети С = (У, Е) с источником з и стоком т выполняется алгоритм Эдмондса-Карпа, то для всех вершин и е е Ъ' — (з, 1) длина кратчайшего пути бу (з, и) в остаточной сети Су монотонно возрастает с каждым увеличением потока. б~(з,и) = б'~(з,и) — 1. (26.7) Исходя из того, как мы выбирали и, можно утверждать, что длина пути до вер- шины и не уменьшилась, т.е. б~У(з,и) > бу(з,и).
(26.8) Мы утверждаем, что в таком случае (и, и) ф Е~. Почему7 Если (и, и) Е Е~, тогда справедливо следующее: бу (з,и) < бу (з,и)+ 1 < < бу~ (з, и) + 1 = = б~~(з,и) (согласно лемме 24.10, неравенство треугольника) (согласно неравенству (26.8)) (согласно уравнению (26.7)), что противоречит предположению б'~ (з, и) < бу (з, и). Теперь посмотрим, как может получиться, что (и, и) ф Ег, но (и, и) Е Е~? Увеличение должно привести к возрастанию потока из и в и. Алгоритм ЭдмондсаКарпа всегда увеличивает поток вдоль кратчайших путей, поэтому последним Доказательство.
Предположим, что для неюторой вершины и Е 'г' - (з, г) существует такое увеличение потока, юторое приводит к уменьшению длины кратчайшего пути из з в и, и покажем, что это предположение приведет нас к противоречию. Пусть г" — поток, который был непосредственно перед первым увеличением, приведшим к уменьшению длины некого кратчайшего пути, а Г"' — поток сразу после этого увеличения. Пусть и — вершина с минимальной длиной кратчайшего пути б~ (з, и), которая уменьшилась в результате увеличения потока, т.е. б~ (з, и) < < бу (з, и).
Пусть р = з -+ и — и — кратчайший путь от з к и в С~~, таюй что (и, и) Е Е~ и Часть Ч1 Алгоритмы для работы с графами 754 ребром кратчайшего пути из з в и в Су является ребро (и, и). Следовательно, бу(в,и) = бу (з,и) — 1 < < б~ (в,и) — 1 = = б~(в,и) — 2 (согласно неравенству (26.8)) (согласно уравнению (26.7)), что противоречит предположению б~~ (з, и) < бу (з, и), а значит, наше предположение о существовании вершины и не верно. ы Следующая теорема устанавливает верхний предел количества итераций алгоритма Эдмондов-Карпа.
Теорема 26.9. Если для некоторой транспортной сети С = (У, Е) с источником з и стоком 1 выполняется алгоритм Эдмондов-Карпа, то общее число увеличений потока, выполняемое данным алгоритмам, составляет О (У Е). бг (з, и) = бу (в, и) + 1.
После того как поток увеличен, ребро (и, и) исчезает из остаточной сети. Оно не может появиться в другом увеличивающем пути, пока не будет уменьшен поток из и в и, а это может произойти только в том случае, если на некотором увеличивающем пути встретится ребро (и, и). Если в этот момент поток в сети С составлял Г"', справедливо следующее равенство: б~~(в,и) = б'~ (з,и) + 1. Поскольку, согласно лемме 26.8, бу (в, и) < б' (в, и), получаем: б~ (з,и) = б~у (з, и) + 1 > бу (з, и) + 1 = бу (з,и) + 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
