Изменения

'''Встреча в середине''' (англ. ''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\times G_X(y)\log)</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> fg({y}) </tex>, которое мы будем искать в нашем отсортированном массивемножестве. Таким образомЕсли в качестве множества использовать отсортированный массив, а в качестве функции поиска {{---}} [[Целочисленный двоичный поиск | бинарный поиск]], то время работы нашего алгоритма составляет <tex> {O(X\log{X})} </tex> на сортировку, и <tex> {O(Y\log{YX})} </tex> на двоичный поиск, что дает в сумме <tex>{O((X + Y)\log{X}})</tex>.

== Задача о нахождение нахождении четырех чисел с суммой равной нулю ==Дан массив целых чисел <tex>{A}</tex>. Требуется найти любые '''<tex> 4''' </tex> числа, сумма которых равна '''<tex> 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>.

<font color=darkgreen>// sum - — массив сумм a + b, cnt - — счетчик массива sum</font> '''function''' findsum('''int['''N''']''' A): String '''for ''' a = 0 to ..N - 1 '''for ''' b = 0 to ..N - 1 sum[cnt].s res = A[a] + A[b]; sum[cnt].a = a; sum[cnt++].b = b; cnt++ sort(sum, key = "res");<font color=darkgreen>// сортируем sum по полю res </font> '''for ''' c = 0 to ..N - 1 '''for ''' d = 0 to ..N - 1 '''if (''' сумма -(A[c] + A[d]) есть в массиве массив sum) ind index = индекс суммы -(A[c] + A[d]) в массиве sum; print '''return''' (sum[indindex].a, sum[indindex].b, A[c], A[d]); '''return; print(''' "No solution"); 

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

Разделим наше <font color=darkgreen>// N — количество всех вещей, w[N] — массив весов всех вещей, cost[N] — массив стоимостей всех вещей, R — ограничение по весу рюкзака.</font> '''function''' knapsack('''int['''N''']''' w, '''int['''N''']''' cost, '''int''' R): '''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") <font color=darkgreen>// сортируем first по весу </font> '''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> first {O({2^{\frac{N}{2}}}\times({N}+\log{2^{\frac{N}{2}}}))} = O({2^{\frac{N}{2}}}\times{N}) </tex> по весу. Далее пройдемся по этому массиву  == Задача о количестве полных подграфов в графе ==[[Файл:cliques.png|450px|thumb|right|Граф с 23 × 1-вершинными кликами (сами вершины), 42 × 2-вершинными кликами (отрезки), 19 × 3-вершинными кликами (светло-синие и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом тёмно-синие треугольники) и большей стоимостью2 × 4-вершинными кликами (тёмно-синие зоны). Очевидно, что подмножестваВсего 86 клик.]]Дан граф <tex>G</tex>, в котором <tex>N</tex> вершин. Требуется подсчитать количество [[Основные_определения_теории_графов#Часто используемые графы | клик]]. Наивное решение — перебор всех возможных подграфов и проверка для которых существует другоекаждого, более легкое и одновременно более ценное подмножествочто он является кликой, сложность — <tex>O(2^N \times N^2)</tex> Этот алгоритм можно удалять.Таким образом в массиве улучшить до <tex> first O(2^N \times N)</tex> . Для этого нужно в функции перебора хранить маску вершин, которые мы имеем подмножестваещё можем добавить. Поддерживая эту маску, отсортированные не можно добавлять только по весу«нужные» вершины, но и по стоимоститогда не нужно будет в конце проверять подграф на то что он — клика. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нас подмножества из первой половине, хранящиеся в массиве Добавлять вершину можно за <tex> first O(1)</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 Разбиваем граф <tex>G</tex> на <tex>2 ** sn - 1 if (существует такое подмножество с индексом j, что first[j].w <= first[i].w && first[j].c /tex> графа <tex>{G}_1</tex> и <tex>{G}_2</tex> по <tex>= first[i].c) удалим множество с индексом i из массива first for mask = 0 to \dfrac{N}{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]}</tex> вершин.w Находим за <= R - curw && first[index].c + curcost tex> ansO(2^{\frac{N}{2}}) ans = first[index]</tex> все клики в каждом из них.c + curcost print ans

Итоговое время работы Теперь надо узнать для каждой клики графа <tex> {G}_1</tex> количество клик графа <tex>{G}_2</tex>, таких, что их объединение — клика. Их сумма и есть итоговый ответ. Для одной клики <tex>K</tex> графа <tex>{G}_1</tex> может быть несколько подходящих клик в <tex>{G}_2</tex>. О клике <tex>K</tex> мы ''"знаем"'' только маску вершин графа <tex>{G}_2</tex>, которые ещё можно добавить. Для каждой такой маски в <tex>{G}_2</tex> нужно предподсчитать ответ. С помощью динамического программирования предподсчитаем для каждой маски вершин графа <tex>{G}_2</tex> количество клик, вершины которых являются подмножеством выбранной маски. Количество состояний — <tex>2^{\frac{N}{2}}</tex>. Количество переходов:<tex>N</tex> . Асимптотика — <tex>O({2^{\frac{N/}{2}}\timesN)</tex>. Для каждой клики <tex>K</tex> (в том числе и пустой) графа <tex>{NG}+\log{_1</tex> прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к <tex>K</tex> (в том числе и пустых). Асимптотика: <tex>O(2^{\frac{N/}{2}}))} = </tex>. Итоговая сложность: <tex>O({2^{\frac{N/}{2}}\times{N}) </tex>.

Еще одна задача, решаемая '''Meet-in-the-middle''' — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает '''<tex> N'''</tex>.Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть '''<tex> K''' </tex> переходов, тогда бы мы сгенерировали <tex> {K^{nN}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{nN}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{n/\frac{N}{2}}})} </tex>. <br>

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

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

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

==CсылкиИсточники информации==*[http://infoarena.ro/blog/meet-in-the-middle infoarena.ro — Meet-in-the-middle]*[http://g6prog.narod.ru/dpl.ps g6prog.narod.ru — Лекции по информатике(36 страница)]*[https://en.wikipedia.org/wiki/Clique_(graph_theory) wikipedia.org — Clique]