Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. > 22.49.Опишите операции алгоритма выталкивания превосходящего потока в сети, пропускные способности которой находятся в равновесии.
|
|
> 22.49. Опишите операции алгоритма выталкивания превосходящего потока в сети,
пропускные способности которой находятся в равновесии.
22.50. Воспользуйтесь концепциями, приведенными в данном разделе (функции вы
соты, подходящие ребра, выталкивание потока через ребра), для описания алгорит
мов вычисления максимального потока методом аугментальных путей.
22.51. Покажите в стиле рис. 22.28 потоки и остаточную сеть после каждой фазы, ког
да вы используете алгоритм выталкивания превосходящего потока с очередью FIFO
для отыскания максимального потока в транспортной сети, показанной на рис. 22.10.
> 22.52. Реализуйте функцию initheights() для программы 22.5, используя поиск в шири
ну, отправляясь от стока.
22.53. Выполните упражнение 22.51 для алгоритма выталкивания превосходящего потока из вершины с максимальной высотой.
о 22.54. Выполните модификацию программы 22.5 с целью реализации алгоритма выталкивания превосходящего потока из вершины с максимальной высотой путем построения обобщенной очереди как очереди с приоритетами. Проведите эмпирическое тестирование таким образом, чтобы у вас были основания включить в таблицу 22.2 строку для этого варианта алгоритма.
22.55. Начертите диаграмму, отображающую число активных вершин, а также число вершин и ребер в остаточной сети по мере выполнения реберного алгоритма выталкивания превосходящего потока с очередью FIFO для конкретных примеров различных видов сетей (см. упражнения 22.7-22.12).
о 22.56. Реализуйте обобщенный реберный алгоритм выталкивания превосходящего потока, который использует обобщенную очередь подходящих ребер. Выполните эмпирические исследования различных сетей (см. упражнения 22.7-22.12), сравнивая их с базовыми методами и проводя более подробный анализ реализаций обобщенных очередей, которые обеспечивают лучшие показатели, чем другие виды очередей.
22.57. Внесите изменения в программу 22.5 с целью периодического пересчета высот вершин, представляющие собой кратчайшие пути из соответствующей вершины в сток в остаточных сетях.
о 22.58. Дайте оценку идеи проталкивания избыточного потока из вершин путем его равномерного распределения по исходящим ребрам, но не путем наполнения одних до насыщения, оставляя пустыми другие.
Часть 5. Алгоритмы на графах
22.59. Проведите эмпирические исследования, чтобы определить, оправданы ли для программы 22.5 вычисления кратчайших путей для определения исходных значений функции высоты, путем сравнения производительности программы при задании функции высоты этим способом для различных сетей (см. упражнения 22.7-22.12) с ее производительностью в случае, когда высоты вершины инициализированы нулями.
о 22.60. Проведите эксперименты с гибридными методами, предусматривающими использование различных комбинаций описанных выше идей. Проведите экспериментальные исследования на примере различных видов сетей (см. упражнения 22.7-22.12) с целью сравнения этих методов с базовыми методами, более подробно останавливаясь на вариантах, показывающих лучшие результаты.
22.61. Внести в реализацию программы 22.5 такие изменения, которые бы явно пре
дупреждали появление дубликатов вершин в обобщенной очереди. Проведите эмпири
ческие испытания на примере различных сетей (см. упражнения 22.7-22.12), чтобы оп
ределить, как отразятся эти изменения на значения фактического времени выполнения
программы.
22.62. Как отразится разрешение принимать дубликаты вершин в обобщенную очередь
на граничном значении времени прогона алгоритма в худшем случае, определяемом
свойством 22.13?
22.63. Внести в реализацию программы 22.5 такие изменения, которые позволили бы
поддерживать явное представление остаточной очереди.
о 22.64. Покажите, что граница, определяемая свойством 12.13, принимает значение О(V3) для реализации, задаваемой упражнением 22.63. Указание: Проведите проверку отдельных границ на число выталкиваний потока, которое соответствует удалению ребер из остаточной сети, и на число выталкиваний потока, в результате которых не появляются полные или пустые ребра.
22.65. Проведите эмпирические исследования на различных сетях (см. упражнения
22.7-22.12), чтобы определить, к каким последствиям приведет использование явных
представлений остаточных сетей (см. упражнение 22.63) на фактических значениях вре
мени прогона алгоритма.
22.66. Докажите, что число выталкиваний потоков в условиях применения обобщен
ного реберного алгоритма выталкивания превосходящего потока, которое соответству
ет удалению ребра из остаточной сети, не превышает 2VE. Предполагается, что такая
реализация поддерживает явное представление остаточной сети.
• 22.67. Докажите, что число выталкиваний потоков в условиях применения обобщен
ного реберного алгоритма выталкивания превосходящего потока, которое не соответ
ствует удалению ребра из остаточной сети, не превышает 4 V2(V+E). Указание: Вос
пользуйтесь суммой высот активных вершин как потенциальной функцией.
• 22.68. Проведите эмпирические исследования для определения фактического числа
проверяемых ребер и отношения времени прогона к V для различных версий алгорит
ма выталкивания превосходящего потока для различных сетей (см. упражнения 22.7-
22.12). Рассмотрите различные алгоритмы, описанные в тексте и в предыдущих упраж
нениях, и остановите свое внимание на тех из них, которые зарекомендовали себя с
лучшей стороны на крупных разреженных сетях. Сравните полученные вами резуль
таты с результатами, полученными в упражнении 22.34.