Материал: 5462
86
которых лежит комбинаторная структура задачи (методы ветвей и границ, динамического программирования).
Задача о коммивояжере в математической постановке эквивалента задаче упорядочения конечного цикла наладочных работ на машине при учете потерь от переналадок.
|
Рассмотрим решение задачи коммивояжера методом ветвей и границ |
|||
(алгоритм Литтла). |
|
|
|
|
|
Этот алгоритм можно сформулировать в виде следующих правил: |
|||
1. |
Находим в каждой строке матрицы С |
(Сij ) минимальный элемент |
||
ui |
min (Cij ) и вычитаем его из всех элементов соответствующей строки. |
|||
|
j 1,n |
|
|
|
В результате получаем матрицу C , приведенную по строкам. Каждый |
||||
элемент этой матрицы определяется по формуле Cij Cij ui . |
||||
2. |
Находим минимальный элемент |
v j в каждом столбце матрицы C : |
||
v j |
min (Cij ). Матрицу C , |
приведенную |
по столбцам, получаем с |
|
|
i 1,n |
|
|
|
помощью преобразования Cij |
Cij |
v j . |
|
|
3. Находим константу приведения 
ui 
v j .
i j
4. Находим степени нулей для приведенной по строкам и столбцам матрицы C
:
rs |
min Cis |
min Crj . |
||
|
i 1,n |
i r |
j 1,n |
j s |
|
|
|
||
Записываем соответствующую степень в правом верхнем углу клетки r, s
5. Выбираем дугу r , s |
, |
для |
которой степень |
|
нулевого |
|
элемента |
|||||||||||
наибольшая: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
r |
|
s |
|
|
max |
rs . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(r, s) |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
6. Выходим на две ветви |
P |
|
|
|
и |
|
Pr s . Ветвь P |
|
содержит переход |
|||||||||
|
|
|
r |
s |
|
|
|
|
|
|
r |
s |
|
|
|
|
|
|
r , s , а |
|
r s – не содержит. Для получения расчетной матрицы |
|
|
|
|||||||||||||
P |
P |
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r |
s |
|
вычеркиваем в матрице C строку r и столбец s . Заменяем C |
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
s |
r |
|
|
|
|
(симметричный элемент) на , чтобы не допустить образования подцикла. 7. Находим приведенную по строкам и столбцам матрицу Рr s и отделяем
ее константу приведения h. Тогда нижняя граница ветви определяется по
формуле |
r s |
h . |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
8. Для получения расчетной матрицы Pr s |
заменяем элемент C |
|
|
на . |
||||
|
|
|
|
|
r |
|
s |
|
87
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9. |
Находим приведенную |
|
по |
строкам |
и |
столбцам |
матрицу |
P r s |
и |
|||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||
определяем ее константу приведения |
|
h . Тогда нижняя граница ветви |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
определяется по формуле |
r |
|
s |
|
h . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
10. |
Сравниваем нижние |
|
|
|
границы |
ветвей. |
|
Если |
|
|
|
|
|
r s , |
то |
|||||||
|
|
|
|
r |
|
s |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
дальнейшему ветвлению подлежит вариант |
P |
|
, в противном случае – |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
r |
s |
|
|
|
|
|
|
|
|
|
вариант Pr s и т.д.
11.Если в результате ветвления получаем размерность сокращенной матрицы 2 2 , то определяем полученный маршрут и его длину (рекорд). В противном случае переходим к шагу 12.
12.Формируем вариант маршрута на базе законченной ветви и определяем его протяженность. Если длина маршрута не превышает нижних границ оборванных ветвей (незаконченных ветвлений), то задача решена. В противном случае развиваем ветви подмножеств с нижней границей, меньшей полученного маршрута до тех пор, пока не получим маршрут с меньшей длиной или не убедимся, что такого не существует.
Пример решения задачи коммивояжера.
Решить задачу для матрицы расстояний в табл. 11
Таблица 11
|
|
|
|
|
|
|
|
|
|
P0 |
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
1 |
2 |
|
3 |
|
4 |
5 |
ui |
|
||
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
30 |
40 |
|
15 |
6 |
6 |
|
||
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2 |
|
10 |
|
18 |
|
9 |
7 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
20 |
30 |
|
|
|
1 |
10 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
25 |
10 |
35 |
|
|
5 |
5 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
9 |
8 |
7 |
|
6 |
|
6 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
1. Справа к табл. 11 присоединяем столбец ui , в котором записываем минимальные элементы строк. Вычитаем ui из соответствующих
элементов матрицы С, получим матрицу, приведенную по строкам (табл.
12):
88
Таблица 12
С
|
j |
|
|
|
|
|
|
|
i |
1 |
2 |
|
3 |
|
4 |
5 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
24 |
34 |
|
9 |
0 |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
||
2 |
|
3 |
|
11 |
|
2 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
19 |
29 |
|
|
|
0 |
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
20 |
5 |
30 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
3 |
2 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
vj |
|
3 |
2 |
1 |
|
0 |
0 |
|
2. Внизу матрицы 12 присоединяем строку |
v j , |
в которой записываем |
|||||||||||||||
минимальные элементы |
|
столбцов. |
Вычитаем |
|
элементы v j из |
||||||||||||
соответствующих столбцов матрицы C . Получим матрицу C , |
|||||||||||||||||
приведенную по столбцам (табл. 13) |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 13 |
|
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
1 |
|
2 |
|
|
|
3 |
|
4 |
5 |
||||||
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
||
1 |
|
|
|
|
22 |
|
|
33 |
|
9 |
|||||||
|
|
|
|
|
|
|
0 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
0 |
|
|
|
|
|
|
|
|
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
2 |
|
|
0 |
|
|
|
|
|
10 |
2 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
16 |
|
27 |
|
|
|
|
0 |
9 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
||
|
4 |
|
|
17 |
|
3 |
|
|
29 |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
0 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
3 |
|
|
|
10 |
|
0 |
|
|
|
|
5 |
|
|
|
0 |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
0 |
|
0 |
|
|
0 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
89
3. Находим константу приведения
ui |
v j |
25 6 |
31. |
|
i |
j |
|
|
|
Нижней |
границей |
(P0 ) множества всех маршрутов |
будет число |
|
31 z(x) . |
|
|
|
|
4. Находим |
степени |
нулей полностью приведенной |
матрицы C |
|
(табл. 13), равные сумме минимальных элементов соответствующих строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых Сij 0 .
5.Определяем максимальную степень нуля. Она равна 10 и соответствует клетке (5,3). Строим дерево ветвлений (рис. 9).
6.Разбиваем множество всех маршрутов Р0 на два: P531 и P153 . Матрицу
P531 с дугой (5,3) получаем из табл. 13 вычеркиваем пятой строки и
третьего столбца. Чтобы не допустить образования подциклов заменяем элемент (3,5) на (табл. 14).
Таблица 14
|
|
|
|
|
|
|
|
|
|
P531 |
|
|
|
|
vj |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ui |
||||
|
|
|
|
|
|
|
|||||
ui |
|
1 |
2 |
4 |
5 |
||||||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
22 |
9 |
0 |
0 |
|
||||
|
|
|
|
|
|
2 |
|
|
|
||
|
|
|
|
|
|
|
|
||||
|
2 |
|
0 |
|
0 |
0 |
|
||||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|||
|
3 |
|
16 |
27 |
0 |
|
0 |
|
|||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|||
|
4 |
|
17 |
3 |
|
0 |
0 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
vj |
|
0 |
3 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
7. Матрицу маршрутов |
|
153 |
|
|
|
|
|
|
|
|
|
P |
получим из табл. 13 путем замены элемента |
||||||||||
С53 на ∞ (табл. 15) |
|
|
|
|
|
|
|
|
|||
90
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
153 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
||
|
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
1 |
2 |
|
3 |
|
4 |
5 |
|
|
|
|
ui |
|||||
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
22 |
33 |
|
9 |
|
|
0 |
|
0 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
2 |
0 |
|
10 |
|
0 |
|
2 |
0 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
3 |
16 |
27 |
|
|
|
0 |
|
9 |
0 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
4 |
17 |
3 |
29 |
|
|
0 |
0 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
5 |
0 |
0 |
|
|
|
0 |
|
|
|
|
|
0 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
vj |
0 |
0 |
10 |
|
0 |
0 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8. Приводим матрицы P531 и P153 по строкам и столбцам. Константа приведения для матрицы P531 :
|
|
h531 |
3. |
|
|
|
|
|
|
|
|
||
Нижняя граница множества P531 : |
|
|
|
|
|
|
|
|
|
||||
|
|
(P531 ) 31 |
3 |
34 . |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
153 : |
|
153 |
|
||
9. Находим константу приведения для множества маршрутов |
P |
h |
10 . |
||||||||||
Следовательно, нижняя граница ( |
|
153 ) |
|
10 41. |
|
|
|
|
|
|
|
||
P |
31 |
|
|
|
|
|
|
|
|||||
10. Сравниваем нижние границы подмножеств P531 и |
|
153 . Так как 34 |
|
||||||||||
P |
41, |
||||||||||||
то дальнейшему ветвлению подвергаем множество P531 (табл. 14). |
|
||||||||||||
Делаем дополнительное приведение матрицы маршрутов |
P531 . |
||||||||||||
Приведенная матрица |
|
153 представлена в табл. 16. |
|
||||||||||
P |
|
||||||||||||