Meet-in-the-middle

Определение:

Meet-in-the-middle (Встреча в середине) — это метод решения уравнения вида $f({x}) = g({y})$, где $x \in {X}$ и $y \in {Y}$, который работает за время $O(F(X) + Y \cdot G_X(y))$, где $F(X)$ — время построения множества $X$, $G_X(y)$ — время поиска элемента $x$ в множестве $X$, удовлетворяющее решению при заданном $y$, или проверка, что такого $x$ не существует.

Meet-in-the-middle разбивает задачу пополам и решает всю задачу через частичный расчет половинок. Он работает следующим образом: переберем все возможные значения ${x}$ и запишем пару значений $({x},{f({x})})$ в множество. Затем будем перебирать всевозможные значения $y$, для каждого из них будем вычислять $g(y)$, которое мы будем искать в нашем множестве. Если в качестве множества использовать отсортированный массив, а в качестве функции поиска — бинарный поиск, то время работы нашего алгоритма составляет ${O(X\log{X})}$ на сортировку, и ${O(Y\log{X})}$ на двоичный поиск, что дает в сумме ${O((X + Y)\log{X}})$.

Задача о нахождении четырех чисел с суммой равной нулю

Дан массив целых чисел ${A}$. Требуется найти любые $4$ числа, сумма которых равна $0$ (одинаковые элементы могут быть использованы несколько раз).

Например : ${A} = ({2,3,1,0,-4,-1})$. Решением данной задачи является, например, четверка чисел $3 + 1 + 0 - 4 = 0$ или $0 + 0 + 0 + 0 = 0$.

Наивный алгоритм заключается в переборе всевозможных комбинаций чисел. Это решение работает за ${O(N^4)}$. Теперь, с помощью Meet-in-the-middle мы можем сократить время работы до ${O(N^2\log{N}})$.

Для этого заметим, что сумму $a + b + c + d = 0$ можно записать как $a + b = -(c + d)$. Мы будем хранить все ${N^2}$ пар сумм $a + b$ в массиве $sum$, который мы отсортируем. Далее перебираем все ${N^2}$ пар сумм $c + d$ и проверяем бинарным поиском, есть ли сумма $-(c + d)$ в массиве $sum$.

Реализация

 // sum - массив сумм a + b, cnt - счетчик массива sum
 function findsum(int[] A): 
   for a = 0..N - 1
     for b = 0..N - 1
       sum[cnt].res = A[a] + A[b]
       sum[cnt].a = a
       sum[cnt].b = b
       cnt++
   sort(sum, key = "res") // сортируем sum по полю res
   for c = 0..N - 1
     for d = 0..N - 1
       if сумма - (A[c] + A[d]) есть в массив sum
          index = индекс суммы -(A[c] + A[d])
          return (sum[index].a, sum[index].b, A[c], A[d])
   return "No solution"

Итоговое время работы ${O(N^2\log{N}})$.

Если вместо отсортированного массива использовать хэш-таблицу, то задачу можно будет решить за время $O(N^2)$.

Задача о рюкзаке

Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (${w_{i} \leqslant 10^{9}}$ ) и ценностью (${cost_{i} \leqslant 10^{9}}$). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма $O({2^{N/2}}\cdot{N})$. Память $O({2^{N/2}})$.

Реализация

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

Реализуем данный алгоритм:

 // N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
 function knapsack(): int
   sn = N / 2
   fn = N - sn
   for mask = 0..2 ** sn - 1
     for j = 0..sn
       if j-ый бит mask == 1
         first[i].w += w[j]
         first[i].c += cost[j]
   sort(first, key = "w") // сортируем first по весу
   for i = 0..2 ** sn - 1
     if существует такое подмножество с индексом j, что first[j].w $\leqslant$ first[i].w and first[j].c $\geqslant$ first[i].c
       удалим множество с индексом i из массива first
   for mask = 0..2 ** fn - 1
     for j = 0..fn
       if j-ый бит mask == 1
         curw += w[j + sn]
         curcost += cost[j + sn]
     index = позиция, найденная бинарным поиском в массиве first, подмножества с максимальным весом, не превыщающим R - curv
     if first[index].w $\leqslant$ R - curw and first[index].c + curcost $\gt$ ans
       ans = first[index].c + curcost
   return ans

Итоговое время работы ${O({2^{N/2}}\cdot({N}+\log{2^{N/2}}))} = O({2^{N/2}}\cdot{N})$.

Задача о нахождении кратчайшего расстояния между двумя вершинами в графе

Нахождение кратчайшего расстояния между двумя вершинами

Еще одна задача, решаемая Meet-in-the-middle — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает $N$. Стандартным подходом для решения данной задачи, является применение алгоритма обхода в ширину. Пусть из каждого состояния у нас есть $K$ переходов, тогда бы мы сгенерировали ${K^{N}}$ состояний. Асимптотика данного решения составила бы ${O({K^{N}})}$. Meet-in-the-middle помогает снизить асимптотику до ${O({K^{N/2}})}$.

Алгоритм решения

1. Сгенерируем bfs-ом все состояния, доступные из начала и конца за ${N/2}$ или меньше ходов.

2. Найдем состояния, которые достижимы из начала и из конца.

3. Найдем среди них наилучшее по сумме длин путей.

Таким образом, bfs-ом из двух концов, мы сгенерируем максимум ${O({K^{N/2}})}$ состояний.

См. также

• Обход в ширину
• Целочисленный двоичный поиск

Источники информации

• Meet-in-the-middle
• Лекции по информатике (36 страница)