Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Потокивсетях
|
|
| Г |
рафы, орграфы и сети - это всего лишь математические абстракции, однако они приносят практическую пользу, поскольку позволяют решать множество важных задач. В этой главе мы расширим сетевую модель решения задач с таким расчетом, чтобы она охватывала динамические ситуации, отождествляющие в нашем воображении движение материалов по сети, в которой различным маршрутам назначаются различные стоимости. Такие расширения позволяют решать удивительно широкие классы задач с длинным списком применений.
Мы увидим, что эти задачи и приложения могут быть решены с помощью нескольких естественных моделей, при этом мы можем переходить от одной из них к другой посредством метода сведения к другим задачам (reduction). Существует несколько различных технически эквивалентных способов формулирования базовых задач. Для реализации алгоритмов, которые их решают, мы выбираем две конкретные задачи, составляем эффективные алгоритмы их решения, а затем разрабатываем алгоритмы, которые решают другие задачи, отыскивая возможности сведения их к уже известным задачам.
В реальной жизни мы не всегда располагаем свободой выбора, какую предполагает этот идеализированный сценарий, поскольку возможность сведения решения одной задачи к решению другой установлена не для каждой пары задач и поскольку известны лишь немногие оптимальные алгоритмы решения любой из этих задач. Возможно, что пока еще не найдено прямого решения заданной задачи, и вполне вероятно, что пока еще не удалось найти эффективного метода, позволяющего сводить решение одной задачи из заданной пары задач к решению другой. Постановка той или иной задачи в виде задачи определения потоков в сетях, ис-
Часть 5. Алгоритмы на графах
следование которой мы проведем в данной главе, имела успех не только потому, что к ней легко сводится решение многих практических задач, но также и потому, что были разработаны многочисленные эффективные алгоритмы решения базовых задач потоков в сетях.
Приводимый ниже пример служит иллюстрацией широты круга задач, которые могут решаться с помощью моделей потоков в сетях, предлагаемых ею алгоритмов и реализаций. Его можно разбить на общие категории, известные как задачи распределения (distribution), сочетания (matching) и поиска сечения (cut); мы поочередно рассмотрим каждую из них. Мы не будем сосредоточивать внимание на конкретных деталях этих примером, зато выделим несколько различных связанных между собой задач. Далее в этой главе, когда наступит пора разработки и реализации алгоритмов, мы дадим строгие формулировки многих из упомянутых здесь задач.
В задаче распределения производится перемещение объектов из одного места сети в другое. Производится ли перевозка гамбургеров или цыплят в экспресс-закусочные, либо игрушек или одежды в магазины уцененных товаров по шоссе через всю страну, или же распределение программных продуктов по компьютерам либо информационных бит для отображения на мониторах во всех уголках света — по сути дела, это одна и та же задача. Задачи распределения сводит трудные проблемы, с которыми мы сталкиваемся при выполнении сложных операций, к решению типовых задач. Алгоритмы, предназначенные для их решения, нашли широкое применение, а без некоторых их них достаточно многочисленные приложения просто не будут работать.
Распределение товаров. У крупной компании имеются заводы, на которых изготавливаются товары, оптовые базы, предназначенные для временного хранения товаров, и розничные торговые точки, в которых товары продаются конечным потребителям. Компания должна регулярно доставлять товары с заводов в розничные торговые точки через оптовые базы, используя для этой цели каналы распределения, которые обладают различными пропускными способностями и различной стоимостью доставки единицы продукции. Можно ли организовать доставку товаров со складов в розничные торговые точки таким образом, чтобы спрос был удовлетворен везде? Каким будет маршрут, выбранный по критерию наименьшей стоимости? Рисунок 22.1 служит иллюстрацией задачи распределения товаров.
На рис. 22.2 показана транспортная задана (transportation problem), представляющей собой частный случай задачи распределения товаров, в которой игнорируются центры распределения и пропускные способности каналов. Эта версия задачи распределения товаров важна сама по себе и представляет интерес (как мы увидим в разделе 22.7) не только в плане непосредственного применения, но и в силу того обстоятельства, что она не является каким-то " специальным случаем" — в самом деле, по степени сложности решения она эквивалентна общей версии рассматриваемой задачи.
Обмен данными. Коммуникационная сеть получает некоторое множество запросов на передачу сообщений между серверами, подсоединенными к этой сети через каналы связи (абстрактные провода), которые передают данные с различной скоростью передачи. Какой должны быть максимальная скорость передачи данных, при которой информация может передаваться между конкретными серверами в такой сети? Если с каждым каналом передачи данных связана конкретная стоимость передачи, то каким будет минимальный по стоимости вариант передачи данных с заданной скоростью, которая меньше максимально возможной?
Глава 22, Потоки в сетях
|
РИСУНОК 22.1. ЗАДАЧА РАСПРЕДЕЛЕНИЯ
В этом примере задачи распределения мы имеем три вершины снабжения (вершины от 0 до 2), четыре распределительных пункта (вершины от 3 до 6), три вершины потребления (вершины от 7 до 9) и двенадцать каналов. Каждая вершина снабжения характеризуется собственным уровнем производства, каждая вершина потребления характеризуется собственным уровнем потребления, и каждый канал обладает определенной максимальной пропускной способностью и устанавливает собственную стоимость доставки единицы продукции. Проблема заключается в том, чтобы минимизировать стоимость доставки материалов по каналам доставки (при условии, что пропускная способность каналов нигде не будет превышена) таким образом, чтобы общий объем материала, поставляемого из каждой вершины снабжения, соответствовал уровню производимой продукции; чтобы общий объем материала, доставляемого на вершины потребления, соответствовал уровню его потребления; и чтобы общая интенсивность поступления материала в каждый распределительный пункт была равна интенсивности, с которой материал покидает их.
|
РИСУНОК 22.2. ТРАНСПОРТНАЯ ЗАДАЧА
Транспортная задача во многом подобна задаче распределения, только в ней не учитываются пропускная способность каналов и отсутствуют распределительные пункты. В рассматриваемом примере мы имеем пять вершин снабжения (от 0 до 4), пять вершин потребления (от 5 до 9) и двенадцать каналов. Задача заключается в том, чтобы найти способ распределения материала по каналам минимальной стоимости с таким расчетом, чтобы поставки материала везде соответствовали спросу на него. В частности, нам нужно присвоить каналам такие веса (интенсивность распределения), чтобы сумма весов исходящих ребер была равна притоку материала в каждую снабжающую вершину; сумма весов входящих ребер должна быть равна суммарной потребности каждой потребляющей вершины; общая стоимость (сумма произведений весов на стоимость ребра для всех ребер) должна быть минимальной по всем присвоенным весам.
Часть 5. Алгоритмы на графах
| Пусть даны два множества, содержащие по N точек; требуется найти множество линейных сегментов, при условии, что границы каждого сегмента совпадают с точками каждого из заданных множеств, суммарная длина которых минимальна. Одним из приложений этой чисто геометрической задачи является радарная система слежения. Каждый поворот радиолокатора дает множество точек, которые представляют самолеты. Мы полагаем, что самолеты достаточно далеко удалены друг от друга в пространстве, так что решение этой задачи позволяет связать положение каждого самолета на одном повороте радиолокатора с его позицией на следующем повороте, сле- |
Транспортные потоки. Городское управление должно разработать план эвакуации людей из города в случае возникновения критических ситуаций. Какое минимальное время потребуется для эвакуации города в предположении, что мы можем регулировать транспортные потоки в такой степени, которая позволяет осуществить минимальную эвакуацию? Планировщики транспортных потоков могут ставить подобные вопросы, принимая решение, где строить новые дороги, мосты или туннели, которые способны смягчить проблему уличного движения в часы пик или в выходные дни.
В задаче сочетания сеть представляет собой возможные способы соединения двух пар вершин. Наша цель в этом случае заключается в таком выборе среди множества соединений (в соответствии со специальным критерием), при котором ни одна из вершин не выбирается дважды. Другими словами, избранное множество ребер определяет путь от одной вершины к другой. Мы можем выбирать колледжи для студентов, работу для соискателей, курсы для свободных часов в школе или членов Конгресса США (Государственной Думы России, Верховной Рады Украины) на посты в различных комитетах. В каждой их таких ситуаций мы можем воспользоваться широким разнообразием критериев, определяющих характер выбора.
Задача о трудоустройстве. Служба трудоустройства организует интервью для группы студентов с некоторым числом компаний; в результате этих интервью появляется ряд предложений работы. Исходя из предположения, что за интервью следует предложение работы, существует взаимная заинтересованность в том, чтобы студенты принимали предложения от компании, поэтому каждая из сторон стремится добиваться максимально возможного трудоустройства. Из примера, представленного на рис. 22.3, следует, что эта задача может оказаться достаточно сложной.