Конспект: матроиды и границы жадности

Понятия

Матроид (E, I) - конечное множество и семейство независимых подмножеств с тремя аксиомами.

База - максимальное независимое множество. Ранг - её размер (у всех баз одинаков).

Субмодулярность - не возрастающая отдача: f(A∪{x})−f(A)≥f(B∪{x})−f(B) при A⊆B, x∉B. Аддитивная цель (сумма весов) - граничный случай, где это равенство; для неё работает более сильная теорема Радо-Эдмондса. Монотонность - добавление элемента не уменьшает цель; без неё оценка 1 − 1/e неверна.

Что унести

АКСИОМЫ
(1) ∅ независимо
(2) подмножество независимого независимо            НАСЛЕДСТВЕННОСТЬ
(3) |A| < |B| ⇒ найдётся x ∈ B \ A с A ∪ {x} ∈ I    ОБМЕН  ← вся суть здесь
    обещан ХОТЯ БЫ ОДИН элемент, а не любой

ТЕОРЕМА РАДО-ЭДМОНДСА
для наследственной системы равносильны:
    система - матроид
    ⇔ жадность по убыванию веса даёт максимум веса ПРИ ЛЮБЫХ весах,
       пропуская отрицательные элементы при выборе среди всех независимых

ЖАДНОСТЬ НА МАТРОИДЕ
A = ∅; для e по убыванию веса: если A ∪ {e} независимо - добавить
цена: сортировка Θ(n·log n) + n проверок независимости (проверка обычно и дороже)

Замеры. Жадность против полного перебора: раздельный матроид - 300 прогонов без расхождений, графовый - 300 без расхождений. Рюкзак 3, 3, 4 при C = 6, ничьи разрешаем исходным порядком предметов: жадность по ценности ошибается на 220 наборах ценностей из 1728 (13%), минимальный пример - ценности 2, 2, 3 (жадно 3, оптимум 4). Случайный тест прошёл бы с вероятностью 87%.

ТРИ СТУПЕНИ, ЕСЛИ МАТРОИДА НЕТ
1. пересечение ДВУХ матроидов - точно за полином (Эдмондс), но НЕ жадностью
   (двудольное паросочетание, назначения); ТРИ матроида - NP-трудно
2. МОНОТОННАЯ субмодулярная цель с f(∅)=0, не больше k>=1 элементов:
   жадность даёт гарантию 1 − 1/e ≈ 0.632.
   Для максимального покрытия улучшение на фиксированное ε>0
   за полином невозможно при P≠NP.
3. остальное - динамика, потоки, приближения

Проверять надо и ЦЕЛЬ, а не только структуру. Максимальное покрытие k множествами: структура - равномерный матроид, но цель (размер объединения) не аддитивна, и теорема не применима. Замер: на множествах A = {2,3,4,5,6}, B = {1,2,4}, C = {3,5,6,7}, D = {2,3,5,6} при k = 2 жадность покрывает 6 элементов из 7 при любом разрыве ничьих (B ∪ C даёт все семь), то есть 0.857 - хуже оптимума, но лучше гарантии 0.632.

Чек-лист: назвать цель → описать допустимые наборы → проверить обмен → при провале перебрать маленькие веса (контрпример гарантирован) → при успехе писать сортировку плюс проверку.

Тихие ошибки: проверять только первые две аксиомы; читать обмен как «любой элемент подойдёт»; забыть проверить аддитивность цели; решив «не матроид», сразу браться за динамику, пропустив пересечение двух матроидов; читать 0.632 как «плохо» (для NP-трудной задачи это сильный результат, на практике обычно 0.9 и выше).

Куда это ведёт

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