Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 55
Текст из файла (страница 55)
12.5. Второй алгоритм для задачи МОД. эта вершина принадлежит (на первом этапе калгпанента[из]=Бз для всех ]). С помощью массива компонента можно вычислить массив кратчайшее за время О(!Е!), просматривая все ребра графа 0 по очереди, как указано на рис. !2.5. Сколько может быть этапов? Мы утверждаем, что число гг связных компонент леса (]I, Т) уменьшается на каждом этапе по крайней мере в два раза. Это вытекает из того, что каждая связная компонента полученного леса (]У, Т) содержит по крайней мере две связные компоненты графа ()г, Т) из предыдущего этапа, так как каждая компонента соединяется с другой компонентой с помощью соответствующего ей кратчайшего ребра.
На первом этапе й= ]]г], и й уменьшается на каждом этапе по меньшей мере вдвое. Поэтому после не более [од!)г! этапов й сведется к единице и алгоритм остановится, выдав в результате МОД. Таким образом, алгоритм может содержать не более ]ой!)г! этапов. С) Пример !2.! (продолжение). На рис. 12.6 показано решение задачи МОД для графа, представленного на рис. 12.3, с использо- 22.д. Жадтий алгоритм ванием алгоритма, построенного в данном параграфе.
Граф (У, Т), получаемый в конце каждого из трех этапов, показан на рис. 12.6(а, б и в). Множества вершин, образующие связные компоненты, поме- (б) [в) Рис. 12.б. чены именами соответствующих переменных — например, Яо Я, и т. д., — и каждое вновь добавленное ребро г помечено целым числ лом 1, таким, что кратчайшееИ=е. Д 12.3 Жадный алгоритм Рассмотрим несколько иную задачу. Пусть, как и в задаче о па. росочетании, нам даны граф 6=()г, Е) и веса нгы)0 для каждого ребра [о„о;) ЕЕ, Требуется найти лгс — ациклический подграф графа 6,— имеющий максимальный общий вес.
Нетрудно понять, что эта задача о лесе максим лоного веса (ЛМВ) очень близка к за- даче МОД. Предположим вначале, что граф 6 связен Поскольку мы считаем, что ю;;)О, то любой оптимальный лес можно сделать максимальным по включению, т. е. остовным деревом графа 6. Кроме того, все остовные деревья графа 6 имеют1)г( — 1 ребер (см. предложение 1.2). Поэтому можно построить функцию расстояния для Е, Гл. Ед Останные оьеревья и маглроидм положив бы= [зт — шы для всех Ьн от[ а Е, где Ф'=п1ах;1 (иьу). При этом сумма расстояний й(Т) любого остовного дерева Т будет свя.
зана с общим весом то (Т) дерева Т соотношением ш(Т)=([Ц вЂ” [) ус х Ру — й(Т). Отсюда сразу же очевидно, что МОД в графе 6 с расстоянием й совпадает с лесом максимального веса в графе 6 с весами гс. Если теперь граф 6 несвязен, то ситуация ненамного сложнее. Мы предоставляем читателю в качестве упражнения проверить, что в этом случае справедливо Предложение 12.1.
Лес максимального веса в графе 6=([г, Е) с весами го является объединением минимальных остовных деревьев для всех связных компонент графа 6 с расстояниями й, где й определяется так, как описано выше. Таким образом, задачи МОД и ЛМВ можно рассматривать, по существу, как одну и ту же задачу.
Следующая лемма является аналогом теоремы [2.1 для задачи ЛМВ. Лемма 12.1. Пусгпь (([)ь Т,), (()ь Т,), ..., ([)ь Ть) ) — остовный лес на множестве [1, и пусть [о, и) — ребро, исходяее из К и имеем!ее наибольший вес. Тогда среди всех лесов, содержащих Т= = [[ е, Т„, существует оптимальный лес, содержащий также (о, и[. Таким образом, задачу ЛВМ можно решить, используя любой из двух алгоритмов для МОД, рассмотренных в предыдущих пара- ЖАЛНЫЙ АЛГОРИТМ Вход. Граф О=-(Ч, Е) с весами нн! на ребрах.
Выход. Лес Р максимального веса в О. Ьед!и Р:=Я; мщ!е ЕФЯ бо Ьед[п пусть [н, ч! — ребро в Е максимального веса; делить [н, ч! из Е; 1 н н ч в разных компонентах графа Гу', Р) гьеп Р'. Р[[Ио УВ епб епе Рнс. 12.7. Жадныд алгоритм длн задачи ЛМВ. графах. Мы, однако, построим другой очень естественный алгоритм — естественный настолько, насколько может быть естественной жадность. Жадный алгоритм, очевидно, заслуживает свое имя.
Он постоянно старается включить в Е ребро наибольшего возможного веса Он не делает этого только в том случае, когда при добавлении такого ребра Е становится недопустимым. Довольно удивительно (и зто указывает на простоту структуры задачи ЛМВ) то, что такой наив. Гл. !2. Оемовяые деревья а мавгроиды ный подход, не содержащий никаких элементов заглядывания впе.
ред или возвращения назад, корректен Следующая теорема утверждает, что это действигельно гак Теорема 12.4. Жадный алгоритм корректно решает задачу ЛМВ. Доказапге.гьство. Корректность алгоритма следует непосредственно из леммы !2.1 „'З Пример 12.1 (продолжение). Решим задачу ЛМВ для графа и весов, представленных на рис. !2.3, используя жадный алгоритм.
Этапы решения представлены на рис. !2.8. () 12.4 Матроиды Задачу ЛМВ можно рассматривать как задачу из некоторого широкого класса комбинаторных задач оптимизации. Определение 12.1. Системой подмножеспгв 5=(Е, д) называется конечное множество Е вместе с семейсгвом д подмножеств множества Е, замкнугым относительно включения (т. е. если А Е Ю и А'е:-А, то А'Е,7). Элементы семейства 7 называются независимими.
Комбинагггорная задача оптимизации для системы подмножеспгв (Е, 7) состоит в следующем. Для каждого еЕ Е задан вес иг(е).-яО, и требуется найти независимое подмножество, имеющее наибольший общий вес. () В этом параграфе, как и в следующем, будем искать алгоритмы решения комбинагорных задач оптимизации для некогорых сисгем подмножеств По мому поводу сделаем два замечания Во-первых, нам нужно описать, каким способом система подмножеств (Е, 2) будет представлягься как вход для вычислительного алгоритма Можно предложить выписывать асе независимьге подмножества из Е, используя подходящее представление. Однако такой способ представления д может оказаться очень неэффективным, так как д может содержать до 2'ег подмножеств Поэгому все рассматривае.
мые системы подмножеств будем представляг ь с помощью алгоритма а!о, который по данному подмножеству l множества Е решаст, верно ли, что (С5. Например, в задаче ЛМВ для графа ('(г, Е) очень неэффективно было бы выписывать все леса графа О. Даже если выписывать только максимальные леса, учитывая тот факт, что а замкнуто относительно включения, у нас может остаться подмножеств. Имеегся другой алгоритм аео, который по данному произвольному подмножеству Е множества Е проверяет, верно ли, что Е не содержит циклов; такой алгоритм Аа рассматривался в задаче 2 из гл. 9, Это приводит нас ко второму замечанию. Задача ЛМВ (т.
е. множество всех индивидуальных задач) соответствует не одной комби- 29! 12.!. Маглроидм наторной задаче оптимизации для некоторой системы подмножеств, а многим задачам, по одной для каждого графа, на котором может быть задана задача поиска ЛМВ Вообще говоря, комбинаторные задачи оптимизации, ссютветствующие нескольким сигтемам подмножеств (Е, 2) с об!т(им алгоритмом и!а, можно рассматривать как подслучаи одной и той же вычислительной задачи. Поэтому, хотя каждая комбинаторная задача оп!имизации для некоторой системы подмножеств содержит бесконечно много индивидуальных задач — по одной для каждого множества весов — и, следовательно, ЖАДНЫЙ АЛГОРИТМ Ьей!п 1:=р! мЫ!е ЕФИ до Ьей!и пусть е †элеме нэ Е с нвнбольшнм весом; удалить е нз Е; Н !+еЕН !Ьеп 1:=1+е епе) епд Рнс. !2.9.
Жадный алгоритм для матрондов. сама может рассматриваться как задача оптимизации, мы будем обычно называ'!ь класс задач с одним и тем же алгори1мом и!а просто «задачей», Следующие примеры поясняю! сказанное выше; в них отмечается также еще один важный аспект, Пример 12.2. Задачу ЛМВ для графа ()г, Е) можно рассматривать как комбииаэорную задачу оптимизации для системы подмножеств ('Е, т), где в — класс подмножеств множества Е, являющихся лесами.
В предыдущем параграфе мы видели, что эту задачу можно решить с помощью жадного алгоритма. Учитывая новые понятия, так переформулируем этот алгори !м, чтобы его можно было применять к любой системе подмножеств !Е, Ю); сооэвегствующий алгоритм приведен на рис. 12ТР) Пример 12.3. Задача о максимальном взвешенном паросочетапии для графа !')г, Е) — это комбинаторная задача оптимизации для системы подмножеств 5=(Е, ое!), где ой' — семейство паросочеганий графа !')1, Е).
К сожалению, жадный алгоритм здесь не работает. Контрпример приведен на рис. 12.!О. Жадный алгоритм, применен. ный к ('Е, еуэ), привел бы к паросочетанию, представленному иа рис 12.10(а), тогда как максимальное взвешенное паросочегание имеет вид, представленный на рис. !2.!0(б) Г) Пример !2Л. Если даны орграф 0=(')г, Л) и веса ш!а)э0 для каждого о ЕЛ, то можно поставить следующую задачу: найти в множестве Л подмножество В наибольшего возможного веса так, чтобы никакие две дуги из В не имели общего конца. Это комбина- ') Впаду в этой главе !+е обознвчает I!!(е) н ! — е=! — (е). !о' Гв.
12. Овтовныв дврввьн и матроиды торная задача оптимизации для системы подмножеств (А, вВ), где подмножество В множества А входит в Я гогда и только тогда, когда никакие две дуги из В не имеют общего конца Хотя на первый Т ' А, о! ов (б) Са) Рис. !2.зо, в згляд эта задача аналогична задаче о паросочетании для неориентированных графов, на самом деле она намного проще, Рассматривая орграф на рис. 12!1, можно 3 заметить, чзо при выборе дуги, вхо- 7 5 2 4 дящей в вершину во не имеет | смысла выбирать никакую другую дугу, кроме дуги, имеющей наив, в больший вес. Это связано с тем, что этот выбор локален в том смыс- 7 о,! ле, что он никак не влияет на допустимость выборов в других вершинах. То же самое справедливо 4 для всех остальных вершин Поэтому в данной задаче жадный алоэ горитм буде ! давать оптимальное решение. ( ) Рис. !2.!! Пример 12.б.
Рассмотрим в графе 6=!'(Г, Е) ге множества ребер, которые являются объединениями вершинно непересекающихся пу- тей; соответствующие примеры приведены на рис. 12.12 (а и б) Се- мейство э!их множеств ребер обозначим через з Негрудно понять, что комбинаторная задача оптимизации для системы !Е, д) — э!о несколько замаскированная ЗК Разница в том, что !еперь мы инте. ресуемся пу!лязга вместо обходов — однако, оказывается, что эти два варианта эквивалентны (см задачу 8) Кроме того, мы имеем дело с задачей максимизации вместо задачи минимизации Но это так же, как при переходе от МОЛ к ЛМВ, не имеет существенного значения (см, задачу 9). Поскольку рассма!риваемая задача, по существу, совпадае~ с пресловутой ЗК, можно предположить, что жадный алгоригм— как и более серьезньк подходы — пе решае! эгу задачу, и это дей- ствительно гак.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
