Презентация на тему Задача коммивояжера

n городов по критерию времени, стоимости или длине маршрута.

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

(рис. 10.36) с вершинами хi ,

Пропускные способности ребер указаны на графе.


Рис. 10.36

графа G(X,U) рис.10.37.

Рис. 10.37

равную бесконечности, т.е.

(клетки главной диагонали матрицы С) (табл. 10.14).




(10.14)

матрицы (табл. 10.14), т.е. в каждом столбце и строке

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



Табл. 10.14.

min aik, получаем табл. 10.15.


Табл. 10.15

минимальные значения в каждом столбце min aik и получим

приведенную матрицу (табл. 10.16). Сумма констант приведения по строкам и столбцам матрицы составит:
Н= 6 + 7 + 6+ 9+ 5 + 5 + 1+4 = 43.
Сумма констант приведения Н = 43 является границей всех циклов, т.е. любой вариант кольцевого маршрута не может быть меньше этой нижней границы.

вершин графа), которые могут привести к построению оптимального (минимального)

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

и .

Пара вершин (xi, хk) на основании a(i,k), которые рассчитываются для всех клеток приведенной матрицы (10.15), содержащих нули. Для определения a(i,k) в строке xi выбирается минимальный элемент (cik = 0) и минимальный в столбце хк. Эти минимальные элементы складываются, а их сумма равна значению a(i,k).

строках укажем справа, а в столбцах — внизу (табл.

10.16), сумму минимальных элементов запишем в клетках, содержащих нули и отметим их кружком (табл. 10.16). Вычислим a(i,k) для каждой клетки с нулевым элементами:

нулями, отмечая их кружками в табл. 10.16, выбираем наибольшее

значение α(i,k)
Таких значений в табл. 10.16 четыре. Выбираем одно из них, например, α(3,1) = 0 + 4 =4 (для строки х3 и столбца x1.
Вычеркивая их, получаем табл. 10.17, в которой нуль, расположенный в строке х1 и столбце х3, заменяем на ∞, так как вершина х3 не должна иметь цикла (3,1), т.е. c13 =∞

два: и (3,1), рис. 10.39. Нижняя

граница вершины представляет сумму значений нижней границы предыдущей вершины, равной 43 и т.е.

Для определения нижней границы вершины вторым слагаемым берется сумма констант приведения матрицы 10.17. Для приведения этой матрицы из строки х1 следует вычесть минимальный элемент 4 и получим матрицу 10.18.

Нижняя граница вершины (3,1) составит H(3,1) = 43 +

4 = 47 (рис. 10.40).


Рис. 10.40

(3,1) определим α и выберем новую пару вершин, входящих

в концевой маршрут.

строках и столбцах, записанных справа и внизу этой таблицы

соответственно. Вычислим сумму констант приведения α(i,k) и включим их в табл. 10.18:


Табл. 10.18

приведения

в качестве звена в кольцевом маршруте.
В табл. 10.18 вычеркиваем столбец х2 и получаем табл. 10.19:
Табл.10.19

Нижняя граница вершины

определяется из условия ,
Для определения нижней границы вершины (1,2) вторым слагаемым берем сумму констант приведения табл. 10.19, вычитая из строки х2 а25 = 7 и в столбце х3 величину α43 = 5, чтобы матрица имела нули в каждой строке и каждом столбце.
Величина приведения
h = 7 + 5. Н(1,2) = 47 + 7 + 5 = 59.

значения для клеток с нулевыми

элементами:

и столбец х6.
Получаем табл. 10.21:
(10.21)

строки х6 минимальный элемент а64 = 3, Получаем табл.

10.22 в виде:

(10.22)



Строим подграф (рис. 10.42), исключаем в табл. 10.22 строку х6 и столбец х4, так как α(6,4) = 5. Получаем табл. 10.23, в которой α44 = 0. Заменяем ∞ чтобы исключить цикл.

отдельные элементы графа (рис. 10.39-10.43) и гамельтонов цикл обхода

вершин исходного графа (рис. 10.44).

Рис. 10.44

(х5,х6), (х6,х4), (х4,х3).
Длина маршрута обхода вершин x3 → x1

→ x2 → x5→ x6→ x4 → x3 графа G(X,Y) (рис. 10. 37) составляет М = 6 + 11 + 14 + 5 + 12 + 14 = 62 и совпадает с нижней границей графа (рис. 10.45).

границ состоит в следующем:
1. На основании графа посещения

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

которых aik = 0, заменяем поочередно нули на ∞

и вычисляем суммы новых констант приведения H(xi, xk), которые записываем в клетке с нулем, отмеченной кружком.
5. Выбираем ребро ветвления (i,k) по максимальной величине суммы констант приведения Нтах. Затем исключаем его из множества пу­тем замены элемента матрицы а1к =∞. В результате будет опреде­лено подмножество маршрутов {(i,k)}.
6. В полученной матрице расстояний по строкам получаем нули, вычитая минимальное значение элементов в соответсвующих строках и определяем нижнюю границу подмножества маршрутов H(i,k).