Страница находится {{Определение|definition='''Meet-in-the-middle''' (Встреча в разработкесередине) — это метод решения уравнения вида <tex> f({x}) = g({y}) </tex>, где <tex> x \in {X} </tex> и <tex> y \in {Y} </tex>, который работает за время <tex> {O((X + Y)\log{X}})</tex>.}}'''Meet-in-the-middle''' разбивает задачу пополам и решает всю задачу через частичный расчет половинок. Он работает следующим образом : переберем все возможные значения <tex> {x} </tex> и запишем пару значений <tex> ({x},{f({x})}) </tex> в массив, который мы отсортируем по второму элементу (значению функции). Затем будем перебирать всевозможные значения <tex> {y} </tex>, для каждого из них будем вычислять <tex> f({y}) </tex>, которое мы будем искать в нашем отсортированном массиве. Таким образом, время работы нашего алгоритма составляет <tex> {O(X\log{X})} </tex> на сортировку, и <tex> {O(Y\log{Y})} </tex> на двоичный поиск, что дает в сумме <tex>{O((X + Y)\log{X}})</tex> == Задача о нахождение четырех чисел с суммой равной нулю ==Дан массив целых чисел <tex>{A}</tex>. Требуется найти любые '''4''' числа, сумма которых равна '''0''' (одинаковые элементы могут быть использованы несколько раз). Например : <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 + N)\log{N}}) = {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 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"); Итоговое время работы <tex> {O(N^2\log{N}}) </tex>. == Задача о рюкзаке ==Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<tex> {w_{i} <= 10^{9}} </tex> ) и ценностью (<tex>{cost_{i} <= 10^{9}} </tex>). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время, можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма <tex>O({2^{N/2}}\times{N})</tex>. Память <tex> O({2^{N/2}})</tex> === Реализация ===Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве <tex> first </tex>. Отсортируем массив <tex> first </tex> по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять.Таким образом в массиве <tex> first </tex> мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нас подмножества из первой половине, хранящиеся в массиве <tex> first </tex>. Реализуем данный алгоритм: // 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 Итоговое время работы <tex> {O({2^{N/2}}\times({N}+\log{2^{N/2}}))} = O({2^{N/2}}\times{N}) </tex>. == Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]Еще одна задача, решаемая '''Meet-in-the-middle''' — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает '''N'''.Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть '''K''' переходов, тогда бы мы сгенерировали <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 страница)] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Динамическое программирование ]]
