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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Содержимое страницы заменено на «Страница находится в разработке»)
Строка 1: Строка 1:
Страница находится в разработке
+
{{Определение
 +
|definition=
 +
'''Meet-in-the-middle''' (Встреча в середине)  — это метод решения уравнения вида <tex> f({x}) = g({y}) </tex>, где <tex> x \in {X} </tex> и <tex> y \in {Y} </tex>, который работает за время <tex> {O((X + Y)\log{X}})</tex>.}}
 +
'''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>
 +
 
 +
== Задача о нахождение четырех чисел с суммой равной нулю ==
 +
Дан массив целых чисел <tex>{A}</tex>. Требуется найти любые '''4''' числа, сумма которых равна '''0''' (одинаковые элементы могут быть использованы несколько раз).
 +
 
 +
Например : <tex> {A} = ({2,3,1,0,-4,-1}) </tex>. Решением данной задачи является, например, четверка чисел <tex> 3 + 1 + 0 - 4 = 0</tex> или <tex> 0 + 0 + 0 + 0 = 0</tex>.
 +
 
 +
Наивный алгоритм заключается в переборе всевозможных комбинаций чисел. Это решение работает за <tex> {O(N^4)}</tex>. Теперь, с помощью '''Meet-in-the-middle''' мы можем сократить время работы до <tex> {O((N + N)\log{N}}) = {O(N^2\log{N}}) </tex>.
 +
 
 +
Для этого заметим, что сумму <tex> a + b + c + d = 0 </tex> можно записать как <tex> a + b = -(c + d)</tex>. Мы будем хранить все <tex> {N^2} </tex> пар сумм <tex> a + b </tex> в массиве <tex> sum </tex>, который мы отсортируем. Далее перебираем все <tex> {N^2} </tex> пар сумм <tex> c + d </tex> и проверяем бинарным поиском, есть ли сумма <tex> -(c + d) </tex> в массиве <tex> sum </tex>.
 +
 
 +
=== Псевдокод ===
 +
  // sum - массив сумм a + b, cnt - счетчик массива sum
 +
  for a = 0 to N - 1
 +
    for b = 0 to N - 1
 +
      sum[cnt].s = A[a] + A[b];
 +
      sum[cnt].a = a;
 +
      sum[cnt++].b = b;
 +
  sort(sum);
 +
 
 +
  for c = 0 to N - 1
 +
    for d = 0 to N - 1
 +
      if (сумма -(A[c] + A[d]) есть в массиве sum)
 +
        ind = индекс суммы -(A[c] + A[d]) в массиве sum;
 +
        print(sum[ind].a, sum[ind].b, A[c], A[d]);
 +
        return;
 +
  print("No solution");
 +
 
 +
Итоговое время работы <tex> {O(N^2\log{N}}) </tex>.
 +
 
 +
 
 +
== Задача о рюкзаке ==
 +
Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<tex> {w_{i} <= 10^{9}} </tex> ) и ценностью (<tex>{cost_{i} <= 10^{9}} </tex>). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время, можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма <tex>O({2^{N/2}}\times{N})</tex>. Память <tex> O({2^{N/2}})</tex>
 +
 
 +
=== Реализация ===
 +
Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве <tex> first </tex>. Отсортируем массив <tex> first </tex> по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять.
 +
Таким образом в массиве <tex> first </tex> мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нас подмножества из первой половине, хранящиеся в массиве <tex> first </tex>.
 +
 
 +
 +
Реализуем данный алгоритм:
 +
  // N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
 +
  sn = N / 2, fn = N - sn;
 +
  for mask = 0 to 2 ** sn - 1
 +
    for j = 0 to sn
 +
      if j-ый бит mask = 1
 +
        first[i].w += w[j];
 +
        first[i].c += cost[j];
 +
  sort(first);
 +
  for i = 0 to 2 ** sn - 1
 +
    if (существует такое подмножество с индексом j, что first[j].w <= first[i].w && first[j].c >= first[i].c)
 +
      удалим множество с индексом i из массива first
 +
 
 +
  for mask = 0 to 2 ** fn - 1
 +
    for j = 0 to fn
 +
      if j-ый бит mask = 1
 +
        curw += w[j + sn];
 +
        curcost += cost[j + sn];
 +
   
 +
    В массиве first бинарным поиском находим подмножество, с максимальным весом, который не превышает R - curw
 +
    if (first[index].w <= R - curw && first[index].c + curcost > ans)
 +
      ans = first[index].c + curcost
 +
  print ans
 +
 
 +
Итоговое время работы <tex> {O({2^{N/2}}\times({N}+\log{2^{N/2}}))} = O({2^{N/2}}\times{N}) </tex>.
 +
 
 +
== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
 +
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
 +
Еще одна задача, решаемая '''Meet-in-the-middle'''  —  это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает '''N'''.
 +
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть '''K''' переходов, тогда бы мы сгенерировали <tex> {K^{n}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{n}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{n/2}})} </tex>. <br>
 +
=== Алгоритм решения ===
 +
 
 +
1. Сгенерируем '''bfs'''-ом все состояния, доступные из начала и конца за <tex> {n/2} </tex> или меньше ходов.
 +
 
 +
2. Найдем состояний, которые достижимы из начала и из конца.
 +
 
 +
3. Найдем среди них наилучшее по сумме длин путей.
 +
 
 +
 
 +
Таким образом, '''bfs-ом''' из двух концов, мы сгенерируем максимум <tex> {O({K^{n/2}})} </tex> состояний.
 +
 
 +
== См. также ==
 +
* [[Обход в ширину]]
 +
 
 +
==Cсылки==
 +
*[http://infoarena.ro/blog/meet-in-the-middle Meet-in-the-middle]
 +
*[http://g6prog.narod.ru/dpl.ps Лекции по информатике(36 страница)]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Динамическое программирование ]]

Версия 04:55, 16 декабря 2012

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

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

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

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

Например : [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 + N)\log{N}}) = {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
 for a = 0 to N - 1
   for b = 0 to N - 1
     sum[cnt].s = A[a] + A[b];
     sum[cnt].a = a;
     sum[cnt++].b = b;
 sort(sum);
 
 for c = 0 to N - 1
   for d = 0 to N - 1
     if (сумма -(A[c] + A[d]) есть в массиве sum)
       ind = индекс суммы -(A[c] + A[d]) в массиве sum;
       print(sum[ind].a, sum[ind].b, A[c], A[d]);
       return;
 print("No solution");

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


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

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

Реализация

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


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

 // N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
 sn = N / 2, fn = N - sn;
 for mask = 0 to 2 ** sn - 1
   for j = 0 to sn
     if j-ый бит mask = 1
       first[i].w += w[j];
       first[i].c += cost[j];
 sort(first);
 for i = 0 to 2 ** sn - 1
   if (существует такое подмножество с индексом j, что first[j].w <= first[i].w && first[j].c >= first[i].c)
     удалим множество с индексом i из массива first
 
 for mask = 0 to 2 ** fn - 1
   for j = 0 to fn
     if j-ый бит mask = 1
       curw += w[j + sn];
       curcost += cost[j + sn];
   
   В массиве first бинарным поиском находим подмножество, с максимальным весом, который не превышает R - curw
   if (first[index].w <= R - curw && first[index].c + curcost > ans)
     ans = first[index].c + curcost
 print ans

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

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

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

Еще одна задача, решаемая Meet-in-the-middle — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает N. Стандартным подходом для решения данной задачи, является применение алгоритма обхода в ширину. Пусть из каждого состояния у нас есть K переходов, тогда бы мы сгенерировали [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сылки