Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
'''Алгоритм Форда-Фалкерсона''' — алгоритм, решающий задачу нахождения максимального [[Определение сети, потока #Определение потока | потока]] в транспортной сети.
 
'''Алгоритм Форда-Фалкерсона''' — алгоритм, решающий задачу нахождения максимального [[Определение сети, потока #Определение потока | потока]] в транспортной сети.
  

Версия 07:12, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

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

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

Идея

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение [math]0[/math]: [math] f(u,v) = 0 [/math] для всех [math] u, v [/math] из [math] V [/math]. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника [math]s[/math] к стоку [math]t[/math], вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.

Реализация

int dfs(int u, int Cmin):         // Cmin — пропускная способность в текущем подпотоке
   if u = t
       return Cmin
   visited[u] = true                  
   for v in u.children
       auto uv = edge(u, v)
       if not visited[v] and uv.f < uv.c
           int delta = dfs(v, min(Cmin, uv.c - uv.f))
           if delta > 0
               uv.f += delta
               uv.backEdge.f -= delta
               return delta
   return 0

Оценка производительности

Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено [math]O(|E|f)[/math], где [math]E[/math] — число рёбер в графе, [math]f[/math] — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за [math]O(E)[/math] и увеличивает поток как минимум на [math]1[/math].


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

Рис. 1

Рассмотрим приведённую справа сеть с источником [math]\ s[/math], стоком [math]\ t[/math], пропускными способностями рёбер [math]\ e_1[/math], [math]\ e_2[/math] и [math]\ e_3[/math] соответственно [math]\ 1[/math], [math]r=\dfrac{\sqrt{5}-1}{2}[/math] и [math]\ 1[/math] и пропускной способностью всех остальных рёбер, равной целому числу [math]M \geqslant 2[/math]. Константа [math]\ r[/math] выбрана так, что [math]\ r^2 = 1 - r[/math]. Мы используем пути из остаточного графа, приведённые в таблице, причём [math]\ p_1 = \{ s, v_4, v_3, v_2, v_1, t \}[/math], [math]\ p_2 = \{ s, v_2, v_3, v_4, t \}[/math] и [math]\ p_3 = \{ s, v_1, v_2, v_3, t \}[/math].

Шаг Найденный путь Добавленный поток Остаточные пропускные способности
[math]e_1[/math] [math]e_2[/math] [math]e_3[/math]
[math]0[/math] [math]-[/math] [math]-[/math] [math]r^0=1[/math] [math]r[/math] [math]1[/math]
[math]1[/math] [math]\{ s, v_2, v_3, t \}[/math] [math]1[/math] [math]r^0[/math] [math]r^1[/math] [math]0[/math]
[math]2[/math] [math]p_1[/math] [math]r^1[/math] [math]r^2[/math] [math]0[/math] [math]r^1[/math]
[math]3[/math] [math]p_2[/math] [math]r^1[/math] [math]r^2[/math] [math]r^1[/math] [math]0[/math]
[math]4[/math] [math]p_1[/math] [math]r^2[/math] [math]0[/math] [math]r^3[/math] [math]r^2[/math]
[math]5[/math] [math]p_3[/math] [math]r^2[/math] [math]r^2[/math] [math]r^3[/math] [math]0[/math]

Заметим, что после шага [math]1[/math], как и после шага [math]5[/math], остаточные способности рёбер [math]e_1[/math], [math]e_2[/math] и [math]e_3[/math] имеют форму [math]r^n[/math], [math]r^{n+1}[/math] и [math]0[/math], соответственно, для какого-то натурального [math]n[/math]. Это значит, что мы можем использовать увеличивающие пути [math]p_1[/math], [math]p_2[/math], [math]p_1[/math] и [math]p_3[/math] бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме. Полный поток после шага [math]5[/math] равен [math]1 + 2(r^1 + r^2)[/math]. За бесконечное время полный поток сойдётся к [math]\textstyle 1 + 2\sum\limits_{i=1}^\infty r^i = 3 + 2r[/math], тогда как максимальный поток равен [math]2M + 1[/math]. Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.

Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину

При использовании поиска в ширину алгоритму потребуется всего лишь два шага. Дана сеть (Рис. 2).

Рис. 2

Благодаря двум итерациям (Рис. 3 и Рис. 4)

Рис. 3
Рис. 4

рёбра [math]AB, AC, BD, CD[/math] насытились лишь на [math]1[/math]. Конечная сеть будет получена ещё через 1998 итераций (Рис. 5).

Рис. 5

См. также

Источники информации