Разрыв: почему некоторые задачи нельзя приблизить

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

Как думаешь, как доказать, что лучше нельзя

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

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

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

Весы, которые врут не больше чем на 10%. Ими нельзя отличить 100 граммов от 105. Но если поставить задачу так, что на весах лежит либо 100 граммов, либо килограмм, - неточные весы ответят безошибочно: 90-110 или 900-1100, перепутать нельзя.

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

Механизм: сведение с разрывом

Схема довода. NP-полная задача A (ответ да или нет) сводится к задаче оптимизации B так, что:

ответ A - «да»   ⇒   OPT(B) <= a
ответ A - «нет»  ⇒   OPT(B) >  α · a

Алгоритм с множителем α на «да» выдаёт не больше α · a, на «нет» - больше α · a (он не может быть лучше оптимума). Сравнение с α · a решает A. Для задачи на максимум неравенства разворачиваются: «да» - оптимум не меньше a, «нет» - меньше a / α. Значит, если P ≠ NP, такого алгоритма нет.

Коммивояжёр. A - гамильтонов цикл в графе на n вершинах. Строим расстояния: 1 между соседями, α · n + 1 между несоседями. Гамильтонов цикл есть - обход длины n. Нет - любой обход использует хотя бы одну пару несоседей, и его длина не меньше (n − 1) + α · n + 1 > α · n. Работает для любого α, в том числе растущего с n, пока штраф записывается многочленом битов. Неравенство треугольника здесь нарушено: α · n + 1 больше 1 + 1. Именно поэтому метрический коммивояжёр приближается, а этот - нет.

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

APX. Задачи, у которых есть приближение с каким-то постоянным множителем, образуют класс APX. Внутри него есть APX-трудные: для них нет PTAS, если P ≠ NP, - существует порог, ниже которого множитель не опустить. Метрический коммивояжёр, вершинное покрытие, MAX-3SAT - APX-трудны. Коммивояжёр без неравенства треугольника и покрытие множествами, если P ≠ NP, - вообще вне APX.

Правило

Невозможность приближения доказывают сведением с разрывом: из NP-полного вопроса строят задачу, где оптимум при ответе «да» не больше a, а при «нет» - больше α · a; алгоритм с множителем α решал бы вопрос. Коммивояжёр без неравенства треугольника не приближается ни с каким постоянным множителем; упаковку в контейнеры нельзя приблизить лучше 3/2, если P ≠ NP.

Разбор: призма и двудольный граф

Два графа на шести вершинах. Треугольная призма - два треугольника, соединённых тремя рёбрами, - гамильтонов цикл в ней есть. Двудольный граф, где две вершины соединены с четырьмя, - нет: цикл обязан чередовать доли, а доли разного размера. iz_grafa строит расстояния со штрафом, kommivoyazhyor считает точный оптимум таблицей по маскам из раздела о динамическом программировании.

def kommivoyazhyor(d):
    n = len(d)
    beskonechno = 10 ** 9
    luchshe = []
    for maska in range(2 ** n):
        luchshe.append([beskonechno] * n)
    luchshe[1][0] = 0
    for maska in range(1, 2 ** n):
        for v in range(n):
            if luchshe[maska][v] < beskonechno:
                for u in range(n):
                    if maska >> u & 1 == 0:
                        novaya = maska | (1 << u)
                        cena = luchshe[maska][v] + d[v][u]
                        if cena < luchshe[novaya][u]:
                            luchshe[novaya][u] = cena
    vse = 2 ** n - 1
    otvet = beskonechno
    for v in range(1, n):
        otvet = min(otvet, luchshe[vse][v] + d[v][0])
    return otvet

def iz_grafa(n, rebra, shtraf):
    d = []
    for i in range(n):
        d.append([shtraf] * n)
        d[i][i] = 0
    for r in rebra:
        d[r[0]][r[1]] = 1
        d[r[1]][r[0]] = 1
    return d

prizma = [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 3],
          [0, 3], [1, 4], [2, 5]]
dvudolnyj = [[0, 2], [0, 3], [0, 4], [0, 5], [1, 2], [1, 3],
             [1, 4], [1, 5]]
for alfa in [2, 10]:
    shtraf = alfa * 6 + 1
    print(alfa, shtraf, kommivoyazhyor(iz_grafa(6, prizma, shtraf)),
          kommivoyazhyor(iz_grafa(6, dvudolnyj, shtraf)), alfa * 6)

2 13 6 30 12
10 61 6 126 60

Столбцы: множитель α, штраф α · n + 1, оптимум для призмы, оптимум для двудольного графа, порог α · n. Призма: 6 - гамильтонов цикл. Двудольный граф: 30 при α = 2, 126 при α = 10 - оба больше порога. Любой алгоритм с множителем 2 на призме выдаст не больше 12, на двудольном - не меньше 30, и по одному сравнению с 12 скажет, есть ли гамильтонов цикл. С множителем 10 - то же с порогом 60.

Тот же довод для любого α: штраф растёт вместе с ним, и пропасть всегда шире погрешности.

Разбор: два контейнера или три

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

def konteinerov(razmery, emkost):
    # перебор раскладок: сначала в 1 контейнер, потом в 2, …
    n = len(razmery)
    for k in range(1, n + 1):
        for kod in range(k ** n):
            zagruzka = [0] * k
            x = kod
            for r in razmery:
                zagruzka[x % k] = zagruzka[x % k] + r
                x = x // k
            if max(zagruzka) <= emkost:
                return k
    return n

def pervyj_podhodyaschij(razmery, emkost):
    zagruzka = []
    for r in sorted(razmery, reverse=True):
        polozhen = False
        for i in range(len(zagruzka)):
            if not polozhen and zagruzka[i] + r <= emkost:
                zagruzka[i] = zagruzka[i] + r
                polozhen = True
        if not polozhen:
            zagruzka.append(r)
    return len(zagruzka)

for chisla in [[3, 1, 1, 2, 2, 1], [5, 4, 3, 3, 3], [4, 4, 3, 3, 2, 2],
               [7, 3, 2, 2, 2]]:
    polovina = sum(chisla) // 2
    print(chisla, sum(chisla) % 2 == 0, konteinerov(chisla, polovina),
          pervyj_podhodyaschij(chisla, polovina))

[3, 1, 1, 2, 2, 1] True 2 2
[5, 4, 3, 3, 3] True 2 2
[4, 4, 3, 3, 2, 2] True 2 3
[7, 3, 2, 2, 2] True 3 3

Первые три набора делятся поровну, оптимум 2. Четвёртый - нет: сумма 16, половина 8, а с семёркой восьмёрки не набрать; оптимум 3. Жадная упаковка на третьем наборе дала 3 при оптимуме 2: две четвёрки легли в один контейнер, и тройки с двойками уже не разошлись.

Это отношение 3/2 - и есть предел. Алгоритм, который всегда давал бы меньше 3/2 · OPT, при оптимуме 2 был бы обязан выдать 2 и тем самым решал бы разбиение. Предел касается малого числа контейнеров: когда их сотни, лишний контейнер - доля процента, и для больших входов известны алгоритмы с ответом OPT + O(log OPT) (Хоберг, Ротфосс, 2017).

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

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

Читают «нет приближения лучше 3/2» как «упаковка безнадёжна». Предел - про худший вход и малые ответы. На больших входах ошибка - O(log OPT) контейнеров сверх оптимума, малая доля.

Путают невозможность приближения с NP-трудностью. Вершинное покрытие NP-трудно и приближается вдвое; коммивояжёр без метрики NP-труден и не приближается никак. Нужен отдельный довод с разрывом.

Сводят без разрыва. Обычное сведение доказывает трудность точного ответа и ничего не говорит о приближённом: «да» и «нет» могут отличаться на единицу.

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

Когда команда месяц ищет «алгоритм с гарантией 1,2» для задачи упаковки или маршрутизации без метрики, десять минут со сведением с разрывом экономят этот месяц: если пропасть строится, искать нечего, нужно менять постановку - ослабить требование, ограничить входы, перейти к эвристике с замером. Знать предел задачи - так же важно, как знать её алгоритм.

Теперь сам

1. В сведении для коммивояжёра штраф α · n + 1. Почему не просто α · n?
2. Числа 6, 5, 4, 3, 2, 2. Делятся ли они на две равные части и сколько контейнеров ёмкостью 11 нужно?
3. Почему этот довод не работает для метрического коммивояжёра?