Изменения

Перейти к: навигация, поиск

Meet-in-the-middle

214 байт добавлено, 16:32, 5 января 2017
Реализация
{{Определение
|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) + Y \times G_X(y))</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> g(y) </tex>, которое мы будем искать в нашем множестве. Если в качестве множества использовать отсортированный массив, а в качестве функции поиска {{---}} [[Целочисленный двоичный поиск | бинарный поиск]], то время работы нашего алгоритма составляет <tex> {O(X\log{X})} </tex> на сортировку, и <tex> {O(Y\log{X})} </tex> на двоичный поиск, что дает в сумме <tex>{O((X + Y)\log{X}})</tex>.
=== Реализация ===
<font color=darkgreen>// sum — массив сумм a + b, cnt — счетчик массива sum</font>
'''function''' findsum('''int['''N''']''' A): String
'''for''' a = 0..N - 1
'''for''' b = 0..N - 1
== Задача о рюкзаке ==
Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<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>.
=== Алгоритм ===
=== Реализация ===
<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
'''return''' ans
Итоговое время работы <tex> {O({2^{\frac{N/}{2}}}\times({N}+\log{2^{\frac{N/}{2}}}))} = O({2^{\frac{N/}{2}}}\times{N}) </tex>.
== Задача о количестве полных подграфов в графе ==
Наивное решение — перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность — <tex>O(2^N \times N^2)</tex>
Этот алгоритм можно улучшить до <tex>O(2^N \times N)</tex>. Для этого нужно в функции перебора хранить маску вершин, которые мы ещё можем добавить. Поддерживая эту маску, можно добавлять только «нужные» вершины, и тогда не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно за <tex>O(1)</tex>, используя [[Побитовые_операции#Побитовое И | побитовое «и» И]] текущей маски и строчки матрицы смежности добавляемой вершины.
===Алгоритм решения===
Разбиваем граф <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>{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}} \times N)</tex>.
Для каждой клики <tex>K</tex> (в том числе и пустой) графа <tex>{G}_1</tex> прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к <tex>K</tex> (В в том числе и пустых). Асимптотика: <tex>O(2^{\frac{N}{2}})</tex>.
Итоговая сложность: <tex>O(2^{\frac{N}{2}} \times N)</tex>
=== Алгоритм решения ===
1. Сгенерируем '''BFS'''-ом все состояния, доступные из начала и конца за <tex> {\dfrac{N/}{2}} </tex> или меньше ходов.
2. Найдем состояния, которые достижимы из начала и из конца.
84
правки

Навигация