Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 50

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 50)

11.2, а следующая теорема посвящена анализу его работы. Теорема !1.1. Венгерский метод, представленный на рис. 11 2, корректно решает задачу о назначениях для полного двудольного графа с 2п вершинами, используя 0(пз) арифмептичгских операций, Доказательство. Легко проверить, что алгоритм, представленный на рис. 11.2, является применением алгоритма АЛЬФАБЕТА к задаче о назначениях; поэтому его корректность следует из леммы 11.1.

Для получения временнбй оценки заметим вначале, чтовозможио не более и+1 этапов, поскольку каждый этап, за исключением ') Читатель должен заметить, что этот маневр со структурой данных аналогичен тому, который был использован в алгоритме Дейкстры в гл. 6. 9 м зозз Гл. ЛЦ Взвешенное лароомгл~ание ВЕНГЕРСКИЙ МЕТОЛ Вход. Матрица [сц) размера пХп с неотрицательными целочислевными элементами. Выход. Оптимальное полное паросочетание (представленное массивом напарник) в полнолг двудольиом графе В = [Ч, (), Е) с числом вершин 1 Ч 1 = 1()[ =и и стоимостями сц. Ьеа!п 1ог а)1 чгшЧ до наларник[чЙ:= О, а!:= О; )ог вц и)~(3 до наларник[о!):=О, 51.'= ш!п(сц»; 1 (сопнпеп1: задание вачалшгых значений) 1ог 1:= 1, ..., п бо (сошшеп1: повторит~ для и агапов) Ьед!п А:= яц 1ог а11 чЕЧ бо свобадная[ч):= О; 1ог ац иц() до невязка[и[;= ов; 1ог ац чь и) для которых ч,РЧ, и!Е() и а!+В! =сц бо И напарник[о!1=0 йеп свабодная[ч;):= и1, е1зе А:= А[)((чи напарник[и!1)»; (сошшеп(: построение вспомогательного графа) ; 'Я:=яц » [ог аВ чг<Ч бо И напарник[с![=О йеп Ьед! п В свободная[чг) Ф О 1Ьеп УВЕЛИЧЕНИЕ(ч!), ко !о конецэтапа! !):= (д[)('!»у ггомвшка[ч!1: О; (ог а)1 ик~(3 бо П 0 < сги — и! — [)к < невязка[пи) йеп нгвязка[ик1."= си,— и! — 1)ю сасвд[иц): ч!) епб! )„, ! з п(И!е Я ~ и бо Ьед! п пусть ч! — любая вершина из !); удалить ч! из Я; )ог ац непомеченные ч,~Ч, такие, что (чп ч!) ЕА 6о поиск: Ьед!п [ ломвглка[ч!1:= чц ~ С):=О0( !»; Ц свободная[ч!) гд О йеп УВЕЛИЧЕНИЕ(ч!), ко !о конецэтапа; )ог а)1 он ~() бо !1 О < с!к — а! — ()к< невязка[их) йеп невязка[их):= с)к — сс! — Вк, сосед[их):= ч)! епб с~6; МОДИФИЦИРОВАТЬ; яо 1о поиск конецзтзпа: епб епб ргосебиге МОДИФИЦИРОВАТЪ (сошшеп1: она вычисляет Ог, пересчитывае~ все а и В и привлекает ио.

вые вершины для продолжения поиска) !!.2, Венгерская метод для задачи о назначениях 259 Ьед!и ! О,:= — пни[невязка[и[ > 0); 2 иео 1ог аи ч!е'1Г до И и! помечена !Ьеи а!:=а!+Ог е!ае а!. 'сс! — Он 1ог аи и)Е() до И невязка[и ) =0 !Ьеп [)! .= О! — О, е!ае [!1.= О -«О; 1ог ап и~~У, для которым невязка[4 > 0 до Ьек!н невязка[и) = невязка[4 — 2ОИ И невязка[и) =О !Ьеи (сопниепи новое допустимое ребро) И напарник[и) =-0 !Ьеп свободная[сосед[иЦ;= и, УВЕЛ!!с!ЕНИЕ(сосед[и)), яо !о конецзтапа; е1ае (сопииеи1: напарник[и) ~ 0) пометка[напарник[и)):= сосед[и[, С):= Я[)(напарник[4), А:= А[)((сосед[и), напарник[и))); епд еид Рис.

!!.2. Венгерский метод последнего, увеличивает паросочетание на одно ребро. Для анализа каждого этапа рассмотрим сложность поиска и модификации двойственных переменных по отдельности. Поиск можно выполнить за 0(п') операций, поскольку никакая вершина не включается в очередь второй раз на одном и том же этапе и удаление вершины из Я обходится в 0(п) операций. С другой стороны, при каждой модификации двойственных переменных либо помечается новая вершина осУ, либо производится увеличение, и этап оканчивается.

Поэтому на каждом этапе возможно самое большее и модификаций двойственных переменных. Каждая модификация требует времени 0(п). Следовательно, каждый этап требует 0(пе) операций, откуда получается нужная оценка. «) Пример 11.1 (венгерский метод в матричной форме). Задачу о назначениях и венгерский метод можно рассматривать на языке матриц. При агом стоимости с„являются элементами некоторой (и хм)- матрицы, а элементы множеств У и (! идентифицируются соответственно со строками и столбцами этой матрицы. Так, следуюшую матрицу можно рассматривать как пример задачи о назначениях„ которую нужно решить венгерским методом. )3 3 2 ! ! 2 0 Гл. 1д Вэеешенное оароеочешание Целые числа, стоящие по краям матрицы, являются соответственно начальными значениями а! и ))и Числа, выделенные жирным шрифтом, обозначают допустимые ребра. Тогда первые три раза поиск будет сразу же приводить к успеху, в результате чего ребра )о„и,), )о,, и,! и )оо и,! включаются в паросочетание Ситуация, возникающая при следующем поиске, представлена ниже.

а 3 ' ! ! 2 о и! о 'о 2 их аз 'о Ое О 225 невязка: 5 2 ь з з сосед: 5 5 5 5 Граф, состоящий из допус2имых ребер, приведен справа (помеченные о-вершины указаны звездочками). В левой части кружками выделены ребра паросочетания, а помеченные строки (о-вершины) отмечены галочками. Массивы невязка)ие) и сосед[их) приведены под соответствующими столбцами.

Очевидно, в данной ситуации необходимо произвести модификацию двойственных переменных. Наименьшая ненулевая невязка равна 2, поэтому О,=1. В результате получаем р 4 3 а ео2 иг ° ~ -1 на "2 о4 и5 Ребро (ом и,! добавлено к допустимому графу, и никакие ребра не удалены. Возобновляя поиск, замечаем, что вершина, для кото- 1Вз. Венгерский иегнод ден задачи о назначениях за1 рой значение свободная отлично от нуля, помечена.

Паросочетание увеличивается, и поиск начинается снова, завершаясь в ситуации: д 4 3 2 2 3 а *о из О4 ие о5 'гу невязка: 4 2 д 2 1 СОСЕД; . 2 2 2 2 Теперь О,= !'2, и модификация приводит к следукзщим таблице н опустимому графу: д 4.5 3.5 2.5 2.5 3.5 - 1,5 и1 о1 ие ,.г' 1,5 и) — 1.5 ' -1.5 о 4 !ге 0.5 невязка: 3 1 3 1 о сосед; 2 2 4 2 2 Отметим, что во время вызова процедуры МОДИФИЦИРОВАТЬ была помечена вершина пе. Опять О,=1!2, и получаем 262 Гл.

Ы. Взвешенное пароеочешанае р 3 4 3 3 3 и о~ иг з ,г: О 'П5 а5 Здесь имеется увеличивающий путь (ою и„п„ие). Ниже приведено получаемое в результате оптимальное паросочетание о, оэ нз О5 из Его стоимость 15 совпадает с ~ч,'~4,с45+~) ер5=15. г) 11.3 Задача о взвешенном паросочетанин в произвольном графе Общую задачу о паросочетании можно сформулировать следующим образом: ппп Х с;,хе ь! при условиях ') ~зх,. =1, 4=1, ..., и, ! =1 х;,>О, 1<4</<п, где и предполагается четным. Так же как в случае задачи о назна- чениях, эта задача линейного программирования может иметь дроб- ные оптимальные решения, бессмысленные с точки зрения паросо- (11.! ) (!1.2) ') По определению кп=о и хн — — хяе П.д.

Задача о завешенном нароеочетанаа четаний. Однако теперь дела намного хуже, Эти дробные решения могут быть базисными допустимыми решениями приведенной выше задачи ЛП. Это означает, что любой метод, аналогичный симплекс- алгоритму, будет для некоторого множества стоимостей заведомо приводить к такому решению. Рассмотрим пример, приведенный на рис.

11.3. Единственным оптимальным решением, соответствующим указанным стоимостям (опущенные ребра имеют стоимость, скажем, 100), является решение хее=х1е=хее=хее=хче=хее=хее=хее="1И 4 ~в ое З ае Рис. 11,3. Таким образом, оптимум достигается при присвоении переменным, соответствующим всем ребрам в циклах нечетной длины, значения ! 12 С другой стороны, из предыдущего параграфа нам известно, что такие проблемы никогда не возникакл при отсутствии циклов нечетной длины Отсюда легко предположить, что именно из-за наличия циклов нечетной длины указанная выше задача ЛП неадекватно описывает задачу о паросочетании.

Следующая теорема подтверждает, что это действительно связано с наличием циклов нечетной длины, причем в очень сильной степени: для того чтобы описать общую задачу о паросочетании, достаточно добавить некоторые ограничения, при которых патологии, аналогичные приведенной для рис. 11.3, немогут быть допустимыми. Напомним, что и считается четным. Рассмотрим все подмножества множества (1, 2,..., п), мощность которых нечетна и больше 1. ЛЕГКО ПрОВЕрИтЬ, Чта ИМЕЕтСя 1Ч'=2» ' — П таКИХ ПОдМНОжсета. Пусть Зь Зь...; Бн — некоторая нумерация этих подмножеств; мощность подмножества 5! будет обозначаться через 151) 2зе+1. Теорема 11.2 (Эдмонде).

Общая задача о паросочетании для множества стоимостей (сы:. 1(1(((и) эквивалентна задаче ЛП: МиииМиЗиРОВатЬ ~1 С;;Хоо Гл. 1д Вееешенное пороесчеыоние На первый взгляд несколько разочаровывает тот факт, что в приведенной формулировке задачи ЛП имеется экспоненциально большое число строк. Однако мы увидим, что это несущественно. Условие (11.3) просто утверждает, что ни на каком множестве, содержащем нечетное число вершин, не може1 быть больше соответствующего числа ребер паросочетания и уе — переменная недостатка. Очевидно, все допустимые паросочетания удовлетворяют новым ограничениям.

Отметим, что эти ограничения не допустили бы патологического оптимума в примере на рис. 1!.3. Действительно, оптимальным решением рассматриваемой задачи ЛП при ограничениях (11.1), (!!.2) и (11.3) для стоимостей, приведенных на рис. 1!.3, будет х„=-х„=х„=-х„= 1, что соответствует правильному паросочетанию. Следовательно, для доказательства теоремы достаточно показать, что задача ЛП с ограничениями (1!.1), (11.2) и (!1.3) всегда имеет целочисленное оптимальное решение, т.

Характеристики

Список файлов книги