GCJ - гамильтоновы циклы

Question

Проблема с застреванием кода заключается в следующем:

Вам дан полный ненаправленный граф с N узлами и K "запрещенными" ребрами. N <= 300, K <= 15. Найти число гамильтоновых циклов в графе, которые не используют ни одного из K "запрещенных" ребер.

К сожалению, объяснения этого здесь, в стеке и по всей сети, очень мало. Я могу выяснить HamCycles для определенного 'n': (n-1)! / 2 .

И я могу сделать короткий набор с динамическим программированием.

Но я не получаю всю болонью подмножества, как сделать это O^K? Я на Python, и мне еще предстоит расшифровать C++. В конце концов я уверен, что потрачу время на изучение C++, а затем расшифрую его. Но в то же время, почему кто-то не может объяснить это лучше где-нибудь в Интернете? Они всегда наполовину объяснения.

Answer 1

Может помочь, если вы укажете на отсутствующие объяснения, но я все равно попробую...

Решение на основе O (2^k) использует принцип исключения включения. Учитывая, что существует k запрещенных ребер, существует 2^k подмножеств этих ребер, включая сам набор и пустой набор. Например, если бы было 3 запрещенных ребра: {A, B, C}, было бы 2³= 8 подмножеств: {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}.

Для каждого поднабора вы рассчитываете количество циклов, которые включают в себя по крайней мере все ребра в этом подмножестве. Если число циклов, содержащих ребра s, равно f(s), а S - множество всех запрещенных ребер, то по принципу включения-исключения число циклов без каких-либо запрещенных ребер равно:

 sum, for each subset s of S: f(s) * (-1)^|s|

где |с| количество элементов в с. Другими словами, сумма количества циклов с любыми ребрами минус количество циклов с хотя бы одним запрещенным ребром плюс число с хотя бы двумя запрещенными ребрами...

Вычисление f(s) не тривиально - по крайней мере, я не нашел простой способ сделать это. Вы можете остановиться и обдумать это, прежде чем читать дальше.

Чтобы вычислить f(s), начните с количества перестановок узлов, не связанных ни с какими s узлами. Если есть m таких узлов, есть m! перестановки, как вы знаете. Назовите количество перестановок c.

Теперь рассмотрим ребра в s для цепочек. Если есть какие-либо невозможные комбинации, такие как узел с 3 ребрами или подцикл в пределах s, то f(s) равно 0.

В противном случае для каждой цепочки увеличьте m на 1 и умножьте c на 2m. (Существует m мест для размещения цепочки в существующих перестановках, и коэффициент 2 объясняется тем, что цепочка может быть вперед или назад.) Наконец, f(s) равно c/ (2m). Последнее деление преобразует перестановки в циклы.