Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Глава 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-разрядными целыми числами, быстро­действие сценария, описание которого помещено в верхней части рисунка, будет в миллиард раз меньшим быстродействия сценария в нижней части рисунка.








© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.