Цветное кодирование: случайные краски вместо памяти о посещённых

Если ты напишешь динамику «вершина и набор цветов» для разноцветного пути, посчитаешь вероятность k!/kᵏ и объяснишь, почему повторов нужно порядка eᵏ, листай до «Теперь сам».

Как думаешь, что мешает динамике

Найти в сети маршрут через шесть разных узлов - путь из шести вершин без повторов. Динамика «в какой вершине стою, сколько вершин прошёл» не работает: она не знает, не была ли вершина уже на пути, и насчитает пути с петлями. Чтобы знать, надо помнить множество пройденных вершин и конечную, а это порядка C(n, 5) · n состояний.

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

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

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

Значок - это сжатая память: шесть цветов вместо имён всех гостей.

Механизм: цвета, наборы и повторы

Разноцветный путь. Вершинам случайно даны цвета 0 … k − 1. Путь разноцветный, если все его вершины разного цвета. Такой путь не повторяет вершин автоматически.

est[v][S] - есть ли разноцветный путь с набором цветов S, кончающийся в v
начало:   est[v][{цвет v}] = да
переход:  est[v][S] = да, если есть ребро u-v, цвет v ∈ S
          и est[u][S без цвета v] = да
ответ:    est[v][все k цветов] = да для какого-то v

Наборы перебираются по возрастанию числа-маски: меньший набор всегда посчитан раньше. Состояний n · 2ᵏ, переходов m · 2ᵏ.

Вероятность удачи. Нужный путь из k вершин разноцветный, если его вершины получили k разных цветов - k! вариантов из kᵏ. Из оценки k! ≥ (k/e)ᵏ (её дают, сравнив ln k! с площадью под кривой ln x) следует k! / kᵏ ≥ e^(−k). Повторив раскраску eᵏ раз, промахнёмся везде с вероятностью не больше (1 − e^(−k))^(eᵏ) ≤ 1/e; ещё eᵏ повторов - не больше 1/e², и так далее. Итого (2e)ᵏ · poly(n), случайный алгоритм с односторонней ошибкой: найденный путь всегда настоящий, промахнуться можно только в «нет».

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

Правило

Цветное кодирование: раскрасить вершины в k цветов случайно и динамикой «вершина, набор цветов» за 2ᵏ · (n + m) найти путь со всеми разными цветами. Нужный путь разноцветен с вероятностью k!/kᵏ ≥ e^(−k), поэтому eᵏ повторов находят его с постоянной вероятностью. Время (2e)ᵏ · poly(n) - путь из k вершин FPT.

Разбор: вероятность разноцветности

Две тысячи случайных раскрасок k вершин в k цветов: в какой доле все цвета разные. Рядом точное значение k!/kᵏ и нижняя оценка e^(−k).

import math
import random

random.seed(4)
for k in [3, 4, 5, 6, 8]:
    udach = 0
    for proba in range(2000):
        cvet = []
        for v in range(k):
            cvet.append(random.randrange(k))
        if len(set(cvet)) == k:
            udach = udach + 1
    tochno = math.factorial(k) / k ** k
    print(k, udach / 2000, round(tochno, 4), round(math.exp(-k), 4))

3 0.226 0.2222 0.0498
4 0.0875 0.0938 0.0183
5 0.034 0.0384 0.0067
6 0.018 0.0154 0.0025
8 0.003 0.0024 0.0003

Доля удач близка к k!/kᵏ: при k = 3 - около 22%, при k = 6 - полтора процента, при k = 8 - четверть процента. Оценка e^(−k) грубее точного значения в несколько раз - для анализа удобна, а на деле повторов нужно меньше. При k = 6 в среднем около 65 раскрасок на один нужный путь.

Разбор: путь из шести вершин в случайном графе

25 вершин, около 30 рёбер. raznocvetnyj_put - динамика с восстановлением пути: в otkuda хранится предыдущая вершина. Раскраски повторяются, пока путь не найдётся; последняя проверка - что вершины разные и соседние соединены ребром.

import random

def raznocvetnyj_put(n, ryobra, cvet, k):
    # otkuda[v][S] - предыдущая вершина пути с набором цветов S,
    # кончающегося в v; -1 - такого пути нет, -2 - путь из одной v
    otkuda = []
    for v in range(n):
        stroka = [-1] * (2 ** k)
        stroka[1 << cvet[v]] = -2
        otkuda.append(stroka)
    for S in range(1, 2 ** k):
        for r in ryobra:
            for u, v in [[r[0], r[1]], [r[1], r[0]]]:
                bit = 1 << cvet[v]
                if S & bit and S != bit and otkuda[v][S] == -1:
                    if otkuda[u][S ^ bit] != -1:
                        otkuda[v][S] = u
    for v in range(n):
        if otkuda[v][2 ** k - 1] != -1:
            put = [v]
            S = 2 ** k - 1
            while otkuda[put[-1]][S] != -2:
                u = otkuda[put[-1]][S]
                S = S ^ (1 << cvet[put[-1]])
                put.append(u)
            return put
    return []

random.seed(21)
n = 25
ryobra = []
for i in range(30):
    a = random.randrange(n)
    b = random.randrange(n)
    if a != b and [a, b] not in ryobra and [b, a] not in ryobra:
        ryobra.append([a, b])
k = 6
popytka = 0
put = []
while len(put) == 0 and popytka < 500:
    popytka = popytka + 1
    cvet = []
    for v in range(n):
        cvet.append(random.randrange(k))
    put = raznocvetnyj_put(n, ryobra, cvet, k)
verno = len(set(put)) == k
for i in range(len(put) - 1):
    a = put[i]
    b = put[i + 1]
    if [a, b] not in ryobra and [b, a] not in ryobra:
        verno = False
print(popytka, put, verno)

1 [0, 4, 24, 13, 2, 7] True

Путь найден с первой раскраски. Это не противоречит вероятности 1,5%: она относится к одному конкретному пути, а в графе путей из шести вершин сотни, и хотя бы один из них оказался разноцветным. Повторы нужны в худшем случае - когда подходящий путь в графе один.

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

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

Ищут путь динамикой «вершина и длина». Она насчитает пути с повторами: v → u → v → … имеет ту же длину.

Делают одну раскраску. Если путь единственный, одна раскраска найдёт его с вероятностью k!/kᵏ - при k = 10 это 0,04%.

Берут меньше k цветов. Тогда разноцветного пути из k вершин не бывает вовсе.

Читают «не нашёл» как доказательство. Алгоритм ошибается только в одну сторону: «нашёл» - точно есть, «не нашёл» - скорее всего нет, но с вероятностью ошибки.

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

Поиск небольших шаблонов в больших графах: путей и деревьев фиксированной формы в сетях взаимодействия белков, мотивов в социальных графах, цепочек транзакций заданной длины. Число вершин - миллионы, размер шаблона - 5-10, и (2e)ᵏ · m здесь практично, а nᵏ - нет. Тот же приём лежит под подсчётом мотивов в анализе сетей.

Теперь сам

1. k = 5. Какова вероятность, что фиксированный путь из пяти вершин окажется разноцветным?
2. Сколько состояний est[v][S] у динамики при n = 1000, k = 10?
3. Почему разноцветный путь не может пройти вершину дважды?