Каков алгоритм динамического программирования для нахождения гамильтонова цикла в графе?

Что такое алгоритм динамического программирования для поиска гамильтонова цикла в неориентированном графе? Я где-то видел, что существует алгоритм с временной сложностью O(n.2^n).


graph algorithm dynamic-programming cycle hamiltonian-cycle
person avd    schedule 07.09.2009    source источник

Ответы (2)


arrow_upward
35
arrow_downward

Действительно, существует O(n2n) алгоритм динамического программирования для нахождения гамильтоновых циклов. Идея, которая является общей, может сократить количество подходов обратного отслеживания O(n!) до O(n22n) или O(n2n< /sup>) (за счет использования большего объема памяти), заключается в рассмотрении подзадач, которые представляют собой наборы с указанными "конечными точками".

Здесь, поскольку вам нужен цикл, вы можете начать с любой вершины. Так что исправьте один, назовите его x. Подзадачи будут такими: «Для заданного множества S и вершины v в S существует ли путь, начинающийся в x и проходящий через все вершины S и заканчивающийся в v?» Назовите это, скажем, poss[S][v].

Как и в большинстве задач динамического программирования, как только вы определите подзадачи, остальное станет очевидным: выполните цикл по всем 2n множествам S вершин в любом «возрастающем» порядке, и для каждого v в каждом таком S, вы можете вычислить poss[S][v] как:

poss[S][v] = (существует некоторое u в S такое, что poss[S{v}][u] равно True и существует ребро u->v)

Наконец, существует гамильтонов цикл тогда и только тогда, когда существует вершина v такая, что существует ребро v->x и poss[S][v] истинно, где S — это множество всех вершин (кроме x, в зависимости от того, как вы его определили).

Если вам нужен фактический гамильтонов цикл, а не просто решать, существует ли он или нет, заставьте poss[S][v] сохранить фактический u, который сделал это возможным, а не только True или False; таким образом вы можете проследить путь в конце.

person ShreevatsaR    schedule 07.09.2009
comment
Под возрастающим порядком вы имеете в виду просто пройтись по числу 0, 1, 2,... или сначала пройтись по наборам размера 0, затем 1, затем 2, затем 3,...? - person mrk; 02.06.2014
comment
@staame Я имею в виду любой порядок, такой, что если A является подмножеством B, то A происходит перед B. Вы действительно можете сделать это, перебирая наборы по размеру, но вы также можете, например, просто перебрать их в порядке их побитового представления (т.е. пройтись по целым числам от 0 до 2^n и интерпретировать каждое как набор). - person ShreevatsaR; 02.06.2014
comment
Спасибо, так что это индукция по размеру графика. Если я правильно понял, то должно быть верно, что для любых двух чисел x,y. x ‹ y подразумевает, что x является подмножеством y при условии, что они пересекаются. - person mrk; 02.06.2014
comment
@staame: Не совсем так. Если X является подмножеством Y, то когда вы представляете X и Y в двоичном виде (стандартным способом, в виде растрового изображения) как x и y соответственно, вы получаете x ‹ y: потому что y содержит все биты x, плюс еще несколько битов, это большее число. Но два набора могут пересекаться, и ни один из них не является подмножеством другого, и всегда одно из соответствующих чисел растрового изображения будет меньше другого — но это ничего не значит. В качестве примера представим X={0,1,3,5,7} как x=10101011 и Y={0,1,2,3,5,7} как y=10101111 и Z={1,3, 6,7} по z=11001010. Тогда x‹y‹z, но X (или Y) не является подмножеством Z. - person ShreevatsaR; 03.06.2014

arrow_upward
2
arrow_downward

Я не могу выделить этот конкретный алгоритм, но есть больше о гамильтоновых циклах на Страница Гамильтона, чем вам, вероятно, когда-либо понадобится. :)

Эта страница представляет собой исчерпывающий список статей, исходного кода, препринтов, технических отчетов и т. д., доступных в Интернете, о гамильтоновом цикле и гамильтоновых путях, а также о некоторых связанных проблемах.

(исходный URL, в настоящее время 404), (Интернет-архив)

person JP Alioto    schedule 07.09.2009