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

Question

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

Answer 1

Действительно существует O(n2^н) алгоритм динамического программирования для поиска гамильтоновых циклов.Идея, которая является общей и может свести многие подходы с возвратом O(n!) к O(n²2^н) или O(n2^н) (за счет использования большего объема памяти) заключается в рассмотрении подзадач, которые наборы с указанными «конечными точками».

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

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

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

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

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

Answer 2

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

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

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