Изменения

'''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>.

'''findsum()''' sum <tex>\leftarrow \emptyset </tex>() '''for''' a = 0 .. N - 1 '''for''' b = 0 .. N - 1 sum[cnt].s <tex>\leftarrow</tex> res = A[a] + B[b] sum[cnt].a <tex>\leftarrow</tex> = a sum[cnt].b <tex>\leftarrow</tex> = b

'''for''' c = 0 .. N - 1 '''for''' d = 0 .. N - 1

index <tex> \leftarrow </tex> = индекс суммы -(A[c] + A[d])

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

sn <tex> \leftarrow </tex> = N / 2 fn <tex> \leftarrow </tex> = N - sn; '''for''' mask = 0 .. 2 ** sn - 1

'''for''' mask = 0 .. 2 ** fn - 1 '''for''' j = 0 .. fn

В index = позиция, найденная бинарным поиском в массиве first бинарным поиском находим подмножество, подмножества с максимальным весом, который не превышает превыщающим R - curwcurv

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

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

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