Задача о максимальном потоке. Алгоритм Форда. Теорема Форда-Фалкерсона

МИНЕСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЯ ОБРАЗОВАНИЯ "БРЕСТСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ А.С. ПУШКИНА"

ЮРИДИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра математического моделирования

КУРСОВАЯ РАБОТА

на тему: Задача о максимальном потоке. Алгоритм Форда. Теорема Форда-Фалкерсона.

              Выполнил

              студент 4 курса

              специальности Бизнес-администрирование

              группы                                                                         Антонюк Ю.В.

                                                 подпись                            Ф.И.О

Руководитель                                          Якубович А.П.

                                                 подпись                             Ф.И.О

Брест 2011

СОДЕРЖАНИЕ

ВВЕДЕНИЕ              3

1 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ              4

1.1 Постановка потоковых задач              4

1.2 История развития алгоритмов решение задачи о максимальном потоке              7             

2 ТЕОРЕМА ФОРДА - ФАЛКЕРСОНА              12

3 АЛГОРИТМ ФОРДА - ФАЛКЕРСОНА              17

ЗАКЛЮЧЕНИЕ              21

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ              22

ВВЕДЕНИЕ

Задачи теории потоков в сетях являются одними из основных в исследовании операций, computer science и инженерном деле. Теория потоков имеет многочисленные приложения в реально возникающих задачах.

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

К теории потоков относятся различные задачи, которые можно классифицировать следующим образом. Задачи транспортного типа – транспортная задача, поиск пути минимальной длины, поиск циклов отрицательного веса (неоптимальных перевозок) и т. д. Задачи определения существования потока – задача о максимальном потоке и, двойственная к ней, задача поиска минимального разреза. А также задача о поиске обобщенного потока – потока с потерями и приобретениями.

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

1 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

1.1 Постановки потоковых задач

Здесь приводится классические и наиболее часто используемые варианты постановки задач теории потоков. Начнем с общей задачи теории потоков.

Пусть G=(V,E) – ориентированный граф, в котором V – множество вершин и E – множество дуг. На множестве дуг графа заданы две функции: c(i,j) – цена дуги (i,j) и u(i,j) – пропускная способность дуги (i,j). Предположим, что паре вершин однозначно соответствует дуга, если она есть. Для каждой вершины iV определим величину bi – потребность в обеспечении. Эта величина показывает, сколько вещества требуется данному стратегическому пункту или сколько вещества в этом пункте в избытке. Если bi0, то пункт i называется пунктом производства (вещество в избытке), если bi0, то пункт i называется пунктом потребления (вещество в недостатке). Если же bi=0, то речь идет о транзитном пункте. С этими обозначениями общая задача теории потоков (она же задача поиска потока минимальной стоимости в общем виде, она же – транспортная задача) запишется следующим образом:

Вектор x=(xij) называется потоком в сети G. Первое ограничение задачи (уравнения баланса) показывает, что поток, проходящий через вершину, должен оставлять (или забирать) ровно необходимое ей количество вещества. Последнее ограничение запрещает превышение пропускной способности дуг сети. Речь идет о поиске оптимального (в смысле транспортных затрат) способа доставки товара (вещества) из пунктов потребления в пункты производства. Задача не имеет решения, если не выполнено условие баланса

однако замкнуть (сбалансировать) задачу можно путем добавления фиктивной вершины, которая будет иметь потенциал, равный

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

Пусть имеются две особые вершины s,tV. Пусть Cjj означает длину дороги из пункта i в пункт j. Требуется найти кратчайший путь из s в t. Для решения задачи о поиске кратчайшего пути, положим в общей модели bs=1 и bt=-1, а для остальных вершин iV/s.t положим bi=0. Выберем uij=1 для всех дуг сети. Решением задачи поиска потока в этом случае будет является кратчайший путь из пункта s в пункт t.

Пусть мы имеем, как и в предыдущем случае две особых вершины: s, которую будем называть истоком, и t, называемую стоком. И мы хотим определить максимальное количество вещества, которое можно перемещать из истока в сток, не превышая пропускных способностей дуг сети и с тем условием, что при перемещении вещество не может накапливаться в вершинах. Для решения этой задачи положим bi=0 для всех, iV,cij=0 для всех (i,j)E и введем дополнительную дугу (t,s), для которой положим cis=-1 и uis=. Такая задача называется задачей поиска максимального потока в сети. Речь идет о том, чтобы найти способ перемещать в единицу времени как можно больше вещества из истока в сток (то же самое, что максимизировать поток, идущий обратно по дуге из t в s).

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

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

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

1.2 История развития алгоритмов решение задачи о максимальном потоке

История развития алгоритмов решения задачи о максимальном потоке

Задача поиска максимального потока в сети в общем случае решается так же, как и известная на тот момент транспортная задача. Симплексный метод специально для этой задачи был модифицирован в 1951 году Данцигом. Алгоритм не был полиномиальным, как и любой симплексный метод. Однако специальный вид задачи позволил предположить, что для ее решения можно применить более простые и быстрые алгоритмы. Первый такой алгоритм, который не похож на симплексный метод, был разработан Фордом и Фалкерсоном в 1956 году. Время работы этого алгоритма не было полиномиальным (таблица 1), однако его идея и его математическое обоснование как раз и легли в основу качественной теории потоков. В предложенном методе использовалась идея «дополняющих путей».

В 1970 году Эдмондс, Карп и, независимо от них Диниц, улучшили алгоритм Форда и Фалкерсона, доказав теорему о том, что алгоритм выполняется за полиномиальное время, если на каждом его шаге использовать увеличивающие цепочки минимальной длины.

В следующем десятилетии алгоритмы поиска максимального потока стали быстрее благодаря новым мощным технологиям. Одну из таких технологий ввел Диниц – его идея блокирующий потоков, основанная на идее кратчайших путей, позволила не только достигнуть новых временных границ, но и дала богатую почву для новых изобретений. Однако Диниц не занимался отдельно задачей поиска блокирующего потока, показав лишь, что даже самый простой метод (1970 год) значительно улучшает оценку Эдмондса и Капа. Карзанов, разрабатывая новые методы поиска блокирующих потоков, развил идею «предпотоков», которая позволила получить самый быстрый на тот момент алгоритм поиска максимального потока для плотных сетей с оценкой O(n3). Алгоритм получил название «волновой» – название, символизирующее идею движения волны (1974 год). Еще одно изобретение в области алгоритмов – масштабирование – было создано Эдмондсом, Карпом и, независимо от них, Диницем (1972 год). Идея масштабирования пропускных способностей сети, однако, требовала, чтобы сами пропускные способности были целыми числами. Оценка времени работы алгоритмов масштабирования была псевдополиномиальной.

Идея масштабирования заключается в декомпозиции задачи поиска максимального потока не подзадачи, называемые ∆-фазами. В процессе        ∆-фазы увеличение потока происходит только вдоль путей с пропускной способностью не меньшей ∆. Когда все такие пути исчерпаны, осуществляется переход на новую фазу масштабирования, путем деления ∆ на два (нацело). На последней фазе ∆=1 – выбираются любые пути, откуда следует, что в конце работы будет найден максимальный поток с точностью до 1 – это максимальная точность для сети с целыми пропускными способностями. Так как каждый раз ∆ делится на 2 нацело, требуется не более чем log2U ∆ -фаз. В 1973 году Диниц и независимо от него Габов разработали новую, другую, схему выполнения каждой отдельной фазы, не такую, которую ипользовали Эдмондс и Карп. Это позволило впервые получить оценку времени работы, в которой множитель O(nm) входит в первой степени, если опустить влияние, как правило, небольшой величины O(logU).

Таблица 1 История улучшений сложности алгоритмов поиска

максимального потока.