Теорема Радо-Эдмондса: жадность верна ровно на матроидах

Коротко

Главный результат темы: жадный алгоритм находит независимое множество максимального веса для ЛЮБЫХ весов, если отрицательные элементы пропускаются, тогда и только тогда, когда структура - матроид. «Тогда» объясняет, почему Крускал, максимальный лес и «не больше k из каждой группы» работают без отдельных доказательств. «Только тогда» - сильнее и полезнее: если структура не матроид, найдутся веса, на которых жадность ошибётся, и искать их надо среди небольших примеров. Крускал из раздела 11 - буквально жадность на графовом матроиде, и его корректность теперь следствие общей теоремы. Проверено машинно: на двух матроидах 600 прогонов без расхождений с перебором, на рюкзаке - 220 наборов ценностей с ошибкой из 1728.

Во всех числах перебора рюкзака ниже при равных ценностях сохраняем исходный порядок предметов: сначала два предмета веса 3, затем предмет веса 4. При другом разрешении ничьих число ошибок меняется; это соглашение относится к замеру, а не к самой теореме.

Если ты можешь сформулировать теорему в обе стороны, объяснить Крускала через неё и знаешь, что ломается у не-матроидов, листай до «Теперь сам».

Как думаешь, в какую сторону теорема полезнее

У утверждения две половины: «на матроиде жадность верна» и «если не матроид - найдутся веса, на которых она неверна». Первая половина экономит доказательства. А вторая?

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

На что это похоже

Признак делимости. Можно каждый раз делить число на 3 в столбик, а можно сложить цифры - и сразу знать ответ. Три аксиомы матроида - такой же признак: вместо того чтобы для каждой новой задачи искать обменный аргумент или контрпример, ты проверяешь структуру допустимых множеств и получаешь ответ сразу, в обе стороны.

Механизм: формулировка и жадный алгоритм

ТЕОРЕМА (Радо, Эдмондс)
Пусть (E, I) - семейство подмножеств, удовлетворяющее аксиомам (1) и (2)
(наследственная система). Тогда равносильны:
    (а) (E, I) - матроид (то есть выполнено и свойство обмена);
    (б) для ЛЮБОЙ весовой функции w: E → R жадный алгоритм находит
        независимое множество максимального веса.

ЖАДНЫЙ АЛГОРИТМ НА МАТРОИДЕ

A = ∅
отсортировать E по УБЫВАНИЮ веса
для каждого e по порядку:
    если w(e) < 0 - пропустить e
    иначе если A ∪ {e} независимо - добавить e в A
вернуть A

цена: Θ(n·log n) на сортировку плюс n проверок независимости
проверка независимости - своя у каждого матроида, и обычно она и дороже всего

ДВЕ ПОСТАНОВКИ, И ИХ НАДО РАЗЛИЧАТЬ

(А) максимум веса среди ВСЕХ независимых множеств
    элементы с отрицательным весом не берут - они только ухудшают,
    и ответ может не быть базой. Это нормально: цель - вес, а не размер

(Б) максимум (или минимум) веса среди БАЗ - то есть ответ обязан быть
    максимальным независимым множеством
    здесь знак веса не важен: берут всё, что не нарушает независимость,
    только порядок сортировки меняется - по убыванию для максимума,
    по возрастанию для минимума

Крускал - это случай (Б): остовное дерево обязано быть остовным,
даже если все веса положительные и «выгоднее» было бы не брать ничего

Правило

Теорема Радо-Эдмондса: для наследственной системы жадность даёт максимальный по весу независимый набор при ЛЮБЫХ весах тогда и только тогда, когда система - матроид; отрицательные элементы в этой постановке пропускаются. Отсюда два следствия. Положительное: доказав матроидность, доказательство правильности жадного алгоритма писать не нужно - оно уже есть. Отрицательное, и более полезное: если структура не матроид, то существуют веса, на которых сортировка по весу с допустимым добавлением ошибётся. Это ограничение данной схемы, а выбор другого алгоритма зависит от задачи. Алгоритм Крускала - жадность на графовом матроиде, и его корректность следствие теоремы, а не отдельный факт. Цена жадности на матроиде - сортировка плюс n проверок независимости, и дорогая часть почти всегда проверка.

Разбор: Крускал - это и есть жадность на матроиде

Вспомним Крускала из раздела 11: сортируем рёбра по возрастанию веса и добавляем ребро, если оно не образует цикл.

СООТВЕТСТВИЕ
элементы E            = рёбра графа
независимые I         = ациклические наборы рёбер (лесá)
проверка независимости = «не образует цикл» (система непересекающихся множеств)
база                  = остовное дерево (в связном графе)

На минимум сортируют по возрастанию, на максимум - по убыванию; это одна и та же жадность в постановке (Б), и переход между ними честный: минимальная по w база - это максимальная по −w база. Важно, что речь про БАЗЫ: при положительных исходных весах w, если бы мы искали максимум веса среди всех независимых множеств при весах −w (постановка А), ответом было бы пустое множество, ведь все веса отрицательные. Крускалу нужно дерево, поэтому он работает с базами и знака не смотрит.

Обоснуем переход от теоремы для всех независимых наборов к базам. У всех баз матроида один размер r: если бы база была меньше другой, обмен разрешил бы увеличить её, вопреки максимальности. Для минимума исходных весов w выберем константу C больше каждого веса и зададим новые веса v(e)=C−w(e)>0. Максимальный по новому весу независимый набор обязательно база: любой допустимый добавленный элемент увеличивал бы вес. Для базы Σv=Cr−Σw, поэтому максимум нового веса равносилен минимуму исходного. Убывание v - возрастание w, то есть порядок Крускала. Для максимума веса базы достаточно прибавить к исходным весам константу, делающую их положительными: сумма каждой базы вырастет на одну и ту же величину Cr. Так переход верен и для отрицательных весов.

ЧТО ДАЁТ ТЕОРЕМА
в разделе 11 корректность Крускала доказывалась свойством разреза - отдельным
рассуждением на полстраницы. Теперь она СЛЕДСТВИЕ: лесá образуют матроид
(проверено в прошлом уроке), значит жадность верна для любых весов

Машинная проверка в обе стороны - 300 случайных наборов весов на графе из шести рёбер: жадность совпала с полным перебором максимального по весу леса во всех 300 случаях. Столько же прогонов на раздельном матроиде («не больше двух из каждой группы», девять элементов) - тоже ноль расхождений.

Это не доказательство теоремы, а проверка того, что мы правильно её поняли: если бы в реализации жадности или в проверке независимости была ошибка, расхождения появились бы.

Разбор: «только тогда» на примере рюкзака

Теперь обратная половина. Наборы, влезающие в рюкзак, матроидом не являются (прошлый урок), значит ОБЯЗАНЫ существовать ценности, на которых жадность по ценности ошибается. Найдём их перебором.

предметы весов 3, 3, 4; вместимость 6
перебрали ВСЕ наборы ценностей из диапазона 1..12 - это 1728 вариантов
жадность по ценности ошиблась в 220 из них

минимальный пример: ценности 2, 2, 3
    жадность: берёт предмет ценности 3 (вес 4), больше ничего не влезает → 3
    оптимум:  два предмета по 2 (вес 3 + 3 = 6)                          → 4

Обрати внимание на логику: мы не искали контрпример наугад и не надеялись на удачу - теорема ГАРАНТИРОВАЛА, что он есть. Осталось только перебрать небольшой диапазон. Это и есть практическая польза половины «только тогда»: она превращает поиск контрпримера из творческой задачи в механическую.

И ещё одно наблюдение из того же замера: жадность ошиблась в 220 случаях из 1728, то есть в 13%. Случайный тест с вероятностью 87% прошёл бы успешно - вот почему «я прогнал тесты» ничего не доказывает даже на трёх предметах.

а что с ДРОБНЫМ рюкзаком, где жадность верна?
    там структура другая: мы выбираем не подмножество, а ДОЛИ,
    и задача вообще не про независимые множества - это линейное
    программирование (раздел 12), у которого своя теория оптимальности

Разбор: почему обмен достаточен и необходим

Сначала докажем прямую половину. Отрицательные веса пропускаем, нулевые на цену не влияют. Положительные элементы идут в порядке w₁≥…≥wₖ>0. Обозначим через Pⱼ первые j элементов. После их просмотра жадный набор Aⱼ максимален по включению в Pⱼ: любой пропущенный элемент уже нарушал независимость, а добавление других элементов не могло устранить это нарушение.

В матроиде такой набор имеет и наибольший размер. Если бы независимый Bⱼ был больше, свойство обмена разрешало бы добавить к Aⱼ элемент из Bⱼ. Получили противоречие максимальности. Значит в каждом начальном отрезке жадность выбрала не меньше элементов, чем любой независимый конкурент B: |A∩Pⱼ|≥|B∩Pⱼ|.

Теперь перейдём от числа элементов к весу. Положим wₖ₊₁=0 и запишем w(A)=Σⱼ(wⱼ−wⱼ₊₁)·|A∩Pⱼ|. Элемент позиции i учитывается во всех отрезках с j≥i; сумма его коэффициентов равна wᵢ−wₖ₊₁=wᵢ. Например, для весов 5,3,2 и выбора первого и третьего элемента числа выбранных в отрезках равны 1,1,2: 2·1+1·1+2·2=7, как и 5+2. Все разности неотрицательны. Поэтому сравнение чисел элементов в каждом отрезке даёт w(A)≥w(B). Это доказательство для любого набора весов.

Для обратной половины пусть обмен нарушен: независимы I и J, |I|<|J|, но к I нельзя добавить ни один элемент из J\I. Пусть всего n элементов. Назначим вес 1+ε элементам I, вес 1 элементам J\I, остальным 0, где ε=1/(n+1). Жадность сначала возьмёт всё I, затем отвергнет всё J\I. Её вес (1+ε)|I|. Вес допустимого J равен |J|+ε|I∩J| и больше: разница равна |J|−|I|−ε|I\J|>0, поскольку первая часть хотя бы 1, а вычитаемая поправка меньше 1. Нулевые элементы этот проигрыш не исправят. Таким образом, отсутствие обмена действительно создаёт веса, на которых схема ошибается.

Что ломается без этого

Первое: применять теорему к системе, у которой нет наследственности: аксиому (2) надо проверить тоже, хотя она обычно очевидна. Второе: сортировать по возрастанию, когда нужен максимум веса: направление определяется задачей, и перепутать его легко, потому что у Крускала (минимум) сортировка возрастающая. Третье: путать две постановки: при максимуме веса среди ВСЕХ независимых множеств элементы с отрицательным весом брать не надо (и ответ тогда не база), а при поиске оптимальной БАЗЫ - надо, как в Крускале. Четвёртое: думать, что из «не матроид» следует «жадность всегда ошибается»: она ошибается НА НЕКОТОРЫХ весах - на твоих конкретных данных может и не ошибиться, и именно поэтому тесты обманчивы. Пятое: считать, что матроидность решает всё: она даёт верный ответ для МАКСИМУМА ВЕСА независимого множества; стоит поменять целевую функцию (например, максимизировать не сумму, а минимум элемента), и теорема к задаче уже не относится.

Зачем это в работе

Теорема помогает выбрать схему алгоритма до реализации. Для этого нужно проверить аксиомы семейства допустимых наборов; удачных примеров недостаточно. В разобранных задачах встречаются два матроида: раздельный («не больше k_i элементов из каждой категории» - квоты, лимиты, распределение по регионам) и графовый (связность, отсутствие циклов - сети, зависимости, деревья). Если задача сводится к одному из них, можно сразу писать сортировку с проверкой и не искать доказательств. А если в условии ограничена сумма ресурса, матроидность всё ещё нужно проверить: при одинаковом расходе 1 на элемент лимит k даёт равномерный матроид, а произвольные расходы рюкзака могут нарушать обмен. Само слово «сумма» не доказывает ни отсутствие матроида, ни какую-либо гарантию приближения.

Теперь сам

Задача: выбрать максимальный по суммарной стоимости набор рёбер графа, в котором ни одна вершина не имеет больше одного инцидентного ребра (то есть паросочетание). Матроид ли это? Сработает ли жадность?

Ответ. Это НЕ матроид, и жадность в общем случае неверна.

проверим обмен на пути из четырёх вершин:  1 - 2 - 3 - 4
рёбра: a = (1,2), b = (2,3), c = (3,4)

независимые (паросочетания): ∅, {a}, {b}, {c}, {a,c}
    {a,b} - общая вершина 2, нельзя
    {b,c} - общая вершина 3, нельзя

A = {b},  B = {a, c},  |A| = 1 < 2 = |B|
    A ∪ {a} = {b, a} - нельзя
    A ∪ {c} = {b, c} - нельзя
обмен нарушен ⇒ не матроид

Теорема обещает веса, на которых жадность ошибётся, - вот они:

веса: a = 2, b = 3, c = 2
жадность берёт b (вес 3), после чего ни a, ни c недоступны → 3
оптимум: a + c = 4

Это та же конфигурация, что в контрпримере про занятия из первой главы, и неслучайно: «короткое посередине мешает двум по краям» - типовая форма нарушения обмена.

При этом паросочетание максимального веса вычислимо точно - но не жадностью: в двудольном графе это поток минимальной стоимости (раздел 12), в общем - алгоритм Эдмондса. Вывод, который стоит унести: «не матроид» исключает универсальную сортировку по весу с допустимым добавлением, а не решение задачи вообще или любой другой жадный алгоритм.

Главное

Теорема Радо-Эдмондса: для наследственной системы жадность находит независимое множество максимального веса ПРИ ЛЮБЫХ весах тогда и только тогда, когда система - матроид; отрицательные элементы при поиске среди всех независимых пропускаются. Прямая половина экономит доказательства: Крускал - жадность на графовом матроиде (элементы - рёбра, независимость - ацикличность, база - остовное дерево), и свойство разреза из раздела 11 больше не нужно. Обратная половина сильнее: если матроида нет, контрпример ГАРАНТИРОВАННО существует, и его ищут перебором маленьких весов - на рюкзаке 3, 3, 4 при вместимости 6 жадность ошибается на 220 наборах ценностей из 1728 (13%), минимальный пример - ценности 2, 2, 3. Паросочетание - тоже не матроид (на пути из четырёх вершин к {b} нельзя добавить ни a, ни c), и жадность по весу даёт 3 вместо 4. «Не матроид» означает, что эта схема не верна для всех весов; выбор другого алгоритма или специального случая остаётся открытым.