Изменения
→Алгоритм нахождения гамильтового цикла
Приведём два алгоритма поиска гамильтонова цикла.
'''bool ''' check_hamiltonian(graph g, '''bool'''[] used, '''int ''' vert, '''int ''' count, '''int'''[] next): '''if ''' (count == g.vertices):
next[vert] = 0
'''return ''' (vert; 0) '''in ''' g.edges '''for (''' i = 0; i < '''to''' g.vertices; i++): '''if ''' (!used[i] && (vert; i) in g.edges):
used[i] = true
next[vert] = i
'''if ''' (check_hamiltonian(g, used, i, count + 1, next)): '''return ''' true
used[i] = false
'''return ''' false
* used — отметки о посещении
Приведём алгоритм, основанный на динамическом программировании, который работает значительно быстрее. Алгоритм основан на следующей идее: будем для каждой пары из подмножества вершин и вершины считать, существует ли гамильтонов путь для этого подмножества вершин, заканчивающихся в выделенной вершине. Суммарно таких состояний будет <tex>O(n2^n)</tex>, для обсчёта каждого из них требуется <tex>O(n)</tex> времени, то есть, суммарно алгоритм работает за <tex>O(n^22^n)</tex> времени. Псевдокод, реализующий этот алгоритм, приведён ниже:
'''bool'''[][] get_dp_table(graph g): '''int ''' n = g.vertices '''bool'''[][] result = new int[1 << n][n]; '''for (int ''' i = 0; i < '''to''' n; i++): '''result'''[1 << i][i] = (0; i) '''in ''' g.edges; '''for (int ''' i = 1; i < ('''to''' 1 << n); i++): '''if ''' (count(i) == 1): '''continue''' '''for (int ''' j = 0; j < '''to''' n; j++): '''if ''' ((1 << j) & i != 0): '''for (int ''' k = 0; k < '''to''' n; k++): '''if ''' (k != j && (1 << k) & i != 0): result[i][j] = result[(1 << j) ^ i][k] && (k; j) '''in ''' g.edges '''return ''' result
В приведённом выше коде считаем, что n меньше количества бит в числовом типе данных, для операций над множествами используются побитовые логические операции в синтаксисе языка C. Функция count считает количество единичных бит в числе (она проста в реализации, но не относится к алгоритма, поэтому не приводится). Граф гамильтонов тогда, когда dp[(1 << n) - 1][i] && (i; 0) <tex>\in</tex> g.edges для некоторого i.
