Филатов_Отчет5_Системный_Анализ
.doc
Наибольшая сумма констант приведения равна 9 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,1*) =126 + 9 =135
Исключение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d21 заменяем на ∞, для исключения образования негамильтонова цикла. (ПОМЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕЕТКА)
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
i j |
2 |
3 |
5 |
6 |
|
1 |
ура |
0 |
8 |
5 |
0 |
3 |
5 |
ура |
1 |
0 |
0 |
4 |
0 |
11 |
ура |
33 |
0 |
6 |
12 |
0 |
0 |
ура |
0 |
|
0 |
0 |
0 |
0 |
|
Нижняя граница подмножества (3,4) равна:
H(2,1) = 126 + 0 = 126
(*5,*4)
(5,4)
(2,1)
(*2,*1)
Шаг №3
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на ∞ и определяем для них сумму образовавшихся констант приведения.
i j |
2 |
3 |
5 |
6 |
|
1 |
ура |
0 |
8 |
5 |
|
3 |
5 |
ура |
1 |
0 |
|
4 |
0 |
11 |
ура |
33 |
|
6 |
12 |
0 |
0 |
ура |
|
|
|
|
|
|
|
i j |
2 |
3 |
5 |
6 |
|
1 |
|
5 |
|
|
|
3 |
|
|
|
6 |
|
4 |
16 |
|
|
|
|
6 |
|
0 |
1 |
|
|
|
|
|
|
|
|
H(4*,2*) = 126+16=142
i j |
3 |
5 |
6 |
|
1 |
0 |
ура |
5 |
0 |
3 |
ура |
1 |
0 |
0 |
6 |
0 |
0 |
ура |
0 |
|
0 |
0 |
0 |
|
H(4,2) = 126
(*5,*4)
(5,4)
(2,1)
(*2,*1)
(*4,*2)
(4,2)
Шаг №4
i j |
3 |
5 |
6 |
|
1 |
0 |
ура |
5 |
|
3 |
ура |
1 |
0 |
|
6 |
0 |
0 |
ура |
|
|
|
|
|
|
i j |
3 |
5 |
6 |
|
1 |
5 |
|
|
|
3 |
|
|
6 |
|
6 |
0 |
1 |
|
|
|
|
|
|
|
H = (3*,6*) =126+6=132
i j |
3 |
5 |
|
1 |
0 |
ура |
|
6 |
ура |
0 |
|
|
|
|
|
H = (3,6) = 126
Остались переходы 1-3, 6-5.
Путь: 5-4-2-1-3-6-5
Длина пути 126.
H(4,2) = 126
(*5,*4)
(5,4)
(2,1)
(*2,*1)
(*4,*2)
(4,2)
(*3,*6)
(3,6)
Ответ: Кротчайший маршрут: 5 4 2 1 3 6 5
Длина маршрута 126
2. Жадный метод
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
∞ |
9 |
8 |
49 |
47 |
13 |
2 |
7 |
∞ |
15 |
40 |
46 |
22 |
3 |
8 |
12 |
∞ |
55 |
39 |
7 |
4 |
35 |
29 |
40 |
∞ |
49 |
62 |
5 |
37 |
34 |
35 |
39 |
∞ |
37 |
6 |
12 |
17 |
5 |
44 |
36 |
∞ |
|
|
|
|
|
|
|
минимальный элемент 5.
Переходы:
из 6 в 3 5
из 3 в 1 8
из 1 во 2 9
из 2 в 4 40
из 4 в 5 49
из 5 в 6 37
Итоговый маршрут: 6-3-1-2-4-5-6. Длина равна 148
Попытаемся еще укоротить маршрут, дополнив данный метод “методом локальных улучшений”
Поочередно меняем местами пары элементов:
6-3-1-2-4-5-6 = 148
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
∞ |
9 |
8 |
49 |
47 |
13 |
2 |
7 |
∞ |
15 |
40 |
46 |
22 |
3 |
8 |
12 |
∞ |
55 |
39 |
7 |
4 |
35 |
29 |
40 |
∞ |
49 |
62 |
5 |
37 |
34 |
35 |
39 |
∞ |
37 |
6 |
12 |
17 |
5 |
44 |
36 |
∞ |
|
|
|
|
|
|
|
Нач. путь |
6 |
1 |
3 |
2 |
4 |
5 |
6 |
Сумма |
Значения |
12 |
8 |
12 |
40 |
49 |
37 |
|
158 |
Путь |
6 |
3 |
1 |
2 |
4 |
5 |
6 |
|
Значения |
5 |
8 |
9 |
40 |
49 |
37 |
|
148 |
Путь |
6 |
1 |
2 |
3 |
4 |
5 |
6 |
|
Значения |
12 |
9 |
15 |
55 |
49 |
37 |
|
177 |
Путь |
6 |
1 |
3 |
4 |
2 |
5 |
6 |
|
Значения |
12 |
8 |
55 |
29 |
46 |
37 |
|
187 |
Путь |
6 |
1 |
3 |
2 |
5 |
4 |
6 |
|
Значения |
12 |
8 |
12 |
46 |
39 |
62 |
|
179 |
Путь |
6 |
1 |
3 |
2 |
4 |
6 |
5 |
|
Значения |
12 |
8 |
12 |
40 |
62 |
36 |
|
170 |
В обрат |
6 |
5 |
4 |
2 |
3 |
1 |
6 |
|
Значения |
36 |
39 |
29 |
15 |
8 |
13 |
|
140 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Нач. путь |
6 |
5 |
4 |
2 |
3 |
1 |
6 |
Сумма |
Значения |
36 |
39 |
29 |
15 |
8 |
13 |
|
140 |
Путь |
6 |
4 |
5 |
2 |
3 |
1 |
6 |
|
Значения |
44 |
49 |
34 |
15 |
8 |
13 |
|
163 |
Путь |
6 |
5 |
2 |
4 |
3 |
1 |
6 |
|
Значения |
36 |
34 |
40 |
40 |
8 |
13 |
|
171 |
Путь |
6 |
5 |
4 |
3 |
2 |
1 |
6 |
|
Значения |
36 |
39 |
40 |
12 |
7 |
13 |
|
147 |
Путь |
6 |
5 |
4 |
2 |
1 |
3 |
6 |
|
Значения |
36 |
39 |
29 |
7 |
8 |
7 |
|
126 |
Путь |
6 |
5 |
4 |
2 |
3 |
6 |
1 |
|
Значения |
36 |
39 |
29 |
15 |
7 |
12 |
|
138 |
В обрат |
6 |
1 |
3 |
2 |
4 |
5 |
6 |
|
Значения |
12 |
8 |
12 |
40 |
49 |
37 |
|
158 |