Поиск решения задачи коммивояжера на взвешенных ориентированных сильносвязных графах методами типа ветвей и границ

1.

Лекция 14
Поиск решения задачи
коммивояжера на
взвешенных
ориентированных
сильносвязных графах
методами типа ветвей и
границ

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

1.
Постановки задач коммивояжера.
2. Решение замкнутой задачи
коммивояжера методами типа
ветвей и границ.
3. Решение разомкнутой задачи
коммивояжера методами типа
ветвей и границ.

3. Часть 1

ЧАСТЬ 1
Постановки задач
коммивояжера

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

СОДЕРЖАТЕЛЬНЫЕ ПОСТАНОВКИ
«КЛАССИЧЕСКИХ» ЗАДАЧ КОММИВОЯЖЕРА
1. Разомкнутая постановка задачи: коммивояжер
должен объехать все n городов, побывав в
каждом по одному разу, и затратив: - минимум
средств на путешествие либо
- минимум средств на максимальный переход.
2. Замкнутая постановка задачи: коммивояжер
должен объехать все n городов, побывав в
каждом по одному разу и вернуться в город из
которого стартовал, затратив:
-минимум средств на путешествие (аддитивная
задача коммивояжера)
- минимум средств на максимальный переход
(минимаксная задача коммивояжера).
4

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

ГРАФОВАЯ ИНТЕРПРЕТАЦИЯ ЗАМКНУТОЙ
ЗАДАЧИ КОММИВОЯЖЕРА
1
2
3
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. Формальная постановка минимаксной разомкнутой задачи коммивояжера

ФОРМАЛЬНАЯ ПОСТАНОВКА МИНИМАКСНОЙ
РАЗОМКНУТОЙ ЗАДАЧИ КОММИВОЯЖЕРА
max max r (i, j ) z (i, j ) min;
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. Переменные для формальной постановки разомкнутой задачи коммивояжера как функции от перестановки

ПЕРЕМЕННЫЕ
ДЛЯ ФОРМАЛЬНОЙ ПОСТАНОВКИ
РАЗОМКНУТОЙ ЗАДАЧИ КОММИВОЯЖЕРА КАК
ФУНКЦИИ ОТ ПЕРЕСТАНОВКИ
Пусть π = {i1, i2, …., in} – некоторая перестановка
вершин графа G(X,U), |X| = n, где ij – номер
вершины, стоящей на j-м месте в перестановке π.
Пусть переменная y(ij,i(j+1)) определена
следующим образом:
y(ij,i(j+1)) =
r(ij,i(j+1)), если дуга (ij. i(j+1)) принадлежит
множеству U;
∞ в противном случае.

11. формальные постановки задач коммивояжера как функции от перестановки

ФОРМАЛЬНЫЕ ПОСТАНОВКИ ЗАДАЧ КОММИВОЯЖЕРА
КАК ФУНКЦИИ ОТ ПЕРЕСТАНОВКИ
Формальная постановка разомкнутой задачи
коммивояжера:
j n 1
R( ) y (i j , i j 1 );
j 1
R min R( ).
opt
Формальная постановка замкнутой задачи
коммивояжера:
j n 1
R( ) y (i j , i j 1 ) y (in , i1 );
j 1
R min R( ).
opt

12. Часть 2.

ЧАСТЬ 2.
Методы типа ветвей и границ,
осуществляющие поиск
решения замкнутой задачи
коммивояжера на
сильносвязном взвешенном
ориентированном графе.

13. ПРОСТОЙ СПОСОБ ВЫЧИСЛЕНИЯ ОЦЕНКИ

Оценкой является суммарный вес удаленных
дуг.
Пусть I – подмножество удаленных дуг.
Тогда оценка Δ равна:
r(i, j ).
( i , j ) I

14. Простой способ вычисления оценки и фронтальный спуск

ПРОСТОЙ СПОСОБ ВЫЧИСЛЕНИЯ
ОЦЕНКИ И ФРОНТАЛЬНЫЙ СПУСК
Граф G(X,U)
4
2
6
5
1
3
7 3
1
( i , j ) I
2
10
4
r (i, j )
7 оценок;
5 сравнений оценок
6
2
1
( I )
Дерево поиска
13
3
1
4
4
1
2
3
3
12
1
13
R = 13; π=1,2,3,4,1

15. Решить замкнутую задачу коммивояжера самостоятельно, пользуясь МВГ, реализующим фронтальный спуск по дереву ветвлений

РЕШИТЬ ЗАМКНУТУЮ ЗАДАЧУ КОММИВОЯЖЕРА
САМОСТОЯТЕЛЬНО, ПОЛЬЗУЯСЬ МВГ, РЕАЛИЗУЮЩИМ
ФРОНТАЛЬНЫЙ СПУСК ПО ДЕРЕВУ ВЕТВЛЕНИЙ
0
3
4
7
0
5
2
1
0
1
0
8
3
1
0
2
4
7
0
0
2
8
7
0
4
0
5
6
2
0
9
2
5
0
4
1
10
0
1
5
0
5
0
7
1
2
0
4
2
0
7
3
4
0
9
0
8
9
0
2
10
12
0
3
1
11
0
0
6
7
3
0
8
4
5
0
0
10
11
7
0
12
8
9
0
3
0
5
6
1
0
2
10
3
0
4
8
3
0
6
0
5
6
4
0
6
3
9
0
7
0
8
7
9
0
4
6
5
0
8
7
0
3
6
4
0
10
0
5
6
11
0
12
4
7
0
11
0
8
2
3
0
7
9
1
0
12
13
0
8
9
17
0
2
16
14
0
14
0
5
16
11
0
13
14
17
0
15
0
18
12
13
0
17
10
2
0
16
17
0
7
8
4
0
9
5
6
0
18
0
3
14
9
0
11
12
15
0
19
0
11
15
16
0
20
13
5
0
20
21
0
12
13
9
0
14
10
11
0
22
0
9
20
15
0
17
18
21
0
23
0
18
22
23
0
27
30
12
0
24

16. УТОЧНЕННЫЙ СПОСОБ ВЫЧИСЛЕНИЯ ОЦЕНКИ

Оценкой является сумма, включающая
суммарный вес удаленных дуг и суммарный
вес дуг с минимальным весом, заходящих в
вершины, соответствующие городам, в которые
коммивояжер еще не въезжал.
Пусть I – подмножество удаленных дуг, а J –
подмножество вершин, соответствующих
городам, в которые коммивояжер еще не
въезжал.
Тогда оценка Δ равна:
( i , j ) I
r (i, j ) min r (i, j ).
j J
i

17. ПРИМЕР ВЫЧИСЛЕНИЯ УТОЧНЕННОЙ ОЦЕНКИ

Пусть I = {(3,1)} – подмножество удаленных
дуг, а J = {2,3,4} – подмножество вершин,
соответствующих городам, в которые
коммивояжер еще не въезжал.
Тогда оценка Δ равна: Δ = 4 + {1+3+5} = 13.
1
7
2
9 8
4
3
3
5
4
1

18. Уточненный способ вычисления оценки и фронтальный спуск

УТОЧНЕННЫЙ СПОСОБ ВЫЧИСЛЕНИЯ
ОЦЕНКИ И ФРОНТАЛЬНЫЙ СПУСК
Граф G(X,U)
4
2
6
Дерево поиска
1
3
5
7 3
1
12
2
4
r (i, j )
( i , j ) I
x j X \ X ( I )
17
3
4
13
4
1
min r (i, j ).
i
2
13
1
( I )
7 оценок;
3 сравнения оценок
3
1
13
R = 13; π=1,2,3,4,1

19. САМОСТОЯТЕЛЬНО

Решить замкнутую задачу коммивояжера
фронтальным спуском по дереву ветвлений на
графе G(X,U), пользуясь простым и
усложненным методами вычисления оценки:
2
2
7
3
6
1
5
3
4
1
8
4

20. Простой способ вычисления оценки и поиск с возвратом

ПРОСТОЙ СПОСОБ ВЫЧИСЛЕНИЯ
ОЦЕНКИ И ПОИСК С ВОЗВРАТОМ
Граф G(X,U)
4
2
6
5
Дерево поиска
1
3
7 3
1
6
2
4
3
1
12
( I )
r (i, j )
( i , j ) I
2
10
1
13
4
4
13
7 оценок;
5 сравнений оценок
1
3
R = 13; π =1,2,3,4,1

21. Уточненный способ вычисления оценки и поиск с возвратом

УТОЧНЕННЫЙ СПОСОБ ВЫЧИСЛЕНИЯ
ОЦЕНКИ И ПОИСК С ВОЗВРАТОМ
Граф G(X,U)
4
2
6
Дерево поиска
1
3
5
7 3
1
12
2
13
4
3
1
( I )
r (i, j )
x j X \ X ( I )
4
1
min r (i, j ).
i
17
4
13
( i , j ) I
2
3
13 1
R = 13; π=1,2,3,4,1

22. САМОСТОЯТЕЛЬНО

Определить решение замкнутой задачи
коммивояжера, осуществляя поиск с возвратом по
дереву ветвлений на графе G(X,U), и пользуясь
простым и усложненным методами вычисления
оценки.
2
2
7
3
6
1
5
3
4
1
8
4

23. ЧАСТЬ 3

РЕШЕНИЕ
РАЗОМКНУТОЙ
ЗАДАЧИ
КОММИВОЯЖЕРА
МЕТОДАМИ ТИПА
ВЕТВЕЙ И ГРАНИЦ

24. АЛГОРИТМ ПЕРЕХОДА ОТ РАЗОМКНУТОЙ «КЛАССИЧЕСКОЙ» ЗАДАЧИ КОММИВОЯЖЕРА К ЗАМКНУТОЙ

Пусть задан орграф G’(X’,U’) на котором
следует решить разомкнутую задачу
коммивояжера при условии, что выделена
стартовая вершина xs и терминальная
вершина xt .
Преобразуем G’(X’,U,) в орграф G”(X’,U”)
добавлением дуги (t,s), обладающей нулевым
весом.
На орграфе G”(X’,U”) ищется оптимальное
решение замкнутой задачи коммивояжера.
Отбрасывая в полученном на предыдущем
шаге подмножестве дуг, дугу (t,s), получим
решение разомкнутой задачи коммивояжера.

25. ПРИМЕР

0
1
3
S
7
t
1
2
8
3
5
5
1
s
7
t
1
8
4
2
б) Граф G”(X’,U”)
4
a) Граф G’(X’,U’)
1
s
1
t
2
в) Решение замкнутой задачи
коммивояжера на G”(X’,U”).
t
s
2
Г) Решение разомкнутой
задачи коммивояжера на
G’(X’,U’).

26. Эквивалентные преобразования графа, на котором решается разомкнутая задача коммивояжера

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ГРАФА, НА КОТОРОМ
РЕШАЕТСЯ РАЗОМКНУТАЯ ЗАДАЧА КОММИВОЯЖЕРА
1.
Если на исходном графе существует
дуга, ведущая из стартовой вершины в
терминальную, то она может быть
отброшена.
Если на исходном графе существуют
дуги, ведущие в стартовую вершину, то
они могут быть отброшены.
Если на исходном графе существуют
дуги, ведущие из терминальной
вершины, то они могут быть отброшены.

27. ПРИМЕР ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ГРАФА

Исходный граф G(X,U)
(s=1, t=3)
12 дуг
Преобразованный граф
G(X,U)
6 дуг
2
3
1
4
2
1
3
4

28. САМОСТОЯТЕЛЬНО

Определить решение методом типа ветвей и границ
разомкнутой задачи коммивояжера фронтальным
спуском по дереву ветвлений на графе G(X,U) и поиском
с возвратом, пользуясь:
а) переходом к замкнутой задаче;
б) простым и усложненным методами вычисления
оценки.
G(X,U)
2
2
1
4
3
6
7
5
s = 2; t = 3.
3
4
1
8
4

29. САМОСТОЯТЕЛЬНО

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