Гамильтоновы графы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Поша)
м (rollbackEdits.php mass rollback)
 
(не показано 85 промежуточных версий 17 участников)
Строка 1: Строка 1:
 +
[[Файл:Hamiltonial.png|300px|thumb|right|Граф додекаэдра с выделенным циклом Гамильтона]]
 
==Основные определения==
 
==Основные определения==
 +
{{Определение
 +
|definition =
 +
'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, проходящий через каждую вершину графа ровно один раз.
 +
}}
  
 
{{Определение
 
{{Определение
 +
|id = defCycle
 
|definition =
 
|definition =
'''Гамильтоновым путём''' называется простой путь, приходящий через каждую вершину графа ровно один раз.
+
'''Гамильтоновым циклом''' (англ. ''Hamiltonian cycle'') называют замкнутый гамильтонов путь.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Гамильтоновым циклом''' называют замкнутый гамильтонов путь.
+
Граф называется '''полугамильтоновым''' (англ. ''Semihamiltonian graph''), если он содержит гамильтонов путь.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 +
|id = hamiltonian_graph
 
|definition =
 
|definition =
Граф называется '''гамильтоновым''', если он содержит гамильтонов цикл.
+
Граф называется '''гамильтоновым''' (англ. ''Hamiltonian graph''), если он содержит гамильтонов цикл.  
 
}}
 
}}
 +
 +
Очевидно, что любой гамильтонов граф также и полугамильтонов.
  
 
==Достаточные условия гамильтоновости графа==
 
==Достаточные условия гамильтоновости графа==
Строка 22: Строка 31:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если <tex>n \ge 3</tex> и <tex>deg\ v \ge n/2</tex>  для любой вершины <tex>v</tex> неориентированного графа  <tex>G</tex>, то  <tex>G</tex> - гамильтонов граф.
+
Если <tex>n \geqslant 3</tex> и <tex>\deg\ v \geqslant n/2</tex>  для любой вершины <tex>v</tex> неориентированного графа  <tex>G</tex>, то  <tex>G</tex> {{---}} гамильтонов граф.
 
}}
 
}}
 +
 
===[[Теорема Оре|Теорема Оре]]===
 
===[[Теорема Оре|Теорема Оре]]===
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если <tex>n \ge 3</tex> и <tex>deg\ u + deg\ v \ge n</tex>  для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа  <tex>G</tex>, то  <tex>G</tex> - гамильтонов граф.
+
Если <tex>n \geqslant 3</tex> и <tex>\deg\ u + \deg\ v \geqslant n</tex>  для любых двух различных несмежных вершин <tex>u</tex> и <tex>v</tex> неориентированного графа  <tex>G</tex>, то  <tex>G</tex> {{---}} гамильтонов граф.
 +
}}
 +
 
 +
===[[Теорема Поша|Теорема Поша]]===
 +
{{Теорема
 +
|about = Поша
 +
|statement = Пусть граф <tex> G </tex> имеет <tex>n \geqslant 3</tex> вершин и выполнены следующие два условия:
 +
 
 +
*для всякого <tex>k,\, 1 \leqslant k < (n-1)/2</tex>, число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>;
 +
*для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>,
 +
 
 +
тогда <tex> G </tex> {{---}} гамильтонов граф.
 
}}
 
}}
 
===[[Теорема_Редеи-Камиона|Теорема Редеи-Камиона]]===
 
===[[Теорема_Редеи-Камиона|Теорема Редеи-Камиона]]===
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Любой сильносвязный [[Турниры|турнир]] - гамильтонов.
+
Любой сильносвязный [[Турниры|турнир]] {{---}} гамильтонов.
 
}}
 
}}
  
===Теорема Гуйя-Ури===
+
===[[Теорема Гуйя-Ури]]===
  
 
{{Теорема
 
{{Теорема
 +
|about=
 +
Ghouila-Houri
 
|statement=
 
|statement=
Пусть G - сильносвязный ориентированный граф. <br>
+
Пусть <tex>G</tex> {{---}} сильносвязный ориентированный граф. <br>
 
<tex>
 
<tex>
  
 
\begin{matrix}
 
\begin{matrix}
     deg^+ v \geq n/2 \\
+
     \deg^+ v \geqslant n/2 \\
     deg^- v \geq n/2 \\
+
     \deg^- v \geqslant n/2 \\
  
  
 
\end{matrix} \Bigg\} \Rightarrow  
 
\end{matrix} \Bigg\} \Rightarrow  
  
</tex> G - гамильтонов.
+
</tex> <tex>G</tex> {{---}} гамильтонов.
 
}}
 
}}
 
 
  
 
===[[Теорема Хватала|Теорема Хватала]]===
 
===[[Теорема Хватала|Теорема Хватала]]===
Строка 60: Строка 81:
 
|statement=
 
|statement=
 
Пусть:
 
Пусть:
* <tex> G </tex> [[Отношение связности, компоненты связности|связный граф]],
+
* <tex> G </tex> {{---}} [[Отношение связности, компоненты связности|связный граф]],
* <tex> n = |VG| \geq 3 </tex> количество вершин,
+
* <tex> n = |VG| \geqslant 3 </tex> {{---}} количество вершин,
* <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex> его последовательность степеней.
+
* <tex> d_1 \leqslant  d_2 \leqslant  \ldots \leqslant  d_n </tex> {{---}} его последовательность степеней.
 
Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
 
Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
<center><tex> d_k \leq k < n/2 \rightarrow d_{n - k} \geq n - k, (*) </tex></center>
+
<center><tex> d_k \leqslant  k < n/2 \Rightarrow d_{n - k} \geqslant n - k, (*) </tex></center>
 
то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
 
то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
 
}}
 
}}
  
===Теорема Поша===
+
== Задача о коммивояжере ==
{{Теорема
+
 
|statement=
+
Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжёре.
Пусть граф G имеет <tex>n \geq 3</tex> вершин. Если для всякого <tex>k,\, 1 \leq k < (n-1)/2</tex> число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>, и для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>, то G - гамильтонов граф
+
 
 +
==== Описание задачи ====
 +
{{Задача
 +
|definition =  
 +
'''Задача о коммивояжере''' (англ. ''Travelling salesman problem, TSP'') — задача, в которой коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
 
}}
 
}}
  
==Алгорит нахождения гамильтового цикла==
+
==== Варианты решения  ====
Основан на [[Обход в глубину, цвета вершин|обходе в глубину]].
+
 
===Псевдокод===
+
Задача о коммивояжере относится к классу [[NP-полнота задач о гамильтоновом цикле и пути в графах | NP-полных задач]]. Рассмотрим два варианта решения с экспоненциальным временем работы.
search_cycle(0, 0, number_of_vertices);
+
 
  bool search_cycle(int v, int w, int d)
+
=====  Перебор перестановок =====
{
+
Можно решить задачу перебором всевозможных [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса | перестановок]]. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма <tex>O({N!}\times{N})</tex>.
    if(w == v)
+
 
      return (d == 0);
+
===== Динамическое программирование по подмножествам (по маскам) =====
    visited[v] = true;
+
 
    for (t <tex>\in</tex> Adj[v])
+
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.
      if(!visited[t])
+
Зафиксируем начальную вершину <tex>s</tex> и будем искать гамильтонов цикл наименьшей стоимости — путь от <tex>s</tex> до <tex>s</tex>, проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор <tex>s</tex> не имеет значения. Поэтому будем считать <tex>s = 0 </tex>.
          if(search_cycle(t, w, d - 1))
+
 
            return true;
+
Подмножества вершин будем кодировать битовыми векторами, обозначим <tex>mask_i</tex> значение <tex>i</tex>-ого бита в векторе <tex>mask</tex>.
    visited[v] = false;
 
    return false;
 
}
 
  
==Источники==
+
Обозначим <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> 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>d[mask][i]</tex> содержит булево значение — существует ли в подмножестве <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
 +
 
 +
Сама динамика будет такая: <br>
 +
<tex>
 +
d[mask][i] = \left\{\begin{array}{llcl}
 +
1&;\ |mask| = 1,\ mask_i = 1\\
 +
\bigvee_{mask[j]=1, (j, i) \in E}\limits d[mask \oplus 2^i][j] &;\ |mask| > 1,\ mask_i= 1 \\
 +
 0&;\ otherwise\\
 +
\end{array}\right.
 +
</tex>
 +
 
 +
Это решение требует <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^j \cdot ((i, j) \in E ? 1:0) </tex>.
 +
 
 +
Тогда динамика перепишется следующим образом: <br>
 +
<tex>
 +
d'[mask] = \left\{\begin{array}{llcl}
 +
mask &;\ |mask| = 1 \\
 +
\sum_{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.
 +
</tex>
 +
 
 +
Особое внимание следует уделить выражению <tex>d'[mask \oplus 2^i] \& M_i</tex> . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве <tex>mask</tex> без вершины <tex>i</tex>, а вторая — подмножество вершин, связанных с <tex>i</tex> ребром. Если эти множества пересекаются хотя бы по одной вершине (их <tex>\&</tex> не равен <tex>0</tex>), то, как нетрудно понять, в <tex>mask</tex> существует гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.
 +
 
 +
Окончательная проверка состоит в сравнении <tex>d'[2^n - 1]</tex> c <tex>0</tex>.
 +
 
 +
Это решение использует <tex>O(2^n)</tex> памяти и имеет асимптотику <tex>O(2^nn)</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 - <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)
 +
    '''return''' ans
 +
Дальше ищем сам цикл:
 +
  '''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'''
 +
 
 +
==== Алгоритм нахождения гамильтонова цикла ====
 +
Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла.
 +
В массиве  <tex>d[i][mask]</tex> мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает <tex> true</tex>, то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.
 +
 
 +
==== Алгоритм нахождения гамильтонова пути ====
 +
Алгоритм нахождения гамильтонова пути легко получить, используя алгоритм нахождения гамильтонова цикла. Нужно добавить в граф еще одну вершину и ребра от нее до всех остальных вершин и из всех остальных вершин до неё. И далее запустить алгоритм поиска цикла от новой вершины. В восстановлении пути учтем, что эта вершина лишняя, и не будем записывать её в путь.
 +
 
 +
== См. также ==
 +
 
 +
*[[Кратчайший путь в ациклическом графе]]
 +
*[[Задача о наибольшей общей подпоследовательности]]
 +
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Задача о рюкзаке]]
 +
*[[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 +
 
 +
==Источники информации==
 
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
 
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
 
*Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
 
*Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
 +
*[http://ru.wikipedia.org/wiki/Гамильтонов_граф Гамильтонов граф]
 +
*[http://ru.wikipedia.org/wiki/Задача_коммивояжёра Задача коммивояжера в русской википедии]
 +
*[http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden Задача коммивояжера в немецкой википедии]
 +
*''Романовский И. В.'' Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3
 +
*''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4
 +
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Обходы графов]]
 +
[[Категория:Гамильтоновы графы]]
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]
 +
[[Категория:Классические задачи динамического программирования]]

Текущая версия на 19:22, 4 сентября 2022

Граф додекаэдра с выделенным циклом Гамильтона

Основные определения

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


Определение:
Гамильтоновым циклом (англ. Hamiltonian cycle) называют замкнутый гамильтонов путь.


Определение:
Граф называется полугамильтоновым (англ. Semihamiltonian graph), если он содержит гамильтонов путь.


Определение:
Граф называется гамильтоновым (англ. Hamiltonian graph), если он содержит гамильтонов цикл.


Очевидно, что любой гамильтонов граф также и полугамильтонов.

Достаточные условия гамильтоновости графа

Теорема Дирака

Теорема:
Если [math]n \geqslant 3[/math] и [math]\deg\ v \geqslant n/2[/math] для любой вершины [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] — гамильтонов граф.

Теорема Оре

Теорема:
Если [math]n \geqslant 3[/math] и [math]\deg\ u + \deg\ v \geqslant n[/math] для любых двух различных несмежных вершин [math]u[/math] и [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] — гамильтонов граф.

Теорема Поша

Теорема (Поша):
Пусть граф [math] G [/math] имеет [math]n \geqslant 3[/math] вершин и выполнены следующие два условия:
  • для всякого [math]k,\, 1 \leqslant k \lt (n-1)/2[/math], число вершин со степенями, не превосходящими [math]k[/math], меньше чем [math]k[/math];
  • для нечетного [math]n[/math] число вершин степени [math](n-1)/2[/math] не превосходит [math](n-1)/2[/math],
тогда [math] G [/math] — гамильтонов граф.

Теорема Редеи-Камиона

Теорема:
Любой сильносвязный турнир — гамильтонов.

Теорема Гуйя-Ури

Теорема (Ghouila-Houri):
Пусть [math]G[/math] — сильносвязный ориентированный граф.
[math] \begin{matrix} \deg^+ v \geqslant n/2 \\ \deg^- v \geqslant n/2 \\ \end{matrix} \Bigg\} \Rightarrow [/math] [math]G[/math] — гамильтонов.

Теорема Хватала

Теорема (Хватал):
Пусть:
  • [math] G [/math]связный граф,
  • [math] n = |VG| \geqslant 3 [/math] — количество вершин,
  • [math] d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n [/math] — его последовательность степеней.

Тогда если [math] \forall k \in \mathbb N [/math] верна импликация:

[math] d_k \leqslant k \lt n/2 \Rightarrow d_{n - k} \geqslant n - k, (*) [/math]
то граф [math] G [/math] гамильтонов.

Задача о коммивояжере

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

Описание задачи

Задача:
Задача о коммивояжере (англ. Travelling salesman problem, TSP) — задача, в которой коммивояжер должен посетить [math] N [/math] городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?


Варианты решения

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

Перебор перестановок

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

Динамическое программирование по подмножествам (по маскам)

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

Подмножества вершин будем кодировать битовыми векторами, обозначим [math]mask_i[/math] значение [math]i[/math]-ого бита в векторе [math]mask[/math].

Обозначим [math]d[i][mask][/math] как наименьшую стоимость пути из вершины [math]i[/math] в вершину [math]0[/math], проходящую (не считая вершины [math]i[/math]) единожды по всем тем и только тем вершинам [math]j[/math], для которых [math]mask_j = 1[/math] (т.е. [math]d[i][mask][/math] уже найденный оптимальный путь от [math]i[/math]-ой вершины до [math]0[/math]-ой, проходящий через те вершины, где [math]mask_j=1[/math]. Если [math]mask_j=0[/math],то эти вершины еще не посещены).

Алгоритм поиска цикла будет выглядеть следующим образом:

  • Начальное состояние — когда находимся в [math]0[/math]-й вершине, ни одна вершина не посещена, а пройденный путь равен [math]0[/math] (т.е. [math]i = 0[/math] и [math]mask = 0[/math]).
  • Для остальных состояний ([math]i \ne 0[/math] или [math]mask \ne 0[/math]) перебираем все возможные переходы в [math]i[/math]-ую вершину из любой посещенной ранее и выбираем минимальный результат.
  • Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как [math]\infty[/math]).

Стоимостью минимального гамильтонова цикла в исходном графе будет значение [math] d[0][2^n-1][/math] — стоимость пути из [math]0[/math]-й вершины в [math]0[/math]-ю, при необходимости посетить все вершины. Данное решение требует [math]O({2^n}\times{n})[/math] памяти и [math]O({2^n}\times{n^2})[/math] времени.

Для того, чтобы восстановить сам путь, воспользуемся соотношением [math] d[i][mask] = w(i, j) + d[j][mask - 2^j] [/math], которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния [math] i = 0 [/math], [math] mask = 2^n - 1[/math], найдем вершину [math]j[/math], для которой выполняется указанное соотношение, добавим [math]j[/math] в ответ, пересчитаем текущее состояние как [math]i = j[/math], [math] mask = mask - 2^j [/math]. Процесс заканчивается в состоянии [math]i = 0[/math], [math] mask = 0 [/math].

Поиск любого гамильтонова пути методом динамического программирования

Пусть [math]d[mask][i][/math] содержит булево значение — существует ли в подмножестве [math]mask[/math] гамильтонов путь, заканчивающийся в вершине [math]i[/math].

Сама динамика будет такая:
[math] d[mask][i] = \left\{\begin{array}{llcl} 1&;\ |mask| = 1,\ mask_i = 1\\ \bigvee_{mask[j]=1, (j, i) \in E}\limits d[mask \oplus 2^i][j] &;\ |mask| \gt  1,\ mask_i= 1 \\  0&;\ otherwise\\ \end{array}\right. [/math]

Это решение требует [math]O(2^nn)[/math] памяти и [math]O(2^nn^2)[/math] времени. Эту оценку можно улучшить, если изменить динамику следующим образом.

Пусть теперь [math]d'[mask][/math] хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве [math]mask[/math], заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: [math]d'[mask][/math] будет равно [math]\sum_{i \in [0..n-1]}\limits d[mask][i] \cdot 2 ^i [/math]. Для графа [math]G[/math] выпишем [math]n[/math] масок [math]M_i[/math], для каждой вершины задающие множество вершин, которые связаны ребром с данной вершиной. То есть [math]M_i = \sum_{j \in [0..n-1]}\limits 2^j \cdot ((i, j) \in E ? 1:0) [/math].

Тогда динамика перепишется следующим образом:
[math] d'[mask] = \left\{\begin{array}{llcl} mask &;\ |mask| = 1 \\ \sum_{i \in [0..n-1] \& mask_i=1}\limits 2^i \cdot ((d'[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| \gt  1 \\  0&;\ otherwise\\ \end{array}\right. [/math]

Особое внимание следует уделить выражению [math]d'[mask \oplus 2^i] \& M_i[/math] . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве [math]mask[/math] без вершины [math]i[/math], а вторая — подмножество вершин, связанных с [math]i[/math] ребром. Если эти множества пересекаются хотя бы по одной вершине (их [math]\&[/math] не равен [math]0[/math]), то, как нетрудно понять, в [math]mask[/math] существует гамильтонов путь, заканчивающийся в вершине [math]i[/math].

Окончательная проверка состоит в сравнении [math]d'[2^n - 1][/math] c [math]0[/math].

Это решение использует [math]O(2^n)[/math] памяти и имеет асимптотику [math]O(2^nn)[/math].

Псевдокод

Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за [math]|mask|[/math] количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния [math]\langle i, mask \rangle[/math] мы смотрим на состояния

[math]\langle j, mask - 2^j \rangle[/math], и [math]|mask| = |mask - 2^j| + 1[/math], то состояния с большим [math]|mask|[/math] должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта. Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).

 // все переменные используются из описания алгоритма, [math]\infty[/math] = бесконечность
 function findCheapest(i, mask):
   if d[i][mask] != [math]\infty[/math] 
     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 - [math]2^j[/math]) + w(i, j))
 return d[i][mask]
 
 function start():
   for i = 0 .. n - 1
     for mask = 0 .. [math]2^n[/math] - 1
      d[i][mask] = [math]\infty[/math]
   d[0][0] = 0
   ans = findCheapest(0, [math]2^n[/math] - 1)
   return ans

Дальше ищем сам цикл:

 function findWay():
   i = 0
   mask = [math]2^n[/math] - 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 - [math]2^j[/math]] + w(i, j) 
         path.push(j)
         i = j
         mask = mask - [math]2^j[/math]
         continue

Алгоритм нахождения гамильтонова цикла

Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла. В массиве [math]d[i][mask][/math] мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает [math] true[/math], то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.

Алгоритм нахождения гамильтонова пути

Алгоритм нахождения гамильтонова пути легко получить, используя алгоритм нахождения гамильтонова цикла. Нужно добавить в граф еще одну вершину и ребра от нее до всех остальных вершин и из всех остальных вершин до неё. И далее запустить алгоритм поиска цикла от новой вершины. В восстановлении пути учтем, что эта вершина лишняя, и не будем записывать её в путь.

См. также

Источники информации

  • Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
  • Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
  • Гамильтонов граф
  • Задача коммивояжера в русской википедии
  • Задача коммивояжера в немецкой википедии
  • Романовский И. В. Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3
  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4