Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. > 22.116.Вычислите максимальный поток с ассоциированным с ним допустимым остов ным деревом для транспортной сети
|
|
> 22.116. Вычислите максимальный поток с ассоциированным с ним допустимым остов
ным деревом для транспортной сети, показанной на рис. 22.10.
> 22.117. Реализуйте функцию dfsR для программы 22.14.
о 22.118. Реализуйте функцию, которая удаляет циклы из частично заполненных деревьев из заданного сетевого потока и строит допустимое остовное дерево для итогового потока, как показано на рис. 22.44. Упакуйте созданную функцию таким образом, чтобы ее можно было использовать для построения исходного дерева в программе 22.14 или в программе 22.15.
22.119. В примере, представленном на рис. 22.46, покажите, как отразится на таблицах потенциалов смена на обратную ориентации ребра, соединяющего вершины 6и 5.
о 22.120. Постройте транспортную сеть и покажите такую последовательность аугментальных ребер, что общий сетевой симплексный алгоритм не останавливается.
> 22.121. Покажите в стиле рис. 22.47 процесс вычисления потенциалов дерева с кор
нем в вершине 0, которое показано на рис. 22.46.
ИЛИ, Покажите в стиле рис. 22.50 процесс вычисления максимального потока минимальной стоимости в транспортной сети, изображенной на рис. 22.10, отправляясь от базового максимального потока и связанного с ним базового остовного дерева, о котором шла речь в упражнении 22.116.
о 22.123. Предположим, что все недревесные ребра пусты. Напишите функцию, которая вычисляет потоки в древесных ребрах, помещая поток в ребре, соединяющем вершину v с ее родителем в дереве, в v-й элемент вектора flow.
о 22.124. Выполните упражнение 22.123 для случая, когда некоторые недревесные ребра могут оказаться заполненными.
22.125. Воспользуйтесь программой 22.12 в качестве основы для построения алгоритма
MST (алгоритм вычисления минимального остовного дерева). Проведите эмпиричес
кие исследования, сравнивая полученную вами реализацию с тремя базовыми алгорит
мами вычисления MST, описанными в главе 20 (см. упражнение 20.66).
22.126. Опишите, какие изменения потребуется внести в программу 22.15, чтобы она
каждый раз начинала поиск подходящего ребра со случайно выбранного ребра, а не
с самого начала.
22.127. Модифицируйте полученное вами решение в упражнении 22.126 таким обра
зом, чтобы каждый раз, когда программа выполняет поиск подходящего ребра, она
начинает его с того места, в котором завершился предыдущий поиск.
22.128. Внесите в приватные функции-элементы из данного раздела такие изменения,
которые позволили бы поддерживать трехсвязные древовидные структуры, включаю-
Глава 22. Потоки в сетях
щие родителя каждого узла, крайнего слева потомка и правого брата (см. раздел 5.4). Используемые вами функции, обеспечивающие наращивание потока в циклах и подстановку подходящего ребра вместо древесного ребра, должны выполняться за время, пропорциональное продолжительности цикла наращивания потока, а функции, вычисляющие потенциалы, должны выполняться за время, пропорциональное размеру меньшего из двух поддеревьев, которые образуются в результате удаления древесного ребра.
о 22.129. Внесите в приватные функции-элементы из данного раздела такие изменения, которые, в дополнение к базовому вектору дерева родительских связей, позволили бы поддерживать два других вектора, индексированные именами вершин: один из них содержит расстояние каждой вершины до корня, а другой вектор — потомка каждой вершины при поиске в глубину (DFS). Используемые вами функции, обеспечивающие наращивание потока в циклах и подстановку подходящего ребра вместо древесного ребра, должны выполняться за время, пропорциональное продолжительности цикла наращивания потока, а функции, вычисляющие потенциалы, должны выполняться за время, пропорциональное размеру меньшего из двух поддеревьев, которые образуются в результате удаления древесного ребра.
• 22.130. Проведите исследование идеи использования обобщенной очереди подходя
щих ребер. Рассмотрите различные реализации такой обобщенной очереди и различ
ные ее усовершенствования, позволяющие избежать чрезмерных вычислений стоимо
стей ребер, например, уделять меньше внимания подмножествам подходящих ребер за
счет ограничения размеров очереди или, возможно, позволить некоторым неподходя
щим ребрам оставаться в очереди.
• 22.131. Выполните эмпирические исследования с целью определить число итераций,
число вычислений потенциалов вершин и отношение времени прогона к E для не
скольких версий сетевого симплексного алгоритма на различных видах сетей (см. уп
ражнение 22.7-22.12). Рассмотрите различные алгоритмы, описанные в тексте и пре
дыдущих упражнениях, и сосредоточьте свое внимание на тех из них, которые
показывают себя с лучшей стороны на крупных разреженных графах.
• 22.132. Напишите клиентскую программу, которая выполняет графическую анимацию
динамики сетевых симплексных алгоритмов. Ваша программа должна создавать изоб
ражения, подобные показанным на рис. 22.50 и других рисунках этого раздела (рис.
22.48). Протестируйте полученную реализацию на эвклидовых сетях, описанных в уп
ражнениях 22.7—22.12.