Meet-in-the-middle
| Определение: |
| Meet-in-the-middle (Встреча в середине) — это метод решения уравнения вида , где и , который работает за время , где время поиска в множестве . |
Meet-in-the-middle разбивает задачу пополам и решает всю задачу через частичный расчет половинок. Он работает следующим образом : переберем все возможные значения и запишем пару значений в массив, который мы отсортируем по второму элементу (значению функции). Затем будем перебирать всевозможные значения , для каждого из них будем вычислять , которое мы будем искать в нашем отсортированном массиве. Таким образом, время работы нашего алгоритма составляет на сортировку, и на поиск, что дает в сумме .
Содержание
Задача о нахождение четырех чисел с суммой равной нулю
Дан массив целых чисел . Требуется найти любые 4 числа, сумма которых равна 0 (одинаковые элементы могут быть использованы несколько раз).
Например : . Решением данной задачи является, например, четверка чисел или .
Наивный алгоритм заключается в переборе всевозможных комбинаций чисел. Это решение работает за . Теперь, с помощью Meet-in-the-middle мы можем сократить время работы до .
Для этого заметим, что сумму можно записать как . Мы будем хранить все пар сумм в массиве , который мы отсортируем. Далее перебираем все пар сумм и проверяем бинарным поиском, есть ли сумма в массиве .
Реализация
// sum - массив сумм a + b, cnt - счетчик массива sum
for a = 0 to N - 1
for b = 0 to N - 1
sum[cnt].s = A[a] + A[b];
sum[cnt].a = a;
sum[cnt++].b = b;
sort(sum);
for c = 0 to N - 1
for d = 0 to N - 1
if (сумма -(A[c] + A[d]) есть в массиве sum)
ind = индекс суммы -(A[c] + A[d]) в массиве sum;
print(sum[ind].a, sum[ind].b, A[c], A[d]);
return;
print("No solution");
Итоговое время работы .
Задача о рюкзаке
Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом ( ) и ценностью (). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время, можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма . Память .
Реализация
Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве . Отсортируем массив по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять. Таким образом в массиве мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нам подмножества из первой половине, хранящиеся в массиве .
Реализуем данный алгоритм:
// N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
sn = N / 2, fn = N - sn;
for mask = 0 to 2 ** sn - 1
for j = 0 to sn
if j-ый бит mask = 1
first[i].w += w[j];
first[i].c += cost[j];
sort(first);
for i = 0 to 2 ** sn - 1
if (существует такое подмножество с индексом j, что first[j].w <= first[i].w && first[j].c >= first[i].c)
удалим множество с индексом i из массива first
for mask = 0 to 2 ** fn - 1
for j = 0 to fn
if j-ый бит mask = 1
curw += w[j + sn];
curcost += cost[j + sn];
В массиве first бинарным поиском находим подмножество, с максимальным весом, который не превышает R - curw
if (first[index].w <= R - curw && first[index].c + curcost > ans)
ans = first[index].c + curcost
print ans
Итоговое время работы .
Задача о нахождении кратчайшего расстояния между двумя вершинами в графе
Еще одна задача, решаемая Meet-in-the-middle — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает N.
Стандартным подходом для решения данной задачи, является применение алгоритма обхода в ширину. Пусть из каждого состояния у нас есть K переходов, тогда бы мы сгенерировали состояний. Асимптотика данного решения составила бы . Meet-in-the-middle помогает снизить асимптотику до .
Алгоритм решения
1. Сгенерируем bfs-ом все состояния, доступные из начала и конца за или меньше ходов.
2. Найдем состояния, которые достижимы из начала и из конца.
3. Найдем среди них наилучшее по сумме длин путей.
Таким образом, bfs-ом из двух концов, мы сгенерируем максимум состояний.
