Xreferat.com » Рефераты по математике » Решение задачи коммивояжера методом ветвей и границ

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

Расчетно-графическая работа

по теории алгоритмов


На тему

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


План


1. Вступление

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

3. Математическая модель задачи коммивояжера

4. Алгоритм решения

5. Выводы

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


1. Вступление


В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа и кватерниона, предложил детскую головоломку, в которой предлагалось совершить «круговое путешествие» по 20 городам, расположенных в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b, … t. Обязательным условием являлось требование: каждый город за исключением первого можно посетить один раз.

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


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


Рассмотрим задачу о коммивояжере.

Имеются n городов, расстояния (стоимость проезда, расход горючего на дорогу и т.д.) между которыми известны. Коммивояжер должен пройти все n городов по одному разу, вернувшись в тот город, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние (стоимость проезда и т.д.) будет минимальным.

Очевидно, что задача коммивояжера – это задача отыскания кратчайшего гамильтонова цикла в полном графе.

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

Решить задачу коммивояжера также можно с помощью алгоритма Крускала и «деревянного» алгоритма. Эти методы ускоряют разработку алгоритма по сравнению с методом полного перебора, однако не всегда дают оптимальное решение.

Существует метод решения задачи коммивояжера, который дает оптимальное решение. Этот метод называется методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ по-другому называют алгоритмом Литтла.

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

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

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

Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами Xi и Xj нет дуги, то ставится символ «∞».

Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в виде следующих правил:

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


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


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


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


каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам.

3. Суммируем элементы Решение задачи коммивояжера методом ветвей и граници Решение задачи коммивояжера методом ветвей и границ, получим константу приведения


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


которая будет нижней границей множества всех допустимых гамильтоновых контуров, то есть


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


4. Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак «∞» и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки


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


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


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


6. Разбиваем множество всех гамильтоновых контуров Решение задачи коммивояжера методом ветвей и границ на два подмножества Решение задачи коммивояжера методом ветвей и границ и Решение задачи коммивояжера методом ветвей и границ. Подмножество Решение задачи коммивояжера методом ветвей и границгамильтоновых контуров содержит дугу Решение задачи коммивояжера методом ветвей и границ, Решение задачи коммивояжера методом ветвей и границ - ее не содержит. Для получения матрицы контуров Решение задачи коммивояжера методом ветвей и границ, включающих дугу Решение задачи коммивояжера методом ветвей и границ, вычеркиваем в матрице Решение задачи коммивояжера методом ветвей и границ строку Решение задачи коммивояжера методом ветвей и границ и столбец Решение задачи коммивояжера методом ветвей и границ. Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент Решение задачи коммивояжера методом ветвей и границна знак «∞».

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


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


8. Находим множество гамильтоновых контуров Решение задачи коммивояжера методом ветвей и границ, не включающих дугу Решение задачи коммивояжера методом ветвей и границ. Исключение дуги Решение задачи коммивояжера методом ветвей и границ достигается заменой элемента Решение задачи коммивояжера методом ветвей и границ в матрице Решение задачи коммивояжера методом ветвей и границ на ∞.

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


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


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

Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений.

11. Если в результате ветвлений получаем матрицу Решение задачи коммивояжера методом ветвей и границ, то определяем полученный ветвлением гамильтонов контур и его длину.

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


3. Математическая модель задачи коммивояжера


Задача коммивояжера может быть сформулирована как целочисленная введением булевых переменных Решение задачи коммивояжера методом ветвей и границ, если маршрут включает переезд из города i непосредственно в город j и Решение задачи коммивояжера методом ветвей и границв противном случае. Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений


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

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


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

Однако этих ограничений не достаточно для постановки задачи коммивояжера, так как они не исключают решения, где вместо простого цикла, проходящего через n вершин, отыскиваются 2 и более отдельных цикла (подцикла), проходящего через меньшее число вершин. Поэтому задача, описанная уравнениями (2) – (4) должна быть дополнена ограничениями, обеспечивающими связность искомого цикла.

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


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


4. Алгоритм решения


Дана матрица расстояний, представленная в таблице 1. Необходимо с помощью алгоритма Литтла решить задачу коммивояжера.


Табл.1

j

i

1 2 3 4 5 6
1 ∞ 7 16 21 2 17
2 13 ∞ 21 15 43 23
3 25 3 ∞ 31 17 9
4 13 10 27 ∞ 33 12
5 9 2 19 14 ∞ 51
6 42 17 5 9 23 ∞

1) Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы Ui из соответствующих элементов строки матрицы.


j

i

1 2 3 4 5 6 Ui
1 ∞ 7 16 21 2 17 2
2 13 ∞ 21 15 43 23 13
3 25 3 ∞ 31 17 9 3
4 13 10 27 ∞ 33 12 10
5 9 2 19 14 ∞ 51 2
6 42 17 5 9 23 ∞ 5

2) Внизу полученной матрицы присоединяем строку Vj, в которой записываем минимальные элементы столбцов. Вычитаем элементы Vj из соответствующих столбцов матрицы.


j

i

1 2 3 4 5 6
1 ∞ 5 14 19 0 15
2 0 ∞ 8 2 30 10
3 22 0 ∞ 28 14 6
4 3 0 17 ∞ 23 2
5 7 0 17 12 ∞ 49
6 37 12 0 4 18 ∞
Vj 0 0 0 2 0 2

3) В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2.


Табл.2

j

i

1 2 3 4 5 6
1 ∞ 5 14 17 019 13
2 03 ∞ 8 02 30 8
3 22 04 ∞ 26 14 4
4 3 00 17 ∞ 23 04
5 7 07 17 10 ∞ 47
6 37 12 08 2 18 ∞

4) Находим константу приведения


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


Таким образом, нижней границей множества всех гамильтоновых контуров будет число

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


5) Находим степени нулей полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак «∞» и устанавливаем сумму минимальных элементов соответствующей строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых Решение задачи коммивояжера методом ветвей и границ.

6) Определяем максимальную степень нуля. Она равна 19 и соответствует клетке (1;5). Таким образом, претендентом на включение в гамильтонов контур является дуга (1;5).

7) Разбиваем множество всех гамильтоновых контуров Решение задачи коммивояжера методом ветвей и границна два: Решение задачи коммивояжера методом ветвей и границ и Решение задачи коммивояжера методом ветвей и границ. Матрицу Решение задачи коммивояжера методом ветвей и границ с дугой (1;5) получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент (5;1) на знак «∞».


j

i

1 2 3 4 6
2 0 ∞ 8 0 8
3 22 0 ∞ 26 4
4 3 0 17 ∞ 0
5 ∞ 0 17 10 47
6 37 12 0 2 ∞

8) Матрицу гамильтоновых контуров Решение задачи коммивояжера методом ветвей и границ получим из таблицы 2 путем замены элемента (1;5) на знак «∞».


j

i

1 2 3 4 5 6
1 ∞ 5 14 17 ∞ 13 5
2 0 ∞ 8 0 30 8
3 22 0 ∞ 26 14 4
4 3 0 17 ∞ 23 0
5 7 0 17 10 ∞ 47
6 37 12 0 2 18 ∞
14

9) Делаем дополнительное приведение матрицы контуров Решение задачи коммивояжера методом ветвей и границ:Решение задачи коммивояжера методом ветвей и границ = 0. Нижняя граница множества Решение задачи коммивояжера методом ветвей и границ равна Решение задачи коммивояжера методом ветвей и границ.


10) Находим константу приведения для множества контуров


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


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


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


11) Сравниваем нижние границы подмножеств Решение задачи коммивояжера методом ветвей и границ и Решение задачи коммивояжера методом ветвей и границ. Так как


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


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

На рис.1 представлено ветвление по дуге (1;5).


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

Рис.1


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

j

i

1 2 3 4 6
2 03 ∞ 8 02 8
3 22 04 ∞ 26 4
4 3 00 17 ∞ 04
5 ∞ 010 17 10 47
6 37 12 010 2 ∞

12) Узнаем степени нулей матрицы. Претендентами на включение в гамильтонов контур будут несколько дуг (5;2) и (6;3). Для дальнейших расчетов выберем дугу (6;3). Разбиваем множество Решение задачи коммивояжера методом ветвей и границ на два подмножества:Решение задачи коммивояжера методом ветвей и границ и Решение задачи коммивояжера методом ветвей и границ (табл. 3 и 4). Чтобы не допустить образования негамильтонова контура, в таблице 3 заменяем элемент (3;6) на знак «∞»


Табл.3

j

i

1 2 4 6
2 0 ∞ 0 8
3 22 0 26 ∞
4 3 0 ∞ 0
5 ∞ 0 10 47

Табл.4

j

i

1 2 3 4 6
2 0 ∞ 8 0 8
3 22 0 ∞ 26 4
4 3 0 17 ∞ 0
5 ∞ 0 17 10 47
6 37 12 ∞ 2 ∞ 2
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: