Точный ответ - законный выбор: сначала посчитай n

Если ты объяснишь, откуда в оценке ветвления берётся основа 1,47, почему выгодно ветвиться по вершине наибольшей степени и почему отдельные части графа решают по отдельности, листай до «Теперь сам».

Как думаешь, сколько это займёт

Нужно выбрать наибольшую группу людей, в которой никто ни с кем не конфликтует: в графе конфликтов это наибольшее независимое множество - вершины без единого ребра между ними. Задача NP-трудна, вершин 24. Подмножеств 2²⁴ ≈ 16,8 миллиона - перебор их всех в движке курса не поместится.

Ответь себе до чтения: сдаться и взять жадный ответ без гарантии? Или точный ответ здесь всё же посилен? Посилен, и не потому, что 24 - мало, а потому, что подмножеств перебирать не нужно. Ветвление с двумя правилами делает 590 вызовов. Экспонента никуда не делась - у неё просто другая основа.

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

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

Обе мысли - про NP-трудные задачи на настоящих входах. Первая про основу экспоненты, вторая про структуру: реальные графы распадаются на части, и части решаются отдельно.

Механизм: ветвление и его основа

Ветвление. Возьмём вершину v. Либо её нет в ответе - убираем v, остаётся n − 1 вершина. Либо она в ответе - тогда её соседей в ответе нет, убираем v вместе с соседями. Если у v степень d, во второй ветке остаётся n − 1 − d вершин.

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

Откуда 1,47. Пока ветвление идёт, d ≥ 2, и число вызовов T(n) удовлетворяет T(n) ≤ T(n − 1) + T(n − 3) (плюс сам вызов - на основу экспоненты это не влияет). Предположим, что T(n) растёт как xⁿ, и подставим: xⁿ = xⁿ⁻¹ + xⁿ⁻³. Поделим на xⁿ⁻³ - получится x³ = x² + 1. Единственный положительный корень x ≈ 1,4656. Это тот же ход, которым в разделе о рекурсии получилось 1,618ⁿ для Фибоначчи (x² = x + 1): основа экспоненты - корень уравнения, которое повторяет форму ветвления. Чем больше отрезает вторая ветка, тем ближе корень к единице.

ветвление                  уравнение       основа    посильное n
                                                     (10⁹ действий)
все подмножества           x = 2           2         29
не брать v / взять v, d>=1  x² = x + 1      1,618     43
не брать v / взять v, d>=2  x³ = x² + 1     1,4656    54

Посильное n - сколько вершин уложится в миллиард вызовов: n = ln 10⁹ / ln x. Переход от двойки к 1,4656 почти удваивает размер, который можно решить точно.

Правило

Точный экспоненциальный алгоритм - законный инструмент, если n посилен для его основы. Основа - корень уравнения ветвления: ветвление «не брать v / взять v, исключив её соседей» по вершине степени не меньше двух даёт T(n) ≤ T(n − 1) + T(n − 3) и основу 1,4656. Отдельные части входа решаются по отдельности: время складывается, а не перемножается.

Разбор: простое ветвление против умного

prosto ветвится по первой живой вершине без правил. umno выбирает вершину наибольшей степени и при степени не больше единицы берёт её без ветвления. Оба считают вызовы. Графы случайные: n вершин и 2n рёбер.

import random

def graf(n, m, zerno):
    random.seed(zerno)
    sosedi = []
    for v in range(n):
        sosedi.append([])
    rebra = 0
    while rebra < m:
        a = random.randrange(n)
        b = random.randrange(n)
        if a != b and b not in sosedi[a]:
            sosedi[a].append(b)
            sosedi[b].append(a)
            rebra = rebra + 1
    return sosedi

def stepen(sosedi, zhivye, v):
    s = 0
    for u in sosedi[v]:
        if zhivye[u]:
            s = s + 1
    return s

def prosto(sosedi, zhivye, schet):
    schet[0] = schet[0] + 1
    v = -1
    for u in range(len(sosedi)):
        if zhivye[u]:
            v = u
            break
    if v == -1:
        return 0
    zhivye[v] = False
    bez = prosto(sosedi, zhivye, schet)
    ubrany = []
    for u in sosedi[v]:
        if zhivye[u]:
            zhivye[u] = False
            ubrany.append(u)
    s = 1 + prosto(sosedi, zhivye, schet)
    for u in ubrany:
        zhivye[u] = True
    zhivye[v] = True
    return max(bez, s)

def umno(sosedi, zhivye, schet):
    schet[0] = schet[0] + 1
    v = -1
    for u in range(len(sosedi)):
        if zhivye[u]:
            if v == -1:
                v = u
            elif stepen(sosedi, zhivye, u) > stepen(sosedi, zhivye, v):
                v = u
    if v == -1:
        return 0
    zhivye[v] = False
    ubrany = []
    for u in sosedi[v]:
        if zhivye[u]:
            zhivye[u] = False
            ubrany.append(u)
    s = 1 + umno(sosedi, zhivye, schet)
    for u in ubrany:
        zhivye[u] = True
    luchshee = s
    if len(ubrany) >= 2:
        bez = umno(sosedi, zhivye, schet)
        luchshee = max(bez, s)
    zhivye[v] = True
    return luchshee

for n in [10, 13, 16]:
    sosedi = graf(n, 2 * n, n)
    a = [0]
    b = [0]
    print(n, 2 ** n, prosto(sosedi, [True] * n, a), a[0],
          umno(sosedi, [True] * n, b), b[0])
for n in [20, 24]:
    sosedi = graf(n, 2 * n, n)
    b = [0]
    print(n, 2 ** n, umno(sosedi, [True] * n, b), b[0])

10 1024 4 115 4 29
13 8192 5 359 5 79
16 65536 8 2599 8 75
20 1048576 10 348
24 16777216 10 590

Столбцы: n, число подмножеств, ответ и вызовы простого ветвления, ответ и вызовы умного. Ответы совпадают - оба точные. На 16 вершинах простое ветвление сделало 2599 вызовов, умное - 75. На 20 и 24 вершинах простое ветвление в движок уже не помещается, умное делает 348 и 590.

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

Разбор: граф из нескольких частей

Граф - несколько отдельных пятиугольников (циклов из пяти вершин). komponenty находит связные части обходом в ширину. Сравниваем простое ветвление по всему графу с тем же ветвлением по каждой части отдельно.

def prosto(sosedi, zhivye, schet):
    schet[0] = schet[0] + 1
    v = -1
    for u in range(len(sosedi)):
        if zhivye[u]:
            v = u
            break
    if v == -1:
        return 0
    zhivye[v] = False
    bez = prosto(sosedi, zhivye, schet)
    ubrany = []
    for u in sosedi[v]:
        if zhivye[u]:
            zhivye[u] = False
            ubrany.append(u)
    s = 1 + prosto(sosedi, zhivye, schet)
    for u in ubrany:
        zhivye[u] = True
    zhivye[v] = True
    return max(bez, s)

def komponenty(sosedi):
    nomer = [-1] * len(sosedi)
    chasti = []
    for start in range(len(sosedi)):
        if nomer[start] == -1:
            chast = [start]
            nomer[start] = len(chasti)
            i = 0
            while i < len(chast):
                for u in sosedi[chast[i]]:
                    if nomer[u] == -1:
                        nomer[u] = len(chasti)
                        chast.append(u)
                i = i + 1
            chasti.append(chast)
    return chasti

for chastej in [1, 2, 3]:
    sosedi = []
    for k in range(chastej):
        for i in range(5):
            sosedi.append([k * 5 + (i + 1) % 5, k * 5 + (i + 4) % 5])
    n = len(sosedi)
    vse = [0]
    celikom = prosto(sosedi, [True] * n, vse)
    po_chastyam = 0
    vyzovov = 0
    for chast in komponenty(sosedi):
        zhivye = [False] * n
        for v in chast:
            zhivye[v] = True
        schet = [0]
        po_chastyam = po_chastyam + prosto(sosedi, zhivye, schet)
        vyzovov = vyzovov + schet[0]
    print(chastej, n, celikom, vse[0], po_chastyam, vyzovov)

1 5 2 21 2 21
2 10 4 241 4 42
3 15 6 2661 6 63

Столбцы: число частей, вершин, ответ и вызовы целиком, ответ и вызовы по частям. По частям вызовы складываются: 21, 42, 63. Целиком - почти перемножаются: 21, 241, 2661. Ветвление не знает, что выбор в одном пятиугольнике ничего не меняет в другом, и перебирает их сочетания.

Две строки кода - поиск компонент и цикл по ним - превращают экспоненту от всего графа в сумму экспонент от частей. Реальные графы конфликтов, зависимостей, совместимости часто распадаются именно так: сто сотрудников, но конфликты только внутри отделов.

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

«Задача NP-трудна - точный ответ невозможен». NP-трудность - про рост на худших входах. Тридцать объектов на настоящих входах обычно решаются точно за секунды разумным ветвлением; отказ от точности здесь - потеря без причины.

Ветвятся по первой попавшейся вершине. Основа ухудшается, и посильный размер падает с пятидесяти до двадцати-тридцати.

Не делят вход на части. Произведение вместо суммы: 2661 вызов вместо 63 на пятнадцати вершинах, и разрыв растёт экспоненциально с числом частей.

Считают оценку худшего случая прогнозом. 1,4656²⁴ ≈ 9600, а сделано 590. Оценка нужна, чтобы знать, когда точно уложишься, а не сколько займёт.

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

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

Теперь сам

1. Ветвление T(n) = T(n − 1) + T(n − 4). Запиши уравнение для основы. Больше она или меньше 1,4656?
2. Граф из четырёх отдельных частей по 10 вершин. Сколько подмножеств перебирает полный перебор по всему графу и сколько - по частям?
3. Почему при наибольшей степени не больше единицы вершину можно брать без ветвления?