Вектор ветвления: как опустить основу ниже двойки

Если ты умеешь по вектору ветвления найти основу экспоненты, объяснишь, почему ветка «все соседи v» законна, и знаешь, откуда 1,618 и 1,4656 для вершинного покрытия, листай до «Теперь сам».

Как думаешь, чем плоха двойка

Дерево поиска из прошлого урока на каждом ветвлении тратит единицу бюджета в обеих ветках. Если k = 30 - это 2³⁰ листьев, миллиард: долго, но посильно. k = 50 - уже нет.

Ответь себе до чтения: можно ли ветвиться так, чтобы хоть одна ветка тратила больше? Если вершина v не в покрытии, то все её рёбра должны закрыть соседи - все соседи сразу в покрытии. У вершины с тремя соседями ветка «не v» тратит три единицы бюджета. Дерево становится несимметричным: одна ветка мелкая, другая глубокая, - и листьев гораздо меньше.

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

Проверка гипотез в расследовании. Глупый способ - по каждому эпизоду две версии с одинаковым весом. Умный - выбрать подозреваемого, замешанного в наибольшем числе эпизодов. Либо виноват он - одна гипотеза закрыла много эпизодов. Либо не он - но тогда виноваты все его «напарники» по этим эпизодам, и это сразу несколько обвиняемых. В обоих случаях продвижение большое, а во втором - огромное.

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

Механизм: вектор ветвления и его корень

Ветвление по вершине. Возьмём вершину v наибольшей степени d:

ветка 1:  v в покрытии             →  удалить v,               k − 1
ветка 2:  v не в покрытии          →  все соседи v в покрытии,  k − d
         (иначе ребро v-сосед никто не закроет)

Если d = 1, граф - отдельные рёбра, и на каждое нужна ровно одна вершина: ветвиться не надо.

Вектор ветвления - на сколько уменьшается параметр в каждой ветке: (1, 1) у ветвления по ребру, (1, d) у ветвления по вершине. Число листьев T(k) ≤ T(k − 1) + T(k − d). Как в главе о точных методах, ищем T(k) вида xᵏ: xᵏ = xᵏ⁻¹ + xᵏ⁻ᵈ, то есть 1 = x⁻¹ + x⁻ᵈ. Общий случай - вектор (d₁, …, dₛ) и уравнение 1 = Σ x^(−dᵢ); его корень больше единицы - основа экспоненты.

Вершинное покрытие:

по ребру                      (1, 1)    2
по вершине, степень >= 2      (1, 2)    1,618
по вершине, степень >= 3      (1, 3)    1,4656
    пути и циклы - напрямую: путь из p вершин - ⌊p/2⌋,
                             цикл из c вершин - ⌈c/2⌉
лучшее известное (Харрис, Нараянасвами, 2024):  1,25284
(до них - 1,2738, Чен, Кандж, Ся, 2010)

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

Правило

Основа экспоненты ветвящегося алгоритма - корень уравнения 1 = Σ x^(−dᵢ), где dᵢ - на сколько уменьшает параметр каждая ветка. Для вершинного покрытия ветвление «v или все её соседи» по вершине степени не меньше трёх даёт вектор (1, 3) и основу 1,4656, если графы со степенями не больше двух решать напрямую.

Разбор: ребро против степени

Граф на 40 вершинах с покрытием из k вершин, вопрос с бюджетом k − 1 - ответ «нет», полное дерево. po_rebru - ветвление прошлого урока, po_stepeni - по вершине наибольшей степени, с остановкой, когда остались отдельные рёбра.

import random

def s_pokrytiem(n, k, m, zerno):
    random.seed(zerno)
    ryobra = []
    while len(ryobra) < m:
        a = random.randrange(k)
        b = random.randrange(n)
        if a != b and [a, b] not in ryobra and [b, a] not in ryobra:
            ryobra.append([a, b])
    return ryobra

def bez(ryobra, vershiny):
    ostalis = []
    for r in ryobra:
        if r[0] not in vershiny and r[1] not in vershiny:
            ostalis.append(r)
    return ostalis

def po_rebru(ryobra, k, schet):
    schet[0] = schet[0] + 1
    if len(ryobra) == 0:
        return True
    if k == 0:
        return False
    for v in ryobra[0]:
        if po_rebru(bez(ryobra, [v]), k - 1, schet):
            return True
    return False

def po_stepeni(ryobra, k, schet):
    schet[0] = schet[0] + 1
    if k < 0:
        return False
    if len(ryobra) == 0:
        return True
    if k == 0:
        return False
    sosedi = {}
    for r in ryobra:
        sosedi[r[0]] = sosedi.get(r[0], []) + [r[1]]
        sosedi[r[1]] = sosedi.get(r[1], []) + [r[0]]
    v = ryobra[0][0]
    for u in sosedi:
        if len(sosedi[u]) > len(sosedi[v]):
            v = u
    if len(sosedi[v]) == 1:
        # остались отдельные рёбра: на каждое - одна вершина
        return len(ryobra) <= k
    if po_stepeni(bez(ryobra, [v]), k - 1, schet):
        return True
    return po_stepeni(bez(ryobra, sosedi[v]), k - len(sosedi[v]), schet)

for k in [5, 7, 9]:
    ryobra = s_pokrytiem(40, k, 80, k)
    a = [0]
    b = [0]
    print(k, po_rebru(ryobra, k - 1, a), a[0],
          po_stepeni(ryobra, k - 1, b), b[0])

5 False 31 False 9
7 False 127 False 13
9 False 511 False 17

Ветвление по ребру - полное дерево: 31, 127, 511. По степени - 9, 13, 17: почти линейно по k. Граф устроен так, что вершины покрытия - концентраторы с десятками соседей. Ветка «не v» требует взять всех соседей и сразу превышает бюджет, а ветка «v» уменьшает граф до похожего. Вектор (1, 15) даёт основу около 1,15 - дерево почти путь.

Оценка 1,618ᵏ для этого алгоритма - худший случай, когда у всех вершин степень 2. На графах с концентраторами - а сети, социальные графы, графы зависимостей обычно именно такие - ветвление по степени работает несравнимо лучше своей оценки.

Разбор: основа для любого вектора

osnova находит корень уравнения 1 = Σ x^(−d) делением отрезка пополам - так же, как в разделе о поиске искали значение монотонной функции.

def osnova(vektor):
    # корень уравнения 1 = сумма x^(-d): x^n = сумма x^(n - d)
    nizh = 1.0
    verh = len(vektor) + 1.0
    for shag in range(60):
        x = (nizh + verh) / 2
        s = 0
        for d in vektor:
            s = s + x ** (-d)
        if s > 1:
            nizh = x
        else:
            verh = x
    return round(verh, 4)

for vektor in [[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [1, 1, 1]]:
    print(vektor, osnova(vektor))

[1, 1] 2.0
[1, 2] 1.618
[1, 3] 1.4656
[1, 4] 1.3803
[2, 2] 1.4142
[1, 1, 1] 3.0

(1, 1) - 2, (1, 2) - 1,618 (золотое сечение, как у Фибоначчи), (1, 3) - 1,4656, (1, 4) - 1,3803. (2, 2) - √2: две ветки, каждая тратит по два, - то же, что одна ветка на единицу с двойным шагом. (1, 1, 1) - 3: три ветки по единице хуже двух по единице.

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

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

Ветвятся по вершине малой степени. Вектор (1, 1) у вершины степени 1 - снова основа 2, и даже хуже: ветка «соседи» ничего не выигрывает. Поэтому вершины степени 1 обрабатывают без ветвления: соседа листа выгодно брать всегда.

Оценивают ветвление на глаз. «Три ветки, но каждая тратит много» и «две ветки по единице» - сравниваются только корнями. (2, 2, 2) даёт √3 ≈ 1,73 - хуже (1, 3), хотя каждая ветка тратит вдвое больше.

Не решают простые остатки напрямую. Пути и циклы - полиномиальный случай; ветвиться по ним - платить экспонентой за то, что считается формулой.

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

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

Теперь сам

1. Вектор ветвления (2, 3). Запиши уравнение и прикинь основу.
2. Почему в ветке «v не в покрытии» можно сразу взять всех соседей v?
3. Граф - цикл из 9 вершин. Сколько вершин нужно для покрытия и надо ли ветвиться?