Матроид: структура, в которой жадность не может ошибиться

Если ты знаешь три аксиомы матроида, умеешь проверить свойство обмена на примере и помнишь, почему рюкзак не матроид, листай до «Теперь сам».

Как думаешь, почему доказательства так похожи

Посмотри на то, что мы делали: в выборе занятий обменивали занятие, в расписании - соседнюю задачу, у Хаффмана - лист дерева, в остовном дереве (раздел 11) - ребро из цикла. Каждый раз одно и то же движение: взять чужой элемент, подставить свой, показать, что не хуже.

Когда четыре доказательства имеют одинаковую форму, это обычно значит, что они - частные случаи одного. Вопрос: какое свойство задачи делает обмен ВОЗМОЖНЫМ? Найдём его - и получим теорему вместо четырёх доказательств.

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

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

Механизм: три аксиомы

МАТРОИД M = (E, I)
    E - конечное множество элементов (основа)
    I - семейство подмножеств E, называемых НЕЗАВИСИМЫМИ

АКСИОМЫ
(1) ∅ ∈ I                                    пустое независимо
(2) если A ∈ I и B ⊆ A, то B ∈ I             НАСЛЕДСТВЕННОСТЬ
(3) если A, B ∈ I и |A| < |B|, то найдётся
    x ∈ B \ A такой, что A ∪ {x} ∈ I          СВОЙСТВО ОБМЕНА

СЛОВАРЬ
БАЗА      - максимальное независимое множество (куда больше ничего не добавить)
РАНГ      - размер базы; из аксиомы (3) следует, что ВСЕ базы одного размера
ЦИКЛ      - минимальное ЗАВИСИМОЕ множество (в графовом матроиде это настоящий цикл)
ВЕСОВОЙ   - матроид, у которого каждому элементу приписан вес

ПРИМЕРЫ МАТРОИДОВ

графовый (лесной)     E = рёбра графа; A независимо ⇔ A не содержит цикла
                      базы = остовные леса, ранг = n − (число компонент)
векторный             E = векторы; A независимо ⇔ ЛИНЕЙНО независимы, то есть
                      ни один вектор набора не выражается через остальные
                      суммами и умножением на числа
                      (отсюда и слово «независимый» во всей теории)
равномерный           E - что угодно; A независимо ⇔ |A| <= k
                      (базы - все k-элементные подмножества)
трансверсальный       дан двудольный граф (вершины разбиты на две группы, рёбра
                      только между группами - раздел 12). E = вершины одной
                      группы; A независимо ⇔ каждой вершине из A можно
                      сопоставить СВОЮ вершину другой группы, соединённую с ней

Правило

Матроид - пара (E, I): конечное множество и семейство независимых подмножеств, для которого выполнены три аксиомы: пустое множество независимо; подмножество независимого независимо (наследственность); и если |A| < |B| для независимых A, B, то в B есть элемент, который можно добавить к A, сохранив независимость (свойство обмена). Из третьей аксиомы следует, что все максимальные независимые множества (базы) имеют одинаковый размер - он называется рангом. Лесá в графе, линейно независимые наборы векторов и подмножества размера не больше k - матроиды; наборы, влезающие в рюкзак, - нет, и ломается именно свойство обмена. Проверять задачу на матроидность стоит именно через третью аксиому: первые две обычно очевидны, а вся суть в третьей.

Разбор: лесá в графе - матроид

Возьмём граф из четырёх рёбер: треугольник 0-1, 1-2, 0-2 плюс отросток 2-3.

E = { a: 0-1,  b: 1-2,  c: 0-2,  d: 2-3 }

независимые (ациклические) подмножества:
    ∅
    {a} {b} {c} {d}
    {a,b} {a,c} {a,d} {b,c} {b,d} {c,d}
    {a,b,d} {a,c,d} {b,c,d}
всего 14

зависимое: {a,b,c} - это треугольник, то есть цикл
и всё, что его содержит

Проверим аксиомы. Пустое множество цикла не содержит - (1) выполнено. Если из ациклического набора убрать ребро, цикл не появится - (2) выполнено. Третья аксиома: все 14 × 14 пар проверены машинно - нарушений ноль. Посмотрим на показательный случай руками:

A = {a, b}   (два ребра треугольника, независимо)
B = {a, c, d} (независимо, больше по размеру)

B \ A = {c, d}
    A ∪ {c} = {a, b, c} - ЦИКЛ, не подходит
    A ∪ {d} = {a, b, d} - ациклично, подходит       ✓

нашёлся хотя бы один - аксиома требует именно «найдётся», а не «любой»

Вот тонкость, которую легко упустить: аксиома обмена не обещает, что подойдёт ЛЮБОЙ элемент из B \ A. Она обещает, что подойдёт хотя бы один. Этого ровно достаточно, чтобы жадность никогда не загнала себя в тупик.

Базы здесь - все трёхэлементные ациклические наборы: {a,b,d}, {a,c,d}, {b,c,d}. Размер у всех один - 3, то есть ранг равен 3. Это общее следствие третьей аксиомы: если бы существовали базы размеров 3 и 4, к меньшей можно было бы что-то добавить - значит она не была максимальной.

Разбор: рюкзак не матроид, и видно, где именно

Возьмём три предмета весами 3, 3, 4 и рюкзак вместимости 6. Назовём независимыми те наборы, которые влезают.

независимые: ∅, {1}, {2}, {3}, {1,2}
    {1,3} = 3 + 4 = 7 > 6 - не влезает
    {2,3} = 7 - не влезает

аксиомы (1) и (2) выполнены: пустое влезает, часть влезающего влезает

ТРЕТЬЯ АКСИОМА:
A = {3} (вес 4), B = {1, 2} (вес 6), |A| = 1 < 2 = |B|
    A ∪ {1} = {3, 1} = 7 > 6     не влезает
    A ∪ {2} = {3, 2} = 7 > 6     не влезает
ни один элемент B не добавляется к A ⇒ свойство обмена НАРУШЕНО

Это единственное нарушение на таком маленьком примере - и его достаточно: матроидом структура не является. И посмотри, что оно означает по-человечески: жадность, взявшая предмет весом 4, оказалась в тупике - она набрала один предмет там, где можно было набрать два, и исправить это добавлением уже нельзя. Ровно это и происходит, когда жадный алгоритм для целого рюкзака выдаёт неоптимум.

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

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

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

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

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

Теперь сам

Пусть E - множество сотрудников, и независимыми считаются наборы, в которых не больше двух человек из каждого отдела. Матроид ли это?

(1) пустой набор: из каждого отдела ноль человек, то есть не больше двух   ✓

(2) наследственность: уберём человека из допустимого набора - количества
    по отделам только уменьшились                                          ✓

(3) обмен: пусть |A| < |B|, оба допустимы.
    Если бы в каждом отделе у A было не меньше людей, чем у B, то |A| >= |B| -
    противоречие. Значит есть отдел, где у B людей БОЛЬШЕ, чем у A.
    В этом отделе у A не больше одного человека (иначе у B было бы три),
    и в нём найдётся человек из B, которого в A НЕТ (у B их больше).
    Добавив именно его, получим не больше двух человек из этого отдела -
    допустимо.                                                              ✓