Реализация алгоритма поиска гамильтонова цикла в графе переборным методом Робертса и Флореса

 

Содержание

 

Введение                                                                                          4                 

1 Постановка задачи                                                                                   6

2 Алгоритм Робертса и Флореса                             7

2.1 Улучшение метода Робертса и Флореса            10

3 Реализация алгоритма  и его описание                                                   12                 

4 Примеры работы программы                                                                 16

Заключение                                                                                                  19

Список использованной литературы                                                         20

Приложение А Листинг  программной реализации алгоритма  поиска гамильтонова цикла переборным методом Робертса и Флореса            21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение 

 

Название «гамильтонов цикл» произошло  от задачи «Кругосветное путешествие» предложенной ирландским математиком  Вильямом Гамильтоном в 1859 году. Нужно  было, выйдя из исходной вершины  графа, обойти все его вершины  и вернуться в исходную точку. Граф представлял собой укладку  додекаэдра, каждой из 20 вершин графа  было приписано название крупного города мира.

Если граф имеет простой цикл, содержащий все вершины графа  по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который  содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение  можно распространить на ориентированные  графы, если путь считать ориентированным. Гамильтонов цикл не обязательно  содержит все ребра графа. Ясно, что  гамильтоновым может быть только связный граф и, что всякий гамильтонов  граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе.

Любой граф G можно превратить в  гамильтонов граф, добавив достаточное  количество вершин. Для этого, например, достаточно к вершинам v1,…, vp графа G добавить вершины u1, …, up и множество  ребер {(vi, ui)} {(ui, vi+1)}.Степенью вершины v называется число ребер d(v), инцидентных  ей, при этом петля учитывается  дважды. В случае ориентированного графа различают степень do(v) по выходящим  дугам и di(v) — по входящим.В отличии  от эйлеровых графов, где имеется  критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла  оказывается NP-полной. Большинство  известных теорем имеет вид: «если  граф G имеет достаточное количество ребер, то граф является гамильтоновым».

Пока неизвестно никакого простого критерия или алгебраического  метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический интерес, но являются слишком общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гамильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является способ Робертса и Флореса, который не предъявляет чрезмерных требований к памяти компьютера, но время в котором зависит экспоненциально от числа вершин в графе.

Основная цель данной курсовой работы состоит в том, что нужно  написать программу реализующую  алгоритм поиска гамильтонова цикла в графе переборным методом Робертса и Флореса.

Основные задачи: изучить  алгоритм поиска гамильтонова цикла в графе переборным методом Робертса и Флореса, реализовать изученный алгоритм в программе на языке LISP.

 

 

 

 

 

 

 

 

 

1 Постановка задачи

 

Задачей программы является реализация Гамильтонова цикла для  графа. Гамильтонов цикл (или путь) это когда мы выходим из любой  вершины графа и обходим все  его вершины. Сам по себе Гамильтонов  путь является частным случаем обычного ациклического пути, когда требуется  попасть из одной вершины графа  в другую. Отличие состоит в  том, что Гамильтонов путь из одной  вершины в другую должен пройти через  все оставшиеся вершины. В свою очередь  частным случаем Гамильтонова пути является задача коммивояжера. Задача коммивояжера может быть сформулирована следующим образом. Коммивояжер должен выехать из заданного города, побывать в каждом из остальных n—1 городов ровно один раз и вернуться в исходный город. Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется проехать наименьшее суммарное расстояние. Нетрудно заметить, что всего существует (n-1)! возможных маршрутов, среди которых один или несколько — оптимальные.

Существует несколько  способов определения оптимального маршрута:

• Простой перебор всех возможных маршрутов с целью найти оптимальный;
• Поиск оптимального маршрута методом ветвей и границ.

В данной курсовой работе будет  рассмотрен метод перебора маршрутов  с возвратом или, так называемый метод Робертса и Флореса.

 

 

 

 

 

 

 

2 Алгоритм Робертса  и Флореса

 

В противоположность алгебраическим методам, с помощью которых пытаются найти сразу все гамильтоновы циклы и при реализации которых приходится хранить, поэтому все цепи, которые могут оказаться частями таких циклов, метод перебора имеет дело с одной цепью, непрерывно продлеваемой вплоть до момента, когда либо получается гамильтонов цикл, либо становится ясно, что эта цепь не может привести к гамильтонову циклу. Тогда цепь модифицируется некоторым систематическим способом (который гарантирует, что, в конце концов, будут исчерпаны все возможности), после чего продолжается поиск гамильтонова цикла. В этом способе для поиска требуется очень небольшой объем памяти и за один раз находится один гамильтонов цикл.

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом  и Флоресом. Начинают с построения (k × n)-матрицы M=[mij], где элемент mij есть i-я вершина (скажем xq), для которой в графе G(X, Г) существует дуга (xj, xq). Вершины xq во множестве Г(xj) можно упорядочить произвольно, образовав элементы j-го столбца матрицы M. Число строк k матрицы M будет равно наибольшей полустепени исхода вершины.

Метод состоит в следующем. Некоторая  начальная вершина (скажем, x1) выбирается в качестве отправной и образует первый элемент множества S, которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например, вершина a) в столбце x1. Затем к множеству S добавляется первая возможная вершина (например, вершина b) в столбце a, потом добавляется к S первая возможная вершина (например, вершина c) в столбце b и т.д. Под «возможной» вершиной мы понимаем вершину, еще не принадлежащую S. Существуют две причины, препятствующие включению некоторой вершины на шаге r во множество S = {x1, a, b, c, … , xr-1, xr}:

• В столбце xr нет возможной вершины.
• Цепь, определяемая последовательностью вершин в S, имеет длину n - 1, т.е. является гамильтоновой цепью.

В случае 2) возможны следующие случаи:

• В графе G существует дуга (xr, x1), и поэтому найден гамильтонов цикл.
• Дуга (xr, x1) не существует и не может быть получен никакой гамильтонов цикл.

В случаях (1) и (2b) следует прибегнуть к возвращению, в то время как в случае (2a) можно прекратить поиск и напечатать результат (если требуется найти только один гамильтонов цикл), или (если нужны все такие циклы) произвести печать и прибегнуть к возвращению.

Возвращение состоит в удалении последней включенной вершины xr из S, после чего остается множество S = {x1, a, b, c, … , xr-1}, и добавлении к S первой возможной вершины, следующей за xr, в столбце xr-1 матрицы M. Если не существует никакой возможной вершины, делается следующий шаг возвращения и т.д.

Поиск заканчивается в том случае, когда множество S состоит только из вершины x1 и не существует никакой возможной вершины, которую можно добавить к S, так что шаг возвращения делает множество S пустым. Гамильтоновы циклы, найденные к этому моменту, являются тогда всеми гамильтоновыми циклами, существующими в графе.

Рассмотрим пример поиска гамильтонова цикла в графе переборным методом Робертса и Флореса, представленном на рисунке 1.

 

 

 

Пример приведен на рисунке 1.

 
Рисунок 1 – граф для поиска гамильтонова цикла

"2"

1. S = {1}.
2. S = {1, 2}.
3. S = {1, 2, 3}.
4. S = {1, 2, 3, 4}.
5. S = {1, 2, 3, 4, 5} - Г 4→3 4→5.
6. S = {1, 2, 3, 4}.
7. S = {1, 2, 3}  3→1 3→2 3→4.
8. S = {1, 2}.
9. S = {1}.

"3"

10. S = {1, 3}  3→2.
11. S = {1, 3, 2} 2→1.
12. S = {1, 3} 2→3.
13. S = {1, 3, 4} 3→4 4→5.
14. S = {1, 3, 4, 5, 4} 5→нет.
15. S = {1, 3, 4}.
16. S = {1, 3}.
17. S = {1}.

"5"

18. S = {1, 5}.
19. S = {1, 5, 4}.
20. S = {1, 5, 4, 3}.
21. S = {1, 5, 4, 3, 2} – Г.
22. S = {1, 5, 4, 3}.
23. S = {1, 5, 4}.
24. S = {1, 5}.
25. S = {1}.
26. S = Ø.

2.1 Улучшение метода Робертса и Флореса

Рассмотрим улучшение  основного переборного метода Робертса и Флореса. Допустим, что на некотором  этапе поиска построенная цепь задается множеством S = {x1, x2, , xr} и что следующей вершиной, которую предполагается добавить к S, является x* S. Рассмотрим теперь две следующие ситуации, в которых вершина является изолированной в подграфе, остающемся после удаления из G(X,Г) всех вершин, образующих построенную до этого цепь.

1. Если существует такая вершина x X\S, что x Г(xr) и Г-1(x)   S, то, добавляя к S любую вершину x*, отличную от  x, мы не сможем в последующем достигнуть вершины x ни из какой конечной вершины построенной цепи, и, значит, эта цепь не сможет привести нас к построению гамильтонова цикла. Таким образом, в этом случае x является единственной вершиной, которую можно добавить к S для продолжения цепи.

2. Если существует такая вершина x X\S, что x Г-1(x1) и Г(x)  S {x*} для некоторой другой вершины x*, то x* не может быть добавлена к S, так как тогда в остающемся подграфе не может существовать никакой цепи между x и x1. Цепь, определяемая множеством S   {x*}, не может поэтому привести к гамильтонову циклу, а в качестве кандидата на добавление к множеству S следует рассмотреть другую вершину, отличную от x*.

Проверка условий 1 и 2 будет, конечно, замедлять итеративную процедуру, и для небольших графов (менее чем с 20 вершинами) не получается никакого улучшения первоначального алгоритма Робертса и Флореса. Но для больших графов эта проверка приводит к заметному сокращению необходимого времени вычислений, уменьшая его обычно в 2 или более раз.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 Реализация алгоритма и его описание

 

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

Частичным решением для гамильтонова цикла является любая последовательность вершин, определяющая простой путь.

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

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