Что такое алгоритм динамического программирования для нахождения гамильтонова цикла в неориентированном графе?
Я где-то видел, что существует алгоритм с временной сложностью O(n.2^n).
Каков алгоритм динамического программирования для нахождения гамильтонова цикла в графе?
Ответ 1
В действительности существует алгоритм динамического программирования O (n2 n) для нахождения гамильтоновых циклов. Идея, которая является общей, которая может уменьшить многие подходы к обратному подходу O (n!) К O (n 2 2 n) или O (n2 n) (за счет использования большего объема памяти), заключается в рассмотрении подзадач, которые являются наборами с указанными "конечными точками".
Здесь, поскольку вам нужен цикл, вы можете начать с любой вершины. Поэтому исправьте его, назовите его x. Подзадачи были бы: "Для данного набора S и вершины v в S существует ли путь, начинающийся с x и проходящий через все вершины S, заканчивающиеся на v?" Назовите это, скажем, poss[S][v].
Как и при большинстве задач динамического программирования, как только вы определяете подзадачи, остальное очевидно: Loop над всеми 2 n устанавливает S вершин в любом "возрастающем" порядке и для каждого v в каждом такой S, вы можете вычислить poss[S][v] как:
poss [S] [v] = (существует такое
uв S, что poss [S & minus; {v}] [u] имеет значение True и существует реброu->v)
Наконец, существует гамильтонов цикл, если существует вершина v такая, что существует ребро v->x, а poss[S][v] - True, где S - множество всех вершин (кроме x, в зависимости от того, как вы его определили).
Если вы хотите, чтобы фактический цикл Гамильтона вместо того, чтобы просто решить, существует ли он или нет, сделайте poss[S][v] сохранить фактический u, который сделал возможным, а не только True или False; таким образом вы можете проследить путь в конце.
Ответ 2
Я не могу вырвать этот конкретный алгоритм, но есть больше о гамильтоновых циклах на Страница гамильтониана, чем вам, вероятно, когда-либо понадобится,:)
Эта страница намеревается быть полный перечень документов, исходный код, препринты, технические отчетов и т.д., доступных на Интернет о гамильтоновском цикле и проблемы гамильтоновых путей как некоторые связанные проблемы.