Изменения

'''Встреча в середине''' (англ. ''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 times G_X(y))</tex>, где <tex> F(X) </tex> {{---}} время построения множества <tex> X </tex>, <tex> G_X(Yy) </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{YX})} </tex> на двоичный поиск, что дает в сумме <tex>{O((X + Y)\log{X}})</tex>.

<font color=darkgreen>// sum - — массив сумм a + b, cnt - — счетчик массива sum</font> '''function'''findsum('''int[''('N''']''' A):String

sum[cnt].res = A[a] + BA[b]

sort(sum, key = "res") <font color=darkgreen>// сортируем sum по полю res</font>

'''if''' сумма -(A[c] + A[d]) есть в массив sum

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

Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве <tex> first </tex>. Отсортируем массив <tex> first </tex> по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять.Таким образом в массиве <tex> first </tex> мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нам подмножества из первой половине, хранящиеся в массиве <texfont color=darkgreen> first </tex>.  Реализуем данный алгоритм: // N - — количество всех вещей, w[N] - — массив весов всех вещей, cost[N] - — массив стоимостей всех вещей, R - — ограничение по весу рюкзака.</font> '''function'''knapsack('''int['''N''']''(' w, '''int['''N''']''' cost, '''int''' R):'''int'''

'''for''' mask = 0..2 ** sn - 1

first[i].w += w[j];

sort(first, key = "w") <font color=darkgreen>// сортируем first по весу</font>

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

== Задача о нахождении кратчайшего расстояния между двумя вершинами количестве полных подграфов в графе ==[[Файл:bfscliques.png|600px450px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]Граф с 23 × 1-вершинными кликами (сами вершины), Еще одна задача42 × 2-вершинными кликами (отрезки), решаемая '''Meet19 × 3-inвершинными кликами (светло-theсиние и тёмно-middle''' — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние синие треугольники) и то, что длина оптимального пути не превышает <tex> N </tex>2 × 4-вершинными кликами (тёмно-синие зоны). Всего 86 клик.Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть Дан граф <tex> K G</tex> переходов, тогда бы мы сгенерировали в котором <tex> {K^{N}} </tex> состоянийвершин. Асимптотика данного решения составила бы <tex> {O({K^{N}})} </tex>Требуется подсчитать количество [[Основные_определения_теории_графов#Часто используемые графы | клик]]. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{N/2}})} </tex>. <br>=== Алгоритм решения ===

1. Сгенерируем '''bfs'''-ом все состоянияНаивное решение — перебор всех возможных подграфов и проверка для каждого, доступные из начала и конца за что он является кликой, сложность — <tex> {O(2^N/\times N^2} )</tex> или меньше ходов.

Этот алгоритм можно улучшить до <tex>O(2^N \times N)</tex>. Найдем состоянияДля этого нужно в функции перебора хранить маску вершин, которые достижимы из начала мы ещё можем добавить. Поддерживая эту маску, можно добавлять только «нужные» вершины, и тогда не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно за <tex>O(1)</tex>, используя [[Побитовые_операции#Побитовое И | побитовое И]] текущей маски и из концастрочки матрицы смежности добавляемой вершины.

3===Алгоритм решения===Разбиваем граф <tex>G</tex> на <tex>2</tex> графа <tex>{G}_1</tex> и <tex>{G}_2</tex> по <tex>\dfrac{N}{2}</tex> вершин. Найдем среди Находим за <tex>O(2^{\frac{N}{2}})</tex> все клики в каждом из них наилучшее по сумме длин путей.

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

== Задача о количестве всех полных подграфов Для каждой клики <tex>K</tex> (в графе ==том числе и пустой) графа <tex>{G}_1</tex> прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к <tex>K</tex> (в том числе и пустых). Асимптотика: <tex>O(2^{\frac{N}{2}})</tex>.

Дан граф <tex>G</tex>, в котором Итоговая сложность: <tex>O(2^{\frac{N}{2}} \times N)</tex> вершин. Требуется подсчитать количество полных подграфов графа <tex>G</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(2{K^N {\times frac{N^}{2}}})} </tex>. <br>=== Алгоритм решения ===

Этот алгоритм можно улучшить до <tex>O(2^N)</tex>. Для этого нужно в рекурсивной функции перебора хранить маску вершин, которые мы ещё можем добавить1. Поддерживая эту маску, можно добавлять только «нужные» вершиныСгенерируем '''BFS'''-ом все состояния, доступные из начала и тогда, не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно конца за <tex>O(1){\dfrac{N}{2}} </tex>, используя побитовое «и» текущей маски и строчки матрицы смежности добавляемой вершиныили меньше ходов.

Решение с meet-in-the-middle.Разбиваем граф <tex>G</tex> на 2 графа <tex>{G}_1</tex> и <tex>{G}_2</tex> по <tex>N/2</tex> вершин. Находим за <tex>O(2^{N/2})</tex> все клики в каждом Найдем состояния, которые достижимы из них. Теперь надо узнать для каждой клики графа <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>, которые ещё можно добавить. Для каждой такой маски в {G}_2</tex> нужно предподсчитать ответ. С помощью метода динамического программирования предподсчитаем для каждой маски вершин графа {G}_2</tex> количество клик, вершины которой являются подмножеством выбранной маски. Количество состояний - <tex>2^{N/2}</tex>. Количество переходов:<tex>N</tex> . Асимптотика - <tex>O(2^{N/2} \times N)</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 страница)]*[httphttps://habrahabren.wikipedia.ruorg/postwiki/191266/ Meet-in-the-middle: оптимизация перебора и не толькоClique_(graph_theory) wikipedia.org — Clique]