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

Лабораторная работа №1. Решение задачи коммивояжёра

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

Для решения следует использовать указанный в варианте способ.

Веса дуг между городами задаются вручную или случайным образом в зависимости от варианта.

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

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

По результатам работы так же отобразить следующую статистику: количество просмотренных маршрутов и время выполнения для 3, 4, 5 и 6 городов в задаче.

 

№	Стартовый город	Веса дуг	Алгоритм
1.	Задается вручную	Случайным образом	Алгоритм Литтла
2.	Случайный	Вручную	Алгоритм полного перебора
3.	Задается вручную	Случайным образом	Венгерский метод
4.	Случайный	Вручную	Метод ветвей и границ
5.	Задается вручную	Случайным образом	Деревянный алгоритм
6.	Случайный	Вручную	Алгоритм Карга-Томпсона
7.	Задается вручную	Случайным образом	Жадный алгоритм
8.	Случайный	Вручную	Алгоритм Литтла
9.	Задается вручную	Случайным образом	Алгоритм полного перебора
10.	Случайный	Вручную	Венгерский метод
11.	Задается вручную	Случайным образом	Метод ветвей и границ
12.	Случайный	Вручную	Деревянный алгоритм
13.	Задается вручную	Случайным образом	Алгоритм Карга-Томпсона
14.	Случайный	Вручную	Жадный алгоритм
15.	Случайный	Случайным образом	Алгоритм Литтла
16.	Задается вручную	Вручную	Алгоритм полного перебора
17.	Случайный	Случайным образом	Венгерский метод
18.	Задается вручную	Вручную	Метод ветвей и границ
19.	Случайный	Случайным образом	Деревянный алгоритм
20.	Задается вручную	Вручную	Алгоритм Карга-Томпсона
21.	Случайный	Случайным образом	Жадный алгоритм
22.	Задается вручную	Вручную	Алгоритм Литтла
23.	Случайный	Случайным образом	Алгоритм полного перебора
24.	Задается вручную	Вручную	Венгерский метод
25.	Случайный	Случайным образом	Метод ветвей и границ
26.	Задается вручную	Вручную	Деревянный алгоритм
27.	Случайный	Случайным образом	Алгоритм Карга-Томпсона
28.	Задается вручную	Вручную	Жадный алгоритм

 

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

Алгоритм Литтла применяют для поиска решения задачи коммивояжера в виде гамильтонова контура. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе, имеющем 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. Получаем гамильтонов контур.

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

http://www.uchimatchast.ru/teory/litl_primer1.php

http://www.uchimatchast.ru/teory/litl_primer2.php

Полный перебор

Метод полного перебора (иногда говорят Метод перебора, подразумевая при этом полный перебор - это не совсем правильно, так как перебор может быть и не полным) заключается в том, что выполняется перебор всех возможных комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся, т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное решение задачи коммивояжера, однако продолжительность таких вычислений может занять непозволительно много времени. Известно, что при значениях n > 12, современный компьютер не смог бы решить задачу коммивояжера даже за все время существования вселенной.

 

Жадный алгоритм

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур. Однако в некоторых ситуациях «жадный» алгоритм определяет-таки кратчайший путь.

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

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

1. Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент. di = min(j) dij

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

3. Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: d_j = min(i) d_ij

4. После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d_i и d_j называются константами приведения.

5. Сумма констант приведения определяет нижнюю границу H

6. Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут. Определяем ребро ветвления и разобъем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

7. Наибольшая сумма констант приведения равна (30 + 0) = 30 для ребра (4,3), следовательно, множество разбивается на два подножества (4,3) и (4*,3*). Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 160 + 30 Исключение ребра (4,3) проводим путем замены элемента d₄₃ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.

8. Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d₃₄ заменяем на М, для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

9. Поскольку нижняя граница этого подмножества (4,3) меньше, чем подмножества (4*,3*), то ребро (4,3) включаем в маршрут. В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (5,2) и (2,1). В результате по дереву ветвлений гамильтонов цикл образуют ребра: По нему и считается длинна и маршрут

http://math.semestr.ru/kom/komm.php