Конспект: каталог NP-полных задач

Понятия

Гамильтонов цикл - цикл через каждую вершину ровно один раз. Эйлеров цикл - по каждому ребру ровно один раз. Задача коммивояжёра - кратчайший обход всех городов с возвратом.

Сумма подмножества - есть ли подмножество чисел с суммой S. Разбиение - делятся ли числа на две части с равными суммами. Упаковка в контейнеры - хватит ли k контейнеров данной вместимости.

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

Оракул - программа, отвечающая на вопрос разрешения; считаются только обращения к ней.

Что унести

СЕМЬ СЕМЕЙСТВ                             РАБОЧАЯ ОДЕЖДА
формулы: SAT, 3-SAT                       совместимость настроек,
                                          проверка схем
выбор вершин: независимое, покрытие       камеры на перекрёстках
покрытия и упаковки                       команда с навыками,
                                          файлы по дискам
порядок: гамильтонов цикл, коммивояжёр    маршрут курьера,
                                          порядок переналадок
числа: сумма, рюкзак, разбиение           бюджет, раздел поровну
разбиение на группы: раскраска            расписание экзаменов, частоты
расписания                                работы на станках

признаки: ищется проверяемый объект;  вариантов 2ⁿ или n!;
          части решения связаны запретами

ПЕРЕБОР С ВОЗВРАТОМ
10 экзаменов, 3 дня:   расписание найдено за 11 вызовов
четвёрка попарно конфликтующих в начале порядка - отказ за 22 вызова;
                               в конце - за 406
сначала решать самое ограниченное

файлы 7 6 5 5 4 4 3 3 2 1, диски по 10:   4 диска, без остатка
файлы 6 6 6 6 6 5 5, та же сумма 40:      нужно 6 дисков;
          сумма / вместимость - только нижняя оценка

ПОРЯДОК
гамильтонов цикл ≤ коммивояжёр:  расстояние 1 по рёбрам, 2 иначе, порог n
призма на 10 вершинах: цикл за 10 вызовов;
граф Петерсена: цикла нет, 274 вызова
семиугольник с хордами: обход 7;   двудольный 3 + 4: обход 8;
                        оба раза 1957 вызовов

полный перебор  (n − 1)!       до 12-13 городов
таблица по подмножествам  2ⁿ · n²     до 20-25
перебор с оценками - тысячи городов на практике, без гарантии

ЧИСЛА
таблица достижимых сумм:  n · S действий,
    S = 2 в степени длины записи  →  экспонента от входа
числа × 4 (по два бита):   472 → 1864 → 7432 действия;
                           перебор - 256 подмножеств всегда

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

разбиение = сумма с целью «половина»
сумма S из чисел с общей суммой T =
    разбиение чисел с добавленными  2T − S  и  T + S

ЛЁГКОЕ / ТРУДНОЕ                             НА ЧЁМ ДЕРЖИТСЯ ЛЁГКОЕ
кратчайший путь / самый длинный простой      подструктура
эйлеров цикл / гамильтонов цикл              чётные степени, связность
2 литерала в скобке / 3 литерала             скобка - следование
2 цвета / 3 цвета                            цвет соседа вынужден
паросочетание / сочетание троек              увеличивающий путь
наименьший разрез / наибольший разрез        равенство с потоком
остов / дерево Штейнера                      жадный выбор
покрытие в двудольном графе /                равенство с паросочетанием
  в произвольном

решётка k × k, путь из угла в угол:   обход - 4, 9, 16 клеток;
                                      простых путей 2, 12, 184, 8512, …

ТРИ ФОРМЫ: есть ли  →  найди  →  найди лучшее
оптимум:   двоичный поиск по порогу, log₂ M обращений к оракулу
поиск:     закрепить часть, спросить, осталась ли задача решаемой;
           n + 1 обращение
           6 переменных - 7 обращений;
           «нет» означает противоположное значение

ПЯТЬ ШАГОВ:  записать точно  →  найти в каталоге
             →  проверить входы (размер, числа, структура)
             →  при нужде доказать трудность  →  выбрать, чем платить

Ловушки джокера

Не узнал задачу и искал быстрый точный алгоритм. Час с каталогом сберёг бы недели.

Счёл трудным всё, где есть граф. Нужно совпадение устройства, а не области.

Принял оценку по объёму за ответ. Семь файлов с суммой 40 потребовали шести дисков, а не четырёх.

Перепутал цикл по рёбрам с циклом по вершинам. Первый проверяется подсчётом степеней.

Понадеялся на таблицу при больших числах. Копейки вместо рублей - в сто раз шире.

Искал таблицу для сильно NP-полной задачи. Трудность там не в числах.

Пообещал трудную задачу по аналогии с лёгкой. Максимум вместо минимума, три вместо двух.

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

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

Проверь себя

По каким признакам задачу относят к семейству из каталога? Как гамильтонов цикл превращается в задачу с расстояниями? Почему таблица на n · S клеток не противоречит NP-полноте и для каких задач она вообще возможна? Назови четыре пары «лёгкое - трудное» и скажи, на чём держится лёгкая. Как из ответов «да» и «нет» получить оптимум и само решение?

Изоморфизм графов сохраняет рёбра и не-рёбра при биекции; совпавшие степени и 1-WL не заменяют сертификат. Изоморфизм подграфа - другая постановка.

Общая надстрока содержит все фрагменты непрерывно. Удали вложенные строки; жадное перекрытие даёт допустимое, но не обязательно кратчайшее решение.

Упаковка множеств запрещает пересечения. Неулучшаемая упаковка наборов размера ≤ d даёт d-приближение; максимальная по включению не обязана быть наибольшей.

Понятия

Что унести

Ловушки джокера

Проверь себя

Комментарии

Оставить комментарий