Решение задачи коммивояжера методом ветвей и границ

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ рОССИЙСКОЙ ФЕДЕРАЦИИ (МИНОБРНАУКИ  РОССИИ)   Федеральное государственное  бюджетное образовательное учреждение  высшего профессионального образования  «Санкт-Петербургский  государственный  политехнический  университет» (ФГБОУ ВПО «СПбГПУ»)   Институт менеджмента и информационных технологий (филиал) федерального  государственного бюджетного образовательного  учреждения высшего профессионального  образования «Санкт-Петербургский  государственный  политехнический  университет» в г.Череповце (ИМИТ «СПбГПУ»)

 

 

 

 

 

Лабораторная  работа №5

 

 

Дисциплина: «Системы и алгоритмы обработки данных»

 

Тема: «Решение задачи коммивояжера методом ветвей и границ»

 

 

 

 

 

Специальность: 230105 «Программное обеспечение ВТ и АС»

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил:
Проверил:	«__»____________ 20__г. _________ .

 

 

 

 

 

 

г. Череповец

2011

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

На плоскости указаны N городов, при этом местоположение каждого  города определяется парой координат. Необходимо найти оптимальный (относительно длины пути) простой цикл, позволяющий коммивояжеру посетить все города и вернуться в исходную точку отправления. Задача должна быть решена алгоритмом поиска с возвратом (backtracking) с оптимизацией перебора при помощи метода ветвей и границ. Дополнительно выводится информация о количестве рекурсивных вызовов. Тестирование выполнять для N<10. Провести сравнение выигрыша по времени, получаемого за счет сокращения вариантов перебора.

Краткие теоретические сведения

Поиск с возвратом

 

Поиск с возвратом (англ. Backtracking) —  общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М.

 

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

 

Метод ветвей и границ

 

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

 

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

 

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

 

В основе метода ветвей и границ лежит  следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения. Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.

 

Алгоритм Литтла

Алгоритм Литтла применяют для поиска решения задачи коммивояжера в виде гамильтонова контура. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе, имеющем N вершин, причем каждая вершина i связана с любой другой вершиной j двунаправленной дугой. Каждой дуге приписан вес С_i,j, причем веса дуг строго положительны (С_i,j≥0). Веса дуг образуют матрицу стоимости. Все элементы по диагонали матрицы приравнивают к бесконечности (С_j,j=∞).

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

Алгоритм Литтла является частным случаем применения метода "ветвей и границ" для конкретной задачи. Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

Алгоритм Литтла

1. Приведение матрицы. В каждой строке матрицы стоимости найдем минимальный элемент и вычтем его из всех элементов строки. Сделаем это и для столбцов, не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.
2. Для каждого нулевого элемента матрицы cij  рассчитаем коэффициент Г_i,j, который равен сумме наименьшего элемента i строки (исключая элемент С_i,j=0) и наименьшего элемента j столбца. Из всех коэффициентов  Г_i,j выберем такой, который является максимальным Г_k,l=max{Г_i,j}. В гамильтонов контур вносится соответствующая дуга (k,l). Если было обнаружено несколько максимальных коэффициентов, то обрабатывается каждый из них (образуется ветвление).
3. Удаляем k-тую строку и столбец l, поменяем на бесконечность значение элемента С_l,k (поскольку дуга (k,l) включена в контур, то обратный путь из l в k недопустим). Также находим и удаляем дугу, которая может замкнуть контур раньше времени и привести к образованию негамильтонового цикла.
4. Повторяем алгоритм с шага 1, пока порядок матрицы не станет равным двум.
5. Затем в текущий ориентированный граф вносим две недостающие дуги, определяющиеся однозначно матрицей прядка 2. Получаем гамильтонов контур.

В ходе решения ведется  постоянный подсчет текущего значения нижней границы. Нижняя граница равна сумме всех вычтенных элементов в строках и столбцах. Определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять какое-либо число, то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину. Итоговое значение нижней границы должно совпасть с длиной результирующего контура.

Особенности реализации

В реализации используются следующие глобальные параметры:

 

1. answer — хранит дуги, добавленные на данный момент в гамильтонов контур; в процессе выполнения всех процедур дуги могут, как включаться, так и исключаться из данного множества
2. result_path — хранит лучший на данный момент гамильтонов контур; перезаписывается в тот момент, когда находится новый контур, если новый контур лучше, по завершению работы процедур содержит оптимальный путь
3. current_record — длина лучшего на данный момент гамильтонова контура, перезаписывается вместе с контуром
4. included_edges_count — количество дуг, добавленных в answer

 

Реализация включает следующие  функции:

 

1. salesman_path 
   Функция служит интерфейсом, она принимает массив городов,  
   вызывает pay_matrix, затем branch_and_bound. Возвращает оптимальный маршрут, полученный с помощью branch_and_bound.
2. pay_matrix 
   Принимает на вход массив городов, формирует и возвращает матрицу стоимостей. В данной задаче предполагается, что между всеми городами существует прямой маршрут, поэтому минимальный путь между вершинами будет равен расстоянию между ними, то есть стоимости всех путей вычисляются как модуль вектора.
3. branch_and_bound 
   Принимает на вход матрицу стоимостей. Инициализирует глобальные параметры, затем вызывает рекурсивную функцию branch на текущей матрице, возвращает сформированный этой функцией оптимальный маршрут.
4. branch 
   Реализует рекурсивный алгоритм Литтла. Используя функции reduce_matrix, max_power_nulls, include_edge, exclude_edge, осуществляет последовательное выполнение шагов 1-3 алгоритма. Производит рекурсивные вызовы на матрицах меньшего порядка, полученных с помощью include_edge для каждого из нулей возвращенных max_power_nulls, увеличивая нижнюю границу по мере углубления. 
   После n-2 вызовов (n – размер исходной матрицы), что соответствует матрице порядка 2, формирует новый ответ из добавленных в answer и двух оставшихся ребер и возвращается к месту последнего ветвления.
5. reduce_matrix 
   На вход поступает текущая матрица стоимостей. Осуществляет приведение матрицы, возвращает сумму всех вычтенных элементов в строках и столбцах. (Реализует шаг 1)
6. max_power_nulls 
   На вход поступает текущая матрица стоимостей. Функция обнаруживает нули с максимальной степенью и возвращает их положение в матрице.
 

7. include_edge 
   На вход поступает текущая матрица стоимостей и координаты ребра. Добавляет ребро в answer, вычеркивает из матрицы одну строку и один столбец, понижая ее порядок на единицу, удаляет то ребро, которое может стать причиной преждевременного замыкания.
8. exclude_edge 
   Входом служат текущая матрица и координаты ребра. В случае ветвления, при завершении обработки одной из ветвей, удаляет ребро, соответствующее этой ветви, из answer, также приравнивает вес этого ребра к бесконечности, таким образом, исключая повторное добавление в параллельных ветвях.

 

Ввод данных для обработки производится через текстовой файл. Результат  выводится в консоль.

Тестирование программы

 

 

Входные данные:

 

Имя	X	Y
A	12	211
B	77	211
C	142	150
D	142	272
E	160	7
F	160	415
G	180	69
H	180	353
I	182	179
J	182	243

 

 

Результаты работы:

 

Enter the filename

FT10.txt

Branch and bound

recursion N 9; bound = 1009.05

 

recursion N 18; bound = 1002.21

 

recursion N 33; bound = 993.488

 

recursion N 49; bound = 993.488

 

A-B-D-F-H-J-I-C-G-E-A

Recursions: 74

Cost: 993.488

 

Do brute?

1

 

Brute force

A-B-C-E-G-I-J-D-H-F-A

Recursions: 6235301

Cost: 993.488

Permutations: 3628800

 

 

Расположение  городов	Branch and bound	Brute force

 

Выводы

В ходе лабораторной работы была разработана  программа, реализующая алгоритм Литтла, основанный на методе ветвей и границ. Данный алгоритм позволяет существенно сократить время поиска гамильтонова пути с наилучшей стоимостью в графе, при этом найденный путь гарантировано будет являться оптимальным. Время работы алгоритма сложно оценить теоретически, большую роль играет входной граф, при этом асимптотическая оценка памяти всегда равна . На тестовом примере данная реализация произвела 74 рекурсивных вызова, найдя всего 4 перестановки, полный перебор на том же примере требует построения минимум 3628800 перестановок. Могут найтись конфигурации графа, при которых время поиска приблизится ко времени полного перебора, но на практике вероятность этого крайне мала, это позволяет использовать алгоритм для решения различных задач.