Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 97
Текст из файла (страница 97)
и Для заданного матронда М = (В,Х) назовем элемент х ф А расширением (ехтелгйоп) множества А е Х, если его можно добавить в А без нарушения независимости, т.е. х — расширение множества А, если А О (х) е 2'. В качестве примера рассмотрим графовый матроид Мг.. Если А — независимое множество ребер, то ребро е является расширением множества А тогда и только тогда, югда оно не принадлежит этому множеству и его добавление в А не приведет к образованию цикла. Если А — независимое подмножество в матроиде М, то если у него нет расширений, говорят, что А — максимальное множество. Таким образом, множество А — максимальное, если оно не содержится ни в одном большем независимом подмножестве матроида М.
Сформулированное ниже свойство часто оказывается весьма полезным. Теорема 16.6. Все максимальные независимые подмножества матроида имеют один и тот же размер. Доказатнельстнво. Докажем теорему методом от противного. Предположим, что А — максимальное независимое подмножество матроида М и что существует другое максимальное независимое подмножество В матроида М, размер которого превышает размер подмножества А.
Тогда из свойства замены следует, что множество А расширяемо до большего независимого множества А О (х) за счет некоторого элемента х е  — А„что противоречит предположению о максимальности множества А. Л В качестве иллюстрации применения этой теоремы рассмотрим графовый матрона Мг: связного неориентированного графа С.
Каждое максимальное независимое подмножество Мг. должно представлять собой свободное дерево, содержащее ровно ٠— 1 ребер, которые соединяют все вершины графа С. Такое дерево называется вставным деревом (зрапшпй гтее) графа С. Говорят, что матроид М = (Я, Х) взвешенный (тве16)ттед), если с ним связана весовая функция в, назначающая каждому элементу х Е Я строго положительный Часть |Ч. Усовершенствованные методы разработки и анализа 470 вес и (х). Весовая функция и обобщается на подмножества Я путем суммирования: и(А) = ~~~ и(х) веА для любого подмножества А С Я.
Например, если обозначить через и(е) длину ребра е графового матроида Мс, то и (А) — суммарная длина всех ребер, принадлежащих множеству А. Жадные алгоритмы на взвешенном матроиде Многие задачи, для которых жадный подход позволяет получить оптимальное решение, можно сформулировать в терминах поиска независимого подмножества с максимальным весом во взвешенном матроиде. Итак, задан взвешенный матроид М = (Я,Т) и нужно найти независимое множество А е Х, для которого величина и(А) будет максимальной.
Назовем такое максимальное независимое подмножество с максимально возможным весом оннгимальным подмножеством матроида. Поскольку вес и (х) каждого элемента хЕ Я положителен, оптимальное подмножество всегда является максимальным независимым подмножеством, что всегда помогает сделать множество А большим, насколько это возможно.
Например, в задаче о минимальном вставном дереве (ш1п1ппип-зрапп1пя~гее ргоЫегп) задается связный неориентированный граф С = (К Е) и функция длин и такая, что и (е) — (положительная) длина ребра е. (Термин "длина" используется здесь для обозначения исходного веса, соответствующего ребру графа; термин "вес" сохранен для обозначения весов в соответствующем матроиде.) Необходимо найти подмножество ребер, которые соединяют все вершины и имеют минимальную общую'длину. Чтобы представить эту проблему в виде задачи поиска оптимального подмножества матроида, рассмотрим взвешенный матроид Мс с весовой функцией и', где и'(е) = ио — и (е), а величина ио превышает максимальную длину ребра. В таком взвешенном матроиде любой вес является положительным, а оптимальное подмножество представляет собой остовное дерево в исходном графе, имеющее минимальную общую длину. Точнее говоря, каждое максимальное независимое подмножество А соответствует остовному дереву, и, поскольку для любого максимального независимого подмножества А справедливо соотношение и'(А) = ((У~ — 1) ио — и(А), то независимое подмножество, которое максимизирует величину и' (А), должно минимизировать величину и (А).
Таким образом, любой алгоритм, позволяющий найти оптимальное подмножество А произвольного матроида, позволяет также решить задачу о минимальном остовном дереве. Глава 16. Жадные алгоритмы 471 В главе 23 приводится алгоритм решения задачи о минимальном остовном дереве, а здесь описывается жадный алгоритм, который работает для произвольного взвешенного матроида. В качестве входных данных в этом алгоритме выступает взвешенный матроид М = (Я, Х) и связанная с ним весовая функция ю. Алгоритм возвращает оптимальное подмножество А. В рассматриваемом псевдокоде компоненты матроида М обозначены как Я [М] и Х [М], а весовая функция — через ю.
Алгоритм является жадным, поскольку все элементы х Е Б рассматриваются в нем в порядке монотонного убывания веса, после чего элемент добавляется в множество А, если множество А 0 (х) — независимое. Океепу(М, ю) А 9 2 Сортировка множества Я[М] в порядке убывания ю 3 аког каждого х Е о[М] в порядке монотонного убывания веса ю(х) 4 бо!Р А О (х) Е Х[М] 5 Изеп А ~ — А 0(х) 6 ге1цгп А Элементы множества Я рассматриваются по очереди, в порядке монотонного убывания веса. Рассматриваемый элемент х добавляется в множество А, если он не нарушает независимость последнего.
В противном случае элемент х отбрасывается. Поскольку по определению матроида пустое множество является независимым и поскольку элемент х добавляется в множество А, только если множество А О (х) — независимое, подмножество А по индукции всегда независимо. Таким образом, алгоритм Окннпт всегда возвращает независимое подмножество А. Вскоре вы увидите, что А — подмножество с максимальным возможным весом, поэтому оно является оптимальным.
Время работы алгоритма Окннл' легко проанализировать. Обозначим через и величину [о[. Фаза сортировки длится в течение времени О (и 1к и). Строка 4 выполняется ровно и раз, по одному разу для каждого элемента множества Я. При каждом выполнении строки 4 требуется проверить, является ли независимым множество А 0 (х). Если каждая подобная проверка длится в течение времени О ( г' (и) ), общее время работы алгоритма составляет О (п !к и + и г" (и) ).
Теперь докажем, что алгоритм Окннзу возвращает оптимальное подмножество. Лемма 16.7 (Матроиды обладают свойством жадного выбора). Пусть М = = (5,Х) — взвешенный матроид с весовой функцией ю, и пусть множество Я отсортировано в порядке монотонного убывания весов. Пусть х — первый элемент множества Я, такой что множество (х) независимо (если он существует).
Если элемент х существует, то существует оптимальное подмножество А множества Я, содержащее элемент х. Часть 1У. Усовершенствованные методы разработки н анализа 472 Доказатеаьсятво. Если такого элемента х не существует, то единственным независимым подмножеством является пустое множество и доказательство закончено. В противном случае предположим, что  — произвольное непустое оптимальное подмножество. Предположим также, что х ф В; в противном случае считаем, что А = В, и доказательство закончено. Ни один из элементов множества В не имеет вес, больший чем ю(х). Чтобы продемонстрировать это, заметим, что из у Е В следует, что множество (у) независимо, поскольку В Е Х, а семейство Х наследственное.
Таким образом, благодаря выбору элемента х обеспечивается выполнение неравенства ю (х) > ю (у) для любого элемента у е В. Построим множество А, как описано ниже. Начнем с А = (х). В соответствии с выбором элемента х, множество А — независимое. С помощью свойства замены будем осуществлять поиск нового элемента множества В, который можно добавить в множество А, пока не станет справедливо соотношение 1А! = )В); при этом множество А останется независимым.
Тогда А =  — (у) 0 (х) для некоторого элемента у е В, так что ю(А) = ю(В) — ю(у)+ю(х) > ю(В). Поскольку множество  — оптимальное, множество А тоже должно быть опти- мальным. Поскольку х е А, лемма доказана. Теперь покажем, что если какой-то элемент не может быть добавлен вначале, он также не может быть добавлен позже. Лемма 16.8. Пусть М = (Я,Х) — произвольный матроид. Если х — элемент Я, представляющий собой расширение некоторого независимого подмножества А множества Я, то х также является расширением пустого множества 9.
Доказатетьсоыо. Поскольку х — расширение множества А, то множество А О (х) независимое. Так как семейство Х является наследственным, то множество (х) должно быть независимым. Таким образом, х — расширение пустого множества И. Следствие 16.9. Пусть М = (Я,Х) — произвольный матроид. Если х — элемент множества Я, который не является расширением пустого множества И„то этот элемент также не является расширением любого независимого подмножества А множества Я. Доказатечьстлво. Это следствие — обращение леммы 16.8.
В следствии 16.9 утверждается, что любой элемент, который не может быль использован сразу, не может использоваться никогда. Таким образом, в алгоритме Глава 16. Жадные алгоритмы 473 бкнюу не может быть допущена ошибка, состоящая в пропуске какого-нибудь начального элемента из множества Я, который не является расширением пустого множества 6, поскольку такие элементы никогда не могут быть использованы. Лемма 16.10 (Матроиды обладают свойством оптимальной подструктуры). Пусть х — первый элемент множества Я, выбранный алгоритмом Оккепу для взвешенного матроида М = (Я, Х).
Оставшаяся задача поиска независимого подмножества с максимальным весом, содержащего элемент х, сводится к поиску независимого подмножества с максимальным весом для взвешенного матроида М' = (У,Т'х), где У = (р Е В: (х,р) Е т), Х' = (ВСЯ вЂ” (х): ВО(х) ЕХ), и весовая функция матроида М' совпадает с весовой функцией матроида М, ограниченной на множество У. (Назовем матрона М сужением (соп1гасбоп) матронда М на элемент х.) Доказательство. Если А — произвольное независимое подмножество с максимальным весом матроида М, содержащее элемент х, то А' = А — (х) — независимое подмножество матроида М'. Справедливо также обратное: из любого независимого подмножества А' матроида М' можно получить независимое подмножество А = А' О (х) матроида М.
Поскольку в обоих случаях выполняется соотношение ю (А) = и (А') + ю (х), решение с максимальным весом, содержащее элемент х, для матроида М позволяет получить решение с максимальным весом для матроида М' и наоборот. И Теорема 16.11 (Корректность жадного алгоритма для матроидов). Если М = = (Я, Х) — взвешенный матроид с весовой функцией и, то алгоритм Окннпу(М, и) возвращает оптимальное подмножество. Доказательство.
Согласно следствию 16.9, обо всех пропущенных ранее элементах, не являющихся расширениями пустого множества 9, можно забыть, поскольку они никогда больше не понадобятся. Когда выбран первый элемент х, из леммы 16.7 следует, что процедура Окнюу не допускает ошибки, добавляя элемент х в множество А, потому что существует оптимальное подмножество, содержащее элемент х. И наконец, из леммы 16.10 следует, что в оставшейся задаче требуется найти оптимальное подмножество матроида М', представляющего собой сужение матроида М на элемент х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
