Карта NP-полных задач: семейства и рабочая одежда

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

Как думаешь, что общего у этих задач

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

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

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

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

У задач тоже есть устройство: что выбирается, что запрещено, что считается. Каталог NP-полных задач - такой определитель, и пользуются им так же: сначала отнести к семейству, потом искать конкретную задачу.

Механизм: семь семейств

Первый список из двадцати одной задачи составил Ричард Карп в 1972 году, через год после теоремы Кука; справочник Гэри и Джонсона 1979 года содержал уже больше трёхсот. Их удобно делить по тому, что в задаче выбирают.

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

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

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

ищется объект, а не число             набор, порядок, разбиение
объект короткий и легко проверяется   значит, вопрос с порогом лежит в NP
вариантов экспоненциально много       подмножеств 2ⁿ, порядков n!
части решения зависят друг от друга   выбор в одном месте ограничивает
                                      выбор в другом
нет очевидной жадной стратегии        локально лучший шаг может закрыть
                                      путь к решению

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

Перебор с возвратом - общий способ решать их точно. Решение строится по частям; как только частичное решение нарушило запрет, ветка бросается, и перебор возвращается к последнему выбору. Об этом был раздел о переборе; здесь важно, как он ведёт себя на трудных задачах.

Правило

NP-полные задачи делятся на несколько семейств: формулы, выбор вершин, покрытия и упаковки, порядок обхода, числа, разбиение на группы, расписания. Задачу узнают по устройству: ищется проверяемый объект среди экспоненциального числа вариантов, и части решения связаны запретами. Узнав семейство, ищут в каталоге конкретную задачу и готовые приёмы для неё.

Разбор: расписание экзаменов - это раскраска

Экзамены - вершины. Ребро соединяет два экзамена, которые сдаёт хотя бы один общий студент. Дни - цвета. Расписание на три дня без накладок - раскраска графа в три цвета, при которой концы каждого ребра окрашены по-разному. Функция raskrasit красит вершины по порядку, пробуя цвета 0, 1, 2 и возвращаясь, если ни один не подошёл; счётчик считает её вызовы. Цвет сверяется только с соседями с меньшим номером (u < v): у остальных в списке лежит ноль или цвет из брошенной ветки.

def raskrasit(sosedi, cveta, v, schyot):
    schyot[0] = schyot[0] + 1
    if v == len(sosedi):
        return True
    for c in range(3):
        mozhno = True
        for u in sosedi[v]:
            if u < v and cveta[u] == c:
                mozhno = False
        if mozhno:
            cveta[v] = c
            if raskrasit(sosedi, cveta, v + 1, schyot):
                return True
    return False

def zapusk(n, ryobra):
    sosedi = []
    for v in range(n):
        sosedi.append([])
    for r in ryobra:
        sosedi[r[0]].append(r[1])
        sosedi[r[1]].append(r[0])
    cveta = [0] * n
    schyot = [0]
    if raskrasit(sosedi, cveta, 0, schyot):
        return [cveta, schyot[0]]
    return ["нельзя", schyot[0]]

ekzameny = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [3, 4],
            [3, 5], [4, 6], [5, 6], [5, 7], [6, 8]]
ekzameny = ekzameny + [[7, 8], [7, 9], [8, 9]]
print(zapusk(10, ekzameny))
print(zapusk(10, ekzameny + [[2, 3], [1, 4]]))
print(zapusk(10, ekzameny + [[0, 9], [2, 9], [1, 9]]))

[[0, 1, 2, 0, 1, 1, 0, 0, 1, 2], 11]
['нельзя', 22]
['нельзя', 406]

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

Во второй строке добавлены две пары, и экзамены 1, 2, 3, 4 теперь все попарно конфликтуют. Четырём таким экзаменам нужно четыре дня; перебор выясняет это за 22 вызова, потому что конфликт сидит в самом начале порядка.

В третьей строке такая же четвёрка - экзамены 0, 1, 2 и 9. Причина отказа та же, но перебору нужно 406 вызовов: он красит вершины с нулевой по восьмую всеми допустимыми способами и каждый раз спотыкается только на последней. Перебор не знает, почему ветка провалилась, и повторяет одну и ту же ошибку в сотнях вариантов.

Вывод для практики: цена перебора зависит от порядка, в котором принимаются решения. Сначала стоит выбирать то, что сильнее всего ограничено, - здесь вершины с наибольшим числом конфликтов. Настоящие решатели вдобавок запоминают причину отказа, чтобы не наступать на неё снова.

Разбор: файлы по дискам - это упаковка в контейнеры

Есть файлы с размерами и диски одинаковой вместимости. Хватит ли k дисков? Функция razlozhit кладёт файлы по одному на любой диск, где есть место, и возвращается при неудаче. В программе k - номер диска в цикле, а число дисков называется diskov. Диски с одинаковым остатком она не различает: класть файл на второй пустой диск бессмысленно, если уже пробовали первый.

def razlozhit(razmery, ostatki, i, schyot):
    schyot[0] = schyot[0] + 1
    if i == len(razmery):
        return True
    probovali = []
    for k in range(len(ostatki)):
        if ostatki[k] >= razmery[i] and ostatki[k] not in probovali:
            probovali.append(ostatki[k])
            ostatki[k] = ostatki[k] - razmery[i]
            if razlozhit(razmery, ostatki, i + 1, schyot):
                return True
            ostatki[k] = ostatki[k] + razmery[i]
    return False

def hvatit(razmery, vmestimost, diskov):
    schyot = [0]
    otvet = razlozhit(razmery, [vmestimost] * diskov, 0, schyot)
    return [otvet, schyot[0]]

fajly = [7, 6, 5, 5, 4, 4, 3, 3, 2, 1]
print(sum(fajly), hvatit(fajly, 10, 4), hvatit(fajly, 10, 5))
drugie = [6, 6, 6, 6, 6, 5, 5]
print(sum(drugie), hvatit(drugie, 10, 4), hvatit(drugie, 10, 5),
      hvatit(drugie, 10, 6))

40 [True, 11] [True, 11]
40 [False, 5] [False, 6] [True, 8]

Оба набора занимают по 40 единиц, диски - по 10. Первый набор укладывается на четыре диска без единой свободной единицы, и нашлось это за 11 вызовов.

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

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

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

Задачу не узнали и ищут быстрый точный алгоритм. Недели уходят на то, что не получилось у нескольких поколений исследователей. Проверка по каталогу заняла бы час.

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

Оценку по объёму приняли за ответ. Сумма размеров, число рёбер, число конфликтов дают границы. Набор из семи файлов выше требует шести дисков при оценке в четыре.

Перебор запускают в случайном порядке. Одна и та же причина отказа стоила 22 вызова или 406 в зависимости от того, где оказалась в порядке обхода.

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

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

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

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

Теперь сам

1. Нужно назначить частоты десяти передатчикам так, чтобы соседние не совпадали, а частот было три. Какая это задача?
2. Нужно выбрать наименьший набор тестов, в сумме покрывающий все ветки программы. Какая это задача?
3. Сумма размеров файлов 95, вместимость диска 10. Какое наименьшее число дисков может понадобиться и может ли понадобиться больше?
4. Почему задача о кратчайшем пути не попадает на карту, хотя путей экспоненциально много?
5. В графе конфликтов есть пять экзаменов, попарно конфликтующих. Что можно сказать о расписании на четыре дня?