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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм нахождения гамильтового пути)
Строка 167: Строка 167:
 
         '''continue'''
 
         '''continue'''
 
Длину пути можно узнать как path.size.
 
Длину пути можно узнать как path.size.
 +
 +
== Задача о коммивояжере ==
 +
 +
{{Задача
 +
|definition =
 +
'''Задача о коммивояжере''' (англ. ''Travelling salesman problem, TSP'') — задача, в которой коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
 +
}}
 +
 +
==== Варианты решения  ====
 +
 +
[[NP-полнота задач о гамильтоновом цикле и пути в графах]]
 +
 +
Так вот задача о коммивояжере относится к классу NP-полных задач. Поэтому, рассмотрим два варианта решения с экспоненциальным временем работы.
 +
 +
==== Перебор перестановок ====
 +
Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Сложность алгоритма  <tex>O({N!}\times{N})</tex>.
 +
 +
==== Динамическое программирование по подмножествам (по маскам) ====
 +
 +
Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.
 +
 +
Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам — дороги. Пусть в графе <tex> G=(V,E)</tex>  <tex> N </tex>
 +
вершин, пронумерованных от <tex>0</tex> до <tex>N-1</tex> и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> w(i,j)</tex>. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.
 +
 +
==== Оптимизация решения ====
 +
 +
Пусть <tex>dp[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^i \cdot ((i, j) \in E ? 1:0) </tex>.
 +
 +
Тогда динамика перепишется следующим образом: <br>
 +
<tex>
 +
d'[mask][i] = \left\{\begin{array}{llcl}
 +
2^i&;\ |mask| = 1,\ mask_i = 1\\
 +
\sum_{j \in [0..n-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>.
 +
 +
 +
== См. также ==
 +
 +
*[[Кратчайший путь в ациклическом графе]]
 +
*[[Задача о наибольшей общей подпоследовательности]]
 +
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Задача о рюкзаке]]
 +
*[[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
 +
  
 
==Источники информации==
 
==Источники информации==
Строка 172: Строка 237:
 
*Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
 
*Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
 
*[http://ru.wikipedia.org/wiki/Гамильтонов_граф Гамильтонов граф]
 
*[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
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 
[[Категория:Гамильтоновы графы]]
 
[[Категория:Гамильтоновы графы]]

Версия 20:47, 9 января 2016

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

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

Определение:
Гамильтоновым путём (англ. 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] гамильтонов.

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

Зафиксируем начальную вершину [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],то эти вершины еще не посещены).

  • Начальное состояние — когда находимся в 0-й вершине, ни одна вершина не посещена, а пройденный путь равен [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]|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 - 2 ** j) + w(i, j))
 return d[i][mask]
 
 for i = 0 .. n - 1
   for mask = 0 .. 2 ** n - 1
    d[i][mask] = [math]\infty[/math]
 d[0][0] = 0;
 ans = findCheapest(0, 2 ** n - 1)
 if ans == [math]\infty[/math]
   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.

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

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


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

NP-полнота задач о гамильтоновом цикле и пути в графах

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

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

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

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

Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе.

Смоделируем данную задачу при помощи графа. При этом вершинам будут соответствовать города, а ребрам — дороги. Пусть в графе [math] G=(V,E)[/math] [math] N [/math] вершин, пронумерованных от [math]0[/math] до [math]N-1[/math] и каждое ребро [math](i, j) \in E [/math] имеет некоторый вес [math] w(i,j)[/math]. Необходимо найти гамильтонов цикл, сумма весов по ребрам которого минимальна.

Оптимизация решения

Пусть [math]dp[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^i \cdot ((i, j) \in E ? 1:0) [/math].

Тогда динамика перепишется следующим образом:
[math] d'[mask][i] = \left\{\begin{array}{llcl} 2^i&;\ |mask| = 1,\ mask_i = 1\\ \sum_{j \in [0..n-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].


См. также


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

  • Романовский И. В. Дискретный анализ. СПб.: Невский Диалект; БХВ-Петербург, 2003. ISBN 5-7940-0114-3
  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4