Реферат алгоритм форда фалкерсона

Обновлено: 07.07.2024

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

алгоритм форд фалкерсон граф

Пояснительная записка к курсовой работе: с., рис., табл., разделов, приложения.

АЛГОРИТМ, ГРАФ, РЕБРО, ВЕРШИНА, МАКСИМАЛЬНЫЙ ПОТОК, ПАРАЛЛЕЛЬНЫЙ, ПСЕВДОКОД, БЛОКСХЕМА, РЕАЛИЗАЦИЯ

Объект исследования: алгоритм Форда-Фалкерсона

Цель работы: закрепление знаний и умений, полученных в процессе теоретического обучения.

Метод работы: закрепление теоретических знаний с помощью разработки программы, реализующий данный алгоритм. Введение Объектом исследования курсовой работы стала реализация алгоритма Форда-Фалкерсона.

Целями работы являлись:

) ознакомление с алгоритмом Форда-Фалкерсона, его историей;

2) реализация алгоритма, для построения нахождения максимального потока сети;

) анализ трудоёмкости алгоритма;

В теории графов транспортная сеть - ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность и поток. Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из источника в сток. Транспортная сеть может быть использована для моделирования, например, дорожного трафика. Целочисленная транспортная сеть - транспортная сеть, все пропускные способности ребер которой - целые числа.

Поток - функция со следующими свойствами для любых вершин:

) Ограничение пропускной способности;

2) Поток не может превысить пропускную способность;

3) Поток из вершины в другую должен быть противоположным в другом направлении;

4) Сохранение потока. для всех , кроме источника и стока.

Граф можно задавать несколькими путями, однако самый просто способ задания - задание графа матрицей смежности. Тем не менее, этот способ подходит исключительно для таких сетей, которые имеют начальную пропускную способностью равную длине ребра.

Алгоритм широко применяется в сфере перевозок, для того чтобы найти оптимальные маршруты перевозки грузов. Также широкое применение он находит в компьютерных технологиях, коммуникационных сетях, электрических сетях.

Суть распараллеливания алгоритма заключается в уменьшении времени работы с большими объемами входных данных. Стоит заметить, что сложность и трудоемкость алгоритма напрямую зависит от способа реализации. Пример описанных в проекте, работает при помощи алгоритма обхода графа в ширину. Этот алгоритм нужен для того, чтобы искать пути в заданном графе из источника в сток.

1. Графы.1 Основные характеристики графов

Граф G - это математический объект, состоящий из множества вершин X = и множества ребер

Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.

При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.

Постановка задачи

Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокав сток.

Исходный граф

Как работает сам алгоритм?

Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:

Отправлять определенное количество потока из текущей вершины в соседние.

Возвращать определенное количество потока из соседних вершин в текущую.

В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.

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

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

Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.

А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.

Возвращаемся обратно к нахождению пути в остаточной сети после модификации.

Разбор конкретного примера

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

Допустим наш алгоритм нашел следующий путь из вершинывнашей остаточной сети, которая на момент начала, совпадает с исходным графом.

Сколько потока можем провести по этому пути.
- Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:

Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.

Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .

Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:

Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:

На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:

Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

На 4-ой итерации находим следующий путь в остаточной сети:

Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

Итоговая остаточная сеть

На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.

Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!

Маршрутом или цепью в неориентированном графе G называется такая последовательность (конечная или бесконечная) ребер a1, a2,…, an,…, что каждые соседние два ребра ai и ai+1имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a1, a2,…, an) имеется первое ребро a1и последнее ребро an. Вершина x1, инцидентная ребру a1, но не инцидентная… Читать ещё >

Алгоритм Форда-Фалкерсона ( реферат , курсовая , диплом , контрольная )

Курсовой проект на тему Алгоритм Форда-Фалкерсона

Реферат алгоритм форд фалкерсон граф Пояснительная записка к курсовой работе: с., рис., табл., разделов, приложения.

АЛГОРИТМ, ГРАФ, РЕБРО, ВЕРШИНА, МАКСИМАЛЬНЫЙ ПОТОК, ПАРАЛЛЕЛЬНЫЙ, ПСЕВДОКОД, БЛОКСХЕМА, РЕАЛИЗАЦИЯ Объект исследования: алгоритм Форда-Фалкерсона Цель работы: закрепление знаний и умений, полученных в процессе теоретического обучения.

Метод работы: закрепление теоретических знаний с помощью разработки программы, реализующий данный алгоритм.

Введение

Объектом исследования курсовой работы стала реализация алгоритма Форда-Фалкерсона.

Целями работы являлись:

1) ознакомление с алгоритмом Форда-Фалкерсона, его историей;

2) реализация алгоритма, для построения нахождения максимального потока сети;

3) анализ трудоёмкости алгоритма;

4) тестирование алгоритма.

В теории графов транспортная сеть — ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность и поток. Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из источника в сток. Транспортная сеть может быть использована для моделирования, например, дорожного трафика. Целочисленная транспортная сеть — транспортная сеть, все пропускные способности ребер которой — целые числа.

Поток — функция со следующими свойствами для любых вершин:

1) Ограничение пропускной способности;

2) Поток не может превысить пропускную способность;

3) Поток из вершины в другую должен быть противоположным в другом направлении;

4) Сохранение потока. для всех, кроме источника и стока.

Граф можно задавать несколькими путями, однако самый просто способ задания — задание графа матрицей смежности. Тем не менее, этот способ подходит исключительно для таких сетей, которые имеют начальную пропускную способностью равную длине ребра.

1. Графы

1.1 Основные характеристики графов

Граф G — это математический объект, состоящий из множества вершин X = 1, x₂,…, x_n> и множества ребер A=1, a₂,…, a_m>. Таким образом, граф полностью определяется совокупностью множеств X, A и обозначается G (X, A).

Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным. Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины.

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым. Граф G (X, A) — полный, если для любой пары вершин x_iи x_j существует ребро (x_i, x_j).

1.2 Пути и маршруты

Маршрутом или цепью в неориентированном графе G называется такая последовательность (конечная или бесконечная) ребер a₁, a₂,…, a_n,…, что каждые соседние два ребра a_i и a_i+₁имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a₁, a₂,…, a_n) имеется первое ребро a₁и последнее ребро a_n. Вершина x₁, инцидентная ребру a₁, но не инцидентная ребру a₂, называется началом маршрута, а вершина x_n, инцидентная ребру a_n, но не инцидентная ребру a_n-₁, называется концом маршрута.

Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут.

Замкнутый маршрут называется циклом. Маршрут (цикл), в котором все ребра различны, называется простым маршрутом или простой цепью (циклом). Маршрут (цикл), в котором все вершины, (кроме первой и последней), различны, называется элементарным маршрутом или элементарной цепью (циклом).

Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длиной пути.

Путь называется контуром, если его начальная вершина совпадает с конечной вершиной.

Путь (контур), в котором все дуги различны, называется простым. Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным.

Иногда дугам графа сопоставляются числа называемые весом, или длиной дуги. Тогда граф называется графом со взвешенными дугами. Иногда веса приписываются вершинам графа, и тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины.

2. Алгоритм Форда-Фалкерсона

2.1 Краткое описание алгоритма

Идея алгоритма заключается в следующем. Выбираем такой путь от источника с к стоку, чтобы для каждого ребра остаточная пропускная способность была строго больше нуля. При этом ребра на данном пути могут проходиться как в прямом, так и в обратном направлении. Выбираем минимальное значение среди остаточных пропускных способностей ребер данного пути. Увеличиваем поток на каждом из ребер данного пути на выбранное минимальное значение. Далее ищем следующий аналогичный путь.

Работа алгоритма продолжается до тех пор, пока удается находить данные пути.

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

ѕ Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью;

ѕ В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся;

ѕ Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток;

ѕ На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью ;

ѕ Для каждого ребра на найденном пути увеличиваем поток на, а в противоположном ему — уменьшаем на ;

ѕ Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его;

ѕ Возвращаемся на шаг 2.

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

Более формально, мы имеем ориентированный граф G = (V; E), со множеством вершин V и множеством ребер E. Во множестве V выделены две вершины: s — источник и t — сток. При этом, у вершины s есть только ходящие ребра, у вершины t есть только входящие ребра.

Если ребро имеет максимальную пропускную способность x и потокy, то остаточной пропускной способностью ребра называется число xy. Смысл остаточной пропускной способности заключается в том, на сколько еще можно увеличить поток на данном ребре.

Следующим этапом выполнения программы является нахождение маршрутов в графе. Поиск маршрутов реализуется с помощью алгоритма обхода графа в ширину. На рисунке 2 представлена блок-схема алгоритма обхода графа в ширину.

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

Рисунок 1 — Общая схема Рисунок 2 — Блок-схема алгоритма поиска в ширину

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

2.2 Анализ сложности алгоритма

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

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

2.3 Псевдокод

Ford_Fulkerson (G, s, t)

1 for каждого ребра (u, v) є E[G]

4 while существует путь p из s в t в остаточной сети G_f

5 do сf (р) «— min f(u, v): (u, v) принадлежит р>

6 for каждого ребра (u, v) in p

Рисунок 4 — Псевдокод алгоритма Форда-Фалкерсона

3. Распараллеленный вариант алгоритма

3.1 Библиотека omp. h

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

Так как потоки выполняют свои операции параллельно, то заканчивать свою работу будут в разное время, поэтому данный вариант распараллеливания будет бесполезен при использовании на задачах класса P = NP.

3.2 Краткое описание распараллеливания алгоритма

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

При распараллеливании используется библиотека omp. h, использующая инструменты OpenMP технологии. Алгоритм делится на несколько потоков, и на каждом из потоков выполняется своя часть программы. Параллелизм реализуется за счет написания прагм в соответствующих фрагментах кода. На рисунке 5 представлен фрагмент кода, с использованием нижеописанных прагм. Полный листинг представлен в приложении Б.

Основной целью распараллеливания был анализ ускорения работы алгоритма. На практике, ускорение заметно только на очень больших наборах данных, но совсем незначительное. Ожидаемое ускорение, вычисленное по формуле Амдаля, при 25% операций выполненных параллельно на 2 процессорах составляет 300% от последовательного выполнения, однако на практике такого ускорения достигнуто не было, в виду целого ряда факторов, влияющих на быстроту выполнения операций.

Рисунок 5 — Фрагмент распараллеленного кода программы

Заключение

алгоритм форд фалкерсон граф

В процессе создания данного проекта была рассмотрена теория графов в общем, изучены понятия путей и маршрутов. Разработана программа, реализующая алгоритм Форда-Фалкерсона в MicrosoftVisualStudio 2010. Алгоритм может найти свое применение в программах для транспортных и коммуникационных сетей, таких как коммутация информационного пакета в Internet, где вершины — роутеры, а ребра это связи между роутерами. Таким образом, чем короче будет путь, тем быстрее пакет достигнет пункта назначения и меньше будут информационные потери.

Список использованных источников

1. ГОСТ 7 .32−2001. Отчёт о научно-исследовательской работе. Структура и правила оформления [Текст]. — Взамен ГОСТ 7 .32−91 ;введ. 2001;07−01. — Минск: Межгос. совет по стандартизации, метрологии и сертификации; М.: Изд-во стандартов, 2001. — 16 с. — (Система стандартов по информации, библиотечному и издательскому делу).

2. ГОСТ 7 .1−2003. Библиографическая запись. Библиографическое описание. Общие требования и правила составления [Текст]. — Взамен ГОСТ 7 .1−84, ГОСТ 7 .16−79, ГОСТ 7 .18−79, ГОСТ 7 .34−81, ГОСТ 7 .40−82 ;введ. 2004;07−01. — М.: Изд-во стандартов, 2004. — 116 с. — (Система стандартов по информации, библиотечному и издательскому делу).

3. Канева, Ольга Николаевна. Дискретная математика [Текст]: учеб. пособие / О. Н. Канева , 2009. — 87 с.

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

Содержание

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение [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).

Читайте также: