Редактирование: Meet-in-the-middle

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|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> f({x}) = g({y}) </tex>, где <tex> x \in {X} </tex> и <tex> y \in {Y} </tex>, который работает за время <tex> O(F(X) + Y \cdot 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>.
 
'''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>.
Строка 16: Строка 16:
 
=== Реализация ===
 
=== Реализация ===
 
   <font color=darkgreen>// sum — массив сумм a + b, cnt — счетчик массива sum</font>
 
   <font color=darkgreen>// sum — массив сумм a + b, cnt — счетчик массива sum</font>
   '''function''' findsum('''int['''N''']''' A): String
+
   '''function''' findsum('''int[]''' A): String
 
     '''for''' a = 0..N - 1
 
     '''for''' a = 0..N - 1
 
       '''for''' b = 0..N - 1
 
       '''for''' b = 0..N - 1
Строка 35: Строка 35:
  
 
== Задача о рюкзаке ==
 
== Задача о рюкзаке ==
Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<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>.
+
Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<tex> {w_{i} \leqslant 10^{9}} </tex> ) и ценностью (<tex>{cost_{i} \leqslant 10^{9}} </tex>). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма <tex>O({2^{N/2}}\times{N})</tex>. Память <tex> O({2^{N/2}})</tex>.
  
 
=== Алгоритм ===
 
=== Алгоритм ===
Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве <tex>\mathtt{first}</tex>. Отсортируем массив <tex>\mathtt{first}</tex> по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять.
+
Разделим наше множество на две части. Подсчитаем все подмножества из первой части и будем хранить их в массиве <tex> first </tex>. Отсортируем массив <tex> first </tex> по весу. Далее пройдемся по этому массиву и оставим только те подмножества, для которых не существует другого подмножества с меньшим весом и большей стоимостью. Очевидно, что подмножества, для которых существует другое, более легкое и одновременно более ценное подмножество, можно удалять.
Таким образом в массиве <tex>\mathtt{first}</tex> мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нам подмножества из первой половины, хранящиеся в массиве <tex>\mathtt{first}</tex>.
+
Таким образом в массиве <tex> first </tex> мы имеем подмножества, отсортированные не только по весу, но и по стоимости. Тогда начнем перебирать все возможные комбинации вещей из второй половины и находить бинарным поиском удовлетворяющие нам подмножества из первой половины, хранящиеся в массиве <tex> first </tex>.
  
 
=== Реализация ===
 
=== Реализация ===
   <font color=darkgreen>// N — количество всех вещей, w[N] — массив весов всех вещей, cost[N] — массив стоимостей всех вещей, R — ограничение по весу рюкзака.</font>
+
   <font color=darkgreen>// N — количество всех вещей, w[] — массив весов всех вещей, cost[] — массив стоимостей всех вещей, R — ограничение по весу рюкзака.</font>
   '''function''' knapsack('''int['''N''']''' w, '''int['''N''']''' cost, '''int''' R): '''int'''
+
   '''function''' knapsack(): '''int'''
 
     sn = N / 2
 
     sn = N / 2
 
     fn = N - sn
 
     fn = N - sn
Строка 65: Строка 65:
 
     '''return''' ans
 
     '''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/2}}\times({N}+\log{2^{N/2}}))} = O({2^{N/2}}\times{N}) </tex>.
  
 
== Задача о количестве полных подграфов в графе ==
 
== Задача о количестве полных подграфов в графе ==
Строка 72: Строка 72:
 
19 × 3-вершинными кликами (светло-синие и тёмно-синие треугольники) и  
 
19 × 3-вершинными кликами (светло-синие и тёмно-синие треугольники) и  
 
2 × 4-вершинными кликами (тёмно-синие зоны). Всего 86 клик.]]
 
2 × 4-вершинными кликами (тёмно-синие зоны). Всего 86 клик.]]
Дан граф <tex>G</tex>, в котором <tex>N</tex> вершин. Требуется подсчитать количество [[Основные_определения_теории_графов#Часто используемые графы | клик]].
+
Дан граф <tex>G</tex>, в котором <tex>N</tex> вершин. Требуется подсчитать количество полных подграфов графа <tex>G</tex> (такие подграфы также называются '''кликами''' (англ. ''clique'')).
  
 
Наивное решение — перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность — <tex>O(2^N \times N^2)</tex>
 
Наивное решение — перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность — <tex>O(2^N \times N^2)</tex>
  
Этот алгоритм можно улучшить до <tex>O(2^N \times N)</tex>. Для этого нужно в функции перебора хранить маску вершин, которые мы ещё можем добавить. Поддерживая эту маску, можно добавлять только «нужные» вершины, и тогда не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно за <tex>O(1)</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</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>{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>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>{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^{\frac{N}{2}})</tex>.
+
Для каждой клики <tex>K</tex> (в том числе и пустой) графа <tex>{G}_1</tex> прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к <tex>K</tex> (В том числе и пустых). Асимптотика: <tex>O(2^{N/2})</tex>.
  
Итоговая сложность: <tex>O(2^{\frac{N}{2}} \times N)</tex>
+
Итоговая сложность: <tex>O(2^{N/2} \times N)</tex>
  
 
== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
 
== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
 
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
 
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
 
Еще одна задача, решаемая '''Meet-in-the-middle'''  —  это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает <tex> N </tex>.
 
Еще одна задача, решаемая '''Meet-in-the-middle'''  —  это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает <tex> N </tex>.
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть <tex> K </tex> переходов, тогда бы мы сгенерировали <tex> {K^{N}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{N}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{\frac{N}{2}}})} </tex>. <br>
+
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]] (англ. ''breadth-first search, BFS'')).. Пусть из каждого состояния у нас есть <tex> K </tex> переходов, тогда бы мы сгенерировали <tex> {K^{N}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{N}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{N/2}})} </tex>. <br>
 
=== Алгоритм решения ===  
 
=== Алгоритм решения ===  
  
1. Сгенерируем '''BFS'''-ом все состояния, доступные из начала и конца за <tex> {\dfrac{N}{2}} </tex> или меньше ходов.
+
1. Сгенерируем '''BFS'''-ом все состояния, доступные из начала и конца за <tex> {N/2} </tex> или меньше ходов.
  
 
2. Найдем состояния, которые достижимы из начала и из конца.
 
2. Найдем состояния, которые достижимы из начала и из конца.
Строка 103: Строка 103:
  
  
Таким образом, '''BFS-ом''' из двух концов, мы сгенерируем максимум <tex> {O({K^{\frac{N}{2}}})} </tex> состояний.
+
Таким образом, '''BFS-ом''' из двух концов, мы сгенерируем максимум <tex> {O({K^{N/2}})} </tex> состояний.
  
 
== См. также ==
 
== См. также ==
Строка 110: Строка 110:
  
 
==Источники информации==
 
==Источники информации==
*[http://infoarena.ro/blog/meet-in-the-middle infoarena.ro — Meet-in-the-middle]
+
*[http://infoarena.ro/blog/meet-in-the-middle Meet-in-the-middle]
*[http://g6prog.narod.ru/dpl.ps g6prog.narod.ru — Лекции по информатике (36 страница)]
+
*[http://g6prog.narod.ru/dpl.ps Лекции по информатике (36 страница)]
*[https://en.wikipedia.org/wiki/Clique_(graph_theory) wikipedia.org — Clique]
+
*[https://en.wikipedia.org/wiki/Clique_(graph_theory) Clique]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Динамическое программирование ]]
 
[[Категория: Динамическое программирование ]]
 
[[Категория: Классические задачи динамического программирования ]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: