коммивояжер

1.

2.

Задача
коммивояжёра
(англ.
Travelling
salesman
problem,
TSP)
(коммивояжёр
—
странствующий
торговец) — одна из самых известных
задач комбинаторной оптимизации
Имеется n населенных пунктов (n 1)
с заданными между ними расстояниями
aij. Если прямого сообщения между
пунктами i и j не существует, то полагаем
aij= . Так считаем aii= .
Требуется определить такой маршрут, начинающийся в
данном населенном пункте, проходящий через все населенные
пункты по одному разу и заканчивающийся в исходном пункте.

3.

Схема маршрута
Расстояния между населенными пунктами
2
1
3
5
4
3 6 1 4
9 9 3 8
7 1 7 5
1 4 6 1
2 5 1 8

4. Метод ветвей и границ (алгоритм Литтла)

Идея алгоритма: определяют нижнюю оценку (для
задач на минимум) и разделяют исходную матрицу
на две примерно равные части. Затем уменьшают
размер матрицы и определяют «плату» за
уменьшение размера матрицы. Размер платы
может быть или положительный или нулевой., т.е.
увеличивать или не изменять размера нижней
оценки. Размер матрицы уменьшается до 2 2. Затем
выполняют движение в обратном порядке и
получают оптимальный маршрут.

5.

3 6 1 4
9 9 3 8
7 1 7 5
1 4 6 1
2 5 1 8
1
2
3
5
4

6.

Упрощение матрицы
3 6 1 4
9 9 3 8
7 1 7 5
1 4 6 1
2 5 1 8
1
3
1
1
1
2 5 0 3
6 6 0 5
6 0 6 4
0 3 5 0
1 4 0 7
0
0
0
0
0

7.

Исключение дуги, которая приведет к наибольшей
оценки
а) выполнить оценку нулей (сумма минимальных элементов по
строке и столбце)
б) определить элемент с максимальной оценкой
в) замена элемента с максимальной оценкой на
3;2
3
2
2 5 0 3
6 6 05 5
6
6 0 6 4
1
3
0 3 5 0
6
1 4 0 7
2
2 5 0 3
6 6 0 5
6 6 4
0 3 5 0
1 4 0 7

8.

Исключение дуги, чтобы избежать замыкание маршрута
1
2
4
5
1
6
0
1
3
5
6
5
0
4
0
0
7
5
3
5
0
1
(2;3)
2
4
5
1 3 4 5
5 0 3
6 0 5
0 5 0
1 0 7
Проверить упрощение матрицы!!!

9.

Исключение дуги, которая приведет к наибольшей оценки
1 3
4
5
1 3
4
5
1 5 0 3
2 6 0 5
4 0 5 0
5 1 7
3
1 5 0 3
5
2 6 0 5
1
3
4 0 5 0
6
5 1 0 7
5;3
5
3

10.

Исключение дуги, чтобы избежать замыкание маршрута
1
2
4
1 4 5
0 3
6 0 5
0 0
(2;5)
1
2
4
1 4 5
0 3
6 0
0 0
Проверить упрощение матрицы!!!

11.

Исключение дуги, которая приведет к наибольшей оценки
1 4 5
03 3
2 6 06
4 0 6 03
1
1 4 5
1 0 3
2 6
4 0 0
2;4
2
4

12.

Исключение дуги, чтобы избежать замыкание маршрута
1 5
1
3
1
1 5 (4;5)
0
4
0
4
0
0
0
0
0
Проверить упрощение матрицы!!!
2
1
Длина маршрута:
3–2–4–1–5-3
1 +3+1+4+1
3
5
4
= 10

13. Задание для самоподготовки

Телевизионная компания планирует связь кабельной сетью
пять высотных домов. Объемы средств, необходимые для
прокладки кабеля между каждыми двумя домами, показаны
на рисунке. Найти сеть, имеющую наименьшую стоимость.
2
5
а
4
1
9
3
10
9
6
5
8
4
7
3