Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 24
Текст из файла (страница 24)
ша ется, Полностью алгоритм приведен на рис. 6.13. Все циклы в нем имеют фиксированную длину, и общее число сравнений, которое требуется произвести в алгоритме, равно гг(п — 1)'-'. Можно следить и за самими кратчайшими путями с помощью другой пхп-матрицы, скажем е,„, определяемой следующим образом: е; =(промежуточная вершина с наибольшим номером на кратчайшем пути из ! в А, если такая существует, и нуль в противном случае) Положим вначале е,„=О, и при выполнении операции треугольника положим е сли г(; ) г(, +с[у„ ег„:= ег в противном случае. Тогда кратчайший путь из 1 в й можно легко восстановить по заключительной матрице е,д (см.
задачу 13). 6.6. Алгоритм Флойда — Уоршглла Рис. 6.14. Граф с циилом отрицательного веса. Начальное Рис. 6,15. Последовательные матрицы расстая. иий и матрицы е;7 прн применении алгоритмд флойда — Уоршелла. З Я !38 Гл. б. Алгоритмы Форда — Фалкерсона и дейкстры Посмотрим теперь, что происходит, если допускаются отрицательные веса дуг с;!. Если при этом нет циклов отрицательной дли. ны, то кратчайшие пути, фигурирующие в доказательстве теоре. мы 6.4, вполне определены и алгоритм работает так же, как с не.
отрицательными весами. Если же имеется цикл отрицательной длины, то некоторое г(лл в процессе алгоритма станет отрицательным. Для доказательства этого рассмотрим простой цикл отрицательной длины, и пусть )) — вершина с наибольшим номером на этом цикле. Тогда из доказательства теоремы 6.4 следует, что этот путь отрицательной длины из й в й по вершинам с номерами и()) будет найден на шаге 1'=й. Пример 6.2. На рис 6,14 показан граф с циклом отрицательной длины, а на рис.
6.15 приведены матрицы т(!) и е;ь получаемые на последовательных шагах применения алгоритма Флойда — Уоршелла. Измененные элементы матриц обведены кружком. Мы останавливаемся, получив т(„= — 1, что соответствует циклу отрицательной длины 4-2-1-4, который можно найти по последней матрице е;ь. Подведем итог. С помощью алгоритма Дейкстры можно решить задачу о кратчайшем пути в графе с а вершинами и неотрицательными весами за время, пропорциональное и'.
Если же допускаются отрицательные веса, можно, используя алгоритм Флойда — Уоршелла, решить задачу о кратчайшем пути при отсутствии циклов отри. нательного веса или даже найти цикл отрицательного веса за время, пропорциональное и'. Алгоритм Дейкстры также можно расшир)п ь на случай отрицательных весов, однако ~огда он тоже будет тре. бовать времени, пропорционального и" 1)че, ВЕ1. Задачн ! )гг, М)1. Мин~я предлагает решение задачи о кратчайшем пути в неориен тированном случае с помощью следующей аналоговой модели Поорудим веревоч.
ную модель для данного неориентированного графа, используя для каждого ребра кусок вереикн, пропорггиональный его длине Возьмем начальную вершину в одну руку, а конечную вершину в другую руку и будем разводить их до тех пор, пока капой-нибудь путь из начальной вершины в нонечную не окажется полностью натянутым. Покажите, что при этом решается задача, двойственная к задаче о кратчайшем пути.
Лайте интерпретапию прямо двойственного алгоритма для этой задачи в терминах веревочной модели (*) Можете ли вы придумать анало. гонон устройство для решения задачи о максимальном потоке? 2. Локажите справедливость равенства (6.7) для а, в рассмотренном примере бесконечной работы алгоритма пометок 3. Предположим, что в рассмотренном примере задачи о потоке, в ко~ором алгоритл~ пометок работает бесконечно долго, десяти чные разложения чисел а; ограничиваются ( десятичными разрядами. Г)очему в этом случае алгоритм пометок будет завершать работу за конечное число шагов? 4. Покажите, что фориула пересчета (6 !О) в алгоритме Дейкстры удовлетво ряет толовою !гэ 9).
б, Покажите, что если в алгоритме Флойда — Уоршелла, приведенном иа рис. 6.)3, остановка происходит при получении первого отрицательного диа- Задачи тонального элемента НМ, го соответствующий этому элементу замкнутый путь яв. ляется простим циклом с отрицательной стоимостью Покажит., г другой сто. роны, ~то если при наличии циклов отрицательной стоимости алгоритм работает до конца, го получаемые в результате значения не обязательно представляют стоимости простых путей. 6 (РР!. а) Докажите следующую георему Кенига — Эгервари, сформули. рован ее как некоторую задачу о максимальном потоке.
Рассмотрим массив ячеек размера тХп где некоторые ячейки выделены как важные Строки и столбцы будем называт~ зинками и будем говорить, что множество линий покрыв ~ег важ. ные ячейки массива. если каждая важная ячейка леж~гт на некоторой линни из данного множества Множество важных ячеек называется независимым если никакие две ячейки из этого множества не лежат на одной и той ж~ линни Теорема (Кениг — Эгервари). Макгамахьная мощносгпь незавпсимово мнгь жестко ю иных ячеек равняется наименыией мощности ин жества шнии", покры. ахющик кв ~амньге майки б) Объясните, как получгмь независимое множество максимальной мощное~и и минимальное покрытие линиями из решения соответствующей задачи о максимальном погоне.
в*) Оцените число шагов этого алгоритма в аависимости от т, п и числа важных ячеек р ?. Покажите, .ак можно применить алгоритм Форда — Фалкерсонз в том случае, когда пропускные способности заданы в вершинах сети 8. Пусть орпентированный граф С представляет сеть связи Максимальное число не пересекающихся по вершинам путей ич вершины ° в вершину 1 называется з-(-связнштыо .Г.яязтмостью сети пазыиаеюя минимальное число вершин (оглнчных от з и Г), уд»л, нне ко~арык ризъедияяе| ь н 1 Докажите, что ь-Г-связност~ равняется х-(-уитвнмости (это один из вариантов ~гаремы Менгера (РР!).
О* Пусгь для каждой дуги в сети наряду с верхней границей потока задана также низхнти граница; т, е. для каждой дуги (й () наложено ~ребование (; ~ ~(гг~о„ а1 Покажи~и, как с помощью алгоритма Форда — Фалкерсона определить, существует лн лопустнт~ый поток из з в ( величины с (Указание: начните с недопусюгмого потока и сшрайтесь получить допусгимый пошк ) б) Покажите, как найти допустимый пото, минимальной величины. в) Покажите кзк найти допустимый поток максимальной величины. !О (РР! Пусть есть и мужчин, и женщин и т брачных маклеров Каждый маклер имеет список некоторых из этих мужчи и жешцин являющихся его клиентами, и может устроить брак между любым мужчиной и любой женщиной из этого списка Потребуем дополнительно, чтобы число браков, которые может устроить маклер 1, не превосходило Ь; В брак могут вступать только лица разно~о поль, и каждый человек может иметь только одного супруга.
Переведите задачу нахождении решения с наибольшим числом браков в задачу нахождения максимального потока з неиагорой сети. 11. Пусгь дана сеть и требуется между всеми парами вершин найти пути с максимальной пропускной способностью в том смысле, что наименьшая пропускная способность дуг на пути должна быть максимальна Модифицируйте алгоритм Флойда — Уоршелла так, чтобы он решал э|у задачу зз время 0(п ) для сети с и вершинами.
12. Чем оправдывается исключение случаев ~=( и й=( в алгоритме Флойда— Уоршелла даже тогда, когда разрешакжся отрицательные веса? Будет ли алгоритм правильно работать, если допусти~к этн случаи? 13. Опишите детали процесса воссшновыния кратчайших путей в алгоритме Флойда — Уоршелла. 140 Гл. б. Алгоритмы Форда — Фолкерсоко и Дейкстры Кемменте)эмк и ссыпки Пример, в котором алгоритм пометок работает бесконечно, взят иэ книги (ГГ) Гогй 1.. )1., Гнйегзоп О.
)(. Г!оъз !п Ке1когйз, рр. 21 — 22. Рппсе1оп, К, йл Ргшсе1оп [)п1чегз!1у Ргеш, !962. [Имеется перевод Форд Д. Р, Фалкерсан Д. Р. Потоки в сетях.— Мс Мир, 1963.! Эдмонде н Карп предложили модификацию алгоритма пометок, в которой увеличение потока на каждом шаге производится вдоль пути с наименьшим возможным числом дуг. Для этого алгоритма онн получили оценку (п" — п)14 для числа уве. личеннй патока (см. также задачу !О в гл.
9). [ЕК] Ейгпопйэ 3., Кагр К. М. ТЬеоге||са! |гпргочегпеп1 !и А!бог!йш!с ЕП!с[епсу 1ог Ке1шогй Г!олч РгоЫешз, 3. ЛСМ, 19, Ко 2 (Арп| !972), 248 — 264. Ссылка на статью Дейкстры приведена в гл. 5. Алгоритм Дейкстры расширен на случай, когда допускаются отрицательные веса дуг, в работах [)че) Ь[егппанзег О. Ь А Оепега1!хей Реппапеп| ЬаЬе! 5ек|пб а|бопйгп !ог йе 5Ьог|ез1 Рай Ьебкееп Ярве|Пей Кобез, 3. Май Апа|узк апб Арр|., 38 (1972), 328 — 334.
(В!.! Вагагаа М. Б., Ьапй!еу )1. ЪЧ. А Она! 5Ьог1ем Рай А|багкпш, 3. 5)ЛМ, 26, Ко 3 (Мау !974), 496 — 50!. Иден в этих работах состоит в нахождении допустимого решения двойственнав задача н последующем применении стандартного алгоритма к задаче с модифицированными весами ггу — пг+пусаб. В работе (ВЦ для такой процедуры получена оценка.
пропорциональная ['г'!'. Алгоритм Флойда — Уоршелла взят нз работ [Г|[ Г!оуб й. ТУ. Л|йогппгп 97: 5Ьог1ез1 Рай, Сошгп. АСМ, 5, Ко 6 (!962), 345. ['лч'Л) Тч'агапа!! 5. А ТЬеогеш оп Воо|еац Маккез, У. ЛСМ, 9, Ыо 1 (1962), 11 — |2. Иден этого алгоритма описывается в очень широкой постановке на языке заллкнутых полуколец и приписывается Кляни в книге [АНШ ЛЬо А, Ч,, Норсгоп 3. Е,, П|гпап 3. О. ТЬе Оез1йп апб Лов|уз|э а| Сош. рыег Л!боп!Ьшз.
)[еаб!пй, Мамо Айй!зоп-Тч'ез!еу РпЫВ|ппб Со., |пс., 1974. (Имеется перевод; Аха А., Хапкрофт Дж., Ульман Дж. Построение н анализ вычислительных алгоритмов.— Мл Мнр. |979.! Веревочная модель для задачи о кратча»шем пути, описанная в задаче 1, содержится в книге [ГГ, с. 189 в русском переводе) н в работе [М1) М!п1у О. 3. А Сопцпеп1 оп 1Ье 5Ьог1ем )[он1е РгоЫегп, О)(, 5, [йо 5 (Ос1оЬег 1957), 724. Дополнительную информацию о задаче о кратчайшем пуча н ее решении методом динамического программирования можно найти в гл. !8 Прямо-двойственные алгоритмы для задачи о потоке минимальной стоимости 7Л Задача о потоке минимальной стоимости Изучим теперь важный и широкий класс задач о сетях, в кото- рых заданы нетривиальные ограничения как в виде пропускных способностей, так и в виде стоимостей Наша цель — применить и специально приспособить для этого случая прямо-двойственный алгоритм так же, как это было сделано для задач о максимальном потоке и кратчайшем пути Это можно сделать двумя способамн: можно рассмотреть исходную задачу как двойственную задачу Д, комбинаториализовать пропускные способности и прийти к некото- рым подзадачам о минимальной стоимости; либо можно рассмотреть исходную задачу как прямую задачу П и комбинаториализовать стоимость, Начнем с первого варианта, в котором все время сохра- няется допустимое решение исходной задачи Д и ие используется явно прямая задача П или ее ограничение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
