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