Задача коммивояжера и методы её решения

 

 

 

 

 

 

 

 

Глава 2. Решение задачи коммивояжера разными способами

2.1. Решение задачи коммивояжера жадным алгоритмом

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

 

Рисунок 2.

Жадный алгоритм (иди в ближайший город из города 1) дает тур 1–(4)–3–(3)–5–(5)–4–(11)–6–(10)–2–(6)–1, где без скобок показаны номера вершин, а в скобках – длины ребер. Длина тура равна сумме длин всех ребер: 4+3+5+11+10+6=39.

 

 

 

 

 

 

 

 

2.2. Решение  задачи коммивояжера алгоритмом  Дейкстры.

Необходимо найти все кратчайшие пути от вершины 1 для графа, представленного на рисунке 3.

Рисунок 3

Составим матрицу длин кратчайших дуг для данного графа.

∞	10	18	8	∞	∞
10	∞	16	9	21	∞
∞	16	∞	∞	15	∞
7	9	∞	∞	∞	12
∞	∞	∞	∞	∞	23
∞	∞	15	∞	23	∞

 

 

Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.

Задаем стартовые условия: d(1)=0, d(x)=∞

Окрашиваем вершину 1, y=1.

Находим ближайшую вершину к окрашенной нами, используя формулу: d(x)=min{d(x); d(y)+ ay,x}

 d(2)=min{d(2) ; d(1)+a(1,2)}=min{∞; 0+10}=10

d(3)=min{d(3) ; d(1)+a(1,3)}=min{∞; 0+18}=18

d(4)=min{d(4) ; d(1)+a(1,4)}=min{∞; 0+8}=8

d(5)=min{d(5) ; d(1)+a(1,5)}=min{∞; 0+∞}=∞

d(6)=min{d(6) ; d(1)+a(1,6)}=min{∞; 0+∞}=∞

Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=8. Включаем вершину 4 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,4).

 d(2)=min{d(2) ; d(4)+a(4,2)}=min{10; 8+9}=10

 d(3)=min{d(3) ; d(4)+a(4,3)}=min{18; 8+∞}=18

d(5)=min{d(5) ; d(4)+a(4,5)}=min{∞; 8+∞}=∞

d(6)=min{d(6) ; d(4)+a(4,6)}=min{∞; 8+12}=20

Минимальную длину имеет путь от вершины 1 до вершины 2 d(2)=10. Включаем вершину 2 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,2).

 d(3)=min{d(3) ; d(2)+a(2,3)}=min{18; 10+16}=18

 d(5)=min{d(5) ; d(2)+a(2,5)}=min{∞; 10+21}=31

d(6)=min{d(6) ; d(2)+a(2,6)}=min{20; 10+∞}=20

Минимальную длину имеет путь от вершины 1 до вершины 3 d(3)=18. Включаем вершину 3 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,3).

 d(5)=min{d(5) ; d(3)+a(3,5)}=min{31; 18+15}=31

 d(6)=min{d(6) ; d(3)+a(3,6)}=min{20; 18+∞}=20

Минимальную длину имеет путь от вершины 1 до вершины 6 d(6)=20. Включаем вершину 6 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (4,6).

 

 d(5)=min{d(5) ; d(6)+a(6,5)}=min{31; 20+23}=31

Минимальную длину имеет путь от вершины 1 до вершины 5 d(5)=31. Включаем вершину №5 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (2,5).

Мы получили ориентированное дерево кратчайших путей начинающихся в вершине 1 для исходного графа .

d(1)=1 Длина маршрута L=0

 d(2)=1-2 Длина маршрута L=10

 d(3)=1-3 Длина маршрута L=18

 d(4)=1-4 Длина маршрута L=8

 d(5)=1-2-5 Длина маршрута L=31

 d(6)=1-4-6 Длина маршрута L=20

Ориентированное дерево с корнем в вершине 1:

 

 

 

 

2.3. Решение  задачи коммивояжера алгоритмом  Литтла

Для примера возьмем  граф, представленный в пункте 2.2.

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

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

∞	10	18	8	∞	∞
10	∞	16	9	21	∞
18	16	∞	∞	∞	15
8	9	∞	∞	∞	12
∞	21	∞	∞	∞	23
∞	∞	15	12	23	∞

 

 

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

 

	1	2	3	4	5	6
1	∞	2	10	0	∞	∞
2	1	∞	7	0	12	∞
3	3	1	∞	∞	∞	0
4	0	1	∞	∞	∞	4
5	∞	0	∞	∞	∞	2
6	∞	∞	3	0	11	∞

 

 

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

	1	2	3	4	5	6
1	∞	2	7	0	∞	∞
2	1	∞	4	0	1	∞
3	3	1	∞	∞	∞	0
4	0	1	∞	∞	∞	4
5	∞	0	∞	∞	∞	2
6	∞	∞	0	0	0	∞

 

 

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,4=2, Г2,4=1, Г3,6=3, Г4,1=2, Г5,2=3, Г6,3=4, Г6,4=0, Г6,5=1,

Максимальное значение имеет Г6,3=4

Удалим из матрицы стоимости строку 6 и столбец 3. Внесем в текущий ориентированный граф дугу (6,3).

	1	2	4	5	6
1	∞	2	0	∞	∞
2	1	∞	0	1	∞
3	3	1	∞	∞	0
4	0	1	∞	∞	4
5	∞	0	∞	∞	2

 

 

В строке и столбце отсутствует элемент равный ∞. Присвоим элементу (,) значение бесконечности чтобы избежать преждевременного замыкания контура. Текущая Нижняя граница=87. 
Нижняя граница равна сумме всех вычтенных элементов в строках и столбцах. Итоговое значение нижней границы должно совпасть с длиной результирующего контура. 
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

	1	2	4	5	6
1	∞	2	0	∞	∞
2	1	∞	0	1	∞
3	3	1	∞	∞	0
4	0	1	∞	∞	4
5	∞	0	∞	∞	2

 

 

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

	1	2	4	5	6
1	∞	2	0	∞	∞
2	1	∞	0	0	∞
3	3	1	∞	∞	0
4	0	1	∞	∞	4
5	∞	0	∞	∞	2

 

 

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,4=2, Г2,4=0, Г2,5=100000000, Г3,6=3, Г4,1=2, Г5,2=3,

Максимальное значение имеет Г2,5=100000000

Удалим из матрицы стоимости строку 2 и столбец 5. Внесем в текущий ориентированный граф дугу (2,5).

	1	2	4	6
1	∞	2	0	∞
3	3	1	∞	0
4	0	1	∞	4
5	∞	0	∞	2

 

 

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

Текущая Нижняя граница=88

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

	1	2	4	6
1	∞	2	0	∞
3	3	1	∞	0
4	0	1	∞	4
5	∞	0	∞	2

 

 

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

 

	1	2	4	6
1	∞	2	0	∞
3	3	1	∞	0
4	0	1	∞	4
5	∞	0	∞	2

 

 

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г1,4=100000002, Г3,6=3, Г4,1=4, Г5,2=3,

Максимальное значение имеет Г1,4=100000002

Удалим из матрицы стоимости строку 1 и столбец 4. Внесем в текущий ориентированный граф дугу (1,4).

	1	2	6
3	3	1	0
4	0	1	4
5	∞	0	2

 

 

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

Текущая Нижняя граница=88

Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

	1	2	6
3	3	1	0
4	0	1	∞
5	∞	0	2

 

 

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

	1	2	6
3	3	1	0
4	0	1	∞
5	∞	0	2

 

 

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.

Г3,6=3, Г4,1=4, Г5,2=3,

Максимальное значение имеет Г4,1=4

Удалим из матрицы стоимости строку 4 и столбец 1. Внесем в текущий ориентированный граф дугу (4,1).

	2	6
3	1	0
5	0	2

 

 

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

Текущая Нижняя граница=88

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