Разрешение, поиск, оптимум: три лица задачи и что делать, узнав её

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

Как думаешь, не теряется ли главное

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

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

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

Игра в двадцать вопросов. Загадан предмет; отвечать можно только «да» и «нет». Хороший игрок каждым вопросом делит оставшиеся возможности пополам и за двадцать вопросов выбирает один предмет из миллиона.

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

Механизм: от ответа к решению и от решения к плану

Три формы задачи.

разрешение   есть ли независимое множество размера не меньше k?  да / нет
поиск        найди независимое множество размера k            сам объект
оптимум      найди наибольшее независимое множество        лучший объект

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

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

От разрешения к оптимуму: деление пополам. Ответ на вопрос «есть ли решение не хуже k» меняется с «да» на «нет» в одной точке. Её ищут двоичным поиском по k: если значения лежат от 0 до M, хватит примерно log₂ M обращений (точнее, log₂(M + 1) с округлением вверх: значений M + 1, и каждый вопрос оставляет половину). Перебор порогов подряд потребовал бы до M обращений, а M бывает числом из условия - длиной маршрута, суммой, - и тогда это экспонента от длины записи.

От разрешения к поиску: достраивание. Спрашиваем у оракула, выполнима ли формула. Если да - закрепляем x₁ = истина, то есть дописываем к формуле скобку из одного литерала x₁, и спрашиваем снова. Ответ «да» - оставляем, ответ «нет» - значит, во всяком выполняющем наборе x₁ ложна, и вместо этой скобки дописываем ¬x₁. Так же с x₂, и далее. После n шагов закреплены все переменные, и на каждом шаге формула оставалась выполнимой. Обращений n + 1.

Приём работает, когда после закрепления части решения остаётся задача того же вида, как у SAT. Для любой другой NP-полной задачи годится обходной путь: вопрос «можно ли достроить это частичное решение» лежит в NP - сертификатом служит достроенное решение, - а к NP-полной задаче сводится всё из NP, значит, и он.

Что делать с задачей, похожей на трудную.

1. записать точно       что дано, что выбирается, что запрещено,
                        что считается
2. узнать               семейство и конкретная задача из каталога;
                        частный случай или обобщение?
3. проверить входы      малы ли размеры? малы ли числа? особая ли
                        структура: дерево, две доли,
                        ограниченная степень?
4. если нужно, доказать трудность сведением известной задачи к своей
5. выбрать плату        точный ответ на малых входах;
                        приближённый с гарантией; хороший без гарантии;
                        точный на особом классе входов

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

Правило

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

Разбор: выполняющий набор из ответов «да» и «нет»

Оракул vypolnima отвечает, есть ли выполняющий набор, согласованный с уже закреплёнными значениями: 1 - истина, -1 - ложь, 0 - ещё не выбрано. Внутри он перебирает наборы, но для функции najti он чёрный ящик: она видит только ответы и считает обращения. Закреплённые значения переданы отдельным списком вместо дописанных скобок - это то же самое. Число в скобке формулы - номер переменной, минус - отрицание; произведение литерала на значение переменной положительно ровно тогда, когда литерал истинен.

def vypolnima(formula, n, izvestnye, vyzovov):
    vyzovov[0] = vyzovov[0] + 1
    svobodnye = []
    for i in range(1, n + 1):
        if izvestnye[i] == 0:
            svobodnye.append(i)
    for kod in range(2 ** len(svobodnye)):
        nabor = list(izvestnye)
        for j in range(len(svobodnye)):
            if kod >> j & 1 == 1:
                nabor[svobodnye[j]] = 1
            else:
                nabor[svobodnye[j]] = -1
        goditsya = True
        for skobka in formula:
            est = False
            for literal in skobka:
                if literal * nabor[abs(literal)] > 0:
                    est = True
            if not est:
                goditsya = False
                break
        if goditsya:
            return True
    return False

def najti(formula, n):
    vyzovov = [0]
    izvestnye = [0] * (n + 1)
    if not vypolnima(formula, n, izvestnye, vyzovov):
        return ["невыполнима", vyzovov[0]]
    for i in range(1, n + 1):
        izvestnye[i] = 1
        if not vypolnima(formula, n, izvestnye, vyzovov):
            izvestnye[i] = -1
    return [izvestnye[1:], vyzovov[0]]

formula = [[1, 2, -3], [-1, 3], [-2, -3], [2, 3],
           [-1, -4], [4, 5, -2], [-5, 6], [3, -6, 1]]
print(najti(formula, 6))
print(najti(formula + [[-1, -3]], 6))
print(najti([[1], [-1, 2], [-2]], 2))

[[1, -1, 1, -1, 1, 1], 7]
[[-1, 1, -1, 1, -1, -1], 7]
['невыполнима', 1]

Шесть переменных - семь обращений: одно, чтобы узнать, есть ли решение вообще, и по одному на переменную. Найден набор «истина, ложь, истина, ложь, истина, истина».

Во второй строке к формуле добавлена скобка, запрещающая x₁ и x₃ одновременно. Обращений снова семь, а набор другой: на первом же шаге оракул ответил «нет» на x₁ = истина, и переменная закреплена ложной. Каждый ответ «нет» - не неудача, а сведения: значит, в любом решении значение противоположное.

Третья формула невыполнима, и это выясняется с первого обращения.

Для формулы из тысячи переменных понадобилась бы тысяча одно обращение. Если бы оракул работал за полиномиальное время, полиномиальным был бы и поиск. Значит, быстро отвечать «выполнима ли» не легче, чем быстро находить набор.

Разбор: наибольшее множество за четыре вопроса

Оракул est_nezavisimoe отвечает, есть ли в графе независимое множество размера k. Две функции ищут наибольший размер: первая спрашивает про 1, 2, 3, … подряд, вторая делит отрезок пополам.

def est_nezavisimoe(n, ryobra, k, vyzovov):
    vyzovov[0] = vyzovov[0] + 1
    for maska in range(2 ** n):
        razmer = 0
        m = maska
        while m > 0:
            razmer = razmer + m % 2
            m = m // 2
        if razmer != k:
            continue
        goditsya = True
        for r in ryobra:
            if maska >> r[0] & 1 == 1 and maska >> r[1] & 1 == 1:
                goditsya = False
                break
        if goditsya:
            return True
    return False

def naibolshee_podryad(n, ryobra):
    vyzovov = [0]
    k = 0
    while k < n and est_nezavisimoe(n, ryobra, k + 1, vyzovov):
        k = k + 1
    return [k, vyzovov[0]]

def naibolshee_deleniem(n, ryobra):
    vyzovov = [0]
    est = 0
    net = n + 1
    while net - est > 1:
        seredina = (est + net) // 2
        if est_nezavisimoe(n, ryobra, seredina, vyzovov):
            est = seredina
        else:
            net = seredina
    return [est, vyzovov[0]]

ryobra = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4],
          [4, 5], [5, 6], [6, 7], [7, 8], [8, 4]]
print(naibolshee_podryad(9, ryobra), naibolshee_deleniem(9, ryobra))
pustoj = []
print(naibolshee_podryad(9, pustoj), naibolshee_deleniem(9, pustoj))

[4, 5] [4, 4]
[9, 9] [9, 4]

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

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

Деление пополам законно, потому что ответ оракула меняется один раз: если есть множество размера k, есть и меньшее. Так бывает не всегда: у вопроса «есть ли множество ровно такого веса» ответ может меняться много раз, и делить пополам по нему нельзя.

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

«Теория про да и нет, а у нас оптимизация». Формы равносильны с точностью до многочлена. NP-полнота вопроса с порогом означает, что и оптимум не найти быстро, если P ≠ NP.

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

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

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

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

Решатель как оракул. Готовые решатели выполнимости и целочисленных программ отвечают на вопрос «есть ли решение с такими ограничениями». Оптимизацию поверх них делают именно так: добавляют ограничение «не хуже k» и сдвигают k, пока ответ не сменится.

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

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

Теперь сам

1. Оракул отвечает, есть ли маршрут не длиннее B. Длины маршрутов - целые от 0 до 1 000 000. Сколько обращений нужно, чтобы найти длину кратчайшего?
2. В формуле сорок переменных. Сколько обращений к оракулу выполнимости нужно, чтобы найти набор?
3. Оракул ответил «нет» после закрепления x₃ = истина. Что из этого следует?
4. Как, имея оракул для вопроса «есть ли вершинное покрытие размера не больше k», найти само наименьшее покрытие?
5. Задача NP-полна, но в каждом входе не больше пятнадцати объектов. Что делать?