Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 22. Потоки в сетях. 22.30. Выполните упражнение 22.29, используя алгоритм построения аугментального пути с максимальной пропускной способностью.
|
|
22.30. 
Выполните упражнение 22.29, используя алгоритм построения аугментального
пути с максимальной пропускной способностью.
22.31. Выполните упражнение 22.29, используя алгоритм поиска аугментального пути
с применением стека.
о 22.32. Найдите семейство сетей, для которых алгоритм поиска максимального аугментального пути требует вычисления 2E lgM аугментальных путей.
• 22.33. Сможете ли вы упорядочить ребра таким образом, чтобы рассмотренные нами
реализации тратили время, пропорциональное Е, на поиск пути в условиях упражне
ния 22.32? При необходимости внесите изменения в свой пример с тем, чтобы достичь
этой цели. Опишите представление графа в виде списков смежных вершин, постро
енное специально для предлагаемого вами примера.
22.34. Проведите эмпирические исследования с целью определения числа аугменталь
ных путей и отношения времени выполнения к V для каждого из четырех алгоритмов,
описанных в этом разделе, для различных видов сетей (см. упражнение 22.7—22.12).
22.35. Разработайте и протестируйте реализацию метода аугментальных путей, кото
рый использует эвристику кратчайшего пути исток-сток эвклидовой сети из раздела
21.5.
22.36. Разработайте и протестируйте реализацию метода аугментальных путей, осно
ванного на альтернативно растущих деревьях поиска с корнями в истоке и стоке (см.
упражнения 21.35 и 21.75).
• 22.37. Реализация программы 22.3 останавливает поиск на графе, как только он на
ходит первый аугментальный путь из истока в сток, производит наращивание потока,
а затем инициирует поиск с самого начала. Другой способ заключается в том, что она
продолжает поиск и находит другой путь. Этот процесс продолжается до тех пор, пока
все вершины не будут помечены. Разработайте и протестируйте второй подход.
22.38. Разработайте и протестируйте метод аугментального пути, который использует пути, не относящиеся к категории простых.
> 22.39. Предложите последовательность простых аугментальных путей, которые создают поток в цикле в сети, показанной на рис. 22.11.
о 22.40. Приведите пример, показывающий, что не все максимальные потоки могут быть получены методом наращивания потоков вдоль некоторой последовательности простых путей из истока в сток, начиная с пустой сети.
22.41. [Габов] Разработайте реализацию построения максимального потока, которая использует т = lgM этапов, при этом i-й этап решает задачу о максимальном потоке, используя первые i разрядов значений пропускных способностей. Начните с нулевого потока в любой точке сети; далее, по завершении первого этапа, выполните инициализацию потока удвоенной величиной потока, вычисленного на предыдущем этапе. Проведите эмпирические исследования на сетях различных видов (см. упражнения 22.7-22.12) и сравните этот метод с базовыми методами.
• 22.42. Докажите, что время выполнения алгоритма, описанного в упражнении 22.41,
есть
22.43. Проведите эксперименты с гибридным методом, который в начале использует один метод вычисления аугментальных путей, а затем переключается на другой метод вычисления аугментальных путей и использует его вплоть до завершения решения за-
Часть 5. Алгоритмы на графах
дачи (частью которой является выбор подходящего критерия, чтобы определить момент переключения с одного метода на другой). Проведите эмпирические исследования на сетях различных видов (см. упражнения 22.7—22.12), выполняя более подробные исследования тех из них, которые показывают лучшие результаты.
22.44. Проведите эксперименты с гибридными методами, по условиям которых производится переключение между двумя или большим числом различных методов вычисления аугментальных путей. Проведите эмпирические исследования на сетях различных видов (см. упражнения 22.7—22.12), выполняя более подробные исследования тех из них, которые показывают лучшие результаты.
о 22.45. Проведите эксперименты с гибридными методами, по условиям которых производится случайный выбор из двух или большего числа различных методов вычисления аугментальных путей. Проведите эмпирические исследования на сетях различных видов (см. упражнения 22.7—22.12), и сравните эти гибридные методы с базовыми методами, выполняя более подробные исследования тех из них, которые показывают лучшие результаты.
о 22.46. Напишите клиентскую функцию для транспортной сети, которая, при заданном целом числе с, находит ребро, увеличение пропускной способности которого в с раз увеличивает максимальный поток до максимальной величины. Разрабатываемая функция может полагать, что клиентская программа уже вычислила максимальный поток с помощью функции MAXFLOW.
•• 22.47. Предположим, что задан минимально загруженный сечение некоторой сети. Облегчает ли эта информация решение задачи вычисления максимального потока? Разработайте алгоритм, который использует заданный минимально загруженный сечение для существенного ускорения поиска аугментальных путей с максимальными пропускными способностями.
• 22.48. Напишите клиентскую программу, которая выполняет анимацию динамики алгоритмов поиска аугментальных путей. Эта программа должна создавать динамические графические изображения, подобные рис. 22.17 и другим рисункам из этого раздела (см. упражнения 17.55 17.59). Протестируйте полученную реализацию на эвклидовых сетях из числа тех, описание которых даны в упражнениях 22.7-22.12.