84
правки
Изменения
→Реализация
{{Определение
|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\log{X} ) + Y\times{hG_X({X}y)}})</tex>, где <tex> F(X) </tex> {h({X---})} время построения множества <tex> X </tex> время поиска , <tex> G_X(y) </tex> {g({y---})} время поиска элемента <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\times{h(log{X}))}} </tex> на двоичный поиск, что дает в сумме <tex> {O((X\log{X} + Y)\times{h(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>.
=== Реализация ===
<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> {O(N^2\log{N}}) </tex>.
Если вместо отсортированного массива использовать [[Хеш-таблица | хэш-таблицу]], то задачу можно будет решить за время <tex> O(N^2) </tex>.
== Задача о рюкзаке ==
Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<tex> {w_{i} \le leqslant 10^{9}} </tex> ) и ценностью (<tex>{cost_{i} \le 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>.
=== Реализация ===
== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
Еще одна задача, решаемая '''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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование ]]
[[Категория: Классические задачи динамического программирования ]]