Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 24
Текст из файла (страница 24)
Узел Л'з имеет два непомеченных соседних узла, а именно М~ и Жо Узел Л', в данный момент не может быть помечен, а узел Ф~ получает пометку 12, 11, поскольку хсз —— — 1 ) О и е (1) = = пнп [е (2), х„] =- ппп (1, 1) = 1. Теперь узел Ж, помечен и просмотрен, а ]У, помечен и пе просмотрен. Узел Ф, имеет только один соседний непомеченный узел, а именно Лго Узел Ю„должен получить пометку [1", 11, поскольку е (1) = ш[п [е (1), ܄— хы] =- ппп И, 3 — 01 =- 1. 1'езультат этой расстановки пометок изображен па рис. 8.5. Так как узел Ж~ оказывается помеченным, то переходим к шагу 2. Ш а г 2.
Так как пометка узла .Т~ есть [1", 1], то увеличиваем х„па 1. В результате получаем х,'с ' — — х„+ 1 =- О + 1 = 1. [2, 1) (з~ о) (г+, 1) Р и с. 8.5. Р и с. 8.6. Переходим к узлу Хп обладающему пометкой [2, 11, и уменьшаем х< з па 1. Получаем х[з — — х, з — 1 .= 1 — 1 = О.
Переходим к узлу Хю имеющему пометку [з', 1), и прибавляем 1 к хмо Получаем: х,'з = х,з + 1 =- 1 + 1 = —. 2. Окончательный результат операции изменения потока иаображен па рис. 8.6. 16 т. хт Гл. 8. ХАксимАльный ~Оток 446 Ш а г 3. Приписываем пометку (8', оо) узлу Ж,. Теперь узлы Л', и Фэ не могут быть помечены, н узел Х, оказывается непомеченным. Конец. Сделаем два замечания. Во-первых, мы увеличиваем поток (рис.
8А), посылая единицу потока по слсду1ощсму пути, увеличи- ваюЩемУ поток: Л'„А,81 Уэ, А,ю Хн Аы, Юо Если бы не было потока по дуге А,э, то нельзя было бы послать поток иэ Хэ в Л „ потому что А18 — ориентированная дуга. Но когда уже имеется ненулевой поток по дуге Ано можно послать поток из Л'8 в Л'„ и в результате новый и прея8ний потоки по этой дуге взаимно уничтожатся. Во-вторых, здесь получается минимальный разрез (Х, Х), гДе Х вЂ” зто еДинственный Узел Л'„а Х вЂ” тРИ Узла Хы Л'8, Л'ь Заметим, что (г, А"), где Г =(ХО Хэ) — тоже минимальный разрез с пропускной способностью, равной Ь„+ Ьэ, + Ьм —— = 1 + 0+ 2 = 3. Здесь Х с: Г.
Как уже отмечалось выше, алгоритм расстановки пометок всегда дает такой минимальный разрез (Х, Х), что Х вЂ” наименьшее среди упорядоченных по включению подмножеств узлов. Если пропускные способности Ьы не являются все целыми числами, то алгоритм может не быть конечным и может да>ко сходиться не к максимальному потоку. Такой пример построен Фордом и Фалкерсоном [67]. Это показывает, что метод расстановки пометок не эквивалентен симплекс-методу для задач линейного программирования. Так как задача о потоке в сети является частным случаем задачи линейного программирования, а симплекс- метод работает при любых действительных числах, то доллэен существовать алгоритм решения потоковой задачи, в которой пропускные способности дуг являются любыми действительными числами.
Перейдем к рассмотрению такой модификации метода расстановки пометок, которая применима для любых неориептирова~яых сетей с действительными пропускными способностями. Ш а г 1. Удалим'иэ сети все дуги, для которых выполняется хы = Ьы, 'такие дуги будем называть насыщенными потоком. (В самом начале нет насыщенных дуг, так как хы — — О.) Переходим к шагу 2. Ш а г 2. Используя любые оставшиеся в сети дуги, находим с помощью метода расстановки пометок произвольный путь, увеличивающий поток; посылаем по нему максимально возможный поток. Если такой путь нашелся, то переходим к шагу 1; если же нет, переходим к шагу 3.
зов МЕТОД РАССТАНОВКИ ПОМЕТОК Ш а г 3. Восстанавливаем в сети всв ранее удаленные дуги (т. е. все дуги, насыщвнныв потоком). Находим некоторый путь из Ог, в ЖО увеличивающий поток, и посылаем по нему максимально возможный поток. Если такой путь нашелся, то переходим к шагу 1; если же нет, то алгоритм закончен и найденный поток— максимальный., Докажем, что этот алгоритм конечен и дает максимальный коток. При каждом изменении потока на шаге 2 по крайней мере одна ноеая дуга окаэыеаетея насыщенной потоком.
После того как шаги г и 2 будут повторены друг за другом некоторов конечное число раз, из сети будет удалено такое количество насыщенных дуг, что уже нельзя будет на шаге 2 получить поток с большей величиной. Если при этом на шаге 2 использовать метод расстановки пометок, то будет помечено некоторое множество узлов Х, а все такие дуги А ы, что ОГ; Е Х, ДГЕ с Х, будут насыгцены потоком.
(Заметим, что поток может идти по дуге в любом направлении.) Величина потока при этом равна Х хц — Х хы = Х Ьц — Х Ьэг'). ЦЕХ, КгЕХ Ф~ЕХ, УЬЕХ Ф~ЕХ, Л .ЕХ Кфх, Лу Х После этого переходим к шагу 3 и восстанавливаем в сети все насыщенные дуги. Теперь можно пометить любой узел Фю который принадлежал Х па шаге 2, если имеется дуга с х„~ О, где У~ ~ Х. Благодаря тому, что в сети восстановлены насыщенные дуги, узел Дг, попадет в множество Х и величина потока в сети возрастет. Затем мы снова перейдем к шагу 1, и когда опять вернемся к шагу 3, величина потока в сети будет снова равна разности ~~~~ ЬЫ вЂ” Я ЬАР Но величина потока пРи этом изменитсЯ, слеДова- 3 у ад тельно, в этот раз на шаге 3 суммы х~, Ьен ~' Ьэ, берутся по другим гд ад множествам дуг (либо по твм же самым множествам дуг, что и в предыдущий раз на шаге 3, но некоторые из них проходятся в противоположном направлении). Так как в сети имеется конечное множество дуг и каждая дуга может быть насыщена потоком в одном из двух направлений, то величина ~Р» Ьгу — ',Р» Ьэ, может г) Сумма х~,.ЬП берется яо тем дугам АН, для которых Л~ЕХ, УГЕХ, Л;ЕХ ИТЕХ и хн)0.
Сумма ~ Ьэ~ борется по том дугам Аы, для которых У8ЕХ, н~ех ьаЕх Дг~ Е Х, и хю) О.— Прим. перев. гл. н млггснмальныи поток 148 припимать конечное множество различных значений. Каждый раз, когда мы возвращаемся к операции 3, величина потока принимает одно из значений ~ ~Ьп — 2 Ьаь ПосколькУ каждый Раз ьз величина потока возрастает, то ни одно из этих значений не повторяется дватггды. Таким образом, алгоритм конечен. Этот яге алгоритм можно использовать и в сетях с ориентированными дугами, по доказательство этого факта довольно громоздко '). Трудность заключается в том, что при осуществлении процедуры изменения потока па шаге 2 поток по некоторой ориентированной дуге может взаимно уничтожиться с преткниат, по пи одна дуга при этом ке будет насыщена потоком.
Поэтому нельзя утверягдать, что на шаге 2 найдется по крайней мере одна новая дуга, насыщенная потоком. Теперь перейдем к изучению следующего вопроса: какое количество итераций в методе расстановки пометок требуется для нахождения максимального потока? 11аждый путь, увеличивающий поток, дает возможность увеличить величину потока по крайней мере на единицу. Если величина максимального потока равна о, то для нахождения максимального потока достаточно не больше чем о раз найти путь, увеличивающий поток. Предположим'теперь, что мы умножили на 10 все пропускные способности дуг. Тогда воличигта максимального потока в новой сети будет равна 10ш Это означает, что для нахождения максимального потока в сети достаточно самое большее 10и раз найти путь, увеличивающий поток.
Следовательно, полезно было бы иметь такую верхнюю оценку количества итераций в процессе расстановки пометок, которая пе зависела бы от величины максимального потока, пе известной до качала вычислений. Такая верхняя оценка была получена впервые Эдмокдсом н Карпом )58). Эта оцеяка справедлива н тогда, когда все пропускные способности дуг — действительные числа. Расстготрнаг подробнее эти результаты а). Сделаеы несколько замечаний и приведем модификацию метода расстановки пометок.
Для удобства будем считать, что сеть, имеющая и узлов, всегда содер кит и (и — 1) дуг, хотя некоторые дуги. могут обладать пропускной способностью, равной пулю. Если задан поток г в некоторой сети, будем использовать символ т) Зто утверждеяяе кс точно. Как показало в работе Пт*), в орясятярованных сетях с нррацкояалькымк лролускяымя скособвостямя дуг рассматркваемый алгорятмтможет не быть конечным. В этой жеуаботе приводится модкфнкацкя алгоритма, которая уже пркмелкма для энооых ориентированных сетей.— Прим. верею э) В переводе исправлены имеющиеся в орягкнале иогрешкостк к влессяыбуточлеккя, содержащксся в работе Здмоядса к Карпа)58*), ноявявшейся после выхода в свет данкой клнгн.— Прим. верее.
«л. мктод глсстлновни ттомвток ттг (Р) для обозначения отой сети вместе с текущим в пей потоком Р В сети Л (Р) дуга Аы может быть насыщепа (итт =- Ь„), и тогда можно считать, что дуги А»т в сети «не существует», поскольку все равно нельзя послать поток из узла»>»т в узел 7»'1 по дуге А„. Так как »кожно послать поток из»«'; в Дгт в сети т>» (Р), то можно считать, что в»»г (Р) имеется дуга Ап с пропускной способностью Ь,т =- л,т Паприктер, можно считать, что па рнс. 8А дуги А,з яе существует, а имеется дуга Аз, с пропускной способностью, равной 1.
В дальней>пен, говоря о сети»«' (Ьг), будем иметь в виду Р и с. 8.8. Р и с. 8.7, сеть, отличающуюся от исходной сети, в которой еще не было потока. Метод расстановки пометок, таким образом, порождает некоторую последовательность сотен: Ж (Рт), Х (Рз), . Д» (Г» ) где Р— максимальный поток. Поток Рк«т получается из потока Рк с помощью добавления в сеть»«' (Р„) некоторого пути, увеличивающего поток. При описании метода расстановки пометок мы до сих пор пе указывали, в каком порядке следует просматривать помеченные узлы.
Будем теперь придер»киваться правила «первым помечен— первым просмотрен». Так, в рассмотренном выше примере (рис. 8А) узел»>»з должен быть просмотрен перед узлом Л»„так как»>»з помечен раныие, чем 7»»т. При использовании правила «первым помечен — первым просмотрев> в методе расстановки пометок, каждый раз будет получаться увсличивагощий потоп путь, который содержит минимальное число дуг (если поток в сети еще пе максимален) '). Сделаем еще одно уточнение.
Если А,т, А,ю Аж,... ..., Аю — некоторый путь, увеличивающий поток, то определим е (7'+ 1) следующим образом:' е (7'+ 1) = ппп [е (7) ЬЬ ет— — и>с 7>т + л«>т,,]. ПРи таком моДифидиРованном опРеДелении пометки е (т' + 1) по крайней мере одна дуга в пути, увеличивающем поток, окая«ется насыщенной потоком, Рассмотрим сеть„ изображенную па рис. 8.7, где числа рядом с дугами означают >) В гл. 10 будет рассмотрен алгоритм Дийкстры ре;шения задачи о кратчайшем пути в сети. В случае когда длины всех дуг равны 1, он сводится к пранилу «первым помечен — первым просмотрен». Отсюда следует, что зто иравило приводит к'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
