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

Question

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

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

К сожалению, объяснения этого здесь, в стеке и по всей сети, очень мало. Я могу определить 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}.

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

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

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

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

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

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

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