Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 52
Текст из файла (страница 52)
Наконец, п. в) нашего предположения также сохраняется, так как к Ув добавляются только цветки из 6, а они, очевидно, удовлетворяют п. в). Наше предположение доказано. Чтобы дать детальное описание алгоритма, необходимо показать, как модифицировать двойственные переменные.
Напомним, что параметр О, вычисляется (см. (б.!6)) как минимум из величин 270 Гп. )А Взвешенное ппроажегнпние Наконец, та)0, если оацЧг. Поэтому В,=п![п(бп 6„6,), где (сгу — он — пу 6, = пни ) 2 гоно, ЕО и лежат в разных псевдоверпэинах), 6,= шш (со — иг — ауг о! ЕО, о, Е)г — ! — О), (11,[З) б,=поп ( — уа(2: 5аЕ Ч",). Описанный алгоритм представлен на рис. 11.5. Теорема 11.3. Алгоритм, представленныйна рис. 11.5, корректно решает задачу о взвешенном паросочетании за время 0(п'). АЛГОРИТМ ПОСТРОЕНИЯ ВЗВЕШЕННОГО ПАРОСОЧ ЕТАНИЯ Вход, симметричная матрица [сн) размера пхп с неотрицательными цело. численными элементами; п четно, Выход.
Полное паросочетание М с наименьшей обшей стоимостью при данных с;. Ьей!п ! ! 1ог ан с!~Ч бо п!.= — пцп(сп»; 2 1ог ан й бо Ти '.=-О; М;= еп (сопнпеп1; исходное паросочетание) чь.= ен (сопппеп1; )ь содержит все нечетные множества Зи, для которых та<О) пЬ!!е [ М ) < гп2 бо Ьей1п построить допустимый граф Оз, включив в него все ребра [ч!, ч!1, для которых пи+а!+ ~Ч~Р ух=он, и стягивая все множества Зк в )ь, 1, )ез~ найти максимальное паросочетанне в Оэ, начиная с текущего паросочетания М; пусть О,— текущий граф после применения алгоритма построения максимального (нсвэвешенного) паросочегания к Оз; пусть Π— множество внешних вершин в О„! — множество внутренних вершин, Ч'о — множество внешних псевдовсршин и Ч'! — множество внутренних псевдовершин; вычислить О,:=-ппп (бг, б„ба) (сопцпеп1: см. (1!.!3)) 1ог ап ч!цО бо а).'= сг!+От! 1ог ап ч!Ш! бо а);=а! — 00 )ш а1! БкЕгуо бо тк .'= Ти — 20г! 1ог ан ЗкцЧ'! бо уи.— — та+20,; построить по максимальному паросочстанню в Оз максимальное превиль.
нос паросочетенне М в графе (Ч, 3е)! положип Хь'=(ЗкЕ)ь()Ч'о: Тк < О» епб епб Рис. П.б, Алгоритм построения взвешенного паросочетания. 1!.З. Задача о взвешенном наооеочетанао !7! 27! Докаэагпельсглао. Согласно нашему утверждению, этот алго тм является вариантом прямо-двойственного метода, применение)итм к задаче ЛП, задаваемой ограничениями (1!.!), (!1.2) и (11.3). С"о кюда с учетом теоремы !!.2 вытекаег его корректность. Для подуя!сю-ия временнбй оценки заметим, что алгоритм состоит из некотсиипго числа поисков увеличивающих путей, чередующихся либо суяоггхичениями, либо с модификациями двойственных переменных. !Илино.
вем каждый поиск шагом, а последовательность шагов между лазо-ия последовательными увеличениями згпапож. Очевидно„не может~умять больше чем п12 этапов; далее мы оценим число шагов в каждом эытые. Шаг может быть одним из трех гипов в зависимости от тогсипе,!удет ли при его завершении 0,=6„0,=6, или 0,=6,. В первом буаучае две внешние першины графа О, соединяются новым допуст12иу 1м ребром. Это означает, чт»а следующем аге мы б аружим Иымбо увеличивающий путь, либо цветок в зависимости от того, ~ибгвзличиы или совпадают свободные вершины, из которых эти виейаз-ие вершины достижимы по увеличивающему пути чечной длниы.'ииеак как каждый цветок уменьшаеч размер текущего графа по крагакей мере на 2, то не может быть больше чем п(2+! шагов типа'Иейна одном этапе.
! на Если О,=б„то на следующем этапе обнаруживается ь ая внешняя вершина. Это означает, что число шагов этого типа т,'Иаяже не пРевосходит и!2. Наконец, если О,=бм то из з'о Удалаетс~ жечечетное множество Я„, соответствующее внутренней псевдовер: ие-не графа 0 . Однако в тот момент, когда оч впервые было добавлгИ1не> к О, оно было внешней псевдовершиной Следовательно, и"о кду этими моментами должно было производи~ься увеличение, Позидуму число таких шагов на этапе ограничено числом нечетных мнохому'.тв Ис в /, в конце предыдущего этапа Но, согласно п. в) нашего ~стведположения, это число не превосходит и!2.
ИедПолучаем, что общее число шагов не превосходит 0(л'). Ка> ый поиск можно выполнить за время 0(п') с помощью соответству1Иы(пей процедуры для задачи о мощности паросочетания. (Шаг, вклкИ!ейющий увеличение, который мог бы потребовать времени пе, чч!Ию-сет ) появиться на этапе только один раз.) Кроме того, множества 'иет 1, Ч'о, Ч', можно определить за время 0(п') при нахождении опти" 1,чьного паросочетания в графе 01, Наконец, построение графиль-зл вычисление О, и модификация переменных также могут быть п(0лизведены за время 0(п'), С) 'ИзПример 1!.2. Применим разработанный нами алгоритм и< ка взвешенного паросочетания к приведенному ниже при,"сказу. „! Кроме весов ребер иа рисунке представлены также начальнысру.чачения а1 и допустимый граф 0з с максимальным паросочечаиириа- на нем.
Внешние вершины помечены звездочками, и нет ни внутре' нащх вершин, ни цветков. Для вычисления О, находим, что 6,— --5 (дяихгигавтся на ребре (п„п,)), 6,=1 (достигается на ребре [пм пв!) и 6,2ти.оо, 'оо, Гл. 11. Вееешеннае ааросочетание 2 3 4 5 о 7 8 ое» ое» поскольку Ч',=и. Отсюда 0,=1. В результате получились такие изменения: аа а1 ° Р» ° Цо» ое ° Внутренняя ое На этом рисунке выделено максимальное паросочетание в графе 61; 6,=! 1достигается на ребре [о„и»!), 6,=2 и б,=ос. Отсюда О, 1, и получаем П.з. Задана с взвешенном лауссонелшнаа У»» УВ» У~» Ув о о Уг» У,. Ув» Уг» Уг Ф(сг Уг Ув)» Здесь показан граф б„получаемый после стягивания цветка (вм пе, У,) в графе 64; е'ь=Ч'о=((2, 3, б)), 6,=1 5 (достигается на ребре М, п»!), 6,=1 (достигается на ребре [п„п»1) н б,=со.
Следо. вательно, 94=1, и получаем Уг. У~» Уг ° т м 2 О 12,2,61 У,,У»)а Уг ° Внутренняя У4 Заметим, что мы модифицировали переменную у<г г, вм соответствующую множеству из Ч'о. На рисунке показано оптимальное паросочетание в 62, '74=»уо= ((2, 3, 6)), 0=(у„о„у„у,, у„у„ и,) и 7=(о,). Увеличение опять невозможно. Г!олучаем 6,=0. 5, 6,=6,=со и приходим к Уг» т =-3 О 12,2,9 У»* , УЗ Лв) Таким обРазом, У, объединЯетсЯ в паРУ с (У„пв, о,) в гРафе бл Теперь 6,=7.25 (достигается на ребре [п„о,)), 6,=1,5 (достигается 274 Гл. !!.
Вэеешеннее нарееенетанае на ребре Ь„и,)) и бе=со, поскольку Чее=п. Отсюда 0,=1,5, и получаем а,, а„ ев, ув, ав) утренняя (ивм нняя На рисунке показано оптимальное паросочетание в 6е, е'в — — Ч',= =((2, 3, б)), 0 — -(о,, о„о„пв) и 1=(о„п„о„о,). Теперь 6,=2.5 (достигается на ребре Ьп и,)) и 6в=оо. Наконец, 0,=6,=1.5, так как (2, 3, б) Е Ч',. Наша модификация дает Уе» в Внутре Уел 7 п,хе, "ве Поскольку ум в 41 — — 0 и, следовательно, множество (2, 3, б) удаляется из .!в, мы больше не стягиваем (п„о„и,) в 6ю По завершении поиска увеличивающего пути в графе 6 ситуация выглядит так, как показано выше.
Находим, что 0,=6,=0.75 (достигается на ребре Ь„, о,)), и модифицируем двойственные переменные следующим образом: 11,4. Выводи о1 о, о1 Заметим, что ребро [ои о,) больше не входит в 6 . Оптимальным ПаРОСОЧЕтаНИЕМ В 61 ЯВЛЯЕТСЯ ПаРОСОЧЕтаНИЕ ([Оо Оо], [О„О ), [о„, о,) [о„, о,]) (мы произвели увеличение вдоль пути [ом о„ои о,1). Так как ]1]4]=4=л/2, то наш алгоритм останавливается и М оптимально. Его стоимость совпадает с ~П~",,а1+~~'=,уев„— -44.
[] 11.4 Выводы Алгоритм нахождения взвешенного паросочетания в произвольном графе, описанный в предыдущем параграфе, является превосходным примером применения прямо-двойственного алгоритма. Он раскрывает природу прямо-двойственного алгоритма как оби(его метода дяя сведения задач с весами к их аналогам без весов. Для выполнения такого сведения мы должны вначале яайти полное множество линейных ограничений, точно характеризующих рассматриваемую задачу (см. теорему 11.2). При этом число неравенств часто будет экспоненциальным, Последнее не служит помехой, поскольку можно так реализовать прямо-двойственный алгоритм, что он все время будет хранить множество активных неравенств— неравенств, соответствующих ненулевым двойственным переменным,— и в большинстве случаев число их будет сравнительно небольшим. Можно показать, что при несколько более аккуратной реализации алгоритм, приведенный на рис. 11.5, требует только 0(л') времени для графов с л вершинами (задача!4).
Таким образом, так же как в случае задачи о невзвешенном паросочетании (вспомните теорему 10.3 и ссылку [МЧ] в конце предыдущей главы), переход к недвудольным графам добавляет, по-видимому, только технические трудности и не влияет на асимптотическую сложность. Гл. !!. Взвешенное парточетопие 276 Задачм 1. Решите приведенную ниже задачу о назначениях; 2. Покажите, что если стоимости с!! целочисленны, то значения двойствен.
ных переменных при применении венгерского метода всегда кратиы 1/2. 3. Покажите, что если стоимости сг! целочисленны, то значения двойственных переменных в алгоритме нахожден~я взвешенного паросочетання в произвольном графе всегда кратиы !)4. 4. Найдите паросочетание наименьшей стоимости для приведенного ниже графа (все отсутствующие ребра имеют стоимость во); 5 3 2 5 5 4 ое 1 3 + е 3. а) Приведите пример, показывающий, что паросочетание мшссимавьлоео веса в некотором (ие обязательно полном) графе может не быть паросочетанием максимальной мощности даже в случае положительных весов. б) Приведите алгоритм для нахождения чаисимального взвешенного полного паросочегания в данном графе.
в*) Приведите алгоритм для нахождения максимального взвешенного паросочетаиин с Л ребрами для фиксированного Л. (Укп ание: добавьте к (11. !), (11.2) и (11.3) равенство ах!в=я. Как зто влияет иа прямо-двойственный алгоритм?) 6*. Покажите, что венгерский метод для взвешенных (не обязательно псиных) двудольных графов можно реализовать так, чтобы он требовал 0())г(1Е! !ой 1г'!) времени. 7. Рассмотрим множество стоимостей с!зйеб на ребрах полного графа К„ с л вершинами. Пусть Вс='(о„, оп) Требуется найти подграф графа К„, в котором степени вершин из 5 нечетны, степени остальных вершин четны (возможно, равны нулю) и который имеет наименьшую возможную стоимость. Покажите, что это задача о паросочетании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
