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

Министерство образования и науки Украины Национальный технический университет Украины Киевский политехнический институт Славутичский филиал Расчетно-графическая работа по теории алгоритмов на тему Решение задачи коммивояжера методом ветвей и границ Выполнил Студент группы ИСС-31 факультета информатики и вычислительной техники

Петренко Василий г. Славутич, 2005 р. План 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 Справа к таблице присоединяем столбец Ui, в котором записываем минимальные элементы соответствующих строк.

Вычитаем элементы Ui из соответствующих элементов строки матрицы. j i123456Ui 2 Внизу полученной матрицы присоединяем строку Vj, в которой записываем минимальные элементы столбцов. Вычитаем элементы Vj из соответствующих столбцов матрицы. j i Vj000202 3 В результате вычислений получаем матрицу, приведенную по строкам и столбцам, которая изображена в виде таблицы 2. Табл.2 j i 4 Находим константу приведения .

Таким образом, нижней границей множества всех гамильтоновых контуров будет число . 5 Находим степени нулей полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак и устанавливаем сумму минимальных элементов соответствующей строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых . 6 Определяем максимальную степень нуля. Она равна 19 и соответствует клетке 15.

Таким образом, претендентом на включение в гамильтонов контур является дуга 15. 7 Разбиваем множество всех гамильтоновых контуров на два и . Матрицу с дугой 15 получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент 51 на знак . j i Матрицу гамильтоновых контуров получим из таблицы 2 путем замены элемента 15 на знак . j i 9

Делаем дополнительное приведение матрицы контуров 0. Нижняя граница множества равна . 10 Находим константу приведения для множества контуров . Следовательно, нижняя граница множества равна . 11 Сравниваем нижние границы подмножеств и . Так как , то дальнейшему ветвлению подвергаем множество . На рис.1 представлено ветвление по дуге 15. рис.1

Переходим к ветвлению подмножества . Его приведенная матрица представлена в таблице ниже. j i Узнаем степени нулей матрицы. Претендентами на включение в гамильтонов контур будут несколько дуг 52 и 63. Для дальнейших расчетов выберем дугу 63. Разбиваем множество на два подмножества и табл. 3 и 4. Чтобы не допустить образования негамильтонова контура, в таблице 3 заменяем элемент 36 на знак Табл.3 j i124620083220264300501047 Табл.4 j i Определим константы приведения для этих матриц

Следовательно Так как , то дальнейшему ветвлению подлежит подмножество . Находим степени нулей матрицы. j i Претендентом к включению в гамильтонов контур станет дуга 32. Разбиваем множество на два и . j i14620084305104710 j i Очевидно Следовательно, очередному ветвлению нужно подвергнуть подмножество . Переходим к ветвлению подмножества . Его приведенная матрица представлена в таблице ниже. j i14620300843011503737

Определяем степени нулей. Претендентом на включение в гамильтонов контур является дуга 54. Разбиваем множество на два подмножества и . j i16208430 j i146200843053737 Находим нижние границы Следовательно, очередному ветвлению нужно подвергнуть подмножество . Но его матрица имеет размерность . Поэтому в гамильтонов контур следует включить дуги, соответствующие в матрице нулевым элементам. Это дуги 21 и 46. На рис.2 представлено дерево ветвлений.

Определим полученный гамильтонов контур. В него вошли дуги . Длина контура равна . Так как границы оборванных ветвей больше длины контура 1 5 4 6 3 2 1, то этот контура имеет наименьшую длину. рис.25. Выводы Задача коммивояжера является частичным случаем гамильтоновой задачи о путешественнике. Суть задачи коммивояжера состоит в нахождении суммарной минимальной характеристики расстояния, стоимости проезда и т.д при этом коммивояжер должен пройти все n городов по одному разу,

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

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

Такое определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять число , то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину . Используя ЭВМ, методом ветвей и границ можно решить задачи коммивояжера для . 6. Список использованной литературы 1. О. Е. Акимов

Дискретная математика. Логика, группы, графы, Москва, 2003, 376 с ил изд. дом Лаборатория базовых знаний. 2. Ф. А. Новиков Дискретная математика для программистов С Петербург, 2002 г. 304 с ил изд. дом Питер. 3. В. М. Бондарев Основы программирования 1998 г 368 с. изд. дом

Феникс