Изменения

Приведём два алгоритма поиска гамильтонова циклаЗафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости — путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>s = 0 </tex>.

'''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 '''to''' g.vertices '''if''' (!used[i] && (vert; обозначим <tex>mask_i</tex> значение <tex>i) '''in''' g</tex>-ого бита в векторе <tex>mask</tex>.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>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>d[i][mask]</tex> уже найденный оптимальный путь от <tex>i</tex>-ой вершины до <tex>0</tex>--}} отметки о посещении* vert {{---}} текущая вершина* count {{---}} количество посещённых вершин ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены).

Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины *Начальное состояние — когда находимся в ещё 0-й вершине, ни одна вершина не посещённыепосещена, а пройденный путь равен <tex>0</tex> (т.е. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером <tex>i = 0 </tex> и параметром <tex>count mask = 10</tex>). Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле. Этот алгоритм *Для остальных состояний (<tex>i \ne 0</tex> или <tex>mask \ne 0</tex>) перебираем все возможные переходы в худшем случае перебирает <tex>(n - 1)!i</tex> путей-ую вершину из любой посещенной ранее и выбираем минимальный результат.*Если возможные переходы отсутствуют, что даёт сложность работы решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>O(n!)\infty</tex>).

Приведём алгоритм, основанный на динамическом программировании, который работает значительно быстрее. Алгоритм основан на следующей идее: будем для каждой пары из подмножества вершин и вершины считать, существует ли гамильтонов путь для этого подмножества вершин, заканчивающихся Стоимостью минимального гамильтонова цикла в выделенной вершине. Суммарно таких состояний исходном графе будет значение <tex>O(n2d[0][2^n)-1]</tex> — стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, для обсчёта каждого из них требуется при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> времени, то есть, суммарно алгоритм работает за памяти и <tex>O({2^n}\times{n^22^n2})</tex> времени. Псевдокод, реализующий этот алгоритм, приведён ниже:

'''bool'''Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] get_dp_table= w(graph gi, j): '''int''' n = g.vertices '''bool'''+ d[j][mask - 2^j] result = new int[1 </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния < n][n] '''for''' tex> i = 0 '''to''' n '''result'''[1 </tex>, < i][i] tex> mask = (0; i) '''in''' g.edges; '''for''' i = 1 '''to''' 2^n - 1 </tex>, найдем вершину < n '''if''' (count(i) == 1) '''continue''' '''for''' tex>j = 0 '''to''' n '''if''' ((1 </tex>, для которой выполняется указанное соотношение, добавим < tex>j) & </tex> в ответ, пересчитаем текущее состояние как <tex>i != 0) '''for''' k = 0 '''to''' n '''if''' (k !j</tex>, <tex> mask = mask - 2^j && (1 </tex>. Процесс заканчивается в состоянии < k) & tex>i != 0) result[i][j] </tex>, <tex> mask = result[(1 0 << j) ^ i][k] && (k; j) '''in''' g/tex>.edges '''return''' result

В приведённом выше коде считаемПрежде чем писать код, что n меньше количества бит в числовом типе данных, для операций над множествами используются побитовые логические операции в синтаксисе языка Cскажем пару слов о порядке обхода состояний. Функция count считает Обозначим за <tex>|mask|</tex> количество единичных бит единиц в числе маске (она проста в реализациииначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния <tex>\langle i, mask \rangle</tex> мы смотрим на состояния <tex>\langle j, mask - 2^j \rangle</tex>, и <tex>|mask| = |mask - 2^j| + 1</tex>, то состояния с большим <tex>|mask|</tex> должны быть посещены позже, но не относится чтобы к алгоритмамоменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта. Однако если использовать рекурсию, поэтому об этом можно не приводитсябеспокоиться (и сэкономить немало кода, времени и памяти). Граф гамильтонов тогда  <span style="color:Green">//Все переменные используются из описания алгоритма, когда dp<tex>\infty</tex> = бесконечность</span> '''function''' findCheapest(i, mask): '''if''' d[i][(1 mask] != <tex>\infty< /tex> '''return''' d[i][mask] '''for''' j = 0 .. n- 1 '''if''' w(i, j) существует '''and''' j- ый бит mask == 1 d[i][mask] = '''min'''(d[i] && [mask], findCheapest(j, mask - 2 ** j) + w(i, j)) '''return''' d[i][mask] '''for''' i= 0 .. n - 1 '''for''' mask = 0 .. 2 ** n - 1 d[i][mask] = <tex>\infty</tex> d[0][0] = 0; ans = findCheapest(0, 2 ** n - 1) '''if''' ans == <tex>\ininfty</tex> g exitДальше ищем сам путь: i = 0 mask = 2 ** n - 1 path.edges для некоторого push(0) '''while''' mask != 0 '''for''' j = 0 .. n - 1 '''if''' w(i, j) существует '''and''' j-ый бит mask == 1 '''and''' d[i][mask] == d[j][mask - 2 ** j] + w(i, j) path.push(j) i = j mask = mask - 2 ** j '''continue'''