84
правки
Изменения
Нет описания правки
Итоговое время работы <tex> {O({2^{N/2}}\cdot({N}+\log{2^{N/2}}))} = O({2^{N/2}}\cdot{N}) </tex>.
== Задача о количестве полных подграфов в графе ==
[[Файл:cliques.png|450px|thumb|right|Граф с 23 × 1-вершинными кликами (сами вершины),
42 × 2-вершинными кликами (отрезки),
19 × 3-вершинными кликами (светло-синие и тёмно-синие треугольники) и
2 × 4-вершинными кликами (тёмно-синие зоны). Всего 86 клик.]]
Дан граф <tex>G</tex>, в котором <tex>N</tex> вершин. Требуется подсчитать количество полных подграфов графа <tex>G</tex> (такие подграфы также называются '''кликами''' (англ. ''clique'')).
Наивное решение - перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность - <tex>O(2^N \times N^2)</tex>
Этот алгоритм можно улучшить до <tex>O(2^N \times N)</tex>. Для этого нужно в функции перебора хранить маску вершин, которые мы ещё можем добавить. Поддерживая эту маску, можно добавлять только «нужные» вершины, и тогда не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно за <tex>O(1)</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>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>.
Итоговая сложность: <tex>O(2^{N/2} \times N)</tex>
== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
Еще одна задача, решаемая '''Meet-in-the-middle''' — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает <tex> N </tex>.
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]](англ. ''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. Сгенерируем '''bfsBFS'''-ом все состояния, доступные из начала и конца за <tex> {N/2} </tex> или меньше ходов.
2. Найдем состояния, которые достижимы из начала и из конца.
Таким образом, '''bfsBFS-ом''' из двух концов, мы сгенерируем максимум <tex> {O({K^{N/2}})} </tex> состояний.
== См. также ==
*[http://infoarena.ro/blog/meet-in-the-middle Meet-in-the-middle]
*[http://g6prog.narod.ru/dpl.ps Лекции по информатике (36 страница)]
*[https://en.wikipedia.org/wiki/Clique_(graph_theory) Clique]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование ]]
