Покрытие множеств: жадность без оптимума, но с гарантией

Коротко

Покрытие множеств - выбрать как можно меньше множеств, чтобы накрыть все элементы. Задача NP-трудна, точной жадности нет: естественный критерий «брать множество, накрывающее больше всего НЕНАКРЫТОГО» даёт не оптимум, а ответ не хуже оптимума примерно в ln n раз (точнее - в H(n) = 1 + 1/2 + ... + 1/n раз), и лучшего отношения не даёт ни один полиномиальный алгоритм - при условии, что P ≠ NP. Так появляется третий режим работы с жадностью: не «доказать оптимальность» и не «отвергнуть», а доказать гарантию. Вершинное покрытие показывает это с неожиданной стороны: «жадность по степени» КОНСТАНТНОЙ гарантии не имеет (только логарифмическую), а грубый приём «берём ОБА конца непокрытого ребра» даёт гарантию 2 - при том что на конкретных данных может отвечать хуже.

Если ты знаешь, что такое c-приближённый алгоритм, помнишь оценки ln n и 2 и понимаешь, почему алгоритм с гарантией может проиграть алгоритму без неё, листай до «Теперь сам».

Как думаешь, когда жадность всё-таки берут

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

Задача NP-трудна - точного быстрого алгоритма нет ни у кого. Отвергнуть жадность? Тогда чем решать? Вопрос: что можно УТВЕРЖДАТЬ про ответ жадного алгоритма, если оптимум недостижим?

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

Оценка ремонта. Точную стоимость заранее не знает никто, и честный подрядчик говорит не «будет столько», а «не дороже чем в полтора раза против сметы». Это не отказ от ответа, а ответ другого типа - с ГАРАНТИЕЙ сверху. Приближённые алгоритмы устроены ровно так: ответ не точный, но отклонение ограничено доказанной величиной.

Механизм: жадность с гарантией

ПОКРЫТИЕ МНОЖЕСТВ
дано: универсум U из n элементов и семейство множеств S₁...S_m
найти: наименьшее число множеств, объединение которых равно U

ЖАДНЫЙ КРИТЕРИЙ: брать множество, накрывающее больше всего ещё НЕНАКРЫТЫХ элементов
цена: Θ(сумма размеров множеств) при аккуратной реализации
гарантия: ответ <= H(n) · оптимум,  где H(n) = 1 + 1/2 + ... + 1/n ≈ ln n

ЧТО ЗНАЧИТ c-ПРИБЛИЖЁННЫЙ АЛГОРИТМ

    для ЛЮБОГО входа:  ответ_алгоритма <= c · оптимум
    (для задач на минимум; для максимума - ответ >= оптимум / c)

c - граница ХУДШЕГО случая, а не типичная ошибка:
алгоритм с гарантией 2 на реальных данных обычно ошибается на проценты

ВЕРШИННОЕ ПОКРЫТИЕ: накрыть все рёбра минимальным числом вершин

приём 1: брать вершину наибольшей СТЕПЕНИ
    КОНСТАНТНОЙ гарантии нет: это частный случай покрытия множеств,
    то есть порядка ln n - хуже двойки
приём 2: пока есть непокрытые рёбра, брать любое из них
    и класть в ответ ОБА его конца
    гарантия 2: взятые рёбра не имеют общих вершин, значит в любом покрытии
    есть хотя бы по одной вершине из каждого - оптимум не меньше числа рёбер,
    а мы взяли ровно вдвое больше

Правило

Если задача NP-трудна, у жадности третий исход: не оптимум и не отказ, а ДОКАЗАННАЯ ГАРАНТИЯ. Алгоритм называют c-приближённым, если для любого входа его ответ не хуже оптимума в c раз; c - граница худшего случая. Жадность для покрытия множеств (брать множество с наибольшим числом ненакрытых элементов) даёт H(n) ≈ ln n, и при P ≠ NP лучшего отношения не добьётся ни один полиномиальный алгоритм - то есть жадность здесь не «пока лучшее, что придумали», а предел возможного. Для вершинного покрытия гарантию 2 даёт не жадность по степени (у неё гарантия лишь логарифмическая - это частный случай покрытия множеств), а приём «взять оба конца произвольного ребра». Важно: алгоритм с гарантией может на конкретных данных ответить ХУЖЕ алгоритма без гарантии - гарантия говорит про худший случай, а не про этот вход.

Разбор: жадность промахивается на трёх множествах

универсум: {1, 2, 3, 4, 5, 6}
множества:  A = {1, 2, 3, 4}
            B = {1, 2, 5}
            C = {3, 4, 6}

ЖАДНОСТЬ
шаг 1: A накрывает 4 элемента, B - 3, C - 3  → берём A
       ненакрыто: {5, 6}
шаг 2: B накрывает из них {5} - один; C накрывает {6} - один → берём B
       ненакрыто: {6}
шаг 3: берём C
ответ: 3 множества

ОПТИМУМ
B ∪ C = {1,2,5} ∪ {3,4,6} = {1,2,3,4,5,6} = U
ответ: 2 множества

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

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

Разбор: алгоритм с гарантией 2 проиграл алгоритму с худшей гарантией

Теперь тот поучительный случай, ради которого стоит мерить, а не рассуждать. Граф: центр 0 соединён с 1, 2, 3, и ещё есть рёбра 1-4, 2-5, 3-6.

рёбра: 0-1, 0-2, 0-3, 1-4, 2-5, 3-6      (7 вершин, 6 рёбер)

ОПТИМУМ (перебором):            {1, 2, 3}             → 3 вершины
ЖАДНОСТЬ ПО СТЕПЕНИ:            {0, 1, 2, 3}          → 4 вершины
«ОБА КОНЦА РЕБРА»:              {0, 1, 2, 5, 3, 6}    → 6 вершин

Смотри, что получилось. Алгоритм с доказанной гарантией 2 дал 6 - ровно вдвое хуже оптимума, то есть уткнулся в свою границу. Алгоритм с гарантией ХУЖЕ - логарифмической - дал 4, то есть точнее. И это не парадокс, а ровно то, что означает слово «гарантия»: она ограничивает худший случай для ВСЕХ входов, а на отдельном входе алгоритм с худшей гарантией может оказаться точнее.

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

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

Первое: читать «гарантия 2» как «ошибается вдвое»: это граница сверху для худшего случая, а типичная ошибка обычно проценты. Второе: выбирать алгоритм по одной лишь гарантии, не замеряя на своих данных - как в разборе выше, где алгоритм с гарантией 2 проиграл алгоритму с логарифмической. Третье: считать, что жадность для покрытия множеств «пока не улучшили»: её ln n неулучшаем при P ≠ NP, то есть искать принципиально лучший полиномиальный алгоритм бессмысленно. Четвёртое: доказывать гарантию на примерах: «на сотне тестов не хуже чем на 10%» - это не гарантия, а наблюдение; гарантия - неравенство, доказанное для любого входа. Пятое: применять приём «оба конца ребра» к ВЗВЕШЕННОМУ вершинному покрытию: там он гарантии не даёт, нужен другой алгоритм - через линейное программированиеРазбирается в разделе 22, глава «ЛП-округление и прямо-двойственный метод»: Округление по порогу: взвешенное вершинное покрытие. Шестое: путать вершинное покрытие с покрытием множеств: формулировки похожи, гарантии разные (2 против ln n), и вершинное покрытие - частный случай покрытия множеств, но с лучшей оценкой.

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

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

Теперь сам

Универсум {1, 2, 3, 4, 5}, множества S₁ = {1, 2, 3}, S₂ = {1, 4}, S₃ = {2, 5}, S₄ = {3, 4, 5}. Что даст жадность и каков оптимум?

Ответ.

ЖАДНОСТЬ
шаг 1: размеры 3, 2, 2, 3. Самое крупное - S₁ (или S₄; возьмём S₁)
       накрыто {1,2,3}, ненакрыто {4,5}
шаг 2: S₂ даёт {4} - один; S₃ даёт {5} - один; S₄ даёт {4,5} - ДВА → берём S₄
       накрыто всё
ответ: 2 множества (S₁ и S₄)

ОПТИМУМ: двух множеств достаточно (S₁ и S₄) - значит 2, меньше одного множества
         не бывает (ни одно не покрывает все пять элементов)

Здесь жадность попала в оптимум, и это нормальный, самый частый исход: плохие случаи надо конструировать специально. На этих данных, кстати, и «неправильный» критерий «самое большое множество по ОБЩЕМУ размеру» дал бы те же два множества (S₁ и S₄ - самые крупные, вместе они покрывают всё), так что различие критериев этот пример не показывает.

А вот пример, где они расходятся:

универсум {1..7}
S₁ = {1,3,6}   S₂ = {1,2,4,5,7}   S₃ = {1,3,4,7}   S₄ = {1,2,5,7}

по ОБЩЕМУ размеру: S₂ (5 элементов), затем S₃ (4), затем S₁ - три множества
по НЕНАКРЫТЫМ:     S₂ (5 новых), затем S₁ даёт {3,6} - два новых, остальные
                   по одному → два множества, и это оптимум

Разница в том, что «общий размер» не замечает перекрытий: S₃ большое, но три его элемента уже накрыты. Правильный критерий считает именно ПРИБАВКУ.

Главное

Если задача NP-трудна, у жадности третий исход - доказанная ГАРАНТИЯ. Алгоритм c-приближён, если для любого входа его ответ не хуже оптимума в c раз; c - граница худшего случая, не типичная ошибка. Покрытие множеств: жадность «больше всего НЕНАКРЫТЫХ элементов» даёт H(n) ≈ ln n, оценка достигается, и её главный член ln n неулучшаем при P ≠ NP. Контрпример к оптимальности крошечный: A={1,2,3,4}, B={1,2,5}, C={3,4,6} - жадность берёт 3 множества, оптимум 2. Вершинное покрытие: гарантию 2 даёт приём «оба конца НЕПОКРЫТОГО ребра» (взятые рёбра попарно независимы, значит оптимум не меньше их числа), а у жадности по степени гарантия лишь логарифмическая - вершинное покрытие есть частный случай покрытия множеств. Замер показывает, что гарантия не равна качеству: на звезде с отростками алгоритм с гарантией 2 дал 6, жадность по степени 4, оптимум 3. Выбор между ними - по замеру на своих данных, а гарантия нужна там, где вход может быть любым.