84
правки
Изменения
→Алгоритм решения
Для одной клики <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>K</tex> (в том числе и пустой) графа <tex>{G}_1</tex> прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к <tex>K</tex> (В том числе и пустых). Асимптотика: <tex>O(2^{N/2})</tex>.
Итоговая сложность: <tex>O(2^{\frac{N/}{2}} \times N)</tex>
== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
