Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 40
Текст из файла (страница 40)
мого в следующем параграфе. 9.4 Алгоритм нахождения максимального потока со сложностью 0( ~ У ('] Наш алгоритм нахождения максимального потока — подобно многим другим комбинаторным оптимизационным алгоритмам, описываемым в последующих главах,— работает по этапам. На каждом этапе строится сеть ГО (1."), где 1' — текущий поток, и по ней находится вспомогательная сеть А М (1). Затем находится тупиковый поток д в ЛМ(1), который добавляется к (, и процесс повторяется.
Добавление й к 1' состоит в прибавлении а(и, о) к 1(и, о) для всех прямых дуг (и, о) из АМ(1) и вычитании й(и, о) из ) (а, и) для всех обратных дуг (и, о) из АМ(1). Процесс оканчивается, когда ь' и ( оказываются не связанными в М((), что означает оптимальность потока (. Основной частью нашего алгоритма является умный способ нахождения тупикового полока д в слоистой сети АМ(1).
Мы не будем увеличивазь поток вдоль отдельных путей; на этот раз мы Гл. У. Задача о максамальном лотоке м = О ч ч м 9.4. лагорио»и нахождении наксимааьеоео попижа З1З попытаемся протолкнуть поток через вершины одновременно вдоль многих путей. Проиллюстрируем это примером. Рассмотрим слоистую сеть, представленную на рис. 9.12.
Определим сквозную пропускную способносглв (спс) вершины о как максимальное количество потока, которое можно протолкнуть через ш т. е. спс Ь! — это сумма пропускных способностей дуг, входящих в в (ао, если о =з), либо сумма пропускных способностей выходящих дуг(оо, если и= — 1) в зависимости от того, какое из этих чисел меньше. Таким образом, в примере на рис 9.12 (а) имеем спс(о,1 =-.3 и слс(о»)=4.
Если попытаться протолкнуть четыре единицы потока через о,„то сразу же обнаруживается, что их придется послать в о„. Если попытаться дальше протолкнуть четыре единицы потока, которые пришли в о„, то обнаруживается, что это невозможно, и, следовательно, нам приходится терять время на возвращение назад.
Рассмотрим, однако, лейсгвительные причины этого. Вершина ем с которой мы начали, имеет достаточно болыпую сквозную пропускную способность. Поэтому было довольно очевидно, что мы застопоримся в некоторой вершине с меньшей сквозной пропускной способностью— в нашем примере о«. Однако этого никак не могло бы случиться, если бы мы начали с вершины, имеющей наименьшую сквозную пропускную способность. Попытаемся поэтому начать с вершины, имеющей минимальную сквозную пропускную способность, на.
пример о,. Распределим три единицы потока между дугами (о„о») и (вп о«), полностью используя их пропускные способности, Поток, пришедший в вершину о;„лолжен пойти теперь по дуге (о„о„) Мы могли бы далее продолжать проталкивать эту единицу потока вплоть до 1 по принципу «в глубншу», однако мы не будем лелать этого. Вместо гмого мы подождем, пока соберется весь поток, который должен пройтп сквозь о„, и обработаем его затем сразу весь. Это означает, что мы никогда не обрабатываем вершину до тех пор, пока не будут обработаны все вершины предыдущего слоя, т.
е. мы движемся от вершины к вершине по принципу «в ширину», Теперь понятно, как обрабатывать вершину. Возьмем вершину о„следующую за о» Нужно вытолкнуть из нее две единицы потока Проделаем это организованно. 11росмотрим все ребра по очереди и заполним их ло их полной пропускной способности либо до момента, когда все требуемые единицы потока будут вытолкнуты.
Так, например, в вершине о« можно вначале рассмотреть дугу (о„о„) и полностью насытить ее. Допустимо также было бы рассмотреть сначала (о„о,) и протолкнуть весь поток в две единицы по этому ребру; однако нашей стратегии противоречило бы неоправданное распределение по олной единице на каждую из дуг (в«, о„) и (о„о,).
Далее мы проталкиваем все трп единицы из о«в о„(хорошо, что мы подождали и пам не пришлось оорабатывать о„дважды) и, наконец, проталкиваем три единицы из ц и д Заметим, что на протяжении этого шага нам не нужно беспокоиться о том, чтобы обрабатываемые вершины имели соответствующую сквозную пропускную способ- Гл. э. Задача о максимальном потоке 214 ность. Зто следует из того, что на каждом слое оощее количество входящего потока, распределенное среди вершин этого слоя, равно спс(о»). Поскольку вершина о, имела наименьшую сквозную пропускную способность, никакая вершина никог!а не будет иметь дело с количеством потока, ббльшим, чем ее сквозная пропускная способность, и, следовательно, пе потребу'ется возврата назад.
Для получения правильного потока иеооходимо привести некоторый поток из в в о,. Однако это абсолютно симметрично тому, что мы проделали, и поэтому можно пройти по дугам в обратном направлении, начиная с вершины и, и обрабатывая вершины слой за слоем тем же способом «в ширину» н входящие дуги так же организованно, как и выше, эффективно протягивая поток. В нашем примере это очень легко сделать: достаточно протянуть три единицы потока из э в оь Окончательный ноток д приведен на рис. 9.12 (а).
Поток у» не тупиковый, и, следоватеяьпо, нам нужно продолжать ту же процедуру. Модифицируем пропускньш способности, чтобы отразить тот факт, что уже получен поилок ди и придем к слоистой сети, приведенной на рис, 9.12 (б) (дуги с нулевыми пропускными способностями опущены). Пытаясь найти вершину с наименьшей сквозной пропускной способностью, обнаруживаем, что о, и о„имеют нулевую сквозную пропускную снос<к»ность Поэтому эти вершины (и все инцидентцые им дуги) можно удалить из сети.
Окончательно приходим к сети, представленной на рис. 9.12 (в), Теперь наименьшую сквозную пропускную способность, а именно 1, имеет вершина и„, и мы тем же методом находим поток ໻— этот поток оказывается просто увеличивающим путем.
После пересчета пропускных способностей и удаления бесполезных дуг и вершин приходим к сети, представленной на рис 9.12 (г). Теперь вершина о„имеет наименьшую сквозную пропускную способность; соответствующий поток д» вЂ” снова путь — показан на рис. 9.12 (г). После пересчета пропускных способностей и удаления бесполезных вершин и дуг обнаруживаем, что вершина ь удалена. Как будет показано, это означает, что суммарный полученный поток д=д,+ +д»+д» является тупиковым, и этап оканчивается. Полностью алгоритм приведен на рис.
9.13. Чтобы показать его корректность и получить временную оценку, нам нужны некоторые предварительные результаты. Лемма 9.!. Дуга а сети АМ(!') удаляется из В на некотором этапе только в том случае, если в А йг (1) нет прямого увеличившои(его пути относительно потока д, проходяи(его через а, Доказательство Если дуга а удаляется на некотором этапе, то либава(а)=ас(а), либо а=-(о, и) и о или и имеетнулевую сквозную пропускную способность.
Предположим, что д(а)=ас(а). Это означает, что и может появиться в увеличивающем пути относительно д в сети АЛ1()) 1олько как обратная дуга. Получаем требуемый ре- умй Алгоритм нахождения максимального патако АЛГОРИТМ ПОСТРОЕНИЯ МАКСИМАЛЬНОГО ПОТОКА Вход. Сеть Н --- (з, 1, У, А, Ь). Выход, Максимальный латок 1 в Н.
Ьед1п 1 = О, выполнена: = «неть; (сопипеп1: задание начальных значений) вЛИе выполнена=«нет«бо Ьей!п (сошгпеп1: новый этап) й;=О; построить вспомогательную сеть АН (1) =-(з, 1, (), В, ас); И 1 не достижима из з в АХ (1) Гйеп выполнена: =«да«е1зе гереа( Ьей!п пЫ!е имеется вершина ч, для которой слс[ч) О бо 11 ч.=з илн ч=-1 Гйеп йо го увглнч е1эе удалить ч н все ннцидентные ей дуги иа Аг((1); пусть ч — любая вершина из АН(1), для которой сис[ч) принимает наименьшее значение (сопипеп1: отличное от нуля); ПРОТОЛКНУТЬ (ч, сис[ч)); ПРОТЯНУТЬ (ч, спс[ч)) епд увели«: 1:=1+а епб епб ргосебиге ПРОТОЛКНУТЬ (у, Л) (сопипеп! ана увеличивает поток д на Л единиц, нроталкиваемых из у в 1 «систематическими способом) (сош1пеп1: процедура ПРОТЯНУТЬ совершенно аналогична) Ьей!п б):= (у) 1ог а!! иц(! — (у) бо треб[и):= О; треб[у):= Л (сопипеп!: треб[и) указывает, сколько единиц потока должно быть нытолкнуто из и) пЛИе (й Ф Я бо Ьей(п пусть ч †элеме нз О,' удалать ч из О, (сопнпепг: 1) должна быть очередью) 1ог аИ ч', таких, что (ч, ч') ЕВ апб ип!И треб[ч) =О бо Ьей(п пс= ш!п(ас [ч, ч'), треб[с)В ас[ч, ч'[:= ас[ч, ч)) — ш; И вс[ч, ч') =О 1Леп удалить (ч, ч') нз В; треб[с'с=- тргб[ч) — ш; гиреб[ч ):= гаргб[ч')+и; добавить ч' к О; й [ч, ч'):= д [ч, ч')+ш епб епб епб Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
