Алгоритм форда фалкерсона в excel
Обновлено: 03.07.2024
Алгоритм Форда-Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.
Содержание
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение [math]0[/math] : [math] f(u,v) = 0 [/math] для всех [math] u, v [/math] из [math] V [/math] . Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника [math]s[/math] к стоку [math]t[/math] , вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью обхода в глубину (dfs). Процесс повторяется, пока можно найти увеличивающий путь.
Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено [math]O(|E|f)[/math] , где [math]E[/math] — число рёбер в графе, [math]f[/math] — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за [math]O(E)[/math] и увеличивает поток как минимум на [math]1[/math] .
Рассмотрим приведённую справа сеть с источником [math]\ s[/math] , стоком [math]\ t[/math] , пропускными способностями рёбер [math]\ e_1[/math] , [math]\ e_2[/math] и [math]\ e_3[/math] соответственно [math]\ 1[/math] , [math]r=\dfrac-1>[/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^[/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_^\infty r^i = 3 + 2r[/math] , тогда как максимальный поток равен [math]2M + 1[/math] . Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.
При использовании поиска в ширину алгоритму потребуется всего лишь два шага. Дана сеть (Рис. 2).
Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.
При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.
Постановка задачи
Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокав сток.
Исходный граф
Как работает сам алгоритм?
Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:
Отправлять определенное количество потока из текущей вершины в соседние.
Возвращать определенное количество потока из соседних вершин в текущую.
В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.
Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.
Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.
Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.
А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.
Возвращаемся обратно к нахождению пути в остаточной сети после модификации.
Разбор конкретного примера
Разобьем одну итерацию проведения потока по выбранному пути на маленькие шаги, чтобы визуально стало понятно, как меняется остаточная сеть после проталкивания очередного потока.
Допустим наш алгоритм нашел следующий путь из вершинывнашей остаточной сети, которая на момент начала, совпадает с исходным графом.
Сколько потока можем провести по этому пути.
- Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:
Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.
Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .
Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:
Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:
На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:
Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
На 4-ой итерации находим следующий путь в остаточной сети:
Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
Итоговая остаточная сеть
На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.
Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!
Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.
При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.
Постановка задачи
Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокав сток.
Исходный граф
Как работает сам алгоритм?
Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:
Отправлять определенное количество потока из текущей вершины в соседние.
Возвращать определенное количество потока из соседних вершин в текущую.
В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.
Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.
Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.
Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.
А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.
Возвращаемся обратно к нахождению пути в остаточной сети после модификации.
Разбор конкретного примера
Разобьем одну итерацию проведения потока по выбранному пути на маленькие шаги, чтобы визуально стало понятно, как меняется остаточная сеть после проталкивания очередного потока.
Допустим наш алгоритм нашел следующий путь из вершинывнашей остаточной сети, которая на момент начала, совпадает с исходным графом.
Сколько потока можем провести по этому пути.
- Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:
Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.
Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .
Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:
Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:
На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:
Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
На 4-ой итерации находим следующий путь в остаточной сети:
Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
Итоговая остаточная сеть
На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.
Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!
Начнем мы с формулировки самой задачи и ее экономического смысла.
Далее коснемся основных понятий и определений теории графов, которые нам понадобятся в процессе решения.
И только после этого мы будем готовы рассмотреть алгоритм ее решения, а также пример его реализации.
Видеоурок "Задача о максимальном потоке в сети, часть 1" вы можете найти на нашем Youtube-канале "Учите компьютер вместе с нами!"
Итак, что собой представляет задача о максимальном потоке? Предположим, что через некоторую логистическую сеть пропускается поток материальных ресурсов. Например, это может быть газотранспортная система, которая соединяет между собой поставщика и потребителя.
Эта система имеет сложную разветвленную структуру и состоит из газораспределительных станций, а также газопроводов, соединяющих эти станции между собой. Каждый такой участок (дуга графа) характеризуется своей пропускной способностью.
Необходимо найти, какой максимально возможный объем газа мы можем передать от поставщика к потребителю в единицу времени.
В данном случае мы будем иметь взвешенный ориентированный граф.
Наши газораспределительные станции представляют собой вершины этого графа, которые соединяются между собой дугами.
Граф является взвешенным, так как каждая дуга имеет свой вес или пропускную способность.
А также, граф является ориентированным, так как каждая дуга имеет направление, по которому осуществляется движение материального потока.
Вершина S1, то есть наш поставщик газа, называется истоком. А вершина S2, то есть потребитель, стоком.
Предположим, что граф имеет ровно один исток и один сток. Если это условие не выполняется, тогда граф все равно следует привести к данному виду.
Важно отметить, что суммарный поток, который вышел по всем дугам из истока, всегда будет равен суммарному потоку, который вошел в сток.
Далее рассмотрим алгоритм Форда-Фалкерсона для нахождения максимального потока, который можно пропустить из вершины S1 в S2.
Итак, на первом этапе мы находим произвольный ориентированный путь из истока в сток и смотрим, какой максимальный поток можно пропустить через него.
Для этого мы оцениваем пропускные способности каждой дуги этого пути и выбираем из них наименьшее значение. Это и понятно. Если одна из дуг имеет очень низкую пропускную способность, то больше нее мы по этому пути пропустить не сможем.
На втором этапе мы уменьшаем пропускные способности дуг на величину пропущенного только что потока. Тем самым мы находим, какой поток можно еще пропустить по этим дугам.
Этапы 1 и 2 повторяются до тех пор, пока между истоком и стоком можно проложить новый ориентированный путь и пропустить по нему хоть какой-то поток.
Итак, найдем произвольный ориентированный путь, соединяющий вершины S1 и S2. Пусть это будет: S1-1-3-2-S2.
Пропускные способности дуг на этом пути равны: (10, 7, 6, 8). Минимальная пропускная способность равна 6. Это и есть тот максимальный поток, который мы можем пропустить по данному пути. обозначим его на графе, сделав соответствующие пометки над каждой дугой.
Одновременно с этим мы должны уменьшить пропускные способности этих дуг на величину пропущенного потока, как показано на рисунке.
Следующий произвольный ориентированный путь: S1-4-5-S2.
Пропускные способности дуг равны: (4, 10, 13). А минимальная пропускная способность равна 4. Обозначим на графе данный поток и уменьшим на его величину пропускные способности дуг, как показано на слайде выше.
Пропускные способности его дуг составляют: (4, 5, 2). То есть, пропускаем поток, равный 2 и отмечаем его на графе.
И в завершение, последний возможный ориентированный путь, S1-3-S2.
Здесь дуги имеют пропускные способности (2, 2). То есть, пропускаем поток, мощностью 2 и отмечаем его на графе.
Легко заметить, что проложить новый путь, с целью пропустить дополнительный поток, больше не возможно. Поэтому, алгоритм Форда-Фалкерсона заканчивает свою работу.
Давайте теперь сложим те потоки, которые мы пропустили через нашу сеть на каждом шаге и найдем максимальный возможный поток: 6+4+2+2=14. Это и есть ответ в задаче.
Интересный момент! На каждом этапе мы отыскивали произвольный путь. Так вот, конечный результат не зависит от того, какие маршруты и в какой последовательности мы строили. Величина максимального потока в любом случае получится равной 14.
Также хочу добавить, что величину максимального потока можно получить, если сложить мощности всех потоков, выходящих из вершины-истока S1: 8+2+4=14.
И она же будет равна мощности всех потоков, которые входят в вершину-сток S2: 8+2+4=14.
Итак, открытым остался вопрос, как быть, если по условию задачи у нас имеется больше чем один исток или больше чем один сток.
Комментариев нет:
Поиск по сайту
Обратите внимание
Как построить график в Excel по известным данным
Ранее у нас уже был обзорный видеоурок о том, с какими задачами вы можете столкнуться при построении графиков в Excel . И я рекомендую н.
НОВИНКИ НА КАНАЛЕ
Мы в FACEBOOK
Мы на YOUTUBE
Рубрикатор
Читайте также: