![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22. Потоки в сетях. ющему исходному значению плюс сумма пропускных способностей исходящих ребер
Следующее соответствие один к одному сохраняет стоимости потоков в обеих сетях неизменными: ребро u-v исходной сети пропускает поток величины f тогда и только тогда, когда в ребре u-[u-v] двудольной сети протекает поток величины c-f (эти два потока должны давать в сумме значение с в силу ограничения на запас-спрос, действующего в вершине [u-v]). Следовательно, любой поток минимальной стоимости в одной сети соответствует потоку минимальной стоимости в другой сети. ■ Поскольку мы не рассматривали прямых алгоритмов решения транспортной задачи, рассмотренное выше сведение одной задачи к другой представляет собой разве что академический интерес. Чтобы воспользоваться этим приемом, мы снова должны привести полученную задачу к (другой) задаче вычисления потока минимальной стоимости, воспользовавшись простым сведением, упоминавшимся при доказательстве свойства 22.31. Возможно, что такие сети допускают на практике более эффективные решения, а возможно и нет. Основная цель изучения эквивалентности транспортной задачи задаче отыскания потока минимальной стоимости заключается в том, чтобы понять, позволит ли отказ от пропускных способностей и проведение анализа на двудольных сетях существенно упростить решение задачи вычисления потока минимальной стоимости; тем не менее, это не так. В этом контексте нам следует рассмотреть другую классическую задачу. Она обобщает задачу о двудольном сочетании, которая подробно изучалась в разделе 22.4. Подобно упомянутой задаче, простота данной задачи также обманчива. Задача распределения. Для заданного взвешенного двудольного графа найти множество ребер минимальной стоимости, такое, что каждая вершина соединена в точности с единственной другой вершиной. Например, мы можем обобщить рассматривавшуюся нами ранее задачу о трудоустройстве, чтобы она включала способы количественной оценки желания компании заполучить каждого претендента на рабочее место (скажем, присваивая каждому претенденту целочисленные баллы, при этом наиболее подходящему претенденту присваиваются более низкие баллы) и количественной оценки желания претендента получить рабочее место в той или иной компании. Таким образом, решение задачи распределения способно предложить метод, учитывающий предпочтения обеих сторон. Свойство 22.32. Задача распределения сводится к задаче вычисления потока минимальной стоимости. Доказательство: Этот результат может быть установлен простым сведением к транспортной задаче. Пусть дана задача распределения, построить транспортную задачу с теми же вершинами и ребрами, при этом все вершины, входящие в одно из множеств, обозначаются как вершины с запасом и им присваивается значение 1, а все вершины, входящие в другое множество, обозначаются как вершины со спросом и им также присваивается значение 1. Каждому ребру необходимо назначить пропускную способность, равную 1, и стоимость, соответствующую весу этого ребра в задаче распределения. Часть 5. Алгоритмы на графах
Сведение этого варианта транспортной задачи к задаче вычисления минимального потока позволяет получить построение, по существу эквивалентное построению, которое мы использовали для сведения задачи двудольного сочетания к задаче вычисления максимального потока (см. упражнение 22.158). ■ Это отношение нельзя считать эквивалентностью, поскольку пока еще не существует известного способа сведения общей задачи о потоке минимальной стоимости к задаче распределения. В самом деле, подобно задаче поиска кратчайшего пути с единственным источником и задаче вычисления максимального потока, задача распределения на первый взгляд кажется более легкой для решения, чем задача вычисления потока минимальной стоимости, на том основании, что, как известно, алгоритмы ее решения обеспечивают более высокую асимптотическую производительность, чем широко известные алгоритмы решения задачи вычисления потока минимальной стоимости. Тем не менее, сетевой симплексный алгоритма настолько хорошо отлажен, что при его удачной Программной реализации он вполне подходит для решения задачи распределения. Более того, как и в задачах поиска максимального потока и кратчайших путей, есть возможность настроить сетевой симплексный алгоритм, чтобы он обеспечивал повышенную производительность на задаче распределения (см. раздел ссылок). Следующее сведение к задаче вычисления потока минимальной стоимости возвращает нас к базовой задаче поиска путей в графах подобных тем, что впервые рассматрива-
лись в разделе 17.7. Как и в случае задачи вычисления эйлерова пути, нам нужен путь, который включает все ребра графа. Признав, что не все графы содержат такой путь, мы можем ослабить ограничение, требующее, чтобы каждое ребро встречалось на пути только один раз.
Задача о почтальоне. Пусть дана некоторая сеть (взвешенный орграф), найти циклический путь минимального веса, включающий каждое ребро, по меньшей мере, один раз (см. рис. 22.52). Напомним, что основное определение, данное в главе 17, проводит различие между циклическими путями (которые могут неоднократно посещать те или иные вершины и ребра) и циклами (состоящими из различных вершин, за исключением первой и последней, которые совпадают). Решение этой задачи может также описывать наилучший маршрут почтальона (который должен пройти все улицы на своем пути). Решение этой задачи может также дать описание маршрута снегоочистителя во время снежной бури; существует множество других аналогичных применений. Задача о почтальоне представляет собой задачу поиска эйлерова пути, которую мы рассматривали в разделе 17.7: решение упражнения 17.92 представляет собой простую проверку Глава 22. Потоки в сетях на существование в орграфе эйлерова пути, а программа 17.14 является эффективным способом найти эйлеров путь в таких орграфах. Этот путь решает задачу о почтальоне, поскольку он включает каждое ребро в точности один раз - ни один другой путь не может обладать более низким весом. Задача усложняется, когда полустепени захода и полустепени исхода не обязательно равны. В общем случае, некоторые ребра приходится проходить более одного раза: задача заключается в том, чтобы минимизировать суммарный вес многократно посещаемых ребер. Свойство 22.33. Задача о почтальоне сводится к задаче вычисления потока с минимальной стоимостью. Доказательство: Дан вариант задачи о почтальоне (взвешенный орграф), определить распределительную сеть с теми же вершинами и ребрами, причем все значения запаса и спроса в вершине равны 0, стоимость ребра устанавливается равной весу соответствующего ребра, на пропускную способность ребер не накладываются никакие ограничения сверху, в то же время все пропускные способности ребер должны быть больше 1. Мы рассматриваем величину f потока в ребре u-v следующим образом: почтальон должен пройти по ребру u-v в сумме f раз. Найдите поток минимальной стоимости для этой сети, воспользовавшись преобразованием, описанным в упражнении 22.146, с целью снятия ограничений нижней границы на пропускную способность ребер. Теорема о декомпозиции потоков утверждает, что мы можем выразить поток как множество циклов, следовательно, мы можем построить циклический путь из этого потока точно так же, как мы строили эйлеров путь на эйлеровом графе: мы производим обход некоторого цикла, выходя из этого цикла для обхода другого цикла всякий раз, когда выходим на вершину, которая входит в этот другой цикл. ■ Подробный анализ задачи о почтальоне показывает, насколь зыбкая граница отделяет тривиальные проблемы от труднорешаемых в области алгоритмов на графах. Предположим, что мы рассматриваем двухсторонний вариант этой задачи, когда сеть неориентированная, а почтальон должен проходить каждое ребро в обоих направлениях. Затем, как мы отмечали в разделе 18.5, поиск в глубину (или любой другой поиск на графе) даст нам немедленное решение. Если, однако, достаточно одного обхода ребра в каком-либо направлении, то формулировка задачи окажется намного сложнее, чем просто сведение к задаче о потоке с минимальной стоимостью, с которой мы только что ознакомились, тем не менее, задача все еще не выходит из категории решаемых. Если некоторые ребра ориентированы, а другие нет, проблема переходит в категорию NP-трудных (см. раздел ссылок). Это всего лишь небольшая часть из нескольких десятков практических задач, формулируемых как задачи о потоке минимальной стоимости. Задача о потоке минимальной стоимости более многообразна, нежели задачи вычисления максимального потока или построения кратчайшего пути, а сетевой симплексный алгоритм эффективно решает все задачи, охватываемые этой моделью. Подобно тому, как мы поступали при изучении максимального потока, мы можем выяснить, как любую задачу о минимальном потоке представить в виде LP-задачи (см. рис. 22.53). Ее постановка есть простое расширение постановки задачи о максимальном потоке: мы добавляем уравнения, которые устанавливают значение фиктивной перемен- Часть 5. Алгоритмы на графах
Существуют другие модели, которые носят еще более общий характер, чем LP-модель; однако LP-модель обладают дополнительным достоинством, заключающимся в том, что LP-задачи в общем случае более сложные, чем задачи о потоке минимальной стоимости, и были разработаны более эффективные алгоритмы их решения. В самом деле, возможно, наиболее важный из этих алгоритмов известен как симплексный метод: сетевой симплексный метод есть специализированная версия симплексного метода, применимого к подмножеству LP-задач, которые соответствуют задачам о потоке минимальной стоимости, а понимание сетевого симплексного алгоритма можно рассматривать как первый шаг к пониманию полного симплексного алгоритма.
|