Студопедия

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

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

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






Глава 22. Потоки в сетях. Следствие. Время, необходимое для того, чтобы найти максимальный поток в разрежен­ной сети, есть 0(V2lgM/lgK).








Следствие. Время, необходимое для того, чтобы найти максимальный поток в разрежен­ной сети, есть 0(V2 lgM/lgK).

Доказательство: Это утверждение непосредственно следует из использования реализа­ции очереди с приоритетами на основе сортирующего дерева, подобной использован­ной при доказательстве свойств 20.7 и 21.5. ■

Для значений М и V, которые обычно встречаются на практике, эта граница значи­тельно ниже границы О(V3), определяемой свойством 22.7. Во многих практических си­туациях алгоритм поиска максимального аугментального пути использует значительно меньше итераций, чем алгоритм поиска кратчайшего аугментального пути, за счет не­сколько завышенной границы затрат на действия по поиску каждого пути.

Желательно изучить множество других вариантов, которые описаны в публикациях, посвященных алгоритмам определения максимальных потоков. Продолжают появляться новые алгоритмы с более точными границами для худшего случая, тем не менее, суще­ствование нетривиальной нижней границы до сих пор не доказано, так что все еще со­храняется возможность открытия алгоритма с простым линейным временем выполнения. Многие алгоритмы этого класса разрабатывались главным образом с целью понижения границ худшего случая для насыщенных графов, поэтому они не обеспечивают лучшей производительности, чем алгоритм поиска максимального аугментального пути для раз­личных видов разреженных сетей, с которыми мы сталкиваемся на практике. Тем не ме­нее, многие варианты ждут своих исследователей, поставивших своей целью обнаруже­ние более эффективных практических алгоритмов определения максимальных потоков. Далее мы рассмотрим еще два алгоритма поиска аугментальных путей, а в разделе 22.3 подвергнем анализу другое семейство алгоритмов.

Один простой алгоритм поиска аугментальных путей предусматривает использование величины уменьшающегося счетчика Р или стека для реализации обобщенной очереди из программы 22.3, благодаря чему поиск аугментальных путей уподобляется поиску в глу­бину. На рис. 22.20 показан поток, вычисленный для нашего небольшого примера по это­му алгоритму. Интуиция подсказывает нам, что этот метод обладает подходящим быстро­действием, легок в реализации и способен провести поток через сеть. Как мы увидим далее, его производительность меняется в широких пределах, от исключительно низкого уровня для одних видов сетей до вполне приемлемого для других.

Другой альтернативой является использование реализации рандомизированной очере­ди в качестве обобщенной очереди, вследствие чего поиск аугментального пути становится рандомизированным поиском. На рис. 22.21 показан поток, вычисленный для нашего не­большого примера с помощью рассматриваемого алгоритма. Этот метод также обладает приличным быстродействием и легок в реализации; кроме того, как мы уже отмечали в разделе 18.8, он может сочетать в себе достоинства как поиска в ширину, так и поиска в глубину. Рандомизация — это мощное инструментальное средства в разработке алгорит­мов, и данная задача представляет собой ситуацию, в которой целесообразно ею восполь­зоваться.

Этот раздел мы завершим более подробным анализом методов, которые мы изучали с тем, чтобы прочувствовать все трудности, связанные с их сравнением между собой или с попытками прогнозирования рабочих характеристик для практических применений.



Часть 5, Алгоритмы на графах


РИСУНОК 22.20. ПОИСК АУГМЕНТАЛЬНОГО ПУТИ С ИСПОЛЬЗОВАНИЕМ СТЕКА

Этот рисунок служит иллюстрацией использования стека для построения обобщенной очереди в нашей реализации метода Форда-Фалкерсона, благодаря чему поиск путей производится так же, как и поиск в глубину. В этом случае рассматриваемый метод работает почти так же успешно, как и поиск в ширину, но в то же время его несколько неустойчивое поведение в какой-то степени объясня­ется тем, что он довольно чувствителен от выбора представления сети и исследованию не подвергался.

РИСУНОК 22.21. РАНДОМИЗИРОВАННЫЙ ПОИСК АУГМЕНТАЛЬНЫХ ПУТЕЙ

Эта последовательность есть результат использования рандомизированной очереди для структуры данных типа бахрома с целью поиска аугментальных путей в рамках метода Форда-Фалкерсона. В этом примере мы случайно натолкнулись на короткий путь с высокой пропускной способностью, благодаря чему нам потребовалось относительно небольшое число аугментальных путей. Несмотря на то что прогнозирование рабочих характеристик этого метода представляет собой достаточно трудную задачу, во многих ситуациях метод проявляет себя с лучшей стороны.







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