Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Упражнения. > 22.49.Опишите операции алгоритма выталкивания превосходящего потока в сети, пропускные способности которой находятся в равновесии.
> 22.49. Опишите операции алгоритма выталкивания превосходящего потока в сети, 22.50. Воспользуйтесь концепциями, приведенными в данном разделе (функции вы 22.51. Покажите в стиле рис. 22.28 потоки и остаточную сеть после каждой фазы, ког > 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.62. Как отразится разрешение принимать дубликаты вершин в обобщенную очередь 22.63. Внести в реализацию программы 22.5 такие изменения, которые позволили бы о 22.64. Покажите, что граница, определяемая свойством 12.13, принимает значение О(V3) для реализации, задаваемой упражнением 22.63. Указание: Проведите проверку отдельных границ на число выталкиваний потока, которое соответствует удалению ребер из остаточной сети, и на число выталкиваний потока, в результате которых не появляются полные или пустые ребра. 22.65. Проведите эмпирические исследования на различных сетях (см. упражнения 22.66. Докажите, что число выталкиваний потоков в условиях применения обобщен
• 22.67. Докажите, что число выталкиваний потоков в условиях применения обобщен • 22.68. Проведите эмпирические исследования для определения фактического числа
|