Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Потокивсетях




Г

рафы, орграфы и сети - это всего лишь математические абстракции, однако они приносят практическую пользу, поскольку позволяют решать множество важных задач. В этой главе мы расширим сетевую модель решения задач с таким расчетом, чтобы она охватывала динамические ситу­ации, отождествляющие в нашем воображении движение ма­териалов по сети, в которой различным маршрутам назнача­ются различные стоимости. Такие расширения позволяют решать удивительно широкие классы задач с длинным спис­ком применений.

Мы увидим, что эти задачи и приложения могут быть ре­шены с помощью нескольких естественных моделей, при этом мы можем переходить от одной из них к другой посред­ством метода сведения к другим задачам (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, следует, что эта задача может оказаться доста­точно сложной.


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал