10.9. Матроиды и «жадный» алгоритм

Рассмотрим множество S, элементам которого s; присвоены неотрицательные веса . Вес подмножества S определяется равным сумме весов всех входящих в подмножество элементов. Пусть — набор подмножеств S. Многие задачи комбинаторной оптимизации сводятся к следующей задаче:

Найти член максимального веса.

Например, к этой задаче сводится нахождение остова максимального веса во взвешенном связном графе G, если — набор всех остовов графа

Для решения этой задачи естественно применить следующий алгоритм, называемый «жадным».

Алгоритм 10.1. «Жадный» алгоритм.

Шаг 1. Выбрать такой элемент что для всех таких s, что . Если такого не существует — останов.

Шаг 2. Выбрать такой элемент что для всех таких что . Если такого не существует, останов.

Шаг 3. Выбрать такой отличный от элемент что — максимально среди всех таких s. Если такого не существует — останов. Очевидно, что алгоритм заканчивает работу, получая максимальный по включению член ?. Однако этот член может иметь не максимальный вес в ?.

Например, если , то алгоритм получит , но членом максимального веса является . Однако если мы изменим веса так, чтобы , то алгоритм снова получит являющееся теперь членом максимального веса.

Исследуем взаимосвязь получаемого «жадным» алгоритмом решения со структурой .

Рассмотрим матроид М на множестве S. Пусть — набор независимых множеств М. Пусть

— независимые множества, элементы которых расставлены в порядке невозрастания весов. Таким образом, и В этом случае лексикографически больше если существует такое k, что для и или для и Множество, которое лексикографически не меньше любого другого множества, называется лексикографически максимальным. Из этого определения следует, что лексикографически максимальное независимое множество должно быть базой.

Множество называется оптимальным по Гейлу в , если для всякого существует такое взаимно однозначное соответствие между и В, что для всех где b — элемент В, соответствующий а. Очевидно, что оптимальными по Гейлу могут быть только базы. Кроме того, если база оптимальна по Гейлу, то должна иметь максимальный вес.

Далее мы принимаем, что элементы всякого множества упорядочены по невозрастанию весов.

Теорема 10.32. Пусть — набор независимых множеств матроида М на а В - база М. Для произвольного взвешивания элементов эквивалентны следующие утверждения:

1. В лексикографически максимально в ?.

2. В оптимально по Гейлу в ??

3. В член максимального веса.

Доказательство.

Пусть -лексикографически максимальная база матроида М. Допустим, что В не оптимальна по Гейлу. Тогда существует такое независимое множество а, что для Рассмотрим независимые множества аксиоме 1.3 существует такой I, что — независимое множество. Но лексикографически больше В, поскольку что противоречит лексикографической максимальности В в . Очевидно.

Пусть — лексикографически максимальная база, а В — база максимального веса. Поскольку справедливо то для всех . Из того, что В — база максимального веса, следует, что Таким образом, В также лексикографически максимальна.

Легко показать (аналогично тому, как это сделано в доказательстве теоремы 10.32), что применение «жадного» алгоритма дает лексикографически максимальную базу, которая по только что доказанной теореме имеет максимальный вес. Таким образом, справедливо следующее утверждение:

Теорема 10.33. Пусть — набор независимых множеств матроида на S, элементам которого присвоены неотрицательные веса. Применение «жадного» алгоритма к набору дает член набора максимального веса.

Из этой теоремы очевидно, что база максимального веса получается, если выбирать элементы матроида в порядке невозрастания весов, отвергая только те элементы, выбор которых нарушает условие независимости получаемого множества. Применение «жадного» алгоритма для получения базы минимального веса очевидно.

Рассмотрим, например, взвешенный граф G на рис. 10.5. Веса ребер приведены на рисунке. Для применения «жадного» алгоритма к получению остова графа G максимального веса необходимо сначала расположить ребра в порядке невозрастания весов. Таким образом, ребра будут упорядочены следующим образом:

С помощью алгоритма будут получены сначала три ребра а, b и , поскольку они не образуют цикла. Ребро f будет отклонено, так как множество содержит цикл. Следовательно, будет выбрано ребро d. Ребро с будет отклонено, поскольку оно образует цикл с уже выбранными ребрами и d.

Рис. 10.5. Взвешенный граф.

По этой же причине будут отклонены ребра g и h. Таким образом, «жадный» алгоритм порождает множество являющееся остовом графа G максимального веса.

Докажем сейчас теорему, обратную теореме 10.33.

Теорема 10.34. Пусть — набор подмножеств множества S, обладающий таким свойством, что если А и то В Тогда применение к набору F «жадного» алгоритма дает член набора максимального веса, только если — набор независимых множеств матроида на

Доказательство. Из аксиом независимости очевидно, что нам необходимо показать, что если то такой существует , что

С этой целью определим веса элементов S следующим образом: , где . Тогда «жадный» алгоритм выберет сначала элементы . Если не существует такого что алгоритм выберет элементы из Поэтому, когда алгоритм закончит работу, в результате получится множество, имеющее вес, равный весу А.

Если , то . Очевидно, что можно выбрать таким, что . Но тогда «жадный» алгоритм не породил члена набора максимального веса, т. е. мы пришли к противоречию.

Применение «жадного» алгоритма к задаче нахождения остова максимального веса было впервые предложено в работе [10.7]. Расширение применения этого алгоритма на матроиды было предложено в работах