Изменения

'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, приходящий проходящий через каждую вершину графа ровно один раз.

Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости — путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>s = 0 </tex>. Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>. Обозначим <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>,то эти вершины еще не посещены). *Начальное состояние — когда находимся в 0-й вершине, ни одна вершина не посещена, а пройденный путь равен <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[0][2^n-1]</tex> — стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</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>|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">//Все переменные используются из описания алгоритма, <tex>\infty</tex> = бесконечность</span> '''function''' findCheapest(i, mask): '''if''' d[i][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>\infty</tex> exitДальше ищем сам цикл: i = 0 mask = 2 ** n - 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 - 2 ** j] + w(i, j) path.push(j) i = j mask = mask - 2 ** j '''continue''' ==Алгоритм нахождения гамильтового пути==Алгоритм нахождения гамильтонова пути легко получить слегка изменив алгоритм нахождения гамильтонова цикла.  '''bool''' findPath(i, mask): '''if''' d[i][mask] '''return''' true '''for''' j = 0 .. n - 1 '''if''' w(i, j) существует '''and''' j-ый бит mask == 1 '''if''' findPath(j, mask - 2 ** j) d[i][mask] = true '''return''' d[i][mask] '''for''' i = 0 .. n - 1 '''for''' mask = 0 .. 2 ** n - 1 d[i][mask] = false d[0][0] = true; ans = findPath(0, 2 ** n - 1) '''if''' ans == false exitДальше ищем сам путь: i = 0 mask = 2 ** n - 1 '''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] == true path.push(j) i коммивояжере = j mask = mask - 2 ** j '''continue'''Длину пути можно узнать как path.size.

== Задача Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжере ==коммивояжёре.

Задача о коммивояжере относится к классу [[NP-полнота задач о гамильтоновом цикле и пути в графах| NP-полных задач]]. Рассмотрим два варианта решения с экспоненциальным временем работы.

Так вот задача о коммивояжере относится к классу NP===== Перебор перестановок =====Можно решить задачу перебором всевозможных [[Метод генерации случайной перестановки, алгоритм Фишера-полных задачЙетса | перестановок]]. ПоэтомуДля этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, рассмотрим два варианта решения с экспоненциальным временем работыподсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.

==== Перебор перестановок = Динамическое программирование по подмножествам (по маскам) =====Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.

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

Задача о коммивояжере представляет собой поиск кратчайшего Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>. Обозначим <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[0][2^n-1]</tex> — стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. Данное решение требует <tex>O({2^n}\times{n})</tex> памяти и <tex>O({2^n}\times{n^2})</tex> времени.

Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать городаДля того, чтобы восстановить сам путь, а ребрам — дороги. Пусть в графе воспользуемся соотношением <tex> Gd[i][mask] =w(Vi,Ej)+ d[j][mask - 2^j] </tex> , которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния <tex> N i = 0 </tex>вершин, пронумерованных от <tex>0mask = 2^n - 1</tex> до , найдем вершину <tex>N-1j</tex> и каждое ребро , для которой выполняется указанное соотношение, добавим <tex>(i, j) \in E </tex> имеет некоторый вес в ответ, пересчитаем текущее состояние как <tex> w(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>.

Пусть теперь <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>.

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 \\

[[Категория: Обходы графов]]