Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 27
Текст из файла (страница 27)
Поэтому мы рассмотрим случай, когда существуют непересекающиеся замкнутые подпутн. Перед тем как продолжить описание алгоритма, отметим, что Ау О для всех дуг (й /), для которых ()). Такие дуги будем называть недействительными. Путь из узла 1 в узел л, а также все непересекающиеся замкнутые подпути могут содержать одну или несколько недействительных дуг. Шаг 2. Последовательно рассмотреть все непересекающиеся замкнутые подпути, полученные в результате решения задачи о назначениях, и удалить из них все недействительные дуги.
Замечание. Поскольку в результате выполнения данного шага недействительные дуги будут удалены нз всех замкнутых подпутей, то последние будут содержать дуги, для каждой из которых номер конечного узла больше номера начального узла. (Напомним, что матрица расстояний является верхней треугольной матрицей.) Обозначим эти подпутн символами й — )ь (з — )ь гз — )в и т. д., где (г<(з«...,(и и гг<!ь (е<!з, „., (иФи. Шаг 3.
Вводя новые недействительные дуги, соединить узел п (конечный узел пути из узла 1 в узел п) с узлом (ы, 1 с г ь ..., )з — с 11 и узел 11 — с узлом 1. Замечание. В результате выполнения шага 3 строится цикл, ведущий из узла 1 в тот же самый узел н проходящий через каждый из оставшихся и — 1 узлов равно один раз. Отметим, что поскольку мы добавляем только недействительные дуги, то значение целевой функпии в задаче коммивояжера точно такое же, как и в задаче о назначениях.
А поскольку решение задачи о назначениях является оптимальным (т. е. стоимость полученного назначения минимальная), то и решение задачи коммивояжера — оптимальное. Для иллюстрации данного алгоритма рассмотрим следующий пример, принадлежащий Лоулеру 140]. Матрица расстояний 1 2 3 4 5 и 7 Из 4 11 — 1б54 162 Глава 2 Шаг 1. Обведенные элементы данной матрицы соответствуют оптимальному решению задачи о назначениях. Редуцированная матрица в задаче о назмачанияк 2 3 4 5 6 7 Шаг 2. Путь из узла 1 в узел 7 следующий: ~ф Π— *'О-'Оз * От Имеются два непересекающихся замкнутых подпутн: О-'О 2. Оз — '-' Оз — '- Оз Поскольку дуги (2, 2) и (6, 5) являются недействительными, то исключим их из построенных подпутей.
В результате мы получим следующие непересекающиеся множества: От — Оа — Оз — *- Оз О="О Шаг 3. Используя недействительные дуги, соединяем не связанные между собой узлы (пути) следующим образом: Ог — — О4 — Оз — От — О5 — Оа — Ог о 163 Детерминированные потоки в евтлк Стоимость данного пути, представляющего решение задачи коммивояжера, равна — 36. В заключение отметим, что следующее решение не является оптимальным, так как в последовательность непересекающихся подпутей включена дуга (2, 5), не являющаяся недействительной: О1 --т О4 — '- Оз — '-т От — 'т Оз — "'+ Оз - Оа — + О1 2.14.
ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ Пусть ел= (Х, А) — ориентированная сеть с одним источником зев(Ч и одним стоком (я(Ч, и пусть дуги (1,1)яА имеют ограниченную пропускную способность. Задача о максимальном потоке заключается в поиске таких потоков по дугам, принадлежащим множеству А, что результирующий поток, протекающий из источника з в сток 1, является максимальным. Предполагается, что в источник может поступать неограниченный поток и что для каждого промежуточного узла сети выполняется условие сохранения потока. Данная задача является нетривиальной, когда пропускная способность Уц каждой дуги представляет собой конечную верхнюю границу потока ~г1 по этой дуге. В равд. 2.2 задача о максимальном потоке была сформулирована в виде задачи линейного программирования, поэтому для ее решения можно воспользоваться обычным симплексиым методом.
В настоящем разделе будет описана еще одна, более эффективная процедура поиска решения данной задачи. Алгоритм начинает работу с некоторого допустимого решения. Затем выполняется процедура расстановки пометок, разработанная Фордом и Фалкерсоном 1151, с помощью которой определяется другой допустимый поток большей величины. В данном алгоритме узлы рассматриваются как промежуточные пункты передачи потока, а дуги — как распределительные каналы. Для формального описания алгоритма необходимо ввести два основных понятия — пометки и аугментального пути') потока. Пометка узла используется для указания как величины потока, так и источника потока, вызывающего изменение текущей величины потока по дуге, соединяющей этот источник с рассматриваемым узлом.
Если ггг единиц потока посылается из узла г в узел 1' и вызывает увеличение потока по этой дуге, то будем говорить, что узел 1 помечается из узла ( символом о Аугментальныа путь называют также увелнчнваюгннм путем,— Прим. перев. 11* Г аг +дь В данном случае узлу 1 приписывается пометка (+дь 1). Аналогично если посылка дг единиц потока вызывает уменьшение потока по дуге, то будем говорить, что узел 1 помечается нз узла 1 символом — дь В данном случае узлу 1 приписывается пометка ( — г)ь 11. Текущий поток из узла 1 в узел 1 увеличивается, когда дт единиц дополнительного потока посылается в узел 1 по ориентированной дуге (1,1) в направлении, совпадающем с ее ориентацией. В данном случае дуга (1,1) называется прямой.
Соответствующий пример показан на рис. 2.47. ~' — © (ч,о пг ьр чу Рис. 2.47. Если узел 1 помечается нз уела 1, то поток по дуге (1,1) увеличивается, поскольку дуга (1,1) является прямой. Рис. 2.48. Если узел 1 помечается иа узла ~, то поток по дуге (1,1) умень. шается, поскольку дуга (1,)) являет. ся обратной. Текущий поток из 1 в 1 уменьшается, когда д; единиц потока посылается в узел 1 по ориентированной дуге (1, 1) в направлении, противоположном ее ориентации. В этом случае дуга (1, 1) называется обратном. Соответствующий пример показан на рис. 2.48.
Если узел 1 помечается из узла 1 и дуга (1,1) прямая, то поток по данной дуге увеличивается и величина, соответствующая оставшейся неиспользованной пропускной способности дуги, должна быть нужным образом скорректирована. Данную величину обычно называют остаточной пропускной способностью дуги. Читатель может легко установить, что если некоторому узлу приписывается пометка и при этом используется прямая ветвь, то она может иметь только положительную «остаточную пропускную способность».
Кроме того, узел 1 может быть помечен из узла 1 только после того, как узлу 1 приписана пометка. Аугментальный путь потока из з в 1 определяется как связная последовательность прямых и обратных дуг, по которым из з в 1 можно послать несколько единиц потока. Поток по каждой прямой дуге увеличивается, не превышая при этом ее пропускной способности, а поток по каждой обратной дуге уменьшается, оставаясь при этом неотрицательным.
Аугментальный путь потока используется для выбора такого способа изменения потока, при котором поток в узле 1 увеличивается и при этом для каждого внутреннего узла сети не будет нарушено условие сохранения потока. Детеряинированнае нотона в сетях 2.мс1. ПРОЦЕДУРА РАССТАНОВКИ ПОМЕТОК ДЛЯ ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ Задача о максимальном потоке часто встречается на практике, причем число узлов н дуг в сети нередко достигает нескольких тысяч. Поэтому для решения таких задач необходимо использовать эффективную процедуру вычислений.
Благодаря простоте постановки задачи о максимальном потоке был разработан эффективный рекуррентный алгоритм поиска оптимального решения (максимального потока), использующий процедуру расстановки пометок. Перейдем к описанию этого алгоритма. Пусть (1, 1) — ориентированная дуга, ведущая из узла 1 в узел 1. В каких случаях поток по данной дуге может быть увеличен? Как отмечалось выше, поток можно увеличить на у1 единиц, если дуга (1,1) является прямой н узлу 1 приписывается пометка [+дь 1]. Остается выяснить, когда это имеет место. Предположим, что дуге (1, 1) уже приписан поток )п) 0 (1п(стп). Очевидно, что величина д; не может превосходить остаточной пропускной способности (тт1 — Тп.
Достаточно ли этого, для того чтобы пометить узел 1? Нет, поскольку из узла 1 не всегда можно получить (1и — )и единиц потока. Отметим, что в узел 1 можно послать столько единиц потока, сколько их добавляется в узел 1, т. е. самое большее дн Следовательно, поток по прямой дуге (1, 1) можно увеличить на величину д1, где а=пни[да Уу — [н]. Точно так же можно пометить узел 1, если дуга (1, () является обратной. Здесь возникает следующий вопрос: возможно ли уменьшение потока по дуге (1, ()? Очевидно, что это возможно только в том случае, когда )п)0. На сколько этот поток может быть уменьшен? Самое большее — на число единиц потока, которое можно взять из узла й т.
е. на величину дь Следовательно, поток по обратной дуге (1, 1) может. быть уменьшен на величину чь где с?1=ш(п[Ф* Ь]. Алгоритм расстановки пометок работает следующим образом. Вначале источнику приписывается пометка [оо, — ], указывающая на то, что из данного узла может вытекать поток бесконечно большой величины. Далее мы ищем аугментальный путь потока от источника к стоку, проходящий через помеченные узлы. Все узлы, отличные от источника, в начальный момент не помечены. Пытаясь достичь стока, мы проходим по прямым и обратным дугам и последовательно помечаем принадлежащие нм узлы.
Возможны два следующих случая: 1. Стоку 1 приписана пометка [+дь А]. В этом случае аугментальный путь потока найден и поток по каждой дуге этого пчти может быть увеличен или уменьшен на величину дт. По- 166 Г 2 еле изменения дуговых потоков текущие пометки стираются и вся описанная выше процедура выполняется заново.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
