История создания алгоритма Форда-Фалкерсона, краткое описание его алгоритма, особенности работы, анализ сложности. Создание распараллеленного варианта алгоритма и его краткое описание. Основные характеристики теории графов, специфика, пути и маршруты.
В теории графов транспортная сеть - ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность и поток. (Разрезом в сети называется разбиение множества ее вершин на два непересекающихся класса, таких что источник и сток лежат в разных классах. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины. Маршрутом или цепью в неориентированном графе G называется такая последовательность (конечная или бесконечная) ребер a1, a2,...,an,…, что каждые соседние два ребра ai и ai 1имеют общую инцидентную вершину. Вершина x1, инцидентная ребру a1, но не инцидентная ребру a2, называется началом маршрута, а вершина xn, инцидентная ребру an, но не инцидентная ребру an-1, называется концом маршрута.Разработана программа, реализующая алгоритм Форда-Фалкерсона в MICROSOFTVISUALSTUDIO 2010.Алгоритм может найти свое применение в программах для транспортных и коммуникационных сетей, таких как коммутация информационного пакета в Internet, где вершины - роутеры, а ребра это связи между роутерами.#include"ff_alg.
Введение
Объектом исследования курсовой работы стала реализация алгоритма Форда-Фалкерсона.
Целями работы являлись: 1) ознакомление с алгоритмом Форда-Фалкерсона, его историей;
2) реализация алгоритма, для построения нахождения максимального потока сети;
3) анализ трудоемкости алгоритма;
4) тестирование алгоритма.
В теории графов транспортная сеть - ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность и поток. Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из источника в сток. Транспортная сеть может быть использована для моделирования, например, дорожного трафика. Целочисленная транспортная сеть - транспортная сеть, все пропускные способности ребер которой - целые числа.
Поток - функция со следующими свойствами для любых вершин: 1) Ограничение пропускной способности;
2) Поток не может превысить пропускную способность;
3) Поток из вершины в другую должен быть противоположным в другом направлении;
4) Сохранение потока. для всех , кроме источника и стока.
Первый отчет «Максимальный поток в сети» датируется 19 ноября 1954 года. Авторы отчета - Форд и Фалкерсон, доказали теорему о максимальном потоке и минимальном разрезе для неориентированных графов: значение максимального потока в сети равно минимальной пропускной способности разреза. (Разрезом в сети называется разбиение множества ее вершин на два непересекающихся класса, таких что источник и сток лежат в разных классах. Пропускной способностью разреза называется сумма пропускных способностей ребер, концы которых лежат в разных классах.) В 1955 году в работе Робахера было упомянуто, что впервые эту теорему доказал Фалкерсон.
Граф можно задавать несколькими путями, однако самый просто способ задания - задание графа матрицей смежности. Тем не менее, этот способ подходит исключительно для таких сетей, которые имеют начальную пропускную способностью равную длине ребра.
Алгоритм широко применяется в сфере перевозок, для того чтобы найти оптимальные маршруты перевозки грузов. Также широкое применение он находит в компьютерных технологиях, коммуникационных сетях, электрических сетях.
Суть распараллеливания алгоритма заключается в уменьшении времени работы с большими объемами входных данных. Стоит заметить, что сложность и трудоемкость алгоритма напрямую зависит от способа реализации. Пример описанных в проекте, работает при помощи алгоритма обхода графа в ширину. Этот алгоритм нужен для того, чтобы искать пути в заданном графе из источника в сток.
1. Графы
Граф G - это математический объект, состоящий из множества вершин X = {x1,x2,...,xn} и множества ребер A={a1, a2,..., am}. Таким образом, граф полностью определяется совокупностью множеств X, A и обозначается G(X, A).
Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины.
Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым. Граф G (X, A)- полный, если для любой пары вершин хіи xj существует ребро (xi, xj).
1.2 Пути и маршруты
Маршрутом или цепью в неориентированном графе G называется такая последовательность (конечная или бесконечная) ребер a1, a2,...,an,…, что каждые соседние два ребра ai и ai 1имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a1,a2,...,an) имеется первое ребро а1и последнее ребро an. Вершина x1, инцидентная ребру a1, но не инцидентная ребру a2, называется началом маршрута, а вершина xn, инцидентная ребру an, но не инцидентная ребру an-1, называется концом маршрута.
Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут.
Замкнутый маршрут называется циклом. Маршрут (цикл), в котором все ребра различны, называется простым маршрутом или простой цепью (циклом). Маршрут (цикл), в котором все вершины, (кроме первой и последней), различны, называется элементарным маршрутом или элементарной цепью (циклом).
Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длиной пути.
Путь называется контуром, если его начальная вершина совпадает с конечной вершиной.
Путь (контур), в котором все дуги различны, называется простым. Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным.
Иногда дугам графа сопоставляются числа называемые весом, или длиной дуги. Тогда граф называется графом со взвешенными дугами. Иногда веса приписываются вершинам графа, и тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины.
2. Алгоритм Форда-Фалкерсона
2.1 Краткое описание алгоритма
Идея алгоритма заключается в следующем. Выбираем такой путь от источника с к стоку, чтобы для каждого ребра остаточная пропускная способность была строго больше нуля. При этом ребра на данном пути могут проходиться как в прямом, так и в обратном направлении. Выбираем минимальное значение среди остаточных пропускных способностей ребер данного пути. Увеличиваем поток на каждом из ребер данного пути на выбранное минимальное значение. Далее ищем следующий аналогичный путь.
Работа алгоритма продолжается до тех пор, пока удается находить данные пути.
Сразу отметим, что данный алгоритм относится к классу недетерминированных, т.е. каждый следующий шаг алгоритма определен неоднозначно. И время работы (количество шагов) алгоритма зависит от того, как будут выбираться шаги.
Неформальное описание алгоритма: ? Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью;
? В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся;
? Пускаем через найденный путь (он называется увеличивающим путем или увеличивающей цепью) максимально возможный поток;
? На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью ;
? Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему - уменьшаем на ;
? Модифицируем остаточную сеть. Для всех ребер на найденном пути, а также для противоположных им ребер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его;
? Возвращаемся на шаг 2.
Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению. На рисунке 1 представлена общая схема работы программы.
Более формально, мы имеем ориентированный граф G = (V; E), со множеством вершин V и множеством ребер E. Во множестве V выделены две вершины: s - источник и t - сток. При этом, у вершины s есть только ходящие ребра, у вершины t есть только входящие ребра.
Если ребро имеет максимальную пропускную способность x и потоку, то остаточной пропускной способностью ребра называется число 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]
2 do f[u,v] «-0
3 f[v,u] «- 0
4 while существует путь p из s в t в остаточной сети Gf
5 do cf(р) «- min {cf(u, v) : (u, v) принадлежит р}
6 for каждого ребра (u, v) in p
7 do f[u,v] «- f[u] cf(p)
8 f[v,u] «- -f[u,v]
Рисунок 4 - Псевдокод алгоритма Форда-Фалкерсона
3. Распараллеленный вариант алгоритма
3.1 Библиотека omp.h
Разработчики OPENMP хотели предоставить простой способ создания потоков в приложениях, не требуя от программиста знаний о создании, синхронизации и уничтожении потоков, а также необходимости определения, сколько потоков следует создать. Для этого разработчики OPENMP создали независимый от платформы набор прагм, директив, вызовов функций и переменных среды, которые явным образом указывают компилятору, как и где именно следует вставить потоки в приложение. Большинство циклов можно распараллелить, вставив всего одну прагму непосредственно перед циклом. Более того, оставив исполнение рутинных функций компилятору и OPENMP, вы можете больше времени уделить определению того, какие циклы следует распараллелить, и как наилучшим образом изменить структуру алгоритмов для достижения максимальной производительности. Максимальная производительность OPENMP реализуется при использовании этого инструмента для распараллеливания "горячих точек", - наиболее трудоемких циклов в приложении.
Написание параллельного варианта сводится к написанию прагм. Прагмы - это директивы препроцессора, игнорируемые компиляторами, которые не поддерживают данную технологию. То есть программа, написанная с применением данной технологии, могут быть скомпилированы как последовательные, при том среда разработки не выдаст никакой ошибки. Список директив, использованных в данной работе: 1) #pragma omp parallel - открывает новый регион для распараллеливания внутренних инструкций. Программа делится на потоки, число которых можно указать с помощью функции omp_num_threads(int n), где n - число потоков.
2) #pragma omp for - применяется для распараллеливания итерационных циклических операций. То есть, несколько итераций выполняется параллельно на нескольких процессорах.
Так как потоки выполняют свои операции параллельно, то заканчивать свою работу будут в разное время, поэтому данный вариант распараллеливания будет бесполезен при использовании на задачах класса 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 с.
4. Левин, А. Самоучитель работы на компьютере в вопросах и ответах[Текст]: учеб. пособие / А. Левин -М.: «Аквариум», 2007г. - 644с.
