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

 

(DEFUN HAMILTCYCLE (GRAPH) 

  ;; GRAPH - граф в виде структуры смежности           ; 

  ;; Результат: гамильтонов цикл в виде списка вершин, ; 

  ;; NIL - если гамильтонова цикла не существует       ; 

     (COND ( (NULL GRAPH) NIL ) 

           (  T  (COND ( (NULL (CDR GRAPH)) 

                             (LIST (CAAR GRAPH))) 

                       (  T  (HC GRAPH (CAAR GRAPH) 

                                 (LIST (CAAR GRAPH)) 

                                 (CDAR GRAPH) 

                             ) 

                       ) 

                 ) 

           ) 

     ) 

  ) 

 

==> HAMILTCYCLE

 

 

  

  (DEFUN HC (GRAPH START VISITED SONS) 

  ;; START   - первая вершина графа           ; 

  ;; VISITED - список пройденных вершин       ; 

  ;; SONS    - соседи просматриваемой вершины ; 

     (COND ( (NULL SONS) NIL ) 

           (  T  (COND ( (AND (MEMBER START SONS) 

                              (EQ (LENGTH GRAPH) 

                                  (LENGTH VISITED)) 

                         ) 

                            (REVERSE VISITED) 

                       ) 

                       ( T (COND 

                             ( (MEMBER (CAR SONS) VISITED) 

                                 (HC GRAPH START VISITED 

                                            (CDR SONS)) ) 

                             (  T  (OR (HC GRAPH START 

                                           (CONS 

                                             (CAR SONS) 

                                             VISITED) 

                                           (NEIGHBOUR3 

                                             (CAR SONS) 

                                             GRAPH) 

                                       ) 

                                       (HC 

                                          GRAPH START VISITED 

                                          (CDR SONS))) )) ) 

                 ) 

           ) 

     ) 

  ) 

 

 

==> HC 

  ;; ------------------------------- ; 

  (DEFUN NEIGHBOUR3 (X GRAPH) 

     (COND ( (NULL (ASSOC X GRAPH)) NIL ) 

           (  T  (CDR (ASSOC X GRAPH)) ) 

     ) 

  ) 

 

==> NEIGHBOUR3 

 

(HAMILTCYCLE '((A . (F D C)) (F . (E D A B)) (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C)))) 

 

==> (a f d e b c)

 

 

Разберем работу функции HAMILTCYCLE. Для пустого графа ее значение равно пустому списку  NIL, а для графа, состоящего из единственной вершины - списку, содержащему эту вершину. Если граф состоит более чем из двух вершин, то вызывается функция HC. Именно эта функция осуществляет продолжение частичного решения.

Частичное решение представлено в виде списка VISITED - это список просмотренных вершин в порядке, обратном порядку их просмотра. Список SONS - это список соседей первой вершины в списке VISITED. С точки зрения частичного решения эта вершина является как раз последней. Поэтому вершины из списка SONS могут входить в продолжения частичного решения. Если этот список пуст, то продолжение частичного решения невозможно и функция HC возвращает значение NIL. В противном случае проверяется, нельзя ли на следующем шаге замкнуть гамильтонов цикл. Это возможно, если, во-первых, начальная вершина содержится в списке SONS и, во-вторых, если пройдены все вершины графа. Поскольку каждая вершина по условию посещается не более одного раза (это следует из определения частичного решения), то достаточно проверить, что длины списков GRAPH и VISITED равны. Если оба вышеупомянутых условия выполнены, то список VISITED представляет собой искомый цикл.

Перейдем теперь к случаю, когда продолжение возможно, но не приводит немедленно к построению полного  решения. Наша цель продолжить частичное  решение. Для этого мы просматриваем  список SONS до тех пор, пока не встретим вершину, которой нет в списке VISITED. Если такая вершина не найдена, то продолжение невозможно. В противном случае вычисляется выражение

   (OR

      (HC GRAPH START (CONS (CAR SONS) VISITED)

          (NEIGHBOUR3 (CAR SONS) GRAPH))

      (HC GRAPH START VISITED (CDR SONS))

   )

 

Это ключевой момент поиска с возвращением. Если при первом вызове функции HC вычисляется значение, отличное от NIL, то это означает, что продолжение (CONS (CAR SONS) VISITED) достроено до полного решения. Это решение и возвращается на верхний уровень. В противном случае с помощью второго вызова функции HC делается попытка найти продолжение, отличное от (CONS (CAR SONS) VISITED).

Обратите внимание на то, что весь механизм возврата оказался спрятанным в рекурсию. Это позволило  сделать программу ясной и  компактной.

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

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

 

 

 

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

Чтобы продемонстрировать, что программа на Лиспе действительно  работает, возьмем граф, который  точно подойдет для задачи коммивояжера, представленный на рисунке 2.

 

 

 

 

 

 

 

Рисунок 2 - Пример графа, имеющего решение задачи коммивояжера

 

 

 

 

 

 

 

 

Тестовые примеры:

1.   $ (HAMILTCYCLE '((1 . (2 6)) (2 . (1 3 4)) (3 . (2 4))

   (4 . (2 3 5)) (5 . (4 6)) (6 . (1 5)))) (рисунок 3)

   Результат: (1 2 3 4 5 6)

 

Рисунок 3 – Скриншот выполнения программы

 

 

 

 

 

2.   $ (HAMILTCYCLE '((A . (F D C)) (F . (E D A B))

   (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C)))) (рисунок 4)

Результат:   (A F D E B C)

Рисунок 4 – Скриншот выполнения программы

 

 

 

 

 

 

Заключение

Мною был рассмотрен и  реализован поиск Гамильтоновых  путей в графе методом перебора Робертса и Флореса. Этот метод не предъявляет чрезмерных требований к памяти компьютера, но время поиска зависит экспоненциально от числа вершин в графе.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1. Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.
2. Судоплатов С.В. , Овчинникова Е.В. Элементы дискретной математики: учебник – Москва: ИНФРА-М, 2002
3. Н.А.Роганова. — Функциональное программирование. — М.: ГИНФО, 2002. – 260 с.
4. С.С. Лавров, Г.С. Силагадзе "Автоматическая обработка данных. Язык Лисп и его реализация" М. 1978
5. Е.В.Олькина. Методические указания по оформлению пояснительных записок к дипломным, курсовым проектам (работам) и отчетов по практикам в соответствии с требованиями государственных стандартов. – Орел: ОрелГТУ, 2007. – 54 с.

 

 

 

 

 

 

 

 

 

 

 

Приложение А

(обязательное)

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

 

(DEFUN HAMILTCYCLE (GRAPH) 

  ;; GRAPH - граф в виде структуры смежности           ; 

  ;; Результат: гамильтонов цикл в виде списка вершин, ; 

  ;; NIL - если гамильтонова цикла не существует       ; 

     (COND ( (NULL GRAPH) NIL ) 

           (  T  (COND ( (NULL (CDR GRAPH)) 

                             (LIST (CAAR GRAPH))) 

                       (  T  (HC GRAPH (CAAR GRAPH) 

                                 (LIST (CAAR GRAPH)) 

                                 (CDAR GRAPH) 

                             ) 

                       ) 

                 ) 

           ) 

     ) 

  ) 

 

==> HAMILTCYCLE

 

 

  

  (DEFUN HC (GRAPH START VISITED SONS) 

  ;; START   - первая вершина графа           ; 

  ;; VISITED - список пройденных вершин       ; 

  ;; SONS    - соседи просматриваемой вершины ; 

     (COND ( (NULL SONS) NIL ) 

           (  T  (COND ( (AND (MEMBER START SONS) 

                              (EQ (LENGTH GRAPH) 

                                  (LENGTH VISITED)) 

                         ) 

                            (REVERSE VISITED) 

                       ) 

                       ( T (COND 

                             ( (MEMBER (CAR SONS) VISITED) 

                                 (HC GRAPH START VISITED 

                                            (CDR SONS)) ) 

                             (  T  (OR (HC GRAPH START 

                                           (CONS 

                                             (CAR SONS) 

                                             VISITED) 

                                           (NEIGHBOUR3 

                                             (CAR SONS) 

                                             GRAPH) 

                                       ) 

                                       (HC 

                                          GRAPH START VISITED 

                                          (CDR SONS))) )) ) 

                 ) 

           ) 

     ) 

  ) 

 

 

==> HC 

  ;; ------------------------------- ; 

  (DEFUN NEIGHBOUR3 (X GRAPH) 

     (COND ( (NULL (ASSOC X GRAPH)) NIL ) 

           (  T  (CDR (ASSOC X GRAPH)) ) 

     ) 

  ) 

 

==> NEIGHBOUR3 

 

(HAMILTCYCLE '((A . (F D C)) (F . (E D A B)) (E . (D F B)) (D . (E F A)) (C . (A B)) (B . (F E C)))) 

 

==> (a f d e b c)