Задача коммивояжера

1. ЗАДАЧА КОММИВОЯЖЕРА

Лекция 10
ЗАДАЧА КОММИВОЯЖЕРА

2. СОДЕРЖАНИЕ

1. Текущий контроль
знаний.
2. Задача коммивояжера и
ее решение перебором.
2

3. Текущий контроль знаний

1. По
заданной
матрице
смежности
вершин М
построить
взвешенный
орграф G(X,U)
.
2. Построить
орграф
G’(X’,U’),
двойственный
орграфу
G(X,U).
3. Определить
на G’(X’,U’)
методом
потенциалов
кратчайшие
пути из
источников в
остальные
вершины.
3

4. Содержательные постановки задач коммивояжера

1. Разомкнутая постановка задачи:
коммивояжер должен объехать все n городов,
побывав в каждом по одному разу, и затратив:
- минимум средств на путешествие либо
- минимум средств на максимальный переход.
2. Замкнутая постановка задачи:
коммивояжер должен объехать все n городов,
побывав в каждом по одному разу и вернуться
в город из которого стартовал, затратив
-минимум средств на путешествие либо
- минимум средств на максимальный переход.
4

5. Графовая интерпретация замкнутой задачи коммивояжера

2
3
1
7
4
6
5
Гамильтонов контур а1=1,2,3,4,7,5,6,1 -.
Гамильтонов контур а2=5,3,4,6,1,2,7,5 -.
5

6. Обозначения и определения

G ( X , U ) взвешенный орграф;
Х - множество вершин;
U - множество дуг;
A(G) - множество контуров графа;
a k k й контур множества A(G);
X(a k ) множество вершин k - го контура;
U(a k ) множество дуг k - го контура;
z(i, j) - булева переменная.
6

7. Формальная постановка аддитивной замкнутой задачи коммивояжера

min;
min;
rr((ii,, jj))zz((ii,, jj))
ii
jj
a
A
(
G
)
:
X
(
a
)
X
z
(
i
,
j
)
0
;
a
A
(
G
)
:
X
(
a
)
X
z
(
i
,
j
)
0
;
k
k
k
k
U
U((aakk ))
((ii,, jj))
xxjj
X
X :: zz((ii,, jj)) 11;;
ii
xxqq
X
X :: zz((qq,,ii)) 11;;
ii
((ii,, jj))
U
U :: zz((ii,, jj)) 11,,00..
7

8. Формальная постановка аддитивной разомкнутой задачи коммивояжера

Формальная постановка
аддитивной разомкнутой задачи
r (i, j ) zкоммивояжера
(i, j ) min;
i
j
a k A(G ) : z (i, j ) 0;
( i , j ) U ( a k )
x j X \ ( xs xt ) : z (i, j )
i
z ( s, i ) 1;
i
z (i, t ) 1;
i
z (i, s ) z (t , k ) 0;
k
i
(i, j ) U : z (i, j ) 1,0.
z ( j , k ) 1;
k
8

9. Формальная постановка минимаксной разомкнутой задачи коммивояжера

Формальная постановка
минимаксной разомкнутой задачи
, j ) z (i, j ) min;
max max r (iкоммивояжера
j
i
a k A(G ) : z (i, j ) 0;
( i , j ) U ( a k )
x X \ ( x
j
s xt ) : z (i , j ) z ( j , k ) 1;
i
k
z ( s, i ) 1;
Самостоятельно:
i
дать формальную
z (i, t ) 1;
i
постановку
z (i, s ) z (t , k ) 0; минимаксной
k
i
замкнутой задачи
(i, j ) U : z (i, j ) 1,0. коммивояжера.
9

10. Графовая интерпретация разомкнутой задачи коммивояжера

Стартовая вершина
первого пути.
2
3
1
7
4
6
5
L1=1,2,3,4,7,5,6 -.
L2=5,3,4,6,1,2,7 -.
Стартовая вершина
второго пути.
10

11. Переход от разомкнутой к замкнутой задаче коммивояжера

L1 =1,3,4,2.
9
2
5
3
1
a1 = 0,1,3,4,2,0.
3
2
7 4
3
5
4
3
3
1
0
Стартовая вершина
разомкнутой задачи
коммивояжера
9
7 4
4
3
0
0
0
0
Фиктивная вершина с нулевыми
инцидентными дугами
11

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

L1 =1,3,4,2.
9
2
5
3
1
Таблица перестановок
3
7 4
3
4
Стартовая вершина
разомкнутой задачи
коммивояжера
№
Перестановка вершин
R
1
1,2,3,4
18
2
1,2,4,3
∞
3
1,3,2,4
∞
4
1,3,4,2
14
5
1,4,3,2
∞
6
1,4,2,3
19
САМОСТОЯТЕЛЬНО: дать формальное
описание алгоритма поиска решения
разомкнутой задачи коммивояжера и
построить его блок-схему.
12

13. ПРИНЦИП РАБОТЫ ГЕНЕРАТОРА ПЕРЕСТАНОВОК

№
1-е чи7сло
2-е число
3-е число
Примечание
1
1
2
3
+
2
1
3
1
-
3
1
3
2
+
4
1
3
3
-
5
2
1
1
-
6
2
1
2
-
7
2
1
3
+
8
2
2
1
-
9
2
2
2
-
10
2
2
3
-
11
2
3
1
+
13

14. АЛГОРИТМ РАБОТЫ ГЕНЕРАТОРА ПЕРЕСТАНОВОК

9
Да
Нет
7
8
M(1)>n
Конец алгоритма
1 Ввод n
Получена новая
перестановка
Да
4 i j : M (i) M ( j ) 0
2
M(i)=i; i=1,2,3,…, n
Да
Нет
3 i, M (i ) n
6 i 1 : M (i ) n M (i ) 1;
M (i 1) M (i 1) 1.
Нет
5 M(n)=M(n)+1
14

15. ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА ГЕНЕРАЦИИ ПЕРЕСТАНОВОК

Достоинства:
1. Генерация всех n! перестановок.
2. Простота алгоритма.
3. Легкость программной реализации.
4. Низкие требования к объему памяти
компьютера
Недостатки:
1. В ходе работы алгоритма генерируется
более n! сочетаний различных чисел:
алгоритм избыточен.
2. Сложность распараллеливания алгоритма.
15

16. Выделение всех контуров на орграфе алгоритмом Неметри

Исходный орграф
3
1
2
4
3
1
2
7
9
Дерево выделения всех контуров,
проходящих через вершину «1»
7
2
4
4
1
Самостоятельно выделить контуры, проходящие через
остальные вершины
3
1
16

17. РЕШИТЬ САМОСТОЯТЕЛЬНО

Найти перебором решение минимаксной
разомкнутой задачи коммивояжера на графе
G(X,U) при условии, что стартовой является
вершина «5».
1
7
2
2
1
5
4
9
3
3
6
10
5
4
8
5
17

18. САМОСТОЯТЕЛЬНО:

1. Составить блок-схемы алгоритмов решения
замкнутой и разомкнутой задач
коммивояжера, включающие генератор
перестановок.
2. Программно реализовать построенные
алгоритмы.
3. Построить графики зависимости времени
счета T от размерности задачи n.
4. Пользуясь методом наименьших квадратов
найти аналитические зависимости T(n).
18