Упаковка множеств: выбрать совместимые заявки

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

Как думаешь, кому одобрить заявки

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

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

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

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

Механизм: три задачи о наборах и одно сведение

Есть множество элементов и семейство его подмножеств - наборов. Три вопроса отличаются тем, сколько раз разрешено занять элемент.

задача             каждый элемент            цель
покрытие           хотя бы в одном наборе    наборов поменьше
упаковка           не больше чем в одном     наборов побольше
точное покрытие    ровно в одном             найти хоть одно

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

Сведение. По графу строим наборы: элементы - рёбра графа, набор вершины v - рёбра, выходящие из v. Два набора пересекаются ровно тогда, когда их вершины соединены ребром: общий элемент и есть это ребро. Значит, k непересекающихся наборов - это k вершин без общих рёбер, то есть независимое множество размера k. Перевод занимает O(|V| + |E|): нужно выписать и все наборы вершин, в том числе пустые наборы для изолированных вершин. Наборы считаются отдельными заявками по их номерам, даже если их содержимое совпадает.

Работает и обратное направление. По наборам строим граф конфликтов: вершина - набор, ребро - если наборы пересекаются. Упаковка - независимое множество в нём. Задачи совпадают с точностью до перевода, и всё, что известно о трудности независимого множества, переносится на упаковку.

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

Гарантия при наборах не длиннее d, где d ≥ 1. Пустые наборы всегда можно взять: они ни с чем не конфликтуют. Отделим их, а дальше рассмотрим только непустые. Возьми любой набор O из наилучшей упаковки. Он пересекается хотя бы с одним взятым жадно - иначе жадный выбор взял бы и его. Пометь O элементом, через который пересёкся. У взятого набора не больше d элементов, а наборы наилучшей упаковки не делят элементов, поэтому на один жадный набор приходится не больше d помеченных. Отсюда: лучшая упаковка не больше d, умноженного на жадную. Это рассуждение не зависит от порядка обхода. Если пустых заявок e, а на непустых OPT ≤ d·GREEDY, после их возвращения e + OPT ≤ d·(e + GREEDY) при d ≥ 1. Так гарантия охватывает и пустые наборы.

Правило

Упаковка множеств - выбрать наибольшее число попарно непересекающихся наборов; она NP-трудна и равносильна независимому множеству в графе конфликтов. Жадный выбор даёт неулучшаемую упаковку, и при наборах размера не больше d, где d ≥ 1, она меньше наилучшей не более чем в d раз. Покрытие требует «хотя бы раз», упаковка - «не больше раза», точное покрытие - «ровно раз».

Разбор: граф, заявки и ловушка на трёх наборах

Функция tochno - перебор с возвратом: брать набор, если он не мешает, или пропускать, бросая ветку, когда даже взяв все оставшиеся, рекорд не побить. Функция zhadno идёт по наборам в заданном порядке.

import random


def tochno(nabory):               # перебор с возвратом и отсечением
    luchshee = [[]]

    def idti(i, vzyato, zanyato):
        if len(vzyato) + len(nabory) - i <= len(luchshee[0]):
            return
        if i == len(nabory):
            luchshee[0] = vzyato
            return
        if not nabory[i] & zanyato:
            idti(i + 1, vzyato + [i], zanyato | nabory[i])
        idti(i + 1, vzyato, zanyato)

    idti(0, [], set())
    return luchshee[0]


def zhadno(nabory, klyuch):       # брать по порядку, если не мешает
    vzyato, zanyato = [], set()
    for i in sorted(range(len(nabory)), key=klyuch):
        if not nabory[i] & zanyato:
            vzyato.append(i)
            zanyato |= nabory[i]
    return vzyato


graf = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2), (4, 5)]
po_vershinam = [{r for r in graf if v in r} for v in range(6)]
print("граф, наборы рёбер:", len(tochno(po_vershinam)),
      "вершин без общих рёбер:", tochno(po_vershinam))

rng = random.Random(21)
zayavki = [set(rng.sample(range(14), rng.randint(2, 4)))
           for _ in range(20)]
opt = tochno(zayavki)
mal = zhadno(zayavki, lambda i: len(zayavki[i]))
bol = zhadno(zayavki, lambda i: -len(zayavki[i]))
print("заявок:", len(zayavki), " точно:", len(opt),
      " жадно с малых:", len(mal), " жадно с больших:", len(bol))
plohoj = [{"a", "b"}, {"a", "c", "d"}, {"b", "e", "f"}]
print("ловушка:", len(tochno(plohoj)),
      len(zhadno(plohoj, lambda i: len(plohoj[i]))))

граф, наборы рёбер: 3 вершин без общих рёбер: [0, 3, 5]
заявок: 20  точно: 5  жадно с малых: 4  жадно с больших: 2
ловушка: 2 1

Первая строка - сведение в действии. Граф на шести вершинах: пятиугольник 0-1-2-3-4, хорда 0-2 и хвост 4-5. Наборы рёбер вершин 0, 3 и 5 не пересекаются, и это независимое множество: ни одного ребра между этими вершинами нет. Больше трёх не выйдет - упаковку перебор проверил целиком.

Вторая строка - лаборатория. Точный ответ пять заявок. Жадный выбор с маленьких нашёл четыре, с больших - две: большая заявка занимает четыре прибора и выбивает сразу несколько соседок. Граница из механизма выполняется: наборы не длиннее четырёх, и 5 ≤ 4 · 2. Но разница между стратегиями - в два с половиной раза, а гарантия у обеих одна и та же.

Разбор: когда «с малых» ошибается

Третья строка. Наборы {a, b}, {a, c, d} и {b, e, f}. Жадный выбор с малых первым берёт {a, b} - он самый короткий. Этот набор задевает оба других: первый через a, второй через b. Итог - один набор. А два длинных набора между собой не пересекаются, и лучшая упаковка - два.

Наивное правило «бери короткие, они меньше мешают» здесь проигрывает вдвое. Мешает не размер набора, а число наборов, которые он задевает: {a, b} короче, но конфликтов у него два, а у каждого длинного - один. Порядок «сначала наборы с наименьшим числом конфликтов» тоже можно обмануть, просто входом побольше: это эвристика, а гарантию даёт только рассуждение из механизма.

И сама граница не завышена. Возьми набор {x₁, …, x_d} и d одноэлементных наборов {xᵢ}. Максимальный размер набора равен d. Если жадный порядок начнёт с первого, он заблокирует все d остальных: один против d. Это пример для произвольного порядка, а не специально для порядка «с малых». В предыдущей ловушке максимальный размер равен трём, поэтому её потеря вдвое согласуется с границей, но не достигает её.

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

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

Упаковку множеств путают с упаковкой в контейнеры. Там предметы с размерами раскладывают по контейнерам, и надо уложить все. Здесь наборы фиксированы, и надо выбрать часть.

Жадный ответ выдают за лучший. На двадцати заявках два жадных порядка дали четыре и две заявки. Точный оптимум равен пяти: лучший из этих жадных порядков тоже не нашёл его.

Неулучшаемую упаковку считают наибольшей. К ловушке с одним набором ничего не добавить, но вдвое больше наборов существует.

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

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

На практике задачу записывают как целочисленную программу: переменная xₛ равна 0 или 1 - взят ли набор, для каждого элемента сумма xₛ по содержащим его наборам не больше единицы, сумма всех xₛ побольше. Практическую скорость решателя проверяют на своём классе экземпляров: она зависит от структуры конфликтов и силы отсечений, а не только от числа наборов. Точному решению трудного экземпляра может не хватить заданного времени. Жадный ответ при этом нужен всё равно - как стартовый рекорд, от которого перебор отсекает ветки.

Теперь сам

Наборы: {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 1} и {1, 3}.

1. Сколько наборов в наибольшей упаковке?
2. Жадный выбор идёт по наборам в записанном порядке. Что он выдаст?
3. Наборы размера 2 - это рёбра. Как называется упаковка таких наборов в языке графов?