Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 38
Текст из файла (страница 38)
9.5 представлены орграф 0=(1~, А) и его списки смежностей. Числа при вершинах указывают порядок, в котором вершины помечаются при использовании ПШ. Числа в скобках соответствуют ПГ. В силу присущей орграфам асимметрии понятие связности для них является более тонким, чем соответствующее понятие для гра- 3[7) 5(б) оь (оь ов) (о7) (о,, о4) (оь ов) а (вь, оь.
7) (оь, о„) А(о,) = А(в,) = А(оь) = А(ов) = Ашь) = 'ь("в ) А(в7) = 7(5) 2(2 о Ряс. 9,5. фов, и проверка связности в этом случае требует несколько петри. виального применения алгоритма ПОИСК (см. задачи 4 и 5). Наиболее важным свойством алгоритма ПОИСК, представленного на рис. 9.1, является то, что это не один алгоритм, а модель для целого класса алгоритмов. Варьируя части программы, заклю. ченные на рис. 9.! в рамочку, можно создать множество алгоритмов, которые будут по-разному обрабатывать один и тот же граф, следуя в общих чертах алгоритму ПОИСК. В качестве простого примера предположим, что вместо часчн помепьить о на рнс. 9.1 вставляются команды счет:=- счет -( 1, порядок (о):=- счет каждый раз, когда используется оператор пометить, н переменной счет присваивается начальное значение 0 в первом выделенном прямоугольнике.
В результате получаем алгоритм, регистрирующий порядок, в котором ПОИСК посещае7 вершины (вспомните рис. 9.3 и 9.5). Другим примером может служить алгоритм пометок Форда — Фалкерсона, обсуждавшийся в гл. б, который, как нетрудно видеть, в действительности являечся более хитрым вариантом алгоритма ПОИСК. Близким примером служит задача нахождеьььия путей в орграфах, которую мы сейчас рассмсп рим подробно. 9.!. Г)омск по графу Пусть дан орграф Р=()г, А) и два множества вершин 5, Т: — )г, соответственно испгочники и цели.
Нужно на(пи путь в Р, идущий из любой вершины множества 5 в любую вершину множества Т. Не удивительно, что эту задачу можно решить, используя легкую АЛГОРИТМ НАЙТИПУТЬ Вход. Орграф 0=(У, А); два подмножества ь, Т нз У. Выход. Путь в 0 нз некоторой вершины подмножества Б в некоторую ве(ь шину подмножества Т, если такой путь существует. Ьея! и !ог ан чаев до пометка(ч]:= О, и чЕТ рлеп ге!игл (ч)1 ! О:=В; м)И1е Я Ф в до Ьеа(п пусть ч †люб элемент нз 01 удалнть ч нз С); (ог ан ч'ЕА(ч) до И ч' не помечена (Ьеп Ьей1п аомгагки(ч'); = ч; И ч'ЕТ щеп ге!игп ПУТЬ(ч') ! еые аобаввть ч' к 1,1 ) епд епд ге1игп ав 0 нет пути нз э в Т» епд ргоседиге ПУТЬ(ч) (сопнпепг; она выдает последовательность вершин от ьЕБ до ч) И пометка(ч) =.
О жеп ге1игп (ч) е1зе геыгп ПУТЬ(пометка (ч)) !! (ч), (сопппеп1: ПУТЬ вЂ” рекурсивная процедура; см. задачу б нз гл. В; 1 обозначает конкатенацию путей, т. е, запись вх подряд), Рвш 9.6. Алгоритм НАЙТИПУТЬ. модификацию алгоритма ПОИСК. Единственные отличия состоят в том, что теперь в качестве начального значения Я берется не (ит), а 5 и для каждой рассматриваемой вершины и' мы ие просто помечаем ее, а делаем несколько больше. В частности, мы полагаем: номе!яка (р') (где пометка — это массив с ))г! элементами) равна предшественнику о вершины о', из-за которой и' рассматривается.
Эти пометки должны помочь при явном нахождении пути из 5 в Т. По определению вершины в 5 имеют пометки О. Полный алгоритм приведен иа рис. 9.6. Пример 9.4. Предположим, что мы хотим найти путь из 5 в Т в орграфе Р, представленном на рис. 9.7(а). Пометки вершин орграфа Р в конце алгоритма показаны на рис, 9,7(б). Мы применяем ПОИСК в варианте ПШ; при этом находим крапгчайииГ1 путь из 5 в Т, т. е. путь с наименьшим числом дуг. В результате находим, Гм 9.
Задача о максимальном аотоко что и, б Т. После этого вызываем процедуру ПУТЬ с аргументом о„. ПУТЬ(о„) вычисляется последовательно и дает (а) ов ив ов "в (б) Рис 9.?. ПУТЬ(ов) — ПУТЬ(пв)((ов) = ПУТЬ(пв!',(пв, пв) = = ПУТЬ(пь)~~(ов ов "в) =- ПУТЬ(пв)П(по ив ов пв)=(пв, оь ов ов ов) и последний путь действительно является кратчайшим путем из 5 в Т. Такое нахождение путей в орграфах имеет удивительно много приложений при решении некоторых намного более сложных комбинаторных задач оптимизации.
В этой и трех последующих главах У.г. Что нехорошо в алгоритме оометохя гон мы разработаем зфрек>ивнь>е алгори>мы для ряда комбпиаторных задач, которые в большой с>епепи сновапы па использовании последовательных итераций типа увгличгншй не сильно отличающихся от гех, что использовались при репкчши задачи о максимальном потоке в гл 6. Во всех этих задачах мы заметим, что иаш алгоритм сводится к нахождению пугей, ведущих из множества источниковых вершин и множество целей в неко>ором всиоло,.шиельноз> орграфе.
Такой поиск и будет обшей чертой, объединяющей э>и различные алгоритмы. 9.2 Что нехорошо в алгоритме пометок! о Рис Всз При анализе сложносчи алгори>ма пометок для задачи о максимальном потоке иа сечи й>==(т й (г, А, Ь) (см. пример 8.7) былоотмечено, что каждый этап >рсбует времени 0((А(); следовательно, весь алгоритм имее> сложное>ь 0(5)А)), где 5 — число производимых увеличений по>ока. Число 5 должно бьп ь не больше (Д вЂ” величины максималыюго потока ь сечи (в предположении, что пропускные способности целочислснны).
Может ли 5 равняться >ч'(? Очвет— да, если мпогокрачно про>ыьо ь»ся неудачный выбор увеличивающих о путей. Пример 9.6. Расс>>о>риь> сечь, >000 >000 представленную иа рис. 0.8. Очевидно, чп> максималышя аг личина потока в этой сс>п равна 2000. (!рпменим к эчой сс>и ал» >000 ритм помеп>к, начиная г иулсвш> потока.
На первой >перации н ка. честве увеличиваю>пего пути мо кно взять путь (5, Р, >!, (), что приводит к потоку величины Е [(а второй ичерацин ножн> уьеличигь поток вдоль пучи (э, и, и, (); так как (о, и) в данный >и>> шп —. абра>ная дуга, >о ю>п путь также допустим согласно ал>ор>пму помо>ок, Величина нового почока равна 2 Легко виде>ь, мо в качесгвс уяеличива>ощих пу ей можно поочередно выбирать (з, и, о, () и (з, о, и, 0, при этом ьеличина по тока будет увеличивачься иа единицу на каждой итерации.
Таким образом, нам придется выполи>пь 2000 и>ерацпй прежде, чем мы придем к оптимальному почоку Если пропускные способности соответствующих четырех дуг положить равными не !000, а произвольному целому числу гв(, то число итерапий буде.> расги как 2~И, То есть алгоритм помечок в худшел> случае требует экспоненциального числа шагов (вспо'п>пе обсуждение в ф 8.5), К счастью, можно >избежать этой экспоненциальной сложности, Гм У. Задача о максимальном аогаоче 206 несколько аккуратнее выбирая увеличивающий путь. Увеличивающие пути, которые мы выбирали в примере 9.5, неудачны тем, что онн длиннее, чем нужно То есть если бы мы выбрали увеличивающий путь (з, о, () вместо пути (К и, о, (), который на одну дугу длиннее, то мы получили бы большой выигрыш в величине потока и существенно уменьшили общее число требуемых итераций, Попробуем (и, +) (о, +) Рис.
9.9. (л е) использовать это наблюдение как предложение для улучшения алгоритма пометок, а именно будем на каждой итерации нскагь самый короткий увеличивающий путь относительно име«щцегося потока. Лрн этом сложность итерации не возрастае«, поскольку выбор нужно«о пути можно осуществить, как будет показано в 2 9.3, просто производя процесс расстановки пометок по принципу «в ширину». Нельзя утверждать, что увеличение потока вдоль кра«чайших путей всегда больше, чем увеличение вдоль более длинных путей; например, если поменять местами пропускные способности дуг (з, и) и (и, и) на рис.
9.8, то увеличение вдоль пути (з, и, и, () будет давать больший выигрыш, чем увеличение вдоль пути (з, и, () Однако, систематически выбирая кратчайший из возможных увеличивающих путей, мы избегаем патологий, подобных «ой, что указана в примере 9.5, а именно многократного выбора малых увеличений. В действительности если всегда выбирать кратчайший из возможных увеличивающих путей относительно данного потока, то можно доказать, что будет не более ф ° )А) этапов.
Грубо говоря, это следует из то)о факта, что при использовании такого правила каждая дуга (и, и) не более )Ц раз может использоваться как перешеек в увеличивающем пути (см. задачу 9), Мы не будем здесь детально рассматривать эти соображения, поскольку в 9 9А будет получен более сильный результат, Следующий пример демонстрирует другой аспект ««расточительности» исходного варианта алгоритма пометок, Пример 9.6. Применим алгоритм пометок к сети, представленной на рис. 9.9. При выполнении первого этапа можно обнаружить увеличивающий пусь (ь, о, г, () и увеличить поток. Пометки в конце первого этапа показаны на рис.
9.9 Причем это кратчайший увели- у,э, Расстановка пометок на сети и попок по орграфу 207 чивающий путь, и е. мы даже включили в алгоритм наше предыдущее предложение. В этом месте алгоритм новичок иогрсбовал бы стереть все пометки и начать следую1ций этап На следующем этапе мы обнаружили бы увеличивающии путь (э, и, ш, (). Интересно, однако, го, что в процессе обнаружения эзого п)зи пы использовали бы почти исключизельно почечки, лосзуипые ппч на предыдущем этапе. Иными словами, этот пугпь лшэкно босло найти, цспользул инфорл<ацию, доступную в шеи ние предыдущего эпгапа.
Следовазельно, стирание пометок — это потеря позгнпиальпо полезной информации, и поэтому желательно не переходш ь к следующей итерапии, пока не будет уверенности в том, что имеющиеся пометки не могут дать никакого вьпшрьппа. Д В й'9 4 мы опишем улучшенный алгоритм пометок, в котором объединим эзи две иден, и именно увеличение вдоль кратчайших пузей и более чем одно увеличение па каждой итерации, для построения эффекзивного алгори1ча для задачи о максимальном потоке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
