![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. На этом рисунке показаны транспортные сети (слева) и остаточные сети (справа) для каждого этапа алгоритма выталкивания превосходящего потока на базе очереди
РИСУНОК 22.28. ОСТАТОЧНАЯ СЕТЬ (ОЧЕРЕДЬ FIFO ДЛЯ ВЫТАЛКИВАНИЯ ИЗБЫТОЧНОГО ПОТОКА) На этом рисунке показаны транспортные сети (слева) и остаточные сети (справа) для каждого этапа алгоритма выталкивания превосходящего потока на базе очереди FIFO, работающего на демонстрационном примере. Содержимое очередей показано под диаграммами транспортных сетей, а метки расстояний — под диаграммами остаточных сетей. На начальном этапе мы проталкиваем поток по ребрам 0-1 и 0-2, переводя тем самым вершины 1 и 2 в категорию активных. На втором этапе мы проталкиваем поток через эти две вершины в 3 и 4, благодаря чему они становятся активными, а вершина 1 перестает быть активной (вершина 2 остается активной, а метка ее расстояния увеличивается). На третьем этапе мы проталкиваем поток через вершины 3 и 4 в вершину 5, и это делает их неактивными (2 все еще остается активной, ее метка расстояния снова увеличивается). На четвертом этапе 2 остается единственным активным узлом, а ребро 2-0 становится приемлемым, поскольку метка расстояния возрастает и одна единица потока проталкивается обратно вдоль 2-0, после чего вычисления завершаются. Глава 22. Потоки в сетях 9 8 7 6 5 4 3____ РИСУНОК 22.29. ХУДШИЙ СЛУЧАЙ ВЫПОЛНЕНИЯ АЛГОРИТМОМ ВЫТАЛКИВАНИЯ ИЗБЫТОЧНОГО ПОТОКА, ПОСТРОЕННОГО НА БАЗЕ ОЧЕРЕДИ FIFO Данная сеть представляет семейство сетей с V вершинами, таких, что общее время прогона алгоритма выталкивания избыточного потока пропорционально V2. Она состоит ребра с пропускной способностью, равной единице, исходящих из истока (вершина 0) и горизонтальных ребер с пропускной способностью v - 2, ведущих слева направо в сток (вершина 10). На начальном этапе алгоритма выталкивания избыточного потока (сверху) мы выталкиваем одну единицу потока из каждого ребра, идущего из истока, в результате чего все вершины становятся активными, за исключением истока и стока. В стандартном представлении графа в виде списков смежных вершин они попадают в очередь FIFO активных вершин в обратном порядке, как показано в строке под диаграммой сети. На втором этапе (в центре) мы выталкиваем единицу потока из вершины 9 в 10, переводя 9 в неактивное состояние (временно), затем выталкиваем единицу потока из вершины 7 в 8, переводя 8 в активное состояние и т.д. Только вершина 1 остается неактивной. На третьем этапе (внизу) мы проходим через аналогичный процесс, чтобы сделать вершину 2 неактивной. Этот процесс продолжается на протяжении V — 2 этапов. Следует отметить, что границы худшего случая дают заниженную оценку, и в силу этого обстоятельства не всегда годятся для прогнозирования производительности алгоритма на реальных сетях (хотя расхождение между ними не настолько велико, какое мы находим в случае алгоритмов определения аугментальных путей). Например, алгоритм FIFO находит поток в сети, представленной на рис. 22.30 за 15 этапов, в то время как оценка, полученная на основании свойства 22.13, утверждает, что число этапов для его вычисления не превышает 182. Чтобы повысить производительность, мы можем попытаться использовать в программе 22.5 стек, рандомизированную очередь или любой другой вид обобщенной очереди. Один из подходов, хорошо зарекомендовавших себя на практике, заключается в такой реализации обобщенной очереди, чтобы функция могла GQGet возвращать максимальную активную вершину. Часть 5. Алгоритмы на графах
РИСУНОК 22.30. АЛГОРИТМ ВЫТАЛКИВАНИЯ ПРЕВОСХОДЯЩЕГО ПОТОКА (С ОЧЕРЕДЬЮ FIFO) Приведенная последовательность диаграмм показывает, как реализация метода выталкивания превосходящего потока находит максимальный поток на демонстрационном примере сети. Он выполняет обработку в несколько этапов. Сначала он проталкивает максимально возможную величину потока из истока по исходящим из него ребрам (диаграмма слева вверху). Затем выполняется проталкивание потока из каждого такого узла и продолжение этой процедуры до тех пор, пока все узлы не придут в равновесие.
|