Изменения

Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1. Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле. Этот алгоритм в худшем случае перебирает <tex>(n - 1)!</tex> путей, что даёт сложность работы <tex>O(n!)</tex>. Приведём алгоритм, основанный на динамическом программировании, который работает значительно быстрее. Алгоритм основан на следующей идее: будем для каждой пары из подмножества вершин и вершины считать, существует ли гамильтонов путь для этого подмножества вершин, заканчивающихся в выделенной вершине. Суммарно таких состояний будет <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 < n; i++): result[1 << i][i] = true; for (int i = 1; i < (1 << n); i++): if (count(i) == 1): continue for (int j = 0; j < n; j++): if ((1 << j) & i != 0): for (int k = 0; k < 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.