Meet-in-the-middle — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Переношу недоделанное вовремя в черновики)
Строка 84: Строка 84:
  
 
Таким образом, '''bfs-ом''' из двух концов, мы сгенерируем максимум <tex> {O({K^{N/2}})} </tex> состояний.
 
Таким образом, '''bfs-ом''' из двух концов, мы сгенерируем максимум <tex> {O({K^{N/2}})} </tex> состояний.
 
== Задача о количестве полных подграфов в графе ==
 
 
Дан граф <tex>G</tex>, в котором <tex>N</tex> вершин. Требуется подсчитать количество полных подграфов графа <tex>G</tex> (такие подграфы также называются '''кликами''' — ''clique'').
 
 
'''1.''' Наивное решение - перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность - <tex>O(2^N \times N^2)</tex>
 
 
'''2.''' Этот алгоритм можно улучшить до <tex>O(2^N)</tex>. Для этого нужно в функции перебора хранить маску вершин, которые мы ещё можем добавить. Поддерживая эту маску, можно добавлять только «нужные» вершины, и тогда не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно за <tex>O(1)</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>, которые ещё можно добавить. Для каждой такой маски в <tex>{G}_2</tex> нужно предподсчитать ответ.
 
С помощью динамического программирования предподсчитаем для каждой маски вершин графа <tex>{G}_2</tex> количество клик, вершины которой являются подмножеством выбранной маски. Количество состояний - <tex>2^{N/2}</tex>. Количество переходов:<tex>N</tex> . Асимптотика - <tex>O(2^{N/2} \times N)</tex>.
 
 
 
Для каждой клики <tex>K</tex> (в том числе и пустой) графа <tex>{G}_1</tex> прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к <tex>K</tex> (В том числе и пустых). Асимптотика: <tex>O(2^{N/2})</tex>.
 
 
 
Псевдокод подсчёта ответа:
 
for mаsk = 0 to (1 << N)
 
  dp[mask] = 1 + sum( [p[mask & matrix[i]  for i = 0 to N if ((mask & ( 1 << i )) > 0))
 
ans = sum(dp[clique1_mask[i]])
 
 
Итоговая сложность: <tex>O(2^{N/2} \times N)</tex>
 
  
 
== См. также ==
 
== См. также ==
Строка 119: Строка 92:
 
*[http://infoarena.ro/blog/meet-in-the-middle Meet-in-the-middle]
 
*[http://infoarena.ro/blog/meet-in-the-middle Meet-in-the-middle]
 
*[http://g6prog.narod.ru/dpl.ps Лекции по информатике (36 страница)]
 
*[http://g6prog.narod.ru/dpl.ps Лекции по информатике (36 страница)]
*[http://habrahabr.ru/post/191266/ Meet-in-the-middle: оптимизация перебора и не только]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Динамическое программирование ]]
 
[[Категория: Динамическое программирование ]]

Версия 23:13, 9 января 2014

Определение:
Meet-in-the-middle (Встреча в середине) — это метод решения уравнения вида [math] f({x}) = g({y}) [/math], где [math] x \in {X} [/math] и [math] y \in {Y} [/math], который работает за время [math] O(F(X) + Y \cdot G_X(y))[/math], где [math] F(X) [/math] — время построения множества [math] X [/math], [math] G_X(Y) [/math] — время поиска элемента [math] x [/math] в множестве [math] X [/math], удовлетворяющее решению при заданном [math] y [/math], или проверка, что такого [math] x [/math] не существует.

Meet-in-the-middle разбивает задачу пополам и решает всю задачу через частичный расчет половинок. Он работает следующим образом: переберем все возможные значения [math] {x} [/math] и запишем пару значений [math] ({x},{f({x})}) [/math] в множество. Затем будем перебирать всевозможные значения [math] y [/math], для каждого из них будем вычислять [math] g(y) [/math], которое мы будем искать в нашем множестве. Если в качестве множества использовать отсортированный массив, а в качестве функции поиска — бинарный поиск, то время работы нашего алгоритма составляет [math] {O(X\log{X})} [/math] на сортировку, и [math] {O(Y\log{Y})} [/math] на двоичный поиск, что дает в сумме [math]{O((X + Y)\log{X}})[/math].

Задача о нахождении четырех чисел с суммой равной нулю

Дан массив целых чисел [math]{A}[/math]. Требуется найти любые [math] 4 [/math] числа, сумма которых равна [math] 0 [/math] (одинаковые элементы могут быть использованы несколько раз).

Например : [math] {A} = ({2,3,1,0,-4,-1}) [/math]. Решением данной задачи является, например, четверка чисел [math] 3 + 1 + 0 - 4 = 0[/math] или [math] 0 + 0 + 0 + 0 = 0[/math].

Наивный алгоритм заключается в переборе всевозможных комбинаций чисел. Это решение работает за [math] {O(N^4)}[/math]. Теперь, с помощью Meet-in-the-middle мы можем сократить время работы до [math] {O(N^2\log{N}}) [/math].

Для этого заметим, что сумму [math] a + b + c + d = 0 [/math] можно записать как [math] a + b = -(c + d)[/math]. Мы будем хранить все [math] {N^2} [/math] пар сумм [math] a + b [/math] в массиве [math] sum [/math], который мы отсортируем. Далее перебираем все [math] {N^2} [/math] пар сумм [math] c + d [/math] и проверяем бинарным поиском, есть ли сумма [math] -(c + d) [/math] в массиве [math] sum [/math].

Реализация

 // sum - массив сумм a + b, cnt - счетчик массива sum
 findsum():
   for a = 0..N - 1
     for b = 0..N - 1
       sum[cnt].res = A[a] + B[b]
       sum[cnt].a = a
       sum[cnt].b = b
       cnt++
   sort(sum, key = "res") // сортируем sum по полю res
   for c = 0..N - 1
     for d = 0..N - 1
       if сумма -(A[c] + A[d]) есть в массив sum
          index = индекс суммы -(A[c] + A[d])
          return (sum[index].a, sum[index].b, A[c], A[d])
   return "No solution"

Итоговое время работы [math] {O(N^2\log{N}}) [/math].

Если вместо отсортированного массива использовать хэш-таблицу, то задачу можно будет решить за время [math] O(N^2) [/math].

Задача о рюкзаке

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

Реализация

Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве [math] first [/math]. Отсортируем массив [math] first [/math] по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять. Таким образом в массиве [math] first [/math] мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нам подмножества из первой половине, хранящиеся в массиве [math] first [/math].


Реализуем данный алгоритм:

 // N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
 knapsack():
   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]
   сортируем first по весу
   for i = 0..2 ** sn - 1
     if существует такое подмножество с индексом j, что first[j].w [math] \leqslant [/math] first[i].w and first[j].c [math] \geqslant [/math] 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 [math] \leqslant [/math] R - curw and first[index].c + curcost [math] \gt  [/math] ans
       ans = first[index].c + curcost
   return ans

Итоговое время работы [math] {O({2^{N/2}}\cdot({N}+\log{2^{N/2}}))} = O({2^{N/2}}\cdot{N}) [/math].

Задача о нахождении кратчайшего расстояния между двумя вершинами в графе

Нахождение кратчайшего расстояния между двумя вершинами

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

Алгоритм решения

1. Сгенерируем bfs-ом все состояния, доступные из начала и конца за [math] {N/2} [/math] или меньше ходов.

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

3. Найдем среди них наилучшее по сумме длин путей.


Таким образом, bfs-ом из двух концов, мы сгенерируем максимум [math] {O({K^{N/2}})} [/math] состояний.

См. также

Cсылки