Выбираем дорогу 6,7.
Отбрасываем 6 строку и 7 столбец.
Движение в обратную сторону, то есть 7,6 уже невозможно и D[7,6]= -.
|
1 |
2 |
3 |
4 |
6 |
8 |
1 |
- |
0 |
0 |
0 |
- |
- |
2 |
0 |
- |
- |
0 |
- |
0 |
3 |
0 |
- |
- |
0 |
- |
- |
4 |
0 |
0 |
0 |
- |
3 |
- |
5 |
- |
2 |
- |
0 |
0 |
- |
7 |
2 |
- |
3 |
0 |
- |
0 |
Приведенное по строкам и столбцам матрицы d.
|
1 |
2 |
3 |
4 |
6 |
8 |
|
|
|
1 |
- |
0 |
0 |
0 |
- |
- |
0 |
Вычитаемых чисел из строк |
|
2 |
0 |
- |
- |
0 |
- |
0 |
0 |
||
3 |
0 |
- |
- |
0 |
- |
- |
0 |
||
4 |
0 |
0 |
0 |
- |
3 |
- |
0 |
||
5 |
- |
2 |
- |
0 |
0 |
- |
0 |
||
7 |
2 |
- |
3 |
0 |
- |
0 |
0 |
||
|
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
Вычитаемых чисел из столбцов
|
|
|||||||
Общая сумма вычитаемых из строк и столбцов будет 0+0=0.
Таким образом меньше чем общая длина циклов обхода всех пунктов в данной ветви уже увеличивается на 0.
Граф ветвей и границ в этот момент будет.
Поиск третьей дороги. Оцениваются нули:
|
1 |
2 |
3 |
4 |
6 |
8 |
||||||
1 |
- |
0 |
0 |
0 |
0 |
0 |
0 |
- |
- |
|||
2 |
0 |
0 |
- |
- |
0 |
0 |
- |
0 |
0 |
|||
3 |
0 |
0 |
- |
- |
0 |
0 |
- |
- |
||||
4 |
0 |
0 |
0 |
0 |
0 |
0 |
- |
3 |
- |
|||
5 |
- |
2 |
- |
0 |
0 |
0 |
3 |
- |
||||
7 |
2 |
- |
3 |
0 |
0 |
- |
0 |
0 |
||||
Самый дорогой ноль D[5,6]=3.
Выбираем дорогу 5,6.
Отбрасываем 5 строку и 6 столбец.
Перемещение по дороге 7,8 ходить нельзя, чтобы замкнуть цикл (в цикле может быть не менее 8 пунктов).
Следовательно, D[7,8] = -.
|
1 |
2 |
3 |
4 |
8 |
1 |
- |
0 |
0 |
0 |
- |
2 |
0 |
- |
- |
0 |
0 |
3 |
0 |
- |
- |
0 |
- |
4 |
0 |
0 |
0 |
- |
- |
7 |
2 |
- |
3 |
0 |
- |
Общая сумма вычитаемых из строк и столбцов будет 0+0=0.
Таким образом меньше чем общая длина циклов обхода всех пунктов в данной ветви уже увеличивается на 0.