Редактирование: Гамильтоновы графы

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, проходящий через каждую вершину графа ровно один раз.
+
'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, приходящий через каждую вершину графа ровно один раз.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
|id = defCycle
 
 
|definition =
 
|definition =
 
'''Гамильтоновым циклом''' (англ. ''Hamiltonian cycle'') называют замкнутый гамильтонов путь.
 
'''Гамильтоновым циклом''' (англ. ''Hamiltonian cycle'') называют замкнутый гамильтонов путь.
Строка 100: Строка 99:
 
}}
 
}}
  
==== Варианты решения  ====
+
==== Варианты решения: ====
  
Задача о коммивояжере относится к классу [[NP-полнота задач о гамильтоновом цикле и пути в графах | NP-полных задач]]. Рассмотрим два варианта решения с экспоненциальным временем работы.
+
[[NP-полнота задач о гамильтоновом цикле и пути в графах]]
 +
 
 +
Задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения с экспоненциальным временем работы.
  
 
=====  Перебор перестановок =====
 
=====  Перебор перестановок =====
Строка 116: Строка 117:
 
Обозначим <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>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>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>i \ne 0</tex> или <tex>mask \ne 0</tex>) перебираем все возможные переходы в <tex>i</tex>-ую вершину из любой посещенной ранее и выбираем минимальный результат.
 
*Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).
 
*Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как <tex>\infty</tex>).
Строка 126: Строка 125:
 
Для того, чтобы восстановить сам путь, воспользуемся соотношением <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[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>.  
+
Пусть <tex>dp[mask][i]</tex> содержит булево значение — существует ли в подмножества <tex>mask</tex> гамильтонов путь, заканчивающийся в вершине <tex>i</tex>.  
  
 
Сама динамика будет такая: <br>
 
Сама динамика будет такая: <br>
Строка 141: Строка 140:
 
Это решение требует <tex>O(2^nn)</tex> памяти и <tex>O(2^nn^2)</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>.
+
Пусть теперь <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>
 
Тогда динамика перепишется следующим образом: <br>
 
<tex>
 
<tex>
d'[mask] = \left\{\begin{array}{llcl}
+
d'[mask][i] = \left\{\begin{array}{llcl}
mask &;\ |mask| = 1 \\
+
2^i&;\ |mask| = 1,\ mask_i = 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 \\
+
\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\\
 
 0&;\ otherwise\\
 
\end{array}\right.
 
\end{array}\right.
Строка 165: Строка 164:
 
Однако если использовать рекурсию, об этом можно не беспокоиться  (и сэкономить немало кода, времени и памяти).
 
Однако если использовать рекурсию, об этом можно не беспокоиться  (и сэкономить немало кода, времени и памяти).
  
   <span style="color:Green">// все переменные используются из описания алгоритма, <tex>\infty</tex> = бесконечность</span>
+
   <span style="color:Green">//Все переменные используются из описания алгоритма, <tex>\infty</tex> = бесконечность</span>
 
   '''function''' findCheapest(i, mask):
 
   '''function''' findCheapest(i, mask):
 
     '''if''' d[i][mask] != <tex>\infty</tex>  
 
     '''if''' d[i][mask] != <tex>\infty</tex>  
Строка 171: Строка 170:
 
     '''for''' j = 0 .. n - 1
 
     '''for''' j = 0 .. n - 1
 
       '''if''' w(i, j) существует '''and''' j-ый бит mask == 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))
+
         d[i][mask] = '''min'''(d[i][mask], findCheapest(j, mask - 2 ** j) + w(i, j))
 
   '''return''' d[i][mask]
 
   '''return''' d[i][mask]
 
    
 
    
   '''function''' start():
+
   '''for''' i = 0 .. n - 1
    '''for''' i = 0 .. n - 1
+
    '''for''' mask = 0 .. 2 ** n - 1
      '''for''' mask = 0 .. <tex>2^n</tex> - 1
+
    d[i][mask] = <tex>\infty</tex>
      d[i][mask] = <tex>\infty</tex>
+
  d[0][0] = 0;
    d[0][0] = 0
+
  ans = findCheapest(0, 2 ** n - 1)
    ans = findCheapest(0, <tex>2^n</tex> - 1)
+
  '''if''' ans == <tex>\infty</tex>
    '''return''' ans
+
    exit
 
Дальше ищем сам цикл:
 
Дальше ищем сам цикл:
   '''function''' findWay():
+
   i = 0
    i = 0
+
  mask = 2 ** n - 1
    mask = <tex>2^n</tex> - 1
+
  path.push(0)
    path.push(0)
+
  '''while''' mask != 0
    '''while''' mask != 0
+
    '''for''' j = 0 .. n - 1
      '''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)  
        '''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)
          path.push(j)
+
        i = j
          i = j
+
        mask = mask - 2 ** j
          mask = mask - <tex>2^j</tex>
+
        '''continue'''
          '''continue'''
+
 
 +
==Алгоритм нахождения гамильтового цикла==
  
==== Алгоритм нахождения гамильтонова цикла ====
+
==Алгоритм нахождения гамильтового пути==
Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла.
+
Алгоритм нахождения гамильтонова пути легко получить слегка изменив алгоритм нахождения гамильтонова цикла.
В массиве  <tex>d[i][mask]</tex> мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает <tex> true</tex>, то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.
 
  
==== Алгоритм нахождения гамильтонова пути ====
+
  '''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.
  
 
== См. также ==
 
== См. также ==
Строка 223: Строка 247:
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Динамическое программирование]]
 
[[Категория:Динамическое программирование]]
[[Категория:Классические задачи динамического программирования]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)