Изменения

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

Meet-in-the-middle

10 байт добавлено, 00:32, 2 января 2014
Багфикс оформления
Теперь надо узнать для каждой клики графа <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>.
21
правка

Навигация