Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 22. Потоки в сетях. о 22.137.Докажите, что все ребра остовного дерева, описанного в доказательстве свойства 22.29, включены в пути
|
|
о 22.137. Докажите, что все ребра остовного дерева, описанного в доказательстве свойства 22.29, включены в пути, ведущие из источника к листьям.
о 22.138. Докажите, что остовное дерево, описанное в доказательстве свойства 22.29, соответствуют дереву кратчайших путей в исходной сети.
22.139. Предположим, что вы используете сетевой симплексный алгоритм для реше
ния задачи, полученной в результате сведения задачи о кратчайших путях из единствен
ного источника, как описано в доказательстве свойства 22.29. (i). Докажите, что этот
алгоритм никогда не использует аугментальный путь нулевой стоимости. (ii) Покажите,
что ребро, которое выходит из цикла, всегда есть родитель вершины назначения реб
ра, добавляемого в цикл. (iii) Как следствие упражнения 22.138, сетевой симплексный
алгоритм не обязан поддерживать потоки в ребрах. Представьте полную реализацию,
использующую все преимущества, вытекающего из этого факта. Выбор нового древес
ного ребра производится случайным образом.
22.140. Предположим, что мы присваиваем положительную стоимость каждому реб
ру сети. Докажите, что задача построения дерева кратчайших путей с единственным
источником минимальной стоимости сводится к задаче о максимальном потоке мини
мальной стоимости.
22.141. Предположим, что мы модифицируем задачу планирования работ с конечны
ми сроками завершения из раздела 21.6 таким образом, что работы могут нарушать
сроки завершения, при этом они получают некоторую положительную стоимость, если
это произойдет. Покажите, что модифицированная таким образом задача сводится к
задаче о максимальном потоке минимальной стоимости.
22.142. Реализуйте класс, который обнаруживает максимальные потоки минимальной
стоимости в распределительных сетях с отрицательной стоимостью. Воспользуйтесь
полученным классом для решения упражнения 22.105 (по условиям которого все сто
имости неотрицательны).
о 22.143. Предположим, что стоимости ребер 0-2 и 1-3 на рис. 22.40 суть -1, а не 1. Покажите, как найти максимальный поток минимальной стоимости путем преобразования заданной сети в сеть с положительными стоимостями, а затем вычислить максимальный поток с минимальной стоимостью на новой сети.
22.144. Реализуйте класс, который обнаруживает максимальные потоки минимальной стоимости в сетях с отрицательной стоимостью. Воспользуйтесь классом MINCOST (который предполагает, что все стоимости неотрицательны).
о 22.145. Зависят ли реализации из разделов 22.5 и 22.6 существенным образом от того факта, что цены принимают неотрицательные значения? Если зависят, укажите, в какой степени; если не зависят, покажите, какие настройки (если таковые имеются) требуется выполнить, чтобы заставить работать сеть с отрицательными стоимостями, либо объясните, почему такие настройки невозможны.
22.146. Расширьте полученный вами в упражнении 22.74 АТД допустимого потока за
счет введения нижних границ пропускных способностей ребер. Реализуйте класс, ко
торый вычисляет максимальный поток минимальной стоимости, который соблюдает
эти границы (если такой поток имеет место).
22.147. Покажите, к каким результатам приводит использование метода сведения за
дач, описанного в тексте, на примере сведения транспортной сети, описанной в уп
ражнении 22.112, к транспортной задаче.
Часть 5. Алгоритмы на графах
о 22.148. Покажите, что задача о максимальном потоке минимальной стоимости сводится к транспортной задаче со всего лишь V дополнительными вершинами и ребрами, если прибегнуть к построению, аналогичному тому, что применялось при доказательстве свойства 22.16.
> 22.149. Реализуйте класс для решения транспортной задачи, основанный на простом сведении задачи о максимальном потоке минимальной стоимости, описанном в доказательстве свойства 22.30.
о 22.150. Разработайте реализацию класса для решения задачи вычисления потока минимальной стоимости, в основу которого положено сведение к транспортной задаче, описанное в доказательстве свойства 22.31.
о 22.151. Разработайте реализацию класса для решения задачи вычисления потока минимальной стоимости, в основу которого положено сведение к транспортной задаче, описанное в упражнении 22.148.
22.152. Напишите программу, генерирующую случайные экземпляры транспортной за
дачи, затем используйте их как основу для эмпирических испытаний различных алго
ритмов и реализаций на способность решения этой задачи.
22.153. Дайте пример крупной динамической транспортной задачи.
22.154. Проведите эмпирические исследования по сравнению двух различных мето
дов сведения произвольных задач о потоках минимальной стоимости к транспортной
задаче, которые обсуждались при доказательстве свойства 22.31.
22.155. Напишите программу, генерирующую случайные экземпляры задачи о назна
чениях, затем используйте их в качестве основы для эмпирических испытаний различ
ных алгоритмов и реализаций на способность решения этой задачи.
22.156. Дайте пример крупной динамической задачи о назначениях.
22.157. Задача о трудоустройстве, описанная в тексте, дает преимущества работода
телям (их суммарная стоимость максимизирована). Сформулируйте версию этой зада
чи, в рамках которой претенденты на рабочие места также могли бы высказывать
свои пожелания. Объясните, как решить вашу версию задачи.
22.158. Проведите эмпирические исследования по сравнению производительности двух
реализаций сетевого симплексного алгоритма, описанных в разделе 22.6, применитель
но к решению вариантов задачи о назначениях (см. упражнение 22.155), с V верши
нами и Е ребрами и разумно выбранным множеством значений V и Е.
22.159. Очевидно, что задача о почтальоне не имеет решения для сетей, которые не
принадлежат к числу сильно связных (почтальон может нанести визит только в вер
шины, содержащиеся в сильной компоненте, в которой он начинает свой обход), од
нако этот факт не оговаривается свойством 22.33. Что произойдет, если мы попыта
емся применить сведение к сети, которая не является сильно связной?
22.160. Проведите эмпирические исследования для различных взвешенных графов (см.
упражнения 21.4—21.8) с тем, чтобы определить среднюю протяженность пути почта
льона.
22.161. Дайте прямое доказательство того, что задача о кратчайшем пути из единствен
ного источника сводится к задаче о назначениях.
22.162. Дайте формулировку произвольной задачи о назначениях как LP-задачи.
Глава 22, Потоки в сетях
о 22.163. Выполните упражнение 22.18 для случая, когда значение стоимости, назначенной каждому ребру, есть -1 (таким образом, вы минимизируете неиспользованное пространство грузовых машин).
о 22.164. Найдите такую модель стоимостей для упражнения 22.18, чтобы ее решением был максимальный поток, требующий минимальное число дней.