Чек-лист «можно ли здесь жадничать» и что делать, если нельзя

Коротко

Практический порядок: назвать цель, описать «допустимые наборы», проверить три аксиомы (вся суть в третьей). Для наследственной системы без обмена сортировку по весу можно опровергнуть малым контрпримером. Когда эта схема не даёт точного решения, проверь три альтернативы. Пересечение ДВУХ матроидов решается точно за полином (двудольное паросочетание - это оно), трёх - уже NP-трудно. Монотонная субмодулярная цель с f(∅)=0 при ограничении числа элементов даёт жадности гарантию 1−1/e. Для максимального покрытия улучшение на фиксированную константу невозможно за полином при P≠NP. Всё остальное - динамическое программирование, потоки или приближения с худшими оценками. Жадность при этом часто остаётся в коде как быстрая эвристика рядом с точным алгоритмом.

Если ты помнишь порядок проверки, знаешь про пересечение двух матроидов и оценку 1 − 1/e, листай до «Теперь сам».

Как думаешь, что делать при провале проверки

Пустой набор и наследственность есть, но обмен нарушен - матроида нет. Значит схема «сортировать по весу и добавлять допустимые элементы» не гарантирует оптимум для всех весов. Другие алгоритмы или специальные случаи задачи этим не исключены. Что дальше: сразу писать динамическое программирование?

Не сразу. Между «матроид» и «ничего не поделаешь» лежат промежуточные случаи, у каждого своя теория и свои гарантии. Вопрос урока - какие именно и как их узнавать.

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

Диагностика в медицине. Есть быстрый тест (три аксиомы), и если он положительный - лечение известно. Если отрицательный, врач не говорит «неизлечимо», а назначает уточняющие исследования: может быть, случай попадает в другую известную категорию с другим протоколом. Пересечение матроидов и субмодулярность - такие категории.

Механизм: порядок проверки и три ступени отступления

ЧЕК-ЛИСТ

1. НАЗВАТЬ ЦЕЛЬ. «Оптимальный» без цели - не формулировка.
   максимум суммы? минимум числа? минимум максимума?

2. ОПИСАТЬ ДОПУСТИМЫЕ НАБОРЫ. Что значит «набор подходит»?

3. ПРОВЕРИТЬ АКСИОМЫ:
   (1) пустой набор допустим? (почти всегда да, но проверить стоит:
       бывают задачи, где требуется выбрать хоть что-то)
   (2) наследственность - убрать элемент из допустимого: допустим?
   (3) обмен - |A| < |B|, найдётся ли x ∈ B \ A с допустимым A ∪ {x}?

4. ПРИ (1), (2) И АДДИТИВНОЙ ЦЕЛИ, ЕСЛИ ОБМЕН НАРУШЕН:
   перебрать маленькие веса против точного алгоритма;
   контрпример сортировке по весу гарантирован теоремой

5. ЕСЛИ АКСИОМЫ ВЫПОЛНЕНЫ И ЦЕЛЬ - СУММА ВЕСОВ:
   сортировать по весу с проверкой независимости; отрицательные элементы
   пропускать при максимуме среди всех независимых, но не при поиске базы
   Для другой цели матроидность сама по себе оптимальность не даёт.

Если пустота или наследственность не выполнены, теорема в такой записи семейства неприменима. Для поиска базы аксиомы проверяют на независимых частичных наборах, а не на одном семействе баз: требование завершить набор базой относится к ответу.

ТРИ АЛЬТЕРНАТИВЫ ТОЧНОЙ СОРТИРОВКЕ ПО ВЕСУ

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

ступень 2: МОНОТОННАЯ СУБМОДУЛЯРНАЯ ЦЕЛЬ, f(∅)=0, не больше k элементов
    субмодулярность: добавление элемента к БОЛЬШЕМУ набору даёт не больше
    пользы, чем к меньшему (убывающая отдача)
    монотонность: добавление элемента никогда не УМЕНЬШАЕТ значение цели
    (без монотонности оценка 1 − 1/e неверна - тогда работают другие схемы)
    при 1 <= k <= числу доступных элементов гарантия 1 − 1/e
    Улучшение для max coverage на фиксированное ε требует P=NP.

ступень 3: ОСТАЛЬНОЕ
    динамическое программирование (если хватает ресурсов),
    поток (если задача о назначении или двудольном паросочетании),
    приближение с худшей оценкой, эвристика с замером

Правило

Порядок работы: цель → описание допустимых наборов → три аксиомы. Для наследственной системы с аддитивной целью нарушение обмена гарантирует контрпример сортировке по весу. Если матроид и цель аддитивна - сортировка по весу с проверкой независимости; доказательство уже есть. Если нет, проверить две промежуточные категории. Пересечение ДВУХ матроидов решается точно за полином (без гарантии у обычной сортировки по весу), трёх - NP-трудно; двудольное паросочетание - пример пересечения двух раздельных матроидов. Монотонная субмодулярная цель с f(∅)=0 и ограничением на число элементов даёт жадности гарантию 1−1/e. Для максимального покрытия улучшить её на фиксированное ε>0 за полином нельзя при P≠NP. Всё остальное - динамика, потоки или приближения. Жадность при этом полезна и в неоптимальных случаях: как быстрая первая оценка и как источник начального решения для более дорогих методов.

Разбор: чек-лист на трёх задачах подряд

ЗАДАЧА 1: выбрать максимальный по стоимости набор рёбер без циклов
1. цель: максимум суммы стоимостей
2. допустимые наборы: ациклические (лесá)
3. (2) убрали ребро из леса - лес      ✓
   (3) |A| < |B|, оба лесá: найдётся ли ребро B, не замыкающее цикл в A?
       да: у A больше компонент связности, чем у B, значит какое-то ребро B
       соединяет две разные компоненты A                                  ✓
ВЕРДИКТ: матроид. Жадность по убыванию стоимости - оптимум (это Крускал)

ЗАДАЧА 2: выбрать максимальный по стоимости набор рёбер, где у каждой
          вершины не больше одного ребра (паросочетание)
1. цель: максимум суммы
2. допустимые: паросочетания
3. (2) убрали ребро - всё ещё паросочетание    ✓
   (3) путь 1-2-3-4, A = {(2,3)}, B = {(1,2), (3,4)}:
       ни одно ребро B к A не добавить                                     ✗
ВЕРДИКТ: не матроид. Контрпример по теореме существует: веса 2, 3, 2 дают
         жадно 3 против оптимума 4.
         Двудольный граф: поток. Общий: взвешенный алгоритм Эдмондса.

ЗАДАЧА 3: выбрать не больше k множеств, чтобы накрыть МАКСИМУМ элементов
1. цель: максимум числа накрытых элементов
2. допустимые наборы: любые из не более k множеств - это РАВНОМЕРНЫЙ матроид!
3. аксиомы выполнены - ограничение чисто по количеству
НО: цель не сумма весов элементов набора, а размер ОБЪЕДИНЕНИЯ -
    она НЕ АДДИТИВНА, и теорема Радо-Эдмондса к ней не относится
ВЕРДИКТ: это субмодулярная максимизация, ступень 2. Гарантия 1 − 1/e

Третья задача - самая поучительная: структура допустимых наборов идеальная (равномерный матроид), а жадность всё равно не точна, потому что ЦЕЛЬ другая. Теорема говорит про максимум СУММЫ ВЕСОВ элементов; как только целевая функция перестаёт быть суммой, нужна другая теория.

замер на четырёх множествах, k = 2 (универсум {1..7}):
    A = {2,3,4,5,6}   B = {1,2,4}   C = {3,5,6,7}   D = {2,3,5,6}

    жадность: A - единственное самое крупное (5 элементов), берёт его.
              дальше B добавляет {1}, C добавляет {7}, D не добавляет ничего
              → 6 элементов, и это не зависит от разрыва ничьих
    оптимум:  B ∪ C = {1,2,4} ∪ {3,5,6,7} = все семь               → 7

    отношение 6/7 = 0.857 - хуже оптимума, но лучше гарантии 0.632

Обрати внимание, почему здесь важна фраза «не зависит от разрыва ничьих». Жадность на первом шаге выбирает САМОЕ крупное множество, и если таких несколько, результат может зависеть от того, какое из них взято. Тогда результат нужно соотнести с конкретным правилом ничьих. Здесь первый выбор однозначен, а дальше любой вариант даёт шесть - значит жадность проигрывает по существу, а не из-за произвольного выбора.

Разбор: что такое субмодулярность и откуда 1 − 1/e

СУБМОДУЛЯРНОСТЬ (убывающая отдача)
    f(A ∪ {x}) − f(A) >= f(B ∪ {x}) − f(B), A ⊆ B, x ∉ B

по-человечески: чем больше у тебя уже есть, тем меньше пользы
от очередного элемента

примеры субмодулярных целей с не возрастающей отдачей:
    размер объединения множеств (покрытие)
    число охваченных пользователей рекламой
    сумма неотрицательных весов охваченных пользователей
сумма весов - ГРАНИЧНЫЙ случай: неравенство выполняется как РАВЕНСТВО
    (отдача не убывает, но и не растёт), то есть формально она тоже
    субмодулярна. Для такой - аддитивной - цели работает более сильный
    результат при матроидном ограничении: точный оптимум по теореме
    Радо-Эдмондса, а не только 0.632

Равенство допустимо: если множества B и C не пересекаются, прибавка C к пустому набору и к {B} одинакова. «Убывающая отдача» здесь означает «не возрастает», а не строгое падение при каждом добавлении.

Условие f(∅)=0 называют нормировкой: пустой набор имеет нулевую ценность. Вместе с монотонностью оно даёт неотрицательность f. Это нужно для относительной гарантии. Для монотонной функции f(S)=|S|−100 и k=1 даже оптимальное значение −99 меньше 0,632·(−99), поэтому такое сравнение не описывает качество решения.

ОТКУДА 1 − 1/e
    на каждом шаге жадность забирает не меньше 1/k от того, что ещё
    осталось до оптимума. После k шагов недобор не больше (1 − 1/k)^k
    от оптимума, а (1 − 1/k)^k → 1/e ≈ 0.368
    значит покрыто не меньше 1 − 1/e ≈ 0.632 от оптимума

и эта граница ТОЧНАЯ в пределе: есть семейства входов, на которых
отношение стремится к 1 − 1/e сверху. При конечном k гарантируется
не меньше 1 − (1 − 1/k)^k; эта граница сильнее 1 − 1/e.

Почему на шаге находится хотя бы 1/k недобора? Пусть O - оптимальные k элементов, A - уже выбранные. Монотонность даёт f(A∪O)≥f(O). Субмодулярность означает, что сумма отдельных прибавок элементов O к текущему A не меньше совместной прибавки. Значит эти не более k прибавок суммарно покрывают f(O)−f(A). Хотя бы одна не меньше этой разности, делённой на k; жадность выбирает наибольшую. Начальный недобор равен f(O), потому что f(∅)=0. Отсюда и повторное умножение недобора на 1−1/k.

Точность худшей границы самой жадности и трудность для всех полиномиальных алгоритмов - разные утверждения. Для максимального покрытия невозможность гарантии 1−1/e+ε при любом фиксированном ε>0 условна: предполагается P≠NP. Это теорема Фейге, а не безусловный запрет улучшить результат на конкретном входе.

Связь с прошлой главой: ln n для покрытия множеств и 1 − 1/e для максимального покрытия - это две стороны одного факта. В первой задаче спрашивают «сколько множеств нужно, чтобы накрыть всё», во второй - «сколько накроем, если дано k множеств». Жадность одна и та же, а форма гарантии зависит от того, что считать ответом.

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

Первое: проверить структуру и забыть проверить ЦЕЛЬ - как в задаче 3, где матроид есть, а теорема не применима. Второе: решив, что матроида нет, сразу браться за динамику: может быть, это пересечение двух матроидов и решается точно. Третье: переносить точность сортировки по весу на пересечение матроидов. Четвёртое: применять 1−1/e без проверки монотонности, субмодулярности, нормировки и ограничения на число элементов. Пятое: принимать гарантию худшего случая за предсказание качества на конкретных данных. Шестое: забывать про замер: даже в тех задачах, где жадность не оптимальна, её часто оставляют в коде - она даёт быстрый ответ и хорошее начальное решение для более дорогих методов.

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

Эти три ступени - готовая карта для разговора о любой задаче выбора. «Выбрать не больше трёх поставщиков в каждом регионе с максимальной суммарной надёжностью» - раздельный матроид, жадность точна. «Назначить задачи исполнителям» - пересечение двух матроидов, решается потоком точно. «Выбрать десять мест под камеры, чтобы покрыть максимум территории» - субмодулярная максимизация, жадность с гарантией 0.632 для фиксированных областей покрытия камер. Если добавляются зависимости, неаддитивные затраты или иной критерий качества, условия нужно проверить заново. Например, информативность произвольного набора признаков не обязана быть субмодулярной. При выборе метода называй конкретную цель, ограничения и доказанную гарантию.

Теперь сам

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

Ответ. Это пересечение ДВУХ матроидов, то есть ступень 1: есть точное полиномиальное решение; сортировка допустимых пар не гарантирует оптимум.

1. цель: максимум суммы ценностей выбранных пар               аддитивна ✓
2. допустимые наборы: наборы пар (сервер, стойка), где
   - каждый сервер встречается не больше одного раза
   - в каждой стойке не больше трёх серверов
3. это ПЕРЕСЕЧЕНИЕ двух раздельных матроидов:
   первый группирует пары по СЕРВЕРУ (квота 1),
   второй - по СТОЙКЕ (квота 3)
   каждый по отдельности - матроид; пересечение не обязано быть матроидом

Проверим, что пересечение действительно не матроид. Квота стоек в задаче - три, и чтобы увидеть нарушение, достаточно заполнить её: пусть в стойке r1 уже стоят два сервера, то есть место осталось одно. Но проще взять ту же конструкцию в чистом виде - с квотой 1 у каждой стойки:

серверы s1, s2; стойки r1, r2 с квотой 1 каждая
совместимость: s1 - только с r1;  s2 - с r1 и с r2

возможные пары: a = (s1, r1),  b = (s2, r1),  c = (s2, r2)
независимые наборы: ∅, {a}, {b}, {c}, {a, c}
    {a, b} нельзя - обе пары занимают r1
    {b, c} нельзя - обе пары занимают s2

проверяем обмен:  A = {b},  B = {a, c},  |A| = 1 < 2 = |B|
    A ∪ {a} = {b, a} - нельзя (r1 занята)
    A ∪ {c} = {b, c} - нельзя (s2 занят)
ни один элемент B к A не добавляется ⇒ обмен нарушен               ✗

Для квоты 3 добавь два других сервера, совместимых только с r1, и включи обе их пары в A и B. Тогда A занимает три места в r1, а B - три в r1 и одно в r2. Добавления a и c к A по-прежнему нарушают соответственно квоту стойки и квоту s2.

Решение через поток: исток → сервер (ёмкость 1), сервер → совместимая стойка (ёмкость 1, цена минус ценность), стойка → сток (ёмкость 3). Добавь также сервер → сток с ёмкостью 1 и ценой 0 для отказа от этого сервера; пропусти ровно n единиц. Тогда назначение и пропуск представлены в одной модели, в том числе при отрицательной ценности. Исходная сеть ациклична, отрицательных циклов нет; начальные потенциалы для отрицательных цен получаем, как в разделе 12.

Для обычного двудольного паросочетания каждую стойку нужно заменить тремя копиями и разрешить оставлять серверы непокрытыми. Без копий обычное паросочетание давало бы квоту 1. Жадная сортировка допустимых пар с пропуском отрицательных весов даёт приближение 1/2 для пересечения двух матроидов, но не обещает точный ответ.

Главное

Порядок проверки: назвать ЦЕЛЬ, описать допустимые наборы, проверить три аксиомы. Для наследственной системы с суммой весов нарушение обмена гарантирует контрпример сортировке по весу. Проверять надо и цель: структура может быть идеальным матроидом, а теорема не применима, если целевая функция не сумма весов (максимальное покрытие k множествами - равномерный матроид с НЕаддитивной целью). Три ступени отступления: пересечение ДВУХ матроидов - точно за полином, без гарантии обычной сортировки (двудольное паросочетание, назначения); монотонная субмодулярная цель с f(∅)=0 и ограничением на количество - жадность с гарантией 1−1/e. Для максимального покрытия улучшение на фиксированное ε невозможно за полином при P≠NP. Субмодулярность - это не возрастающая отдача: f(A∪{x})−f(A)≥f(B∪{x})−f(B) при A⊆B, x∉B. Оценки ln n и 1 − 1/e - две формы одного факта про одну и ту же жадность.