Алгоритмы - построение и анализ (1021735), страница 163
Текст из файла (страница 163)
Этот алгоритм выполняется за время 0 (~ЯЕ). Задан неориентированный двудольный граф С = (У, Е), где Ъ' = Е и В и у всех ребер ровно одна точка находится в Ь. Пусть М вЂ” паросочетание в С. Мы говорим, что простой путь Р в С является увеличиваиниим иуизем (ап(рпеп11пя рат(т) по отношению к М, если он начинается в некоторой свободной вершине множества Ь, заканчивается в некоторой свободной вершине В, а его ребра попеременно принадлежат М и Е— — М. (Это определение увеличивающего пути связано с определением увеличивающего пути в транспортной сети, но несколько отличается от него.) В данной задаче путь трактуется как последовательность ребер, а не последовательность вершин.
Кратчайший увеличивающий путь по отношению к паросочетанию М вЂ” это увеличивающий путь с минимальным числом ребер. Для заданных двух множеств А и В, симметрическая разность (зушшетйс ййегепсе) А ® В определяется как (А — В) 0 ( — А), т.е. это элементы, которые входят ровно в одно из двух множеств. а) Покажите, что если М вЂ” некоторое паросочетание, а Р— увеличивающий путь по отношению к М, то симметрическая разность множеств М ® Р является паросочетанием, и ~М9 Р~ = ~М)+ + 1.
Покажите, что если Рм Рз,..., Рь — увеличивающие пути по отношению к М, не имеющие общих вершин, то симметрическая разность М Ю (Р1 0 Рз 0. 0 Рь) является паросочетанием с мощностью ~М~ + 1с. Общая структура алгоритма имеет следующий вид: НОРскОгт КАВР(С) 1 М+-О 2 гереа1 3 П сть Р у — (Ры Рз,..., Рь ) максимальное множество кратчайших увеличивающих путей по отношению к М, не имеющих общих вершин М вЂ” М Е (Р1 О Рз О " и Рь) 5 нп111 'Р = 6 б ге1пгп М 792 Часть Ч( Алгоритмы для работы с графами Далее в этой задаче вам предлагается проанализировать число итераций данного алгоритма (т.е. число итераций цикла гереат) и предложить реализацию строки 3.
б) Для двух заданных паросочетаний М и М' в С покажите, что каждая вершина графа О = (У, М ® М') имеет степень не больше 2. Сделайте вывод, что С' является обьединением непересекающихся простых путей или циклов. Докажите, что ребра каждого такого простого пути или цикла по очереди принадлежат М и М*. Докажите, что если ~М~ ( (М'), то М Щ М* содержит как минимум )М'! — )М( увеличивающих путей по отношению к М, не имеющих общих вершин.
Пусп ) — длина кратчайшего увеличивающего пути по отношению к паросочетанию М и пусть Ры Рз,..., Рь — максимальное множество увеличивающих путей длины 1 по отношению к М, не имеющих общих вершин. Пусть М' = М 9 (Рт 0 Рз О 0 Рь) и предположим, что Р— кратчайший увеличивающий путь по отношению к М'. в) Покажите, что если Р не имеет общих вершин с Ры Рз,..., Ры то Р содержит больше чем ( ребер.
г) Теперь предположим, что Р имеет общие вершины с Ры Рз,..., Ры Пусть А — множество ребер (М ® М') ® Р. Покажите, что А = = (Рт 0 Рз О . О Рь) 9 Р и что ~А~ > (й + 1) 1. Покажите, что Р содержит более ( ребер. д) Докажите, что если кратчайший увеличивающий путь для М содержит 1 ребер, то размер максимального паросочетания составляет не более (М)+ Я/() + 1).
е) Покажите, что число повторений цикла гереат в данном алгоритме не превышает 2т/Г. (Уииалие: на сколько сможет вырасти М после итерации номер т(Г?) ж) Предложите алгоритм для поиска максимального множества кратчайших увеличивающих путей Ры Рз,...,Рь для заданного паросочетания М, не имеющих общих вершин, время работы которого — О (Е). Покажите, что суммарное время выполнения процедуры Норскогт Клнв составляет О ( /7Е). 793 Глава 26.
Задача о максимальном потоке Заключительные замечания Транспортные сети и связанные с ними алгоритмы рассматриваются в работах Ахуя (АЬща), Магнанти (Майпапй) и Орлина (Ог!ш) [7], Ивена (Ечеп) [87], Лоулера (1.а~ч1ег) [196], Пападимитриу (Рараг)(ш1птои) и Стейглица (Иге(8!йк) [237], Таржана (Тапап) [292]. Широкий обзор алгоритмов для задач поиска потоков в сетях можно найти также в книге Голдберга (Оо!дЬегй), Тардоса (Тап1оз) и Таржана [119]. В работе Шрайвера (БсЬг1]чег) [267] предлагается интересный исторический обзор исследований в сфере транспортных сетей.
Метод Форда-Фалкерсона представлен в работе Форда (Рогд) и Фалкерсона (РиПсегзоп) [93], которые являются основоположниками формальных исследований ряда задач в области транспортных сетей, включая задачи поиска максимального потока и паросочетаний. Во многих ранних реализациях метода Форда-Фалкерсона поиск увеличивающих пугей осуществляется с помощью поиска в ширину; Эдмонде (Ейпопдз) и Карп (Кшр) [86] и, независимо от них, Диниц (Ейшс) [76] доказали, что такая стратегия дает полиномиальный по времени алгоритм. Диницу [76] также принадлежит идея использования "тупиковых потоюв™ (Ыос1с1п8 йод з); предпотоки впервые предложил Карзанов (Кагхапоч) [176].
Метод проталкивания предпотока описан в работах Голдберга [117] и Голдберга и Таржана [121]. Голдберг и Таржан приводят алгоритм со временем работы О (Уз), в котором для хранения множества переполненных вершин используется очередь, а также алгоритм на основе использования динамических деревьев, время работы которого достигает О (УЕ 18 (Уз(Е + 2)).
Неюторые другие исследователи разработали алгоритмы проталкивания предпотока для поиска максимального потока. В работах Ахуя и Орлина [9] и Ахуя, Орлина и Таржана [10] приводятся алгоритмы, использующие масштабирование. Чериян (СЬепуап) и Махешвари (МаЬезЬчаг)) [55] предложили проталкивать поток из переполненной вершины с максимальной высотой. В работе Черияна и Хейджерапа (Найегпр) [54] предлагается использовать случайные перестановки списков соседей; другие исследователи [14, 178, 241] развили данную идею, предложив искусные методы дерандомизации, что позволило получить ряд более быстрых алгоритмов.
Алгоритм, предложенный Кингом (Кшй), Рао (Као) и Таржаном [178], является самым быстрым из них — время его работы составляет О(УЕ 1обе (~,,я,~) У). Асимптотически самый быстрый из известных в настоящее время алгоритмов для задачи максимального потока разработан Голдбергом и Рао [120], время его работы равно О(ш)п(уз7з, Е ч ~) Е 18(у~/Е+ 2) 18 С), где С = шах(„„)ее с (и, и). Этот алгоритм не использует метод проталкивания предпотока, он основан на нахождении тупиковых потоков. Все предыдущие алгоритмы, включая рассмотренные в данной главе, используют некоторое понятие расстояния (в алгоритмах проталкивания предпотока используется аналогичное понятие высоты), где каждому ребру неявно присвоена длина 1.
В этом же алгоритме используется другой под- Часть Ч1. Алгоритмы для работы с графами ход: ребрам с высокой пропускной способностью присваивается длина О, а ребрам с низкой пропускной способностью — длина 1. Неформально при таком выборе длин кратчайшие пути от источника к стоку будут иметь высокую пропускную способность, следовательно, потребуется меньшее количество итераций. На практике на сегодняшний день при решении задач поиска максимального потока алгоритмы проталкивания предпотока превосходят алгоритмы, основанные на увеличивающих путях и линейном программировании.
В исследованиях Черкасски (СЬег1сазз1су) и Голдберга 156] подчеркивается важность использования при реализации алгоритма проталкивания предпотока двух эвристик. Первая состоит в том, что в остаточном графе периодически производится поиск в ширину, чтобы получить более точные значения высот. Вторая эвристика — это"эвристика промежутка" (яар леппзг1с), описанная в упражнении 26.5-5. Авторы пришли к заключению, что наилучшим вариантом метода проталкивания предпотока является вариант, в котором для разгрузки выбирается переполненная вершина с максимальной высотой.
Наилучший известный к настоящему времени алгоритм поиска максимального паросочетания (описанный в задаче 26-7) был предложен Хопкрофтом (Норстой) и Карпом (Кар) 1152]; время его работы составляет О (т/ГЕ). Задачи поиска паросочетаний подробно рассматриваются в книге Ловаса (1.отазг) и Пламмера (Р!шшпег) 1207]. Введение Эта часть содержит избранные темы теории алгоритмов, расширяющие и дополняющие материал, ранее изложенный в данной книге. В некоторых главах вводятся новые вычислительные модели, такие как комбинационные схемы или параллельные вычислительные машины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
