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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгорит нахождения гамильтового цикла)
(Исправление опечаток)
 
(не показаны 74 промежуточные версии 11 участников)
Строка 1: Строка 1:
[[Файл:450px-Hamiltonian Dodecahedron Graph.svg.png|250px|thumb|right|Граф додекаэдра с выделенным циклом Гамильтона]]
+
[[Файл:Hamiltonial.png|300px|thumb|right|Граф додекаэдра с выделенным циклом Гамильтона]]
 
==Основные определения==
 
==Основные определения==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Гамильтоновым путём''' называется простой путь, приходящий через каждую вершину графа ровно один раз.
+
'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, проходящий через каждую вершину графа ровно один раз.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 +
|id = defCycle
 
|definition =
 
|definition =
'''Гамильтоновым циклом''' называют замкнутый гамильтонов путь.
+
'''Гамильтоновым циклом''' (англ. ''Hamiltonian cycle'') называют замкнутый гамильтонов путь.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Граф называется '''полугамильтоновым''', если он содержит гамильтонов путь.
+
Граф называется '''полугамильтоновым''' (англ. ''Semihamiltonian graph''), если он содержит гамильтонов путь.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 +
|id = hamiltonian_graph
 
|definition =
 
|definition =
Граф называется '''гамильтоновым''', если он содержит гамильтонов цикл.  
+
Граф называется '''гамильтоновым''' (англ. ''Hamiltonian graph''), если он содержит гамильтонов цикл.  
 
}}
 
}}
  
Строка 29: Строка 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> {{---}} гамильтонов.
 
}}
 
}}
 
 
  
 
===[[Теорема Хватала|Теорема Хватала]]===
 
===[[Теорема Хватала|Теорема Хватала]]===
Строка 67: Строка 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-полных задач]]. Рассмотрим два варианта решения с экспоненциальным временем работы.
 +
 
 +
=====  Перебор перестановок =====
 +
Можно решить задачу перебором всевозможных [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса | перестановок]]. Для этого нужно сгенерировать все <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> 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>, то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.
  
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; i < g.vertices; i++):
 
    if (!used[i] && (vert; i) in g.edges):
 
      used[i] = true
 
      next[vert] = i
 
      if (check_hamiltonian(g, used, i, count + 1, next)):
 
        return true
 
      used[i] = false
 
  return false
 
  
* used — отметки о посещении
+
== См. также ==
* vert — текущая вершина
 
* count — количество посещённых вершин
 
  
Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром count = 1. Если процедура возвращает true, то в массиве next будет храниться следующая вершина на гамильтоновом цикле.
+
*[[Кратчайший путь в ациклическом графе]]
 +
*[[Задача о наибольшей общей подпоследовательности]]
 +
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Задача о рюкзаке]]
 +
*[[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]]
  
==Источники==
+
==Источники информации==
 
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
 
*Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.
 
*Седжвик Р. Фундаментальные алгоритмы на 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
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
+
[[Категория:Обходы графов]]
 +
[[Категория:Гамильтоновы графы]]
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]
 +
[[Категория:Классические задачи динамического программирования]]

Текущая версия на 14:28, 31 января 2019

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

Основные определения[править]

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