Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм поиска максимального потока методом аугментального пути
Эффективный подход к решению задачи о максимальном потоке был разработан Л.Р. Фордом (L.R. Ford) и Д.Р. Фалкерсоном (D.R. Fulkerson) в 1962 г. Это обобщенный метод предусматривает инкрементное увеличения потоков вдоль пути от истока к стоку, который является основой для целого семейства алгоритмов. В классической литературе он известен под названием метода Форда-Фалкерсона (Ford-Fulkerson method); широкое распространение также получил более образный термин, метод аугментального пути (augmenting path method). Рассмотрим произвольный ориентированный путь (не обязательно простой) из истока в сток в st-сети. Пусть х есть минимальное значение неиспользованной пропускной способности ребер на этом пути. Мы можем повысить величину потока в сети, по меньшей мере, на величину х, увеличив поток во всех ребрах, составляющих указанный путь, на эту величину. Неоднократно повторяя это действие, мы осуществляем первую попыт- Глава 22, Потоки в сетях ку вычисления потока в сети: находим другой путь, наращиваем поток вдоль этого пути и продолжаем эту процедуру до тех пор, пока каждый из таких путей, ведущих из истока в сток, не получит, по меньшей мере, одно заполненное ребро (так что больше мы не сможем наращивать потоки подобным способом). В одних случаях такой алгоритм вычисляет максимальный поток, в других случаях это ему не удается. На рис. 22.6. показан случай, когда этому алгоритму не удается вычислить максимальный поток. Чтобы усовершенствовать рассматриваемый алгоритм таким образом, чтобы он всегда находил максимальный поток, мы рассмотрим более общий способ наращивания потока вдоль произвольного пути, ведущего из истока в сток в неориентированном графе, положенном в основу сети. Ребра такого пути относятся либо к категории прямых (forward) ребер, направления которых совпадают с направлением потока (когда мы следуем по пути из истока в сток, мы идем по ребру из его начальной вершины в его конечную вершину), либо к категории обратных (backwafd) ребер, которые направлены против потока (при общем направлении из истока в сток, мы идем вдоль ребра из его конечной вершины в его начальную вершину). Теперь мы имеем возможность нарастить поток в сети по любому пути за счет увеличения потоков в прямых ребрах и уменьшения потоков в обратных ребрах. Величина, на которую поток может быть увеличен, ограничивается минимальной неиспользованной пропускной способностью и потоком в обратных ребрах. На рис. 22.12 показан соответствующий пример. В новом потоке, по меньшей мере, одно из прямых ребер, включенных в путь, заполняется, либо одно из обратных ребер, включенных в путь, становится пустым. Описанный выше процесс служит основой классического алгоритма Форда-Фалкерсона вычисления максимального потока (алгоритм аугментального пути). Сформулируем его следующим образом: Начните выполнение алгоритма в любом месте сети. Наращивайте поток вдоль произвольного пути из истока в сток, содержащего незаполненные ребра или пустые обратные ребра, продолжая этот процедуру до тех пор, пока не останется в сети ни одного такого пути. РИСУНОК 22.12. НАРАЩИВАНИЕ ПОТОКА ВДОЛЬ ПРОИЗВОЛЬНОГО ПУТИ Представленная на рисунке последовательность диаграмм служит иллюстрацией наращивания потока в сети вдоль пути, включающего как прямые, так и обратные ребра. Отправляясь от потока, изображенного на левой диаграмме и выполняя операции слева направо, мы сначала наращиваем поток в ребре 0-2, а затем в ребре 2-3 (дополнительные потоки показаны черным цветом). Далее мы уменьшаем поток в ребре 1-3 (показан белым цветом) и отводим извлеченную часть этого потока в ребро 1-4, а затем в 4-5, в результате чего получаем поток, показанный на правой диаграмме. Часть 5. Алгоритмы на графах Как ни странно, но этот метод всегда находит максимальный поток независимо от способа выбора путей. Подобно методу отыскания дерева MST, обсуждавшегося в разделе 20.1, и методу Беллмана-Форда поиска кратчайшего пути, обсуждавшегося в разделе 21.7, это общий алгоритм, который полезен тем, что постулирует правильность всего семейства более специализированных алгоритмов. Мы свободны в выборе любого из этих методов, как бы мы не выбирали путь. Рисунок 22.13 служит иллюстрацией нескольких различных последовательностей аугментальных путей, каждый из которых позволяет найти максимальный поток в сети, предложенной в качестве примера. Далее в этом разделе мы рассмотрим несколько алгоритмов, которые вычисляют последовательности аугментальных путей; каждый из которых приводит к нахождению максимального пути. Эти алгоритмы различаются по числу аугментальных путей, которые они вычисляют, по длине вычисляемых путей, однако все они реализуют алгоритм Форда-Фалкерсона и находят максимальный поток. Чтобы показать, что любой поток, вычисленный с помощью любой реализации алгоритма Форда-Фалкерсона, и в самом деле имеет максимальную величину, мы покажем, что этот факт эквивалентен ключевому условию, известному как теорема о максимальных потоках и минимальных сечениях (maxflow-mincut theorem). Понимание этой теоремы представляет собой очень важный шаг к пониманию алгоритмов на транспортной сети. Как следует из названия, теорема зиждется на непосредственной зависимости между потока- РИСУНОК 22.13. ПОСЛЕДОВАТЕЛЬНОСТИ АУГМЕНТАЛЬНЫХ ПУТЕЙ В трех представленных на рисунке примерах мы производим наращивание потока вдоль различных последовательностей аугментальных путей до тех пор, пока станет невозможно найти новые аугментальные пути. Поток, который удается получить в каждом случае, есть максимальный поток. Классическая теорема из теории сетевых потоков утверждает, что мы получаем максимальный поток в любой сети, независимо от того, какую последовательность путей мы используем (см. свойство 22.5). Глава 22. Потоки в сетях
ми и сечениями в сетях, поэтому мы начнем с определения терминов, имеющих отношение к сечениям. Напомним, что в соответствии с определением, данным в разделе 20.1, сечение (cut) графа есть разбиение множества вершин графа на два непересекающихся подмножества, а пересекающее ребро (crossing edge) есть ребро, соединяющее вершину некоторую одного подмножества с вершиной другого подмножества. Применительно к транспортным сетям мы уточним эти определения следующим образом (см. рис. 22.14). Определение 22.3. st-сечение есть сечение, которое помещает вершину s в одно из своих множества, а вершину t — в другое множество. Каждое пересекающее ребро, соответствующее st- сечению, есть либо s/-pe6po, ведущее из вершины, которая принадлежит множеству, содержащему вершину s, в вершину, входящую во множество, содержащую вершину t, либо ts-ребро, которое ведет в обратном направлении. Иногда мы называем множество пересекающих ребер разделяющим множеством (cut set). Пропускная способность st -сечения в транспортной сети есть сумма пропускных способностей ребер этого st-сечения, а поток через st -сечение есть разность между суммой потоков в этих st-pe6pax и суммой потоков в ts-ребрах этого сечения. Удаление разделяющего множества приводит к делению связного графа на две связных компоненты, при этом отсутствуют пути, соединяющие какую-либо РИСУНОК 22.14. ТЕРМИНОЛОГИЯ, ИСПОЛЬЗУЕМАЯ ПРИ ОПИСАНИИ st-СЕЧЕНИЯ В рассматриваемой st-cemu имеется один исток s и один сток t. st-сечение есть разбиение вершин на множество, содержащее вершину s (белые кружки), и множество, содержащее вершину t (черные кружки). Ребра, связывающие вершины одного множества с вершинами другого множества (выделенные серым цветом), представляют собой разделяющее множество. Прямое ребро ведет из вершины множества, содержащего s, в вершину множества, содержащего t, обратное ребро ведет в другом направлении. В показанное на этой диаграмме сечение входят четыре прямых ребра и два обратных ребра.
|