Жадные алгоритмы и матроиды

Когда жадность оптимальна?

Жадный алгоритм принимает локально наилучшее решение на каждом шаге, не пересматривая прошлых решений. Просто и быстро — но не всегда оптимально. Жадный алгоритм для задачи о рюкзаке даёт не оптимум. Жадный алгоритм Крускала для MST — даёт оптимум. Почему? Ответ — матроидная структура задачи. Матроиды — это абстрактная алгебраическая структура, и для них жадность всегда оптимальна. Это один из самых глубоких и красивых результатов комбинаторной оптимизации.

Жадный алгоритм для MST: доказательство

Алгоритм Крускала: сортируем рёбра по весу. Жадно добавляем минимальное ребро, не создающее цикл.

Лемма об отсечении (Cut Lemma): для любого разреза (S, V∖S) минимальное ребро через разрез входит в MST.

Доказательство: пусть e* — минимальное ребро через разрез, и T — MST, не включающее e*. Добавим e* в T → образуется цикл, который пересекает разрез как минимум в одном другом ребре e'. Так как e* минимально в разрезе: w(e*) ≤ w(e'). Заменим e' на e* в T → новое дерево T' с весом w(T') ≤ w(T). Но T — MST → w(T') = w(T), и e* входит в MST. ✓

Матроид: определение

Матроид M = (E, I): E — «элементы», I ⊆ 2^E — «независимые» множества. Аксиомы:

I1 (не пустой): ∅ ∈ I.

I2 (наследование): если Y ∈ I и X ⊆ Y, то X ∈ I (подмножество независимого — независимо).

I3 (обмен): если X, Y ∈ I и |X| < |Y|, то существует e ∈ Y∖X: X ∪ {e} ∈ I.

Аксиома I3 — ключевая! Она означает «можно всегда вырасти»: меньшее независимое можно дополнить элементом из большего.

Базис матроида: максимальное независимое множество. По I3 все базисы имеют одинаковый размер (ранг матроида).

Примеры матроидов

Графовый матроид (цикловой матроид): E = рёбра графа G, I = ациклические подграфы (леса). Базис = остовное дерево (MST!).

Проверка аксиом: ∅ — лес ✓. Подграф леса — лес ✓. Обмен: если |F₁| < |F₂| для лесов, то F₂ имеет больше компонент связности → существует ребро из F₂, соединяющее разные компоненты F₁ → добавим его к F₁ без цикла ✓.

Линейный матроид: E = столбцы матрицы A над полем F, I = линейно независимые подмножества столбцов. Ранг матроида = ранг матрицы.

Матроид разбиения: E разбит на группы E₁,...,Eₖ. I = множества с не более 1 элементом из каждой Eᵢ. Используется для представления расписаний.

Однородный матроид Uₖₙ: I = все подмножества E размером ≤ k. Это «k-разреженный» матроид.

Теорема Радо-Эдмондса

Теорема: жадный алгоритм оптимален для задачи максимального взвешенного независимого множества тогда и только тогда, когда (E, I) — матроид.

Жадный алгоритм: сортировать элементы по убыванию веса. Добавлять следующий элемент, если после добавления множество остаётся независимым.

Доказательство «⇐» (матроид → жадность оптимальна): индукция по размеру множества. На каждом шаге максимальный элемент должен входить в какой-то оптимум (иначе можно заменить через аксиому обмена).

Доказательство «⇒» (жадность оптимальна → матроид): если I₃ нарушена, строим веса, на которых жадность даёт неоптимальное решение.

Следствия

MST: графовый матроид → алгоритм Крускала оптимален ✓.

Задача назначения: двудольный граф G, нужно выбрать k рёбер, не инцидентных одной вершине (= паросочетание размера k). Это пересечение двух матроидов разбиения! → полиномиально решаемо (алгоритм Эдмондса).

Задача Хаффмана: оптимальный префиксный код для сжатия. Жадный алгоритм Хаффмана оптимален — структура матроидная.

Пересечение матроидов

Задача: найти максимальное независимое множество I ∈ I₁ ∩ I₂ (пересечение двух матроидов).

Алгоритм: O(r² · T_oracle), где r — ранг, T_oracle — время проверки независимости. Полиномиально!

Пересечение 3 матроидов: NP-трудно. Это граница полиномиальной разрешимости.

Примеры:

Максимальное паросочетание в двудольном графе = пересечение двух матроидов разбиения
Раскраска двудольного графа = пересечение двух матроидов (назначение цветов)

Полный разбор: жадный алгоритм для взвешенного матроида

Задача: граф G с 5 вершинами и 7 рёбрами с весами. Найти MST.

Рёбра по убыванию веса: (1-2, 8), (2-5, 7), (3-4, 6), (1-3, 5), (2-4, 4), (1-4, 3), (4-5, 2).

Жадный алгоритм (Крускал, начинаем с максимального веса — для MST обычно с минимального, но здесь иллюстрируем):

Берём минимальные: (4-5, 2): лес = {4-5} ✓. (1-4, 3): {4-5, 1-4} ✓. (2-4, 4): {4-5, 1-4, 2-4} ✓. (1-3, 5): {4-5, 1-4, 2-4, 1-3} ✓ — 4 ребра для 5 вершин = дерево.

MST = {4-5, 1-4, 2-4, 1-3}, вес = 2+3+4+5 = 14.