Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 23
Текст из файла (страница 23)
Пример, принадлежагдий Форду и Фалкерсону !Гг), показы. вает, что в том случае, когда пропускные способности иррацио. пальцы, рассматриваемый метод не галька может не останавливаться, ио може«акже сходиться к потоку, величина которого строго меньше о<и ималь«ого значения! Эдмонде и Карп (ЕК! предложили модификацию алгоритма поме<ок и показали, что их модифицированный алгоритм пометок требует не более чем (по — п)74 итера ций увеличения потока независимо от величин пропускных спо.
собностей. Л4ы не будем здесь ~рачить время на описание их идей, поскольку позже обсудим даже более эффек<явные алгоритмы нахождения максимального потока (см. задачу (О в гл 9). Мы, однако, приведем упочянут<лй пример Фор.<а и Фалкерсона, поскольку он дает возможность лучше понять работу как прямо- двойственного алгоритма, так и алгоритма помезок Поток в этом примере будет увеличиваться шаг за шагом, причем л-й ~паг (г<)1) будет состоять из двух операпий увеличения потока соответственно на величины аол, и а„+, При этом величины а; будут удовлетворя<ь разностному уравнению 6.3. Проблема конечности алгоритма пометок )з( А1 х, У1 Г4 (а) о Х' о Уч У4 о х г о4 (нг Х4 о (в) Рис.
6.9. Патоло~ ический пример для алгоритма Форда и Фалкерсона, а) Сеть 6) и в) Первая н вгорая части вага п. Показаны только дуги увеличивакяцих ну~ей. ными пропускными способностями (О, и„, ал„„а„„), Упорядочим соответственно х,: и у';. Увеличение п(а) Выберем увеличивающий путь (а, х,', г(ь х„., уа', г), при ятом остаточные пропускные способности будут равны (О, а„+„О, а„+,) (см.
рис. б.9(б)). !32 Рл. б. Алеоритлал Форда — Фалкерсона а Дейкстрел Увеличение п(б). Выберем увеличивающий путь (э, х,', ул', д,', л'„а,', х,', у,', 1), при этом остаточные пропускные способности будут равны (а„л„О, а,„„а„„) (см. рис, 6.9(в)). Остаточные пропускные способности в конце шага и пригодны для начала шага и+1, и, используя индукцию, можно показать, что каждый шаг увеличивает поток на величину а„л,+а„+л — — а„. Получаем требуемый пример, в котором алгоритм не останавливается.
В действительности максимальный поток в рассматриваемой сеги равен 45, так что алгоритм Форда — Фалкерсона достигает только одной четверти величины оптимального потока. Как примирить этот пример с тем фактом, что рассматриваемый алгоритм получен в результате применения прямо-двойственного алгоритма? Прежде всего напомним, что (как отмечено выше) результат о конечности прямо-двойственного алгоритма (теорема 5.4) в данном случае не применим, поскольку мы не используем симплекс-алгоритм для ограниченной прямой задачи ОП и не имеем механизма устранения зацикливания. На самом же деле задача ОП сильно вырожденна (имеет всего одну ненулевую компоненту в правой части), всегда имеет оптимальное значение! и зацикливается. Задача ДОГ!, двойственная к ограниченной прямой задаче, также зацикливается, поскольку увеличивающие пути повторяются в фиксированной последовательности.
Между тем в двойственной задаче Д, т. е. в самой задаче о максимальном потоке, величина потока возрастает монотонно. Отсюда видно, что использование прямо-двойственного алгоритма для построения специализированного комбинаторного алгоритма песе~ с собой определенную опасность. Оно возлагает на нас отвелственносзь за правильное разрешение неопределенностей для обеспечения конечности алгоритма. Например, в случае задачи о максимальном потоке необходимо указать, как выбирать увеличивающие пути так, чтобы избежать катастрофы, подобной только что описанной. Стоит сказать, однако, что вопрос о конечности, поднятый примером Форда и Фалкерсона, в некотором смысле более математический, чем практический, поскольку цифровые вычислительные машины всегда работают с рациональными числами.
В наших дальнейших рассмотрениях, особенно касающихся сложности вычислений, всегда будет предполагагься, что данные могуг быть представлены с помощью конечного числа двоичных разрядов. При этом возникает практический вопрос, связанный с вопросом о конечности алгоритма, о том, сколько шагов как функция общего числа двоичных разрядов в данных может потребоваться для вычисления. Ниже, в гл.
9, мы увидим, что некоторое усовершенствование основного алгоритма увеличения потока обеспечит хорошее поведение в этом смысле. б.й. Алгорппхи дейкстры !ЗЗ 6.4 Апгермтм Дейкстры Опишем ~еперь детали эффективной реализации прямо-двойственного алгоритма для задачи о кратчайшем пути, построенного в гл. б,— алгоритма Дейкстры. Напомним читателю, что веса сы всех дуг в задаче о кратчайшем пути предполагаются неотрицательными. В дальнейшем будет видно, что это важное ограничение. АЛГОРИТМ ДЕЙКСТРЫ Вход. Орграф [З=[Ч, А) со стоимостями сч„~п его дуг; вершина а~Ч.
Выход, Массив р кратчайших расстояний ог и до всех ч~Ч. Ьей[п положить гЧ.=-(а); р [а):=О; 1ог а11 уЕЧ вЂ” (х) бо р [у1:= с,„; п[М1е тЧУ а Ч бо Ьей[п найти ш!п (р [у[; ухе'гЧ), скажем р [х); положить тЧ:= Ус[[[к): 1ог а11 уЕгЧ вЂ” хЧ йо р [у1:= ппп (р [у), р [х[+с„„) епб епб Рис. 6.10. Алгоритм Дейкстры. Вместо распространения неизменяющихся пометок назад от вершины [будем двигаться вперед из вершины в. На каждом шаге у нас будет множество вершин [Р и пометки р (х) для всех х Р У, обладающие свойством р(х) =(кратчайшая длина пути из в в х, в хопюром все промежуточные вершины принадлежат [и').
(б,9) Рассмотрим вершину х([Р' с наименьшим значением р(х). В крагчайшем пути из в в эту вершину х все промежуточные вершины принадлежат Ж', ибо в противном случае значение р(х) не было бы наименьшим среди всех пометок, приписанных вершинам, не входящим в В' (мы воспользовались неотрицательностью весов сн). Поэтому можно добавить х к Ф' и вычислить новые значения пометок р(у) для у[[[у' по формуле р(у)=пип(р(у), р(х)+с„„) для всех у([аг. (б.!О) Эта формула показывает, что либо р(у) для у([Р' не изменяется при добавлении х к [[у, либо новое Р(у) равняется кратчайшему расстоянию от в до х по вершинам из [[у плюс расстояние непосредственно от х до у (см.
задачу 4). Когда Гб' совпадет с [г, р(х) будет кратчайшим расстоянием из з в х без каких-либо дополнительных ограничений. Вначале положим [го=о, все р=-со и будем начинать алгоритм с добавления з к [Р'. Описанный алгоритм приведен на рис. б.10, В нем предполагается, что с„а=-оо, если дуга (х, у) отсутствует.
)34 ' г"а, б. Алеорптмы Форда — Фалаерсона и Дейкстры На рис. 6.11 показана последовательность шагов применения алгоритма Дейкстры к задаче о кратчайшем пути, использованной в примере 1 гл. 5. Кратчайший путь относительно легко восстано. (а) (г) 2 (в) (е) Рнс. б, П. Последовательные этапы прняенення алторнтна Дейкстры. вить обычным способом — для этого достаточно в каждой вершине отмечать, откуда пришла ее пометка в соответствии с (6ДО).
В рассматриваемом примере каждый раз, когда вершина добавляется к (р', соответствующая дуга штрихуется. В результате получается дерево с корнем в ь, содержащее кратчайшие пути из а во все остальные вергпины. Время работы алгоритма Дейкстры можно оценить сверху следующим образом Число шагов на каждой итерации пропорпионально числу вершин, ие входящих в (1т, которое не превосходит и Поскольку происходит и итераций (включая начальное ггрисвоение], то общее время работы алгоритма не превосходит по порядку а'-'. 6,5. Алгоритм Флойда — Уоршелла 6.5 Апгорнтм Фпойда — Уоршеппа В заключении этой главы приведем очень эффективный, просто программируемый и широко используемый алгоритм, который находит краичайгцие пути одновременно между всеми парами вершин Более того, он имеет важное преимущество перед алгоритмом Дейкстры, а именно он работает и в ~ом случае, когда допускаются отрицательные веса дуг, и позволяет в этом случае Рис.
6.!2. Операция греугольннка Лля грикеироаанного / и всех остальных Г и л. находить циклы с отрицательной стоимостью. Однако этот алгоритм не является, по-.впдимому, прямо-двойственным. Алгоритм работает с массивом размера и ха, содержащим числа йы, вначале равные весам сы дуг ориентированного графа 6= =(1', Е) Для дальнейшего удобно положить си=по для всех Е Ядром алгоригма является следующая операция. Определение 6.4. Пусть дана матрица расстояний йы размера п кп Операцигй треугольника для фиксированной вершины 1 называется операция ага: = ппп (йм, а, + й,а) для всех 1, /г = 1, ..., и, таких, что 1, йФ1. Заметим, что допускается 1=А. (З Эта операция для каждой пары 1 и я заменяет элемент йга расстоянием йы+г(га, если оно короче (рис. 6.12).
Алгоритм Флойда — Уоршелла основан на приводимой ниже теореме; индуктивное доказательство этой теоремы позволяет легко понять, почему алгоритм правильно работает. Теорема 6.4. После выполнения операции треугольника последовательно для значений 1'=1, 2,, п каждый элемент йга сгпановится равным длине кратчайшего пути из 1 в й в предположении, чгпа веса сы)0. Доказательства.
Докажем по индукции, что после применения операции треугольника для /=1, элемент йи для любых 1 и я равен 136 Гл. б, Алгоришмы Форда — Филкерсока и Дейкстры длине кратчайшего пути из ! в й по вершинам с номерами о~[',. Для 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, до д;и.=' ш1п' (д1к, дц+д,к) епд Рис, 6.13. Алгоритм Флойда — Уоршелла по вершинам с номерами о ~1„— 1, поэтому г(ц,+г(це — оптимальное расстояние по вершинам с номерами п~(„, Зт(им индукцня завер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
