Курсовая работа: Решение задачи коммивояжера методом ветвей и границ
|
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 |
∞ |
12) Узнаем степени нулей
матрицы. Претендентами на включение в гамильтонов контур будут несколько дуг
(5;2) и (6;3). Для дальнейших расчетов выберем дугу (6;3). Разбиваем множество  на два
подмножества: и  (табл. 3 и 4). Чтобы не допустить
образования негамильтонова контура, в таблице 3 заменяем элемент (3;6) на знак
«∞»
Табл.3
|
j
i
|
1 |
2 |
4 |
6 |
| 2 |
0 |
∞ |
0 |
8 |
| 3 |
22 |
0 |
26 |
∞ |
| 4 |
3 |
0 |
∞ |
0 |
| 5 |
∞ |
0 |
10 |
47 |
Табл.4
Страницы: 1, 2, 3, 4
|
