Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 22, Потоки в сетях. Чтобы получить начальное представление о возможных количественных различиях, мы воспользуемся двумя моделями транспортных сетей
|
|
Чтобы получить начальное представление о возможных количественных различиях, мы воспользуемся двумя моделями транспортных сетей, построенных на основе эвклидовой модели графа, которые применялись раньше для сравнения с другими алгоритмами на графах. Обе модели используют граф, для построения которого использованы V точек на плоскости со случайными координатами, принимающими значения между 0 и 1, при этом ребрами соединяются точки, расположенные на фиксированном удалении друг от друга. Эти ребра отличаются друг от друга различными присвоенными им значениями пропускной способности.
Первая модель просто присваивает одно и то же постоянное значение каждой пропускной способности. В обсуждении, проводимом в разделе 22.4, утверждается, что этот вариант задачи о потоках в сети решается легче, чем эта же задача в общем виде. В рассматриваемых нами эвклидовых графах потоки ограничены полустепенью исхода истока и полустепенью захода стока, так что для каждого алгоритма требуется найти всего лишь несколько аугментальных путей. Однако эти пути существенно различаются для различных алгоритмов, и в этом мы вскоре убедимся.
Вторая модель присваивает случайные значения весов из некоторого фиксированного диапазона значений пропускных способностей. Эта модель генерирует типы сетей, которые исследователи обычно имеют в виду, обращаясь к данной задаче, и рабочие характеристики, которые различные алгоритмы демонстрируют на таких сетях, дают богатую пищу для размышлений.
Иллюстрацией обеих моделей служит рис. 22.22, на нем также показаны четыре потока, вычисленные четырьмя различными методами на двух сетях. Возможно, самой красноречивой характеристикой этих примеров является то, что сами потоки отличаются друг от друга по характеру. Все они имеют одну и ту же величину, но в рассматриваемых сетях имеется много максимальных потоков, в то же время различные алгоритмы выбирают различные ребра при их вычислении. На практике такая ситуация — обычное дело. Мы можем попытаться наложить дополнительные ограничения на потоки, которые мы намерены вычислить, однако такие изменения в условиях задачи существенно усложняют поиск ее решения. Задача отыскания потока минимальной стоимости, которую мы будем исследовать в разделах 22.5-22.7, представляет собой один из способов формализации подобных ситуаций.
В таблице 22.1 представлены более подробные количественные результаты, которые могут быть использованы всеми четырьмя методами для вычисления потоков в сетях, показанных на рис. 22.22. Производительность алгоритма вычисления аугментальных путей зависит не только от числа аугментальных путей, но также и от длины таких путей и затрат на их поиск. В частности, время выполнения алгоритма пропорционально числу ребер, проверенных во внутреннем цикле программы 22.3. Как обычно, это число может меняться в широких пределах, даже для одного и того же заданного графа, и зависит от свойств его представления; но основной нашей задачей является изучение характеристик различных алгоритмов. Например, на рис. 22.23 и 22.24 показаны деревья поиска, соответственно, алгоритма вычисления максимальной пропускной способности и алгоритма поиска кратчайшего пути. Эти примеры подтверждают общий вывод о том, что метод поиска кратчайшего пути затрачивает больше усилий на отыскание аугментальных путей с меньшим потоком, чем алгоритм вычисления максимальной пропускной способности, благодаря чему легче понять, почему предпочтение отдается последнему.
Часть 5. Алгоритмы на графах
|
РИСУНОК 22.22. ТРАНСПОРТНАЯ СЕТЬ СО СЛУЧАЙНЫМИ ПОТОКАМИ
На этом рисунке представлены вычисления максимальных потоков в случайных эвклидовых графах на базе двух различных моделей пропускных способностей. В сетях слева всем ребрам присвоена единица в качестве пропускных способностей, в сетях справа ребрам присваиваются случайные значения пропускной способности. Исток находится в верхней части сети ближе к середине, а сток — в середине нижней части сети. Показанные на диаграммах потоки, направлены сверху вниз и вычислены с помощью, соответственно, алгоритма поиска кратчайшего пути, алгоритма вычисления максимальной пропускной способности, алгоритма, использующего стек, и рандомизирующего алгоритма. Поскольку вершины не имеют высоких степеней, а пропускные способности принимают малые целочисленные значения, существует много различных потоков, которые достигают максимума в условиях этих примеров.
Полустепень захода истока равна 6, так что все указанные выше алгоритмы вычисляет поток в рамках модели единичной пропускной способности, представленной в левой части рисунка, с помощью шести аугментальных путей.
Эти методы находят аугментальные пути, которые по своему характеру существенно отличаются для модели со случайными весами, представленной в правой части рисунка. В частности, методы, в основу которых положен стек, ищут длинные пути с малым весом и даже выполняют построение потока с разъединенным циклом.
Глава 22. Потоки в сетях
Таблица 22.1. Эмпирический анализ алгоритмов вычисления аугментальных путей
В этой таблице представлены параметры производительности алгоритмов вычисления потоков в сетях путем построения аугментальных путей на примере эвклидовой сети с близкими связями (со случайными значениями пропускной способности и с максимальной величиной потока, равной 286) и с пропускными способностями, равными единице (при величине максимального потока, равной 1). Алгоритм вычисления максимальной пропускной способности превосходит все другие алгоритмы на обоих типах сетей.. Алгоритм случайного поиска находит аугментальные пути, которые не намного длиннее, чем кратчайший путь, и проверяет меньшее число узлов. Алгоритм, использующий стек, очень хорошо зарекомендовал себя в условиях случайных весов, однако, несмотря на то что он находит очень длинные пути, он вполне может конкурировать с другими алгоритмами на сетях единичными весами.
РИС. 22.23. АУГМЕНТАЛЬНЫЕ ПУТИ С МАКСИМАЛЬНОЙ ПРОПУСКНОЙ СПОСОБНОСТЬЮ (БОЛЬШОЙ ПРИМЕР)
На этом рисунке показаны аугментальные пути, вычисленные с посредством алгоритма определения максимальной пропускной способности для эвклидовой сети со случайными значениями весов, которая изображена на рис. 22.22, вместе с ребрами остовного дерева поиска на графе (изображены серым цветом). Полученный в результате поток показан на диаграмме внизу справа.
Часть 5. Алгоритмы на графах
Возможно, основной урок, который можно вынести из подробного исследования конкретной сети, состоит в том, что различие в оценке верхней границы, полученной с применением свойств 22.6-22.8, и фактическим числом аугментальных путей, которые потребуются конкретному алгоритму в условиях заданного приложения, может оказаться огромным. Например, в транспортной сети, представленной на рис. 22.23, имеется 177 вершин и 2000 ребер с пропускной способностью, не превышающей 100 единиц, так что количественное значение 2ElgM в соответствии со свойством 22.8 превышает 25000 путей, однако алгоритм вычисления максимальной пропускной способности находит максимальный поток, используя всего лишь семь аугментальных путей. Аналогично, количественная оценка VE/2 для этой сети, определяемая свойством 22.7, составляет порядка 177000 путей, однако алгоритму кратчайших путей для той же цели достаточно всего лишь 37 путей.
Как отмечалось выше, относительно низкие степени узлов и местоположение соединений частично объясняют причину таких расхождений между теоретической оценкой и производительностью, полученной на практике. Мы можем доказать, что существуют более точные границы Производительности, учитывающие эти детали, однако подобные расхождения результатов, полученных на модели транспортной сети и в реальных сетях, являются скорее правилом, а не исключением. С другой стороны, на основании этих результатов мы можем утверждать, что эти сети имеют недостаточно общий характер, чтобы представлять сети, с которыми нам приходится иметь дело на практике; опять-таки, анализ худшего случая, возможно, еще больше далек от практики, чем все рассмотренные виды сетей.
Подобного рода огромные расхождения побуждают исследователей повышать интенсивность поисков с целью снижения границ для худшего случая. Существуют множество других возможных реализаций алгоритмов, использующих аугментальные пути, требующих подробных исследований, которые могут привести к более существенному улучшению их Производительности в худшем случае или большему повышению производительности на практике, чем все те методы, которые мы изучали (см. упражнения 22.56-22.60). Многочисленные более сложные методы, которые, как мы показали, обладают более высокой производительностью, описаны в публикациях, посвященных результатам исследований (см. раздел ссылок).
При исследовании множества других задач, которые сводятся к задаче о максимальном потоке, возникают важные осложнения. Когда применяются подобного рода сведения, получаемая при этом транспортная сеть может обладать некоторой специальной структурой, особенностями которой могут воспользоваться специальные алгоритмы с целью повышения производительности. Например, в разделе 22.8 мы будем рассматривать сведение, которое дает транспортную сеть с единичной пропускной способностью всех ребер.
Даже когда мы ограничиваем внимание только алгоритмами вычисления аугментальных путей, мы убеждаемся в том, что изучение алгоритмов нахождения максимального потока можно рассматривать одновременно как науку и как искусство. Искусство проявляется в выборе стратегии, которая наиболее эффективна в данной практической ситуации, а наука лежит в основе понимания природы задачи. Помогут ли новые структуры данных решить задачу нахождения максимального потока за линейное время, либо мы сможем доказать, что такое решение не существует?
Глава 22. Потоки в сетях
РИСУНОК 22.24. КРАТЧАЙШИЙ АУГМЕНТАЛЬНЫЙ ПУТЬ (БОЛЕЕ КРУПНЫЙ ПРИМЕР)
На этом рисунке изображены аугментальные пути, построенные с помощью алгоритма кратчайшего пути для эвклидовой сети со случайными весами, представленной на рис. 22.22, с ребрами остовного дерева поиска на графе (серого цвета). В этом случае рассматриваемый алгоритм обладает намного меньшим быстродействием, чем алгоритм вычисления максимальной пропускной способности, изображенный на рис. 22.23, в силу того, что он требует большее количество аугментальных путей (показаны первые 12 путей из общего числа 37 путей) и что остовные деревья оказываются больших размеров (обычно они содержат почти все вершины).
Часть 5. Алгоритмы на графах
В разделе 22.3 будет показано, что никакой алгоритм вычисления аугментальных путей не может показывать линейную производительность в худшем случае, и будет представлено другое обобщенное семейство алгоритмов, которые обеспечивают упомянутую линейность.