Расчетно-графическаяработа
по теорииалгоритмов
На тему
«Решениезадачи коммивояжера методом ветвей и границ»
План
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 15 2 ∞ 8 2 30 10 3 22 ∞ 28 14 6 4 3 17 ∞ 23 2 5 7 17 12 ∞ 49 6 37 12 4 18 ∞
Vj 2 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 ∞ 8 8 3 22 ∞ 26 4 4 3 17 ∞ 5 ∞ 17 10 47 6 37 12 2 ∞
8) Матрицу гамильтоновыхконтуров /> получимиз таблицы 2 путем замены элемента (1;5) на знак «∞».
j
i 1 2 3 4 5 6
1 ∞ 5 14 17 ∞ 13 5 2 ∞ 8 30 8
3 22 ∞ 26 14 4
4 3 17 ∞ 23
5 7 17 10 ∞ 47
6 37 12 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 ∞ 8 3 22 26 ∞ 4 3 ∞ 5 ∞ 10 47
Табл.4
j
i 1 2 3 4 6
2 ∞ 8 8
3 22 ∞ 26 4
4 3 17 ∞
5 ∞ 17 10 47
6 37 12 ∞ 2 ∞ 2
8
Определим константыприведения для этих матриц
/>, />
Следовательно
/>, />
Так как />, то дальнейшемуветвлению подлежит подмножество />. Находим степени нулей матрицы.
j
i 1 2 4 6 2
03 ∞
02 8 3 22
022 26 ∞ 4 3
00 ∞
08 5 ∞
010 10 47
Претендентом к включениюв гамильтонов контур станет дуга (3;2). Разбиваем множество /> на два /> и />.
j
i 1 4 6
2 8
4 3 ∞
5 ∞ 10 47 10
j
i 1 2 4 6
2 ∞ 8
3 22 ∞ 26 ∞ 22 4 3 ∞
5 ∞ 10 47
Очевидно
/>, />
Следовательно, очередномуветвлению нужно подвергнуть подмножество />.
Переходим к ветвлениюподмножества />. Определяем степени нулей.Претендентом на включение в гамильтонов контур является дуга (5;4). Разбиваеммножество /> надва подмножества: /> и />.
Находим нижние границы
/>, />
Следовательно, очередномуветвлению нужно подвергнуть подмножество />. Но его матрица имеет размерность/>. Поэтомув гамильтонов контур следует включить дуги, соответствующие в матрице /> нулевымэлементам.
Определим полученныйгамильтонов контур. В него вошли дуги
/>
Длина контура равна
/>
Так как границыоборванных ветвей больше длины контура 1 – 5 – 4 – 6 – 3 – 2 – 1, то этотконтура имеет наименьшую длину.
алгоритмкрускал коммивояжер
/>
Рис.25
Выводы
Задача коммивояжераявляется частичным случаем гамильтоновой задачи о путешественнике. Суть задачикоммивояжера состоит в нахождении суммарной минимальной характеристики(расстояния, стоимости проезда и т.д.), при этом коммивояжер должен пройти все n городов по одному разу, вернувшись втот город, с которого начал.
Существуют несколькометодов решения задачи коммивояжера: метод полного перебора, с помощью методаветвей и границ (алгоритм Литтла), алгоритма Крускала, «деревянного» алгоритмаи т.д. Однако только метод ветвей и границ дает нам в итоге самое оптимальноерешение.
Основная идея методаЛиттла состоит в том, что вначале строят нижнюю границу длин маршрутов длявсего множества гамильтоновых контуров />. Затем все множество контуров /> разбивают надва подмножества таким образом, чтобы первое подмножество />состояло изгамильтоновых контуров, содержащих некоторую дугу (i,j), а другое подмножество /> не содержалоэтой дуги.
Для практическойреализации идеи метода ветвей и границ применительно к задаче коммивояжеранужно найти метод определения нижних границ подмножества и разбиения множествагамильтоновых контуров на подмножества (ветвление). Такое определение нижнихграниц базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число />, то задачаостанется эквивалентной прежней, то есть оптимальность маршрута коммивояжера неизменится, а длина любого гамильтонова контура изменится на данную величину />.
Используя ЭВМ, методомветвей и границ можно решить задачи коммивояжера для />.
6. Список использованнойлитературы
1. О. Е. Акимов «Дискретнаяматематика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом«Лаборатория базовых знаний».
2. Ф. А. Новиков «Дискретнаяматематика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом«Питер».
3. В. М. Бондарев «Основыпрограммирования» 1998 г., 368 с. изд. дом «Феникс»