Meet-in-the-middle - Алгоритмика
Meet-in-the-middle

Meet-in-the-middle

автор Сергей Слотин
обновлено сент. 10, 2021

Рассмотрим какую-нибудь задачу на перебор подмножеств, которую мы умеем решать за $O(2^n \cdot poly(n))$, где $poly(n)$ — какой-то полином от размера задачи $n$. Метод meet-in-the-middle (дословно, «встреча в середине») позволяет соптимизировать перебор до $O(2^{n/2} \cdot poly(n))$ в большом классе таких задач.

В качестве конкретного примера, рассмотрим задачу о рюкзаке — нужно выбрать подмножество $a_i$ с суммарным весом $w$:

bool find_subset(int *a, int n, int w)
    for (int mask = 0; mask < (1 << n); mask++) {
        int s = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1)
                s += a[i];
        if (s == w)
            return true;
    }
    return false;
}

Здесь мы перебираем все подмножества и каждое проверяем за $O(n)$, что дает асимптотику $O(2^n \cdot n)$.

В теории можно избавиться от проверки за $O(n)$, если перебирать маску рекурсивно и поддерживать текущую сумму на префиксе, возможно добавляя во время спуска только один элемент. Однако мы погонимся за более мощной оптимизацией.

Решение

Разделим массив на две части. Заметим, что искомое подмножество имеет какое-то количество элементов из левой половины и какое-то количество элементов из правой (возможно, нулевое). Попытаемся посчитать все суммы слева и справа по отдельности и найти пару, дающую нужную общую сумму.

Сначала посчитаем суммы для всех подмножеств среди первых $l = \lfloor \frac{n}{2} \rfloor$ элементов и положим в хеш-таблицу:

unordered_set<int> t;

int l = n / 2;

for (int mask = 0; mask < (1 << l); mask++) {
    int s = 0;
    for (int i = 0; i < n; i++)
        if (mask >> i & 1)
            s += a[i];
    t.insert(s);
}

Затем переберем все суммы среди оставшихся $r = n - l = \lceil \frac{n}{2} \rceil$ элементов и для каждой попытаемся найти подходящую половину (с суммой $s_l = w - s_r$) через предподсчитанную хеш-таблицу:

int r = n - l;

for (int mask = 0; mask < (1 << r); mask++) {
    int s = 0;
    for (int i = 0; i < r; i++)
        if (mask >> i & 1)
            s += a[l + i];
    if (t.count(w - s))
        return true;
}

Обе фазы (а значит и сам алгоритм) работают за $O(2^{n/2} \cdot n)$: мы перебираем $2^{n/2}$ подмножеств и для каждого за $O(n)$ считаем сумму и делаем запрос добавления / проверки наличия в хеш-таблицу за $O(1)$.

Заметим, что оба перебора всё ещё можно так же соптимизировать в $O(n)$ раз через трюк с рекурсией.

Другие примеры

Задача. Найти количество чисел до $10^{14}$ с суммой цифр $s$.

Разделим число на левую часть (старшие 7 разрядов) и правую (младшие 7 разрядов). Для всех чисел левой части предподсчитаем, сколько из них имеют сумму $s$ и запишем это в массив предподсчёта (его размер будет $7 \times 9 + 1 = 64$). Затем переберем правую часть, и тогда для «левой» суммы $s$ нам нужно найти количество правых частей с суммой $(w - s)$, для чего мы просто за $O(1)$ обращаемся к предподсчитанному массиву.

На больших ограничениях эта задача решается через динамику по цифрам.

Задача. Дан граф из $n$ вершин. Нужно найти количество клик — подграфов, в котором все вершины связаны со всеми.

Сначала научимся решать задачу полным перебором. Пусть у нас есть матрица смежности графа. Как быстро проверить, что подмножество вершин $m$ является кликой?

За $O(n^2)$ можно пройтись по всем парам включенных вершин и для каждой проверить, есть ли единичка в матрице смежности. Проверку можно соптимизировать до $O(n)$, посчитав маску $m'$, равную побитовому «И» строчек матрицы смежности, соответствующих вершинам $m$. Теперь, если $m$ является подмножеством $m'$, то есть

$$ m \; \& \; m' = m $$

то подграф $m$ является кликой: для всех его вершин есть ребро из всех других.

Воспользуемся этим трюком для слияния ответов в meet-in-the-middle. Разделим граф на две части, найдем для левой все клики и пометим их маски единицами в специальном массиве is_clique[mask] размера $2^{n/2}$.

Теперь будем перебирать подграфы второй половины, и для каждой клики нам нужно найти количество клик левой половины, являющихся подграфами пересечения списков смежности для правой половины ($m'$ из проверки выше).

Чтобы сделать это быстро, предподсчитаем поверх массива is_clique динамику «как много подмасок данной маски являются кликами». Эту динамику можно посчитать за $O(2^{n/2})$, если для каждой маски $m$ рассмотреть два варианта — когда первая вершина $v$ включена в клику и когда не включена:

$$ f[m] = f[m \; \& \; g_v \oplus 2^v] + f[m \oplus 2^v] + is\_clique[m] $$

Итоговая асимптотика алгоритма будет $O(2^{n/2} \cdot n)$.

Задача. Неявно задан очень большой невзвешенный граф, в котором у каждой вершины не более $k$ переходов. Требуется найти расстояние от $s$ до $t$, если известно, что оно не превышает $n$.

Запустим обход в ширину одновременно из обеих вершин, записывая рядом с вершинами расстояния от $s$ или $t$ найденные соответствующим обходом. Когда обход с одной стороны зайдет в вершину, посещенную другим обходом, то восстанавливаем путь размера $(d_s + d_t)$ и завершаемся.

Так как расстояние не превосходит $n$, то алгоритм гарантированно завершится за $O(\frac{n}{2})$ «волн». Так как каждая вершина связана с не более $k$ другими, и в «родителя» алгоритм не заходит, на следующей волне будет не более чем в $(k-1)$ раз больше вершин, чем на предыдущей.

Значит суммарно будет посещено $O((k-1)^{n/2})$ вершин, чему и будет равна асимптотика алгоритма.