Оглавление

Введение_________________________________________________________2

Глава 1. Задача о коммивояжере_____________________________________3

1. Общая постановка задачи______________________________________3
2. Математическая модель задачи_______________________________3

Глава 2. Метод ветвей и границ____________________________________5

2.1.    Основные понятия и определения_____________________________5

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

2.3.    Решение задачи методом ветвей и границ_______________________5

Глава 3. Программная реализация метода ветвей и границ_____________12

3.1.    Язык программирования___________________________________12

3.2.    Описание алгоритма_______________________________________12

3.3.    Описание основных структур данных_________________________15

3.4.    Описание интерфейса с пользователем________________________16

Заключение___________________________________________________17

Литература___________________________________________________18

Текст программы______________________________________________19

3. Введение

     Задача  состоит в том, чтобы коммивояжер (торговец) обошел все намеченные города единожды и в таком порядке, чтобы  его путь был наименьшим.

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

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

     Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.

      Глава 1. Задача о  коммивояжере

     1.1. Общая постановка задачи

     Имеется N городов, которые должен обойти коммивояжер  с минимальными затратами. При этом на его маршрут накладывается два ограничения:

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

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

     1.2. Математическая модель задачи и способы её решения

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

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

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

     Минимальным путем будем называть маршрут, проходящий по всем городам и имеющий минимальную  длину.

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

1. промежуточная длина будет расти, когда торговец будет двигаться к конечному городу,
2. а значит длина всего пути будет больше длины минимального маршрута.

     следовательно  такой маршрут можно отбросить.

     Пояснения показаны на рисунке 1.

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

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

Глава 2. Метод ветвей и границ

2.1. Основные понятия  и определения 

     Графом  называется непустое конечное множество, состоящее из двух подмножеств и . Первое подмножество (вершины) состоит из любого множества элементов. Второе подмножество (дуги) состоит из упорядоченных пар элементов первого подмножества . Если вершины и такие, что , то это вершины смежные.

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

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

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

     В терминах теории графов задачу можно  сформулировать следующим образом. Задано n вершин и матрица {c_ij}, где c_ij ≥0 – длинна (или цена) дуги (i, j), . Под маршрутом коммивояжера z будем понимать цикл i₁, i₂,…, i_n, i₁ точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера, длина маршрута l(z) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i₁ – фиксирована. Требуется найти маршрут z₀ Î Z, такой, что l(z₀)= min l(z), z Î Z.

2.3. Решение задачи методом ветвей и границ

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

     Сравнивая нижние границы φ ( ) и φ ( ), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

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

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

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

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

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

     Для выделения претендентов на включение  во множество дуг, по которым производится ветвление, рассмотрим в приведенной  матрице все элементы, равные нулю. Найдем степени Θ_ij нулевых элементов этой матрицы. Степень нулевого элемента Θ_ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c_ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

     Множество маршрутов, не включающих дугу (i, j) получаем путем замены элемента c_ij на бесконечность.

     Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей: 

     Решение задачи

     Для удобства изложения везде ниже в  платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

     Найдем  нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца  число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r₁=15, r₂=1, r₃=0, r₄=16, r₅=5, r₆=5.

     После их вычитания по строкам получим: 
 

     Минимумы  по столбцам: h₁=5, h₂=h₃=h₄=h₅=h₆.

     После их вычитания по столбцам получим  приведенную матрицу: 

     Найдем  нижнюю границу φ(Z) = 15+1+0+16+5+5+5 = 47.

     Для выделения претендентов на включение  во множество дуг, по которым производится ветвление, найдем степени Θ_ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ₁₄ = 10 + 0,  
Θ₂₄ = 1 + 0, Θ₃₆ = 5+0, Θ₄₁ = 0 + 1, Θ₄₂ = 0 + 0, Θ₅₆ = 2 + 0, Θ₆₂ = 0 + 0,  
Θ₆₃ = 0 + 9, Θ₆₅ = 0 + 2. Наибольшая степень Θ₁₄ = 10. Ветвление проводим по дуге (1, 4).

     Нижняя  граница для множества  остается равной 47. Для всех маршрутов множества из города A мы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ ( ) = 47 + 10.

     В матрице, соответствующей  полагаем c₁₄= ∞. 

     После проведения процедуры приведения с r₁=10 получим новую нижнюю границу 57 + 10 = 67.

     В матрице, соответствующей  , вычеркиваем первую строку и четвертый столбец и положим c₄₁= ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c¹_ij}: 

     Для приведения надо вычесть минимум  по первому столбцу: h₁=1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы 
φ ( ) = 67 и φ ( ) = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины.

     Рис. 1. Ветвление на первом шаге

      Приведенная платежная матрица для 

     Далее продолжаем процесс ветвления. Найдем степени Θ_ij нулевых элементов этой матрицы Θ₂₁ =16, Θ₃₆ = 5, Θ₄₂ = 2, Θ₅₆ = 2, Θ₆₂ = 0, Θ₆₃ =9, Θ₆₅ = 2. Наибольшая степень Θ₂₁. Затем множество разбивается дуге (2, 1) на два новых и .

     В матрице для  вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c₄₂= ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2. 

     Для приведения надо вычесть минимум  по строке 4: r₄=2. При этом нижняя граница станет равной 48+2 = 50.

     Нижняя  граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ ( ) = 64 и φ ( ) = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

     Рис. 2. Ветвление на втором шаге 

     Приведенная платежная матрица для   

     Степени Θ_ij нулевых элементов этой матрицы Θ₃₆ = 5, Θ₄₅ = 0, Θ₅₆ = 22, Θ₆₂ = 13, Θ₆₃ =7, Θ₆₅ = 0. Наибольшая степень Θ_56. Затем множество разбивается дуге (2, 1) на два новых и .

     Нижняя  граница для равна 50 + 22 = 72. В матрице для вычеркиваем строку 5 и столбец 6 и полагаем c₆₅= ∞. Получим матрицу: 

     Для приведения надо вычесть минимум  по строке 3: r₃=5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов .