Изменения
В этом разделе ничего не оптимизируется: выше находили самый дешевый гам. цикл, а здесь находим любой гам. путь, то есть другая задача.
{{Определение
|definition =
'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, приходящий проходящий через каждую вершину графа ровно один раз.
}}
{{Определение
|id = defCycle
|definition =
'''Гамильтоновым циклом''' (англ. ''Hamiltonian cycle'') называют замкнутый гамильтонов путь.
Обозначим <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>-ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены).
Алгоритм поиска цикла будет выглядеть следующим образом: *Начальное состояние — когда находимся в <tex>0</tex>-й вершине, ни одна вершина не посещена, а пройденный путь равен <tex>0</tex> (т.е. <tex>i = 0</tex> и <tex>mask = 0</tex>).
*Для остальных состояний (<tex>i \ne 0</tex> или <tex>mask \ne 0</tex>) перебираем все возможные переходы в <tex>i</tex>-ую вершину из любой посещенной ранее и выбираем минимальный результат.
*Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).
Для того, чтобы восстановить сам путь, воспользуемся соотношением <tex> d[i][mask] = w(i, j) + d[j][mask - 2^j] </tex>, которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> i = 0 </tex>, <tex> mask = 2^n - 1</tex>, найдем вершину <tex>j</tex>, для которой выполняется указанное соотношение, добавим <tex>j</tex> в ответ, пересчитаем текущее состояние как <tex>i = j</tex>, <tex> mask = mask - 2^j </tex>. Процесс заканчивается в состоянии <tex>i = 0</tex>, <tex> mask = 0 </tex>.
===== Оптимизация решения Поиск любого гамильтонова пути методом динамического программирования =====
Пусть <tex>dpd[mask][i]</tex> содержит булево значение — существует ли в подмножества подмножестве <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
Сама динамика будет такая: <br>
Это решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</tex> времени. Эту оценку можно улучшить, если изменить динамику следующим образом.
Пусть теперь <tex>d'[mask]</tex> хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве <tex>mask</tex>, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: <tex>d'[mask]</tex> будет равно <tex>\sum_{i \in [0..n-1]}\limits d[mask][i] \cdot 2 ^i </tex>. Для графа <tex>G</tex> выпишем <tex>n</tex> масок <tex>M_i</tex>, для каждой вершины задающие множество вершин, которые связаны ребром в с данной вершиной. То есть <tex>M_i = \sum_{j \in [0..n-1]}\limits 2^i j \cdot ((i, j) \in E ? 1:0) </tex>.
Тогда динамика перепишется следующим образом: <br>
<tex>
d'[mask][i] = \left\{\begin{array}{llcl}2^imask &;\ |mask| = 1,\ mask_i = 1\\\sum_{j i \in [0..n-1]\& mask_i=1}\limits 2^i \cdot ((d[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| > 1 \\
0&;\ otherwise\\
\end{array}\right.
Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).
<span style="color:Green">//Все все переменные используются из описания алгоритма, <tex>\infty</tex> = бесконечность</span>
'''function''' findCheapest(i, mask):
'''if''' d[i][mask] != <tex>\infty</tex>
'''for''' j = 0 .. n - 1
'''if''' w(i, j) существует '''and''' j-ый бит mask == 1
d[i][mask] = '''min'''(d[i][mask], findCheapest(j, mask - <tex>2 ** ^j</tex>) + w(i, j))
'''return''' d[i][mask]
'''function''' start(): '''for''' i = 0 .. n - 1 '''for''' mask = 0 .. <tex>2 ** ^n </tex> - 1 d[i][mask] = <tex>\infty</tex> d[0][0] = 0 ans = findCheapest(0, <tex>2 ** ^n </tex> - 1) '''ifreturn''' ans == <tex>\infty</tex> exit
Дальше ищем сам цикл:
'''function''' findWay(): i = 0 mask = <tex>2 ** ^n </tex> - 1 path.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 - <tex>2 ** ^j</tex>] + w(i, j) path.push(j) i = j mask = mask - <tex>2 ** ^j</tex> '''continue'''
==== Алгоритм нахождения гамильтонова цикла ====
==== Алгоритм нахождения гамильтонова пути ====
Алгоритм нахождения гамильтонова пути легко получить слегка изменив , используя алгоритм нахождения гамильтонова цикла. Чтобы найти путь, мы запускаем наш Нужно добавить в граф еще одну вершину и ребра от нее до всех остальных вершин и из всех остальных вершин до неё. И далее запустить алгоритм поочередно из каждой поиска цикла от новой вершины графа. В восстановлении пути учтем, что эта вершина лишняя, и не будем записывать её в путь.
== См. также ==
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Классические задачи динамического программирования]]
