Meet-in-the-middle

2014-12-09T18:06:14Z

Mariel21:

{{Определение
|definition=
'''Meet-in-the-middle''' (Встреча в середине) — это метод решения уравнения вида <tex> f({x}) = g({y}) </tex>, где <tex> x \in {X} </tex> и <tex> y \in {Y} </tex>, который работает за время <tex> O(F(X) + Y \cdot G_X(y))</tex>, где <tex> F(X) </tex> {{---}} время построения множества <tex> X </tex>, <tex> G_X(y) </tex> {{---}} время поиска элемента <tex> x </tex> в множестве <tex> X </tex>, удовлетворяющее решению при заданном <tex> y </tex>, или проверка, что такого <tex> x </tex> не существует.
}}
'''Meet-in-the-middle''' разбивает задачу пополам и решает всю задачу через частичный расчет половинок. Он работает следующим образом: переберем все возможные значения <tex> {x} </tex> и запишем пару значений <tex> ({x},{f({x})}) </tex> в множество. Затем будем перебирать всевозможные значения <tex> y </tex>, для каждого из них будем вычислять <tex> g(y) </tex>, которое мы будем искать в нашем множестве. Если в качестве множества использовать отсортированный массив, а в качестве функции поиска {{---}} [[Целочисленный двоичный поиск | бинарный поиск]], то время работы нашего алгоритма составляет <tex> {O(X\log{X})} </tex> на сортировку, и <tex> {O(Y\log{X})} </tex> на двоичный поиск, что дает в сумме <tex>{O((X + Y)\log{X}})</tex>.

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

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

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

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

=== Реализация ===
// sum - массив сумм a + b, cnt - счетчик массива sum
'''findsum'''():
'''for''' a = 0..N - 1
'''for''' b = 0..N - 1
sum[cnt].res = A[a] + B[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"
Итоговое время работы <tex> {O(N^2\log{N}}) </tex>.

Если вместо отсортированного массива использовать [[Хеш-таблица | хэш-таблицу]], то задачу можно будет решить за время <tex> O(N^2) </tex>.

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

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

Реализуем данный алгоритм:
// N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
'''knapsack'''():
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]
сортируем first по весу
'''for''' i = 0..2 ** sn - 1
'''if''' существует такое подмножество с индексом j, что first[j].w <tex> \leqslant </tex> first[i].w '''and''' first[j].c <tex> \geqslant </tex> 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 <tex> \leqslant </tex> R - curw '''and''' first[index].c + curcost <tex> > </tex> ans
ans = first[index].c + curcost
'''return''' ans

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

== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
Еще одна задача, решаемая '''Meet-in-the-middle''' — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает <tex> N </tex>.
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть <tex> K </tex> переходов, тогда бы мы сгенерировали <tex> {K^{N}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{N}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{N/2}})} </tex>. <br>
=== Алгоритм решения ===

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

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

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

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

== См. также ==
* [[Обход в ширину]]
* [[Целочисленный двоичный поиск]]

==Cсылки==
*[http://infoarena.ro/blog/meet-in-the-middle Meet-in-the-middle]
*[http://g6prog.narod.ru/dpl.ps Лекции по информатике (36 страница)]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Динамическое программирование ]]

Викиконспекты - Вклад участника [ru]

Meet-in-the-middle