Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 54
Текст из файла (страница 54)
Поэтому такое ребро можно включить в искомое дерево, не теряя оптимальности. Предположим, что это ребро [о„о,1. Далее, применяем теорему к множествам [/,=(оп о,), [/„..., [/„ и Т=-([о„о,1). Теперь теорема утверждает, что можно добавить к дереву кратчайшее ребро, исходящее из о, или о, (отличное от [о„оь)), и после этого останется возможность дополнить образованное дерево до оптимального МОД. Алгоритм теперь очевиден: начинаем, например, с множества [/=(о,) и рекурсивно добавляем к Т кратчайшее ребро, исходящее из [/, до тех пор, пока к [/ не будут добавлены все вершины, в результате чего будет построено неко торов дерево. 2В2 Гл.
12. Остаеные деревья и матроиды Этот алгоритм для задачи МОД приведен на рис. 12.2. Для облег- чения основной вычислительной задачи — нахождения кратчайшего ребра, исходящего из (1, — мы храним массив ближайшая(п). Для каждой вершины с6(г — (/ значением ближайшая(и) является вершина из (1, ближайшая к ш Поэтому для нахождения кратчай- шего ребра, исходящего из (е', достаточно найти кратчайшее ребро АЛГОР1!ТМ НОСТРОГИ(ИЯ М!ИП1МАЛЬНОГО ОСТОВ1ГОГО ЛЕРЕВА Вход. Множество верн.нн Н и рясстояння бн мшкду всеми парами вершин чьч,нзН.
Выход. Кратчайшее остовное зерево (Н, Т). Ьей)п О:=(чг), Т.=йз; 1ог вн чЕН вЂ” (чг) йо блимайшая(ч):=ч,! !сопмпеп(: задание начальных значений) ыЬИе 0 Ф Н' йо Ьей!п пн'и:=сч; 1ог вн чЕН вЂ” Б до И б(ч, ближайшая(ч)) < пнп 1Ьеп ппп."=б(ч, близсайшая(ч)), следующая:=ч; (сошшеп1.
найтн в Н вЂ” !) вершину, ближайшую к О) Б:=О ()(следращия), Т:=Т()((следующая, бшжайшая(следующая)1); 1ог вц чЕУ вЂ” 0 йо И д!ч, ближайшая(ч!) > б(ч, следующая~ Шеп ближайшая(ч):=следующая; епй епд Рнс. !2.2. Алгоритм посгроенвя минимального остовного веревя. среди ребер вида (и, ближайшая(в)), пр)г. Естественно, массив ближайшая должен пересчитываться каждый раз, когда новая вер. шина добавляется к (г'. В остальном алгоритм совершенно очевиден.
Теорема 12.2. Алгоритм, представленный на рис. 11,2, корректно решает задачу МОД за время 0(!)г(з). Доказательство. Так как в конце алгоритма ((1(=((г( и к Т всегда добавляется ребро, исходящее из (г', то получающийся в результате граф ((г, Т) является остовиым деревом в 6. Остается показать, что это дерево оптимально Покажем индукцией по мощности множества (е', что всегда существует оптимальное остовное дерево в 6, содержащее соответствующее множество Т.
Это, оче. видно, справедливо, когда (е'=(и,) и Т=Я. Предположим, что утверждение справедливо для некоторого 1=-((е!, 1(1(((г!. Частичное остовное дерево ((1, Т) можно рассматривать как часть леса ((Уы Т,),..., ((Глы Тх)), где У,=(е',й=((г! — ((е'(+1 и Т,= —... Т„= Применяя теорему 12.1, получаем, что среди всех дере. вьев, содержащих Т, существует кратчайшее дерево, содержащее Т и кратчайшее ребро, исходящее из (е'.
Но по предположению индукции существует глобально оптимальное дерево, содержащее Т. 12.2. Алгоритм го сложностью 0 (!Е!!о81У!) 283 Поэтому существует также оптимальное остовное дерево, содержащее дерево Т и кратчайшее ребро, исходящее из О, которые вместе в точности образуют дерево Т на следующем этапе, когда !И = =/+1 Этим завершается шаг индукции. Для получения временнбй оценки заметим, что алгоритм состоит из !У! — 1 этапов; на каждом этапе добавляется одно ребро. Присвоение начальных значений требует времени О(!У!), и нахождение !4 10 9 о> Рис.
!2.3. значения переменной следующая также требует времени О(!У!> Наконец, новые значения элементов массива ближайшая также можно вычислить за время О(!У!). Отсюда следует оценка О(!УР) для всего алгоритма. Г3 Пример 12.1. Найдем с помощью алгоритма, приведенного на рис.
!2.2, минимальное остовное дерево в графе 0= (У, Е), показанном на рис. !2.3. (Считается, что если (оо о>)(Е, то г(ы.—.-оо.) Начиная с вершины ц, получим девять этапов, представленных на рис. !2.4. Около каждой вершины щ еще не вошедшей в множество (I, указано зн, ~ение ближайшая Ы. Искомое минимальное остовное дерево предс>авлено на рис, 12.4(и). 17,2 алгоритм со сложностью О() Е) 1оя) У!) для задачи о минимальном остовном дереве Алгоритм для нахождения МОД из предыдущего параграфа со =ложностью О(!У!') не легко улучшить, если в качестве входных данных используется матрица расстояний размера !У!х !У!.
Причила этого очень проста: любой алгоритм, который строит МОД, дол. кен просмотреть каждый элемент матрицы расстояний хотя бы один >аз. Ибо если некоторый элемент г(п никогда ле просматривается ьчгоритмон, то мы не можем быть уверены, что соответствующее реб>о следует исключить из МОД. Например, мы можем проскочить сратчайшее ребро, хотя легко понять, что кратчайшее ребро всегда >ключается в МОД.
Таким образом, просмотр совершенно необхо Гл. 12. Оотовяьее деревья и матроидье Нв Нв О О Рис. !2.4. Не Н, Н, О О О () Не Н, НЕ О О О (в) (д) (ж) нЗ О н, О н, О (и) Нв Н, Н, О О О (б) Нь Нб Нв О О О (г) (с) (э) Нв О Нь О «2.2. Алгоритм оо сложностью О (1Е!1од! 1'1) 285 димой информации уже требует 8(!У!ь) времени, и, следовательно, алгоритм, представленный на рис. 12.2, асимптотически оптимилен Однако в некоторых практических ситуациях требуется найти МОД для разреженных графов, т, е.
графов, число ребер в которых намного меньше, чем ('~~'), Например, в задачах 4 и 5 в связи с некоторыми геометрическими задачами будут введены графы, имею. щие не более 3. !У! ребер. Совсем не очевидно, что для нахождения МОД для таких графов оценка О(!У!ь) неулучшаема. В данном параграфе мы построим алгоритм для задачи МОД с временем работы О(!Е!!од!У!). Этот алгоритм асимптотически лу цпе предыдущего ) алгоритма прп применении к графам, имеющим меньше чем> (д(!У!ь/!ой!У!) ребер. Алгоритм основан на теореме !2.!. Теорема 12.1, по существу, утверждает, что при добавлении к Т кратчайшего ребра, исходящего из некоторои компоненты леса (У, Т), не теряется возможность прийти в результате к оптимальному дереву. Наш предыдущий алгоритм использует эту теорему в ограниченной степени: в нем ребра добавляются только к одной компоненте леса (У, Т).
Алгоритм, который мы сейчас собираемся построить, добавляет ребра одно. временно ко всем компонентам леса (У, Т), заставляя минимальное остовное дерево «расти« во всех направлениях. Посмотрим, как воплотить эту простую идею. Работа нашего алгоритма будет состоять из этапов. На каждом этапе находятся связные компоненты леса (У, Т) и определяется кратчайшее ребро, исходящее из каждой компоненты. В конце этапа все эти ребра добавляются к Т. Затем вычисляются связные компоненты Я» ... ...,Еь леса (У, Т) за время О(!Е!) с использованием алгоритма ПОИСК (см, пример 9. ! и задачу ! из гл. 9). Чтобы для каждого множества вершин Яь выбрать ребро крат. чайшее(ь) — кратчайшее ребро, исходящее из Я» — все ребра просматриваются по очереди.
Если обнаруживается ребро, кратчайшее среди всех просмотренных ребер, исходящих из Е» то в качестве кратчайшее(1) берется это ребро. После того как все ребра таким образом просмотрены, значения в массиве кратчайшее являются окончательными.
Описанный алгоритм приведен на рис. 12.5. Теорема 12.3. Алгоритм, представленный на рис. 12.5, корреюпчо находит МОД для графа (У, Е) и функции расстояния й за время 9(|Е!!од!У!). Доказательство. Корректность алгоритма также следует из теоремы !2.1. Поскольку к Т добавляются кратчайшие ребра, исхо вящие из каждой компоненты леса (У, Т), то теорема !2. ! гарантиэует, что все эти добавления к МОД допустимы. (Одновременное хобавление ребер не порождает циклов. Почему?) 286 Гл. !2.
Остовные деревья и литроиды Назовем каждое выполнение цикла п[аЦе этапалг. Этап состоит из вычисления массива кратчайшее и нахождения связных компонент леса (]ч, Т). Последнее можно выполнить за время 0(]Т!)= =0([[г!), используя ПОИСК (см. задачу 1 из гл. 9); в действительности за время 0([]г!) можно вычислить массив компонента, содержащий для каждой вершины имя связной компоненты, которой ВТОРОЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ МОД Вход. Связный граф О=(Ч, Е) и расстояния д(и, ч) для каждого ребра [и, ч[чЕ. Выход. Кратчайшее вставное дерево (Ч, Т) в О. Ьеа!п Т:=Я, С;=((ч ), ..., (чаЦ; (сошгпеп1: задание начальных значений; С вЂ” набор связных компонент в (Ч, ТП мЬИе [С] М 1 до Ьеа!п 1ог а И 5! С С до ш1 и [11: = ьо; !ог аИ [и, ч]СЕ до Ьей(п пусть 5„5; — множества, содержащие соответственно ч и и; П1М! Тпеп Ьей [п П д (и, ч) < гп1п !1] Гпеп пип Ц]:=д (и, ч), кротчайшвеЦ]:=[и, ч]; п д (и, ч) < пип Ц) !ьеп гп1п Щ:=с( (ч, и), крошчойшвеЦ]:=-[и, ч]; епд епд (созпшепг: крвтчвдшееЦ] — зто кратчайшее ребро, выходящее из5;) !ог ан 51сС до Т:=ТЦ(кротчайшееЦ]); найти мйожество С связных компонент графа (Ч, Т) епд епд Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
