Курсовая работа: Решение задачи коммивояжера методом ветвей и границ
|
j i |
1 | 2 | 3 | 4 | 5 | 6 |
|
| 1 | ∞ | 5 | 14 | 17 | ∞ | 13 | 5 |
| 2 | 0 | ∞ | 8 | 0 | 30 | 8 |
|
| 3 | 22 | 0 | ∞ | 26 | 14 | 4 |
|
| 4 | 3 | 0 | 17 | ∞ | 23 | 0 |
|
| 5 | 7 | 0 | 17 | 10 | ∞ | 47 |
|
| 6 | 37 | 12 | 0 | 2 | 18 | ∞ |
|
|
14 |
|
|||||
9) Делаем дополнительное
приведение матрицы контуров 
:
= 0. Нижняя граница множества 
равна 
.
10) Находим константу приведения для множества контуров
:
Следовательно, нижняя
граница множества 
равна
11) Сравниваем нижние
границы подмножеств 
и 
. Так как
то дальнейшему ветвлению
подвергаем множество 
.
На рис.1 представлено ветвление по дуге (1;5).
Рис.1
Переходим к ветвлению
подмножества 
. Его приведенная матрица
представлена в таблице ниже.
|
j i |
1 | 2 | 3 | 4 | 6 |
| 2 |
03 |
∞ | 8 |
02 |
8 |
| 3 | 22 |
04 |
∞ | 26 | 4 |
| 4 | 3 |
00 |
17 | ∞ |
04 |
| 5 | ∞ |
010 |
17 | 10 | 47 |
| 6 | 37 | 12 |
010 |
2 | ∞ |
