![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22. Потоки в сетях. 22.30. Выполните упражнение 22.29, используя алгоритм построения аугментального пути с максимальной пропускной способностью.
22.30. 22.31. Выполните упражнение 22.29, используя алгоритм поиска аугментального пути о 22.32. Найдите семейство сетей, для которых алгоритм поиска максимального аугментального пути требует вычисления 2E lgM аугментальных путей. • 22.33. Сможете ли вы упорядочить ребра таким образом, чтобы рассмотренные нами 22.34. Проведите эмпирические исследования с целью определения числа аугменталь 22.35. Разработайте и протестируйте реализацию метода аугментальных путей, кото 22.36. Разработайте и протестируйте реализацию метода аугментальных путей, осно • 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.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.
|