![]() Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сведение к задаче о потоке минимальной стоимости
Поток минимальной стоимости представляет собой общую модель, которая может охватывать множество полезных практических задач. В данном разделе мы дадим обоснование этого утверждения, доказав возможность сведения самых разнообразных задач к задаче о потоке минимальной стоимости. Вполне очевидно, что задача о потоке минимальной стоимости носит более общий характер, нежели задача о максимальном потоке. В частности, если мы назначим в построении, показанном на рис. 22.42, фиктивному ребру стоимость, равную единице, а другим ребрам стоимость, равную нулю, то любой максимальный поток минимальной стоимос- Часть 5. Алгоритмы на графах
Однако больший интерес представляет тот факт, что мы можем проверить возможность использования свойств полученных нами алгоритмов решения задачи о потоке минимальной стоимости для разработки новых общих алгоритмов решения задачи о максимальном потоке. Мы уже отмечали, что общий алгоритм вычеркивания циклов, применяемый при решении задачи о максимальной потоке минимальной стоимости, позволяет получить общий алгоритм вычисления аугментальных путей для задачи о максимальном потоке. В частности, такой подход приводит к реализации, которая находит аугментальные пути без поиска в сети (см. упражнения 22.133 и 22.134). С другой стороны, этот алгоритм может строить аугментальные пути с нулевым потоком, в связи с чем его рабочие характеристики трудно оценить (см. раздел ссылок). Задача о максимальном потоке минимальной стоимости носит более общий характер, нежели задача поиска кратчайшего пути. Это утверждение следует из возможности ее сведения к другой задаче. Свойство 22.29. Задача о кратчайшем пути с единственным источником (в сетях, в которых нет отрицательных циклов) сводится к задаче о допустимых потоках минимальной стоимости. Доказательство: Пусть дана задача поиска кратчайшего пути с единственным источником (сеть и исток в вершине s), требуется построить транспортную сеть с теми же вершинами, ребрами и стоимостями ребер и наделить ребра неограниченной пропускной способностью. Добавьте новую вершину истока с ребром, ведущим в s и имеющим стоимость ноль и пропускную способность V— 1, а также новую вершину стока с ребрами, ведущими из всех других вершин и имеющими нулевые стоимости и пропускные способности, равные 1. Это построение представлено на рис. 22.51. Решим задачу о допустимом потоке минимальной стоимости на этой сети. При необходимости удалим из решения все циклы с тем, чтобы получить решение с остовным деревом. Это остовное дерево непосредственно соответствует остовному дереву кратчайших путей в исходной сети. Подробное доказательство этого факта оставляем читателям на самостоятельную проработку (см. упражнение 22.128). ■ Таким образом, все задачи, рассмотренные в разделе 21.6, которые сводятся к задаче поиска кратчайших путей в сети с единственным источником, также сводятся к задаче о потоке минимальной стоимости. Это множество задач включает задачу календарного планирования работ с конечными сроками завершения и с разностными и прочими ограничениями. Как мы убедились при изучении задач о Максимальном потоке, имеет смысл проанализировать во всех подробностях работу сетевого симплексного алгоритма при решении задачи поиска кратчайших путей с использованием приведения, описанного в свойстве 22.29. В этом случае данный алгоритм поддерживает остовное дерево с корнем в истоке, во многом напоминая алгоритмы на базе поиска, которые рассматривались главе 21, однако потенциалы и приведенные стоимости дают дополнительную гибкость при разработке методов выбора следующего ребра для включения в дерево. Глава 22. Потоки в сетях
В общем случае мы не используем тот факт, что задача о потоке минимальной стоимости есть правильное обобщение задачи о минимальном потоке и задачи поиска кратчайших путей, поскольку в нашем распоряжении имеются специальные алгоритмы, гарантирующие более высокую производительность при решении обеих этих задач. Однако если таких реализаций нет, то качественная реализация сетевого симплексного алгоритма, возможно, обеспечит быстрое решение конкретных примеров обеих задач. Разумеется, мы должны избегать циклов сведения одних задач к другим или построения задач обработки сетей, которые используют такие сведения. Например, реализация алгоритма вычеркивания циклов из программы 22.9 использует как алгоритмы вычисления максимального потока, так и алгоритмы поиска кратчайших путей для решения задачи о потоке с минимальной стоимостью (см. упражнение 21.96). Далее мы проведем анализ нескольких сетевых моделей. Сначала мы покажем, что предположение о том, что все стоимости неотрицательны, не является ограничивающим, так как мы можем преобразовать сети с неотрицательными стоимостями в сеть без таковых.
Свойство 2230. В задаче о потоке с минимальной стоимостью мы можем предположить, что стоимость ребер неотрицательна, без потери общности. Доказательство: Мы докажем этот факт для допустимых потоков минимальной стоимости в распределительных сетях. Это результат верен и для максимальных потоков с минимальной стоимостью в силу эквивалентности этих двух задач по свойству 22.22 (см. упражнения 22.143 и 22.144). Пусть дана распределительная сеть, заменим любое ребро u-v, имеющее стоимость х < 0 и пропускную способность с, на ребро v-u с той же пропускной способностью, но имеющее стоимость -x (положительное число). Далее, мы можем уменьшить значение запаса-спроса вершины и на с и увеличить значение запаса-спроса вершины v на с. Такая операция соответствует проталкиванию с единиц потока из и в v с соответствующим уточнением сети. Если в случае ребер с отрицательной стоимостью решение задачи о потоке минимальной стоимости для преобразованной сети помещает поток f в ребро v-u, то мы помещаем поток с —/в ребро u-v исходной сети; в случае ребер с положительной стоимостью в преобразованной сети назначаются те же потоки, что и в исходной сети. Такое распределение потоков сохраняет ограничения на запас и спрос во всех вершинах. Часть 5. Алгоритмы на графах
Это сведение одной задачи к другой показывает, что мы можем сосредоточить свое внимание только на положительных стоимостях, однако в общем случае на практике мы не удосуживаемся делать это, поскольку полученные в разделах 22.5 и 22.6 реализации имеют дело исключительно с остаточными сетями и без труда выполняют обработку отрицательных стоимостей. Важно иметь в своем распоряжении некоторую нижнюю границу стоимостей в ряде контекстов, но эта граница не должна быть нулевой (см. упражнение 22.145). Далее мы покажем, что, как это делалось в случае задачи о максимальном потоке, при желании можно было бы ограничиться рассмотрением ациклических сетей. Более того, можно было бы также предположить, что ребра не имеют ограничений на пропускную способность (не существует верхней границы величину потока в таких ребрах). Комбинация этих двух вариантов приводит к следующим классическим формулировкам задачи о потоках минимальной стоимости. Транспортная задача. Решим задачу о потоке минимальной стоимости для двудольной распределительной сети, все ребра которой направлены из вершины с запасом в вершины со спросом и обладают неограниченной пропускной способностью. Как уже было показано в начале данной главы (см. рис. 22.2), обычно эта задача моделирует распределение товаров из складов (вершины с запасом) в розничные торговые точки (вершины со спросом) по каналам распределения (ребра) с конкретной стоимостью поставки единицы товара. Свойство 22.31. Транспортная задача эквивалентна задаче о потоке с минимальной сто-имоетъю. Доказательство: Пусть задана транспортная задача, мы можем решить ее, присваивая каждому ребру пропускную способность, более высокую, чем значения запаса или спроса вершин, которые оно соединяет, и решая возникающую при этом задачу нахождения допустимого ребра минимальной стоимости на построенной в процессе решения этой задачи распределительной сети. Поэтому нам всего лишь достаточно установить, что решение стандартной задачи сводится к решению транспортной задачи. Для разнообразия, опишем новое преобразование, которое линейно только на разреженных сетях. Построение, подобное тому, что мы использовали при доказательстве свойства 22.16, позволяет установить этот результат для неразреженных сетей (см. упражнение 22.148). Пусть дана стандартная распределительная сеть с V вершинами и Е ребрами, построим для транспортной задачи двудольную сеть с V вершинами запаса, Е вершинами спроса и 2Е ребрами следующим образом. Для каждой вершины исходной сети включим в двудольную сеть вершину с величиной запаса или спроса, равной соответству-
|