Изменения

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

Гамильтоновы графы

11 081 байт добавлено, 09:11, 13 октября 2020
В этом разделе ничего не оптимизируется: выше находили самый дешевый гам. цикл, а здесь находим любой гам. путь, то есть другая задача.
{{Определение
|definition =
'''Гамильтоновым путём''' (англ. ''Hamiltonian path'') называется простой путь, приходящий проходящий через каждую вершину графа ровно один раз.
}}
{{Определение
|id = defCycle
|definition =
'''Гамильтоновым циклом''' (англ. ''Hamiltonian cycle'') называют замкнутый гамильтонов путь.
}}
===[[Теорема Гуйя-Ури]]===
{{Теорема
Ghouila-Houri
|statement=
Пусть <tex>G </tex> {{---}} сильносвязный ориентированный граф. <br>
<tex>
\begin{matrix}
\deg^+ v \geqslant n/2 \\ \deg^- v \geqslant n/2 \\
\end{matrix} \Bigg\} \rightarrow Rightarrow
</tex> <tex> G </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 '''to''' g.vertices '''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 ==== Описание задачи ===={{Задача|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>,то эти вершины еще не посещены). Алгоритм поиска цикла будет выглядеть следующим образом: * vert Начальное состояние — когда находимся в <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\\* count \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'''
Приведённая процедура работает следующим образом: перебираются всё рёбра из текущей вершины в ещё не посещённые==== Алгоритм нахождения гамильтонова цикла ====Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла. Чтобы проверить граф на гамильтоновость, необходимо запустить процедуру из вершины с номером 0 и параметром В массиве <tex>count = 1d[i][mask]</tex>мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. Если процедура возвращает trueВ этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то в массиве next будет храниться следующая вершина на гамильтоновом циклезапускаем функцию рекурсивно от нее. Этот алгоритм в худшем случае перебирает Если она возвращает <tex>(n - 1)!true</tex> путей, то есть до вершины можно добраться, то записываем, что даёт сложность работы <tex>O(n!)</tex>мы можем посетить вершину. Проходы так же осуществляются по рёбрам.
Приведём ==== Алгоритм нахождения гамильтонова пути ====Алгоритм нахождения гамильтонова пути легко получить, используя алгоритм, основанный на динамическом программировании, который работает значительно быстреенахождения гамильтонова цикла. Алгоритм основан на следующей идее: будем для каждой пары из подмножества Нужно добавить в граф еще одну вершину и ребра от нее до всех остальных вершин и вершины считать, существует ли гамильтонов путь для этого подмножества из всех остальных вершин, заканчивающихся в выделенной вершинедо неё. Суммарно таких состояний будет <tex>O(n2^n)</tex>, для обсчёта каждого из них требуется <tex>O(n)</tex> времени, то есть, суммарно И далее запустить алгоритм работает за <tex>O(n^22^n)</tex> временипоиска цикла от новой вершины. ПсевдокодВ восстановлении пути учтем, реализующий этот алгоритмчто эта вершина лишняя, приведён ниже:и не будем записывать её в путь.
'''bool'''[][] get_dp_table(graph g): '''int''' n = g.vertices '''bool'''[][] result = new int[1 << n][n] '''for''' i = 0 '''to''' n '''result'''[1 << i][i] = (0; i) '''in''' gСм.edges; '''for''' i = 1 '''to''' 1 << n '''if''' (count(i) также == 1) '''continue''' '''for''' j = 0 '''to''' n '''if''' ((1 << j) & i != 0) '''for''' k = 0 '''to''' n '''if''' (k != j && (1 << k) & i != 0) result[i][j] = result[(1 << j) ^ i][k] && (k; j) '''in''' g.edges '''return''' result
В приведённом выше коде считаем, что n меньше количества бит *[[Кратчайший путь в числовом типе данных, для операций над множествами используются побитовые логические операции в синтаксисе языка C. Функция count считает количество единичных бит в числе (она проста в реализации, но не относится к алгоритма, поэтому не приводится). Граф гамильтонов тогда, когда dpациклическом графе]]*[[Задача о наибольшей общей подпоследовательности]]*[[Задача о наибольшей возрастающей подпоследовательности]]*[[(1 << n) - 1Задача о рюкзаке]]*[i[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] && (i; 0) <tex>\in</tex> g.edges для некоторого i.
==Источники информации==
*Седжвик Р. Фундаментальные алгоритмы на 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
[[Категория:Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория:Гамильтоновы графы]]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Классические задачи динамического программирования]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/50565...75091»

Навигация