Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 22. Потоки в сетях. Программа 22.3. Реализация максимального потока в аугментальных путях.___
|
|
Программа 22.3. Реализация максимального потока в аугментальных путях._______
Предлагаемый класс реализует общий алгоритм определения максимального потока посредством вычисления аугментальных путей (Форд-Фалькерсон). Он использует поиск по приоритету с целью обнаружения пути из истока в сток в остаточной сети (см. программу 22.4), затем добавляет в этот путь максимально возможную величину потока, многократно повторяя этот процесс до тех пор, пока не останется ни одного такого пути. Построение объекта этого класса устанавливает в заданных ребрах сети такие величины потоков, что поток из истока в сток становится максимальным.
Вектор st сохраняет остовное дерево с поиском по приоритету, при этом в st[v] содержится указатель на ребро, которое соединяет вершину v с ее родителем. Функция ST возвращает имя родителя вершины, заданной в качестве ее аргумента. Функция augment использует ST для обхода пути с целью определения его пропускной способности и последующего наращивания потока.
template < class Graph, class Edge> class MAXFLOW { const Graph & G; int s, t; vector< int> wt; vector< Edge *> st;
int ST(int v) const { return st[v]-> other(v); } void augment (int s, int t)
{ int d = st[t]-> capRto(t);
for (int v s ST(t); v! = s; v = ST (v)) if (st[v]-> capRto(v) < d)
d = st[v]-> capRto(v); st[t]-> addflowRto(t, d); for (int v = ST(t); v! = s; v = ST (v))
st[v]-> addflowRto(v, d); }
bool pfs(); public:
MAXFLOW(const Graph & G, int s, int t): G(G),
s(s), t(t), st(G.V()), wt(G.V()) { while (pfs()) augment(s, t); } };
Как мы вскоре убедимся, эти базовые алгоритмические инструментальные средства дают нам простые (и полезные во многих приложениях) решения задачи о потоках в транспортных сетях. Однако всесторонние исследования, показывающие, какой из конкретных методов является наилучшим, сами по себе являются достаточно сложной задачей, поскольку время выполнения этих методов зависит от:
■ Числа аугментальных путей, необходимых для отыскания максимального пути.
■ Времени, необходимого для отыскания каждого аугментального пути.
Эти количественные величины могут изменяться в широких пределах, в зависимости от вида обрабатываемой сети и от стратегии поиска на графе (структура данных применительно к бахроме).
Часть 5. Алгоритмы на графах
Программа 22.4. Реализация поиска по приоритету для определения
аугментальных путей__________________________________________________
Данная реализация поиска по приоритету была получена на основе реализации, которую мы использовали для алгоритма Дейкстры (программа 21.1) и в которую были внесены изменения, в соответствии чем веса приняли целочисленные значения, с целью обеспечения возможности обработки ребер остаточной сети и обеспечения останова при достижении стока или возврата значения false, если не существует пути из истока в сток. Заданное определение приоритета Р позволяет получить аугментальный путь с максимальной пропускной способностью (отрицательные величины сохраняются для очередей по приоритетам с тем, чтобы были выполнены требования интерфейса программы 20.10); другие определения приоритета Р приводят к различным алгоритмам вычисления максимальных алгоритмов.
template < class Graph, class Edge> bool MAXFLOW< Graph, Edge>:: pfs() { PQi< int> pQ< G.V<), wt); for (int v = 0; v < G.V(); v++)
{ wt[v] = 0; st[v] = 0; pQ. insert (v); } wt[s] = -M; pQ.lower(s); while (! pQ.empty())
{ int v = pQ.getmin(); wt[v] = -M;
if (v == t || (v! = s 66 st[v] == 0)) break; typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) { int w = e-> other (v);
int cap = e-> capRto (w);
int P = cap < -wt[v]? cap: -wt[v];
if (cap > 0 & & -P < wt[w])
{ wt[w] = -P; pQ.lower(w); st[w] = e; } } >
return st[t]! = 0; }
По-видимому, простейшая реализация алгоритма Форда-Фалкерсона использует кратчайший аугментальный путь (измеренный по числу ребер, образующих этот путь, а не по потоку или по пропускной способности). Этот метод был предложен Эдмондсоном (Edmondson) и Карпом (Karp) в 1972 г. Чтобы его реализовать, мы организуем очередь для бахромы либо путем использования возрастающего счетчика для Р, либо путем использования АТД очереди вместо АТД очереди с приоритетами, которая применялась в программе 22.3. В этом случае поиск аугментального пути сводится к поиску в ширину (BFS) в остаточной сети, точно такому, какой был описан в разделах 18.8 и 21.2. На рис. 22.17 показана реализация этого метода Форда-Фалкерсона в действии на демонстрационном примере сети. Для краткости мы будем называть этот метод алгоритмом вычисления максимального потока с использованием кратчайшего аугментального пути. Из этого рисунка легко видеть, что длины аугментальных путей образуют неубывающую последовательность. Проведенный нами анализ этого метода во время доказательства свойства 22.7 показывает, что это свойство является для него характерным.
Другая реализация алгоритма Форда-Фалкерсона, предложенная Эдмондсоном и Карпом, может быть описана следующим образом: выполняется наращивание вдоль пути, который увеличивает поток на наибольшую величину. Значение приоритета Р, которое было ис-
Глава 22, Потоки в сетях
пользовано в программе 22.3, обеспечивает реализацию этого метода. Этот приоритет заставляет алгоритм выбирать ребра из бахромы таким образом, чтобы количество потока, который пропускается через прямое ребро или удаляется из обратного ребра, было максимальным. Этот метод мы будем называть алгоритмом вычисления максимального потока путем наращивания потока до максимальной пропускной способности (maximum-capacity-augment ing-path maxflow algorithm). Рисунок 22.18 служит иллюстрацией работы этого алгоритма на той же транспортной сети из рис. 22.17.
Это всего лишь два примера (которые мы сейчас способны анализировать!) реализаций алгоритма Форда-Фалкерсона. В конце этого раздела мы изучим также и другие реализации. Однако прежде чем приступить к такому изучению, мы рассмотрим задачу анализа методов вычисления аугментальных путей с тем, чтобы исследовать их свойства и, в конечном итоге, определить, какой из методов обеспечивает наивысшую производительность.
Пытаясь сделать нужный нам выбор из семейства алгоритмов, представленных программой 22.3, мы попадаем в привычную ситуацию. Должны ли мы прежде всего принимать во внимание производительность, обеспечиваемую выбираемым алгоритмом в худшем случае, или это всего лишь математический домысел, не имеющий отношения к сетям, с которыми мы имеем дело на практике?
РИСУНОК 22.17. КРАТЧАЙШИЕ АУГМЕНТАЛЬНЫЕ ПУТИ
Рассматриваемая последовательность диаграмм показывает, как реализация метода Форда-Фалкерсона, выполняющая поиск кратчайшего аугментального пути, находит максимальный поток на демонстрационном примере транспортной сети. По мере продвижения алгоритма, длины путей увеличиваются: первые четыре пути в верхнем ряду имеют длину 3, последний путь в верхнем ряду и все пути во втором ряду имеют длину 4; два пути в нижнем ряду имеют длину 5, и процесс завершается отысканием двух путей длиной 7, при этом в каждом из них присутствует обратное ребро.
Часть 5, Алгоритмы на графах
Этот вопрос особо актуален в рассматриваемом контексте, поскольку границы в классическом худшем случае, на которые мы можем ориентироваться, намного выше, чем фактическая производительность, которую мы получаем при работе с графами на практике.
Многие другие факторы еще больше осложняют ситуацию. Например, время выполнения в худшем случае для многих версий зависит не только от числа вершин V и числа ребер Е, но также и от значений пропускных способностей ребер в сети. Разработка алгоритма максимального потока с высокой гарантированной производительностью в течение нескольких десятилетий привлекала к себе внимание многих исследователей, которые предложили множество методов решения. Оценка всех этих методов применительно к различным типам сетей, которые встречаются на практике, с достаточной степенью точности позволяет нам сделать правильный выбор, однако она более расплывчата, чем оценка той же задачи в других ситуациях, которые мы изучали ранее, например, в таких, как практические приложения алгоритмов сортировки или поиска.
Памятуя обо всех этих трудностях, рассмотрим теперь классические результаты, касающиеся производительности метода Форда-Фалкерсона в худшем случае: одну общую границу и две специальные границы, по одной на каждый из алгоритмов вычисления аугментального пути, которые мы уже освоили. Эти результаты в большей степени расширяют наше представление о внутренних характеристиках алгоритмов, чем обеспечивают возможность прогнозировать с достаточной степенью точности производительность этих алгоритмов с целью их сравнения и последующих выводов. Эмпирическое сравнение этих методов мы проведем в конце этого раздела.
Свойство 22.6. Пусть М есть максимальная пропускная способность ребер в сети. Число аугментальных путей, необходимых для любой реализации алгоритма Форда-Фалкерсона, равно максимум VM.
РИСУНОК 22.18. АУГМЕНТАЛЬНЫЕ ПУТИ С МАКСИМАЛЬНОЙ ПРОПУСКНОЙ СПОСОБНОСТЬЮ
Рассматриваемая последовательность диаграмм показывает, как реализация метода Форда-Фалкерсона, выполняющая поиск аугментального пути с максимальной пропускной способностью, находит максимальный поток на демонстрационном примере транспортной сети. По мере продвижения алгоритма, пропускная способность путей уменьшается, однако их длина может как увеличиваться, так и уменьшаться. Этому методу требуется найти всего лишь девять аугментальных путей, чтобы вычислить тот же максимальный поток, который представлен на рис. 22.17.
Глава 22, Потоки в сетях
Доказательство: Любое сечение содержит максимум V ребер с пропускной способностью М, т.е., их максимальная пропускная способность есть VM. Каждый аугментальный путь увеличивает поток через сечение, по меньшей мере, на 1, следовательно, выполнение алгоритма прекратится после VM проходов, поскольку в результате выполнения множества процедур наращивания все сечения должны быть насыщены до их пропускной способности. ■
Как уже говорилось выше, в типовых ситуациях от такой границы мало проку, поскольку М может быть очень большим числом. Что еще хуже, легко описать ситуацию, когда число итераций пропорционально максимальной пропускной способности ребра. Например, предположим, что мы используем алгоритм определения самого длинного аугментального пути (возможно, основанного на интуитивном представлении, что чем больше путь, тем больший поток мы загружаем в ребра сети). Поскольку мы ведем подсчет итераций, мы на время игнорируем затраты на вычисление такого пути. Классический пример, представленный на рис. 22.19, показывает сеть, для которой число итераций алгоритма определения самого длинного аугментального пути равно максимальной пропускной способности ребер. Этот пример свидетельствует о том, что мы должны проводить более подробные исследования, чтобы выяснить, обеспечивают ли другие конкретные реализации существенное уменьшение итераций по сравнению с оценкой, данной свойством 22.6.
РИСУНОК 22.19. ДВА СЦЕНАРИЯ ДЛЯ АЛГОРИТМА ФОРДА-ФАЛХЕРСОНА
Представленная на рисунке сеть служит иллюстрацией того, что число итераций, выполняемых алгоритмом Форда-Фалкерсона, зависит от пропускных способностей ребер в сети и от последовательности аугментальных путей, выбираемых реализацией рассматриваемого алгоритма. Она состоит из четырех ребер с пропускной способностью Х и одного ребра с пропускной способностью 1. Сценарий, описание которого дано в верхней части рисунка, показывает, что реализация, которая попеременно использует цепочки 0-1-2-3 и 0-2-1-3 как аугментальные пути (например, та, что предпочитает длинные пути), потребует X пар итераций, подобных двум парам, показанным на рисунке, причем каждая такая пара увеличивает общих поток на 2. Сценарий в нижней части рисунка показывает, что реализация, которая выбирает цепочки 0-1-3, а затем 0-2-3 в качестве аугментальных путей (например, та, что предпочитает короткие пути), определяет максимальный поток всего за две итерации.
Если пропускные способности ребер выражены, скажем, 32-разрядными целыми числами, быстродействие сценария, описание которого помещено в верхней части рисунка, будет в миллиард раз меньшим быстродействия сценария в нижней части рисунка.