На этом шаге мы рассмотрим реализацию и использование алгоритмов с возвратом.
До сих пор мы рассматривали только такие алгоритмы на графах, в процессе работы которых нам никогда не приходилось возвращаться назад.
Если, например, при поиске на графе вершина была просмотрена, то она и останется в списке просмотренных вершин до окончания работы алгоритма.
Однако существует большой класс задач, для которых неизвестны такие алгоритмы. Пожалуй, наиболее известной такой задачей является задача коммивояжера (см., например, [2]) - задача о поиске кратчайшего маршрута между N городами, при этом лишь некоторые из городов непосредственно соединены дорогами.
Мы рассмотрим здесь задачу о поиске такого марщрута, который начинается и заканчивается в одном и том же городе и, кроме того, не заходит в один и тот же город дважды. Эта задача известна как задача поиска гамильтонова цикла в графе. Как ясно из предыдущего, гамильтонов цикл - это простой замкнутый путь, содержащий все вершины графа. Заметим, что гамильтонов цикл есть далеко не в каждом графе.
Алгоритм, с помощью которого мы будем искать гамильтоновы циклы, называется "поиск с возвращением". В основе его лежит понятие частичного решения. Пусть решение задачи представляется в виде некоторой последовательности. В нашем случае это просто последовательность всех вершин графа, удовлетворяющая очевидным ограничениям. Начальный отрезок последовательности, который удовлетворяет ограничениям, определяющим полное решение, называется частичным решением.
Частичным решением для гамильтонова цикла является любая последовательность вершин, определяющая простой путь.
Если в последовательность, представляющую частичное решение, добавить новый элемент так, что расширенная последовательность снова будет частичным решением, то новая последовательность называется продолжением частичного решения. Продолжение, как правило, неоднозначно.
Идея поиска с возвращением состоит в том, чтобы, начав с тривиального частичного решения, последовательно продолжать его до тех пор, пока не будет получено полное решение, либо продолжение станет невозможным. В последнем случае мы возвращаемся на шаг назад и пробуем построить другое продолжение. Если пространство поиска конечно, то либо мы получим полное решение, либо убедимся в невозможности его построения, поскольку осуществлен полный перебор возможных продолжений.
После этих замечаний приведем реализацию алгоритма поиска гамильтонова пути в связном неориентированном графе. Программа [1, с.134-135].
(DEFUN HAMILTCYCLE (LAMBDA (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) ) ) ) ) ) )) ; ---------------------------------------- ; (DEFUN HC (LAMBDA (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))) )) ) ) ) ) )) ; ------------------------------- ; (DEFUN NEIGHBOUR3 (LAMBDA (X GRAPH) (COND ( (NULL (ASSOC X GRAPH)) NIL ) ( T (CDR (ASSOC X GRAPH)) ) ) ))
Тестовые примеры:
$ (HAMILTCYCLE '((1 . (2 6)) (2 . (1 3 4)) (3 . (2 4)) (4 . (2 3 5)) (5 . (4 6)) (6 . (1 5)))) (1 2 3 4 5 6) $ (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 прекратит работу, как только найдет первый гамильтонов цикл или просмотрит все возможности. Можно также поставить задачу об отыскании всех гамильтоновых циклов данного графа.
Заметим, что алгоритм поиска с возвращением можно интерпретировать как поиск в графе. Вершинами этого графа являются частичные решения, а ребрами - те пары частичных решений, одно из которых является непосредственным продолжением другого. Выбор того или иного алгоритма поиска на графе определяет стратегию поиска с возвращением.
Замечания.
- Не поленитесь и загляните в [3, с.108-114]!
- [1, с.137]. Мы рассмотрели реализацию на языке LISP нескольких
простых алгоритмов на графах. Эти реализации чрезвычайно
просты и наглядны, что достигается, с одной стороны, выбором
представления данных, а с другой - использованием чисто
функциональных методов программирования. Функциональный подход имеет кроме очевидных достоинств и недостатки.
К последним относится в первую очередь недостаточная эффективность
полученных программ. Это касается как быстродействия, так и использования памяти.
Эффективность программы часто имеет первостепенное значение. Скажем поэтому несколько слов о том, как можно было бы повысить эффективность приведенных выше программ.
Одна из причин относительно невысокого быстродействия наших программ связана с накладными расходами на организацию рекурсии. Быстродействие программы можно было бы повысить, заменив рекурсию итерацией, что в принципе всегда возможно [4]. Однако это может привести к весьма сложным и малопонятным программам, доставляющим много трудностей при отладке.
Еще одна причина неэффективности заключается в следующем. В наших алгоритмах очень часто встречается операция поиска заданного элемента в списке.
Общая схема поиска выглядела таким образом:
(DEFUN SUCHTHAT (LAMBDA (P LST) ; Функция SUCHTHAT выбирает из списка LST первый ; ; элемент обладающий свойством P. Если такого ; ; элемента нет, то возвращается значение NIL ; (COND ( (NULL LST) LST ) ( (P (CAR LST)) (CAR LST) ) ( T (SUCHTHAT P (CDR LST)) ) ) ))
Здесь P - некоторый предикат, проверяющий выполнение условия поиска. Такой поиск называется последовательным. Время, затрачиваемое на него, пропорционально в среднем длине просматриваемого списка. Если поиск выполняется много раз, то возможно, имеет смысл по-другому организовать данные. Можно, например, использовать так называемое бинарное дерево поиска.
Скорость поиска в таком дереве, вообще говоря, зависит от порядка включения в него узлов, однако во многих случаях она может быть пропорциональна двоичному логарифму от полного числа узлов.
Алгоритм поиска в дереве поиска:
(DEFUN SEARCH (LAMBDA (A TREE) ; Функция SEARCH ищет в дереве TREE элемент A. ; ; В случае успеха функция возвращает поддерево дерева ; ; TREE, в котором элемент A является корнем; в случае ; ; неудачного поиска функция возвращает NIL ; (COND ( (NULL TREE) NIL ) ( (EQUAL A (CAR TREE)) TREE ) ( (LESSP A (CAR TREE)) (SEARCH A (CADR TREE)) ) ( T (SEARCH A (CADDR TREE)) ) ) ))
(1) Крюков А.П., Радионов А.Я., Таранов А.Ю., Шаблыгин Е.М. Программирование на языке R-Лисп. - М.: Радио и связь, 1991. - 192 с.
(2) Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.
(3) Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.
(4) Баррон Д. Рекурсивные методы в программировании. - М.: Мир, 1974. - 80 с.
Со следующего шага мы начнем знакомиться с прагматикой языка LISP.
