Курсовая работа: Решение задачи коммивояжера методом ветвей и границ
|
j
i
|
1 |
2 |
3 |
4 |
5 |
6 |
| 1 |
∞ |
5 |
14 |
19 |
0 |
15 |
| 2 |
0 |
∞ |
8 |
2 |
30 |
10 |
| 3 |
22 |
0 |
∞ |
28 |
14 |
6 |
| 4 |
3 |
0 |
17 |
∞ |
23 |
2 |
| 5 |
7 |
0 |
17 |
12 |
∞ |
49 |
| 6 |
37 |
12 |
0 |
4 |
18 |
∞ |
|
Vj
|
0 |
0 |
0 |
2 |
0 |
2 |
3) В результате
вычислений получаем матрицу, приведенную по строкам и столбцам, которая
изображена в виде таблицы 2.
Табл.2
|
j
i
|
1 |
2 |
3 |
4 |
5 |
6 |
| 1 |
∞ |
5 |
14 |
17 |
019
|
13 |
| 2 |
03
|
∞ |
8 |
02
|
30 |
8 |
| 3 |
22 |
04
|
∞ |
26 |
14 |
4 |
| 4 |
3 |
00
|
17 |
∞ |
23 |
04
|
| 5 |
7 |
07
|
17 |
10 |
∞ |
47 |
| 6 |
37 |
12 |
08
|
2 |
18 |
∞ |
4) Находим константу
приведения
Таким образом, нижней
границей множества всех гамильтоновых контуров будет число
5) Находим степени нулей
полностью приведенной матрицы. Для этого как бы заменяем в ней все нули на знак
«∞» и устанавливаем сумму минимальных элементов соответствующей строки и
столбца. Степени нулей записаны в правых верхних углах клеток, для которых  .
6) Определяем
максимальную степень нуля. Она равна 19 и соответствует клетке (1;5). Таким
образом, претендентом на включение в гамильтонов контур является дуга (1;5).
7) Разбиваем множество
всех гамильтоновых контуров  на два:  и  . Матрицу  с дугой (1;5) получаем табл.2
путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова
контура, заменяем элемент (5;1) на знак «∞».
|
j
i
|
1 |
2 |
3 |
4 |
6 |
| 2 |
0 |
∞ |
8 |
0 |
8 |
| 3 |
22 |
0 |
∞ |
26 |
4 |
| 4 |
3 |
0 |
17 |
∞ |
0 |
| 5 |
∞ |
0 |
17 |
10 |
47 |
| 6 |
37 |
12 |
0 |
2 |
∞ |
8) Матрицу гамильтоновых
контуров  получим
из таблицы 2 путем замены элемента (1;5) на знак «∞».
Страницы: 1, 2, 3, 4
|
