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

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

Как думаешь, найдёт ли решение слепой перебор соседей

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

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

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

Сборка мебели по принципу «что не сходится, то и правим». Дверца не закрывается - значит, криво стоит либо она, либо боковая стенка; подгоняем наугад одну из двух. От этого может перекоситься что-то ещё - правим и его.

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

Механизм: блуждание числа совпадений

Задача. Есть n логических переменных, каждая истинна или ложна. Литерал - переменная или её отрицание. Формула - набор скобок, в каждой два литерала, соединённых «или»; формула истинна, когда истинны все скобки. Нужно найти значения переменных, при которых формула истинна, или сказать, что таких нет. Задача называется 2-SAT; в разделе про графы упоминалось, что её решают и без случайности, через компоненты сильной связности.

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

Почему это работает. Пусть формула выполнима; зафиксируем одно её решение S. Обозначим X число переменных, значения которых сейчас совпадают с S. Это число от 0 до n; при X = n алгоритм стоит в решении S.

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

• если с S расходятся обе переменные, любой выбор увеличивает X на единицу;
• если расходится одна, с вероятностью 1/2 выбрана она и X растёт, иначе выбрана совпадавшая и X убывает.

В любом случае X увеличивается с вероятностью не меньше 1/2. Это блуждание по пути от 0 до n, которое в худшем случае честное, а обычно сносит вправо. Блуждание, которое шагает вправо не реже честного, доходит до конца в среднем не позже него, а честному на путь длины n нужно не больше n² шагов. Алгоритм может остановиться и раньше, наткнувшись на другое решение.

Предел шагов. Дадим алгоритму 2n² шагов. По неравенству Маркова он не уложится с вероятностью не больше 1/2. Продолжим ещё на 2n² шагов с того набора, на котором остановились, - оценка n² верна с любого начала, - и так k раз, всего 2kn² шагов: если решение есть, оно не найдено с вероятностью не больше 1/2ᵏ. Если после этого решения нет, отвечаем «невыполнима». Это алгоритм Монте-Карло с односторонней ошибкой: найденное решение проверяется подстановкой и всегда верно.

Правило

Случайное блуждание для 2-SAT: пока есть ложная скобка, менять значение случайной из двух её переменных. Если формула выполнима, число совпадений с решением растёт на каждом шаге с вероятностью не меньше 1/2, и решение находится в среднем не больше чем за n² шагов. За 2kn² шагов выполнимая формула остаётся нерешённой с вероятностью не больше 1/2ᵏ. Ответ «невыполнима» может быть ошибочным, найденное решение - нет.

Разбор: десять переменных, двадцать скобок, сто запусков

Скобка записана парой чисел: число i означает переменную i, число −i - её отрицание. Литерал истинен, когда значение переменной совпадает со знаком числа: znacheniya[abs(a)] == (a > 0). Функция narushena проверяет, что оба литерала скобки ложны. Формула строится так, чтобы решение заведомо было: сначала загадывается набор значений, потом берутся случайные скобки, которые на нём истинны. Сто запусков блуждания с набора «все переменные ложны», предел - 2 · 5 · n² шагов.

import random

def narushena(skobka, znacheniya):
    a = skobka[0]
    b = skobka[1]
    pervaya = znacheniya[abs(a)] == (a > 0)
    vtoraya = znacheniya[abs(b)] == (b > 0)
    return not pervaya and not vtoraya

def bluzhdanie(formula, n, predel):
    znacheniya = [False] * (n + 1)
    for shag in range(predel + 1):
        plohaya = -1
        for i in range(len(formula)):
            if narushena(formula[i], znacheniya):
                plohaya = i
                break
        if plohaya == -1:
            return shag
        if shag < predel:
            peremennaya = abs(formula[plohaya][random.getrandbits(1)])
            znacheniya[peremennaya] = not znacheniya[peremennaya]
    return -1

random.seed(76)
n = 10
zagadano = [False]
for i in range(n):
    zagadano.append(random.getrandbits(1) == 1)

formula = []
while len(formula) < 20:
    a = random.randint(1, n)
    b = random.randint(1, n)
    if a == b:
        continue
    if random.getrandbits(1) == 0:
        a = -a
    if random.getrandbits(1) == 0:
        b = -b
    if not narushena([a, b], zagadano):
        formula.append([a, b])

opytov = 100
vsego = 0
hudshij = 0
neudach = 0
for opyt in range(opytov):
    shagov = bluzhdanie(formula, n, 2 * 5 * n * n)
    if shagov == -1:
        neudach = neudach + 1
    else:
        vsego = vsego + shagov
        hudshij = max(hudshij, shagov)
print(round(vsego / (opytov - neudach), 1), hudshij, neudach, n * n)

protivorechie = [[1, 2], [1, -2], [-1, 2], [-1, -2]]
print(bluzhdanie(protivorechie, 2, 2 * 5 * 2 * 2))

8.8 38 0 100
-1

Первая строка: в среднем 8,8 смены значения, в худшем из ста запусков - 38, неудач нет; оценка n² равна ста. Оценка - для самой неудобной формулы, у которой решение одно и блуждание честное; у случайной формулы решений много, и почти каждый шаг приближает к какому-нибудь из них.

Вторая строка - формула из четырёх скобок, перебирающих все сочетания знаков двух переменных: при любых значениях одна из скобок ложна. Блуждание исчерпало предел в сорок шагов и вернуло −1. Ответ «невыполнима» здесь верен, но получен не доказательством, а тем, что решение не нашлось за отведённое время: будь формула выполнимой, такое случилось бы с вероятностью не больше 1/2⁵.

Разбор: три переменных в скобке, и блуждание идёт назад

Применим тот же алгоритм к формуле, где в каждой скобке три литерала. Рассуждение повторяется до предпоследней строки. Скобка ложна, в решении S она истинна, значит хотя бы одна из трёх её переменных расходится с S. В худшем случае расходится ровно одна, и алгоритм выбирает её с вероятностью 1/3. С вероятностью 2/3 он меняет переменную, которая совпадала, и X убывает.

две переменные в скобке:   вперёд ≥ 1/2,  назад ≤ 1/2     честное блуждание, n² шагов
три переменные в скобке:   вперёд ≥ 1/3,  назад ≤ 2/3     снос назад, порядка 2ⁿ шагов

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

Разница между «n²» и «2ⁿ» получилась из разницы между 1/2 и 1/3. Это не доказательство того, что формулы с тремя литералами трудны, - это показывает только, что данный алгоритм на них не работает. Но граница проходит именно здесь: для двух литералов в скобке известны быстрые алгоритмы, а для трёх ни одного быстрого не найдено, и раздел про вычислимость объяснит, почему в это мало кто верит.

Блуждание для трёх литералов всё же улучшают. Если после 3n шагов решения нет, начинают заново со случайного набора значений: случайное начало в среднем совпадает с решением в половине переменных, и короткая попытка успевает дойти оттуда с заметной вероятностью. Отдельный подсчёт, который здесь опущен, показывает, что такой алгоритм работает за время порядка (4/3)ⁿ - всё ещё экспонента, но для ста переменных это уже триллионы шагов вместо числа из тридцати одной цифры.

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

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

«Не нашёл» читают как «нет». Ответ «невыполнима» - это «за 2kn² шагов не найдено». Вероятность ошибки задаётся числом k, и её нужно назначить осознанно.

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

Оценку n² переносят на другие ограничения. Она получена из того, что в скобке два литерала. Стоит разрешить третий - и вероятность шага вперёд падает ниже половины.

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

Формулами с двумя литералами записываются задачи с попарными ограничениями: «эти две задачи нельзя ставить в один слот», «если выбран этот вариант, должен быть выбран и тот», размещение подписей на карте по одну или другую сторону от точки. Для них есть линейный алгоритм через компоненты сильной связности, и в готовой системе берут его. Блуждание проще на порядок и хранит только текущий набор значений.

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

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

Теперь сам

1. Формула (x₁ или x₂), (не x₁ или x₃), (не x₂ или не x₃). Все переменные ложны. Какие скобки ложны и что может сделать первый шаг алгоритма?
2. В формуле 30 переменных. Сколько шагов достаточно в среднем и сколько нужно дать алгоритму, чтобы выполнимая формула осталась нерешённой с вероятностью не больше 1/1024?
3. Скобка ложна. В решении S истинны оба её литерала. С какой вероятностью шаг алгоритма увеличит число совпадений с S?
4. В скобках по четыре литерала. С какой вероятностью шаг идёт в верную сторону в худшем случае?
5. Алгоритм вернул набор значений. Нужно ли верить ему на слово?