Метод ветвей и границ

Вычитание минимумов по строке

	1	2	3	4	5	6	7
1	INF	6	40	36	39	80	94
2	4	INF	61	3	98	26	26
3	81	4	INF	97	97	93	18
4	12	84	17	INF	24	56	65
5	69	25	65	97	INF	10	0
6	1	83	20	35	22	INF	67
7	12	56	23	18	68	44	INF

Нахождение минимальных по строкам

Мнимальные по строкам:6 3 4 12 0 1 12

Почти новая мин граница 38

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 5 0 12 10 0

Новая мин граница 65

Результат вычитания минимумов по столбцам

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=21
(2:4)=7
(3:2)=14
(4:1)=0
(4:3)=6
(4:5)=9
(5:6)=13
(5:7)=14
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:21 7 14 9 14 9 6

Максимальная степень 0 находятся на позициях (1:2)

Нули на предыдущих этапах:(1:2)

Начинаем разделение

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

(1:2)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (1,2)

	1	2	3	4	5	6	7
1	INF	INF	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

Вычитание минимумов по строке

	1	2	3	4	5	6	7
1	INF	INF	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

Нахождение минимальных по строкам

Мнимальные по строкам:21 0 0 0 0 0 0

Почти новая мин граница 86

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0 0 0

Новая мин граница 86

Результат вычитания минимумов по столбцам

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:5)=8
(2:4)=7
(3:2)=39
(4:1)=0
(4:3)=6
(4:5)=0
(5:6)=13
(5:7)=14
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:8 7 39 6 14 9 6

Максимальная степень 0 находятся на позициях (3:2)

Удаление из матрицы 1:2

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

Результат удаления из матрицы 1:2

	1	3	4	5	6	7
2	1	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (1,2)

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Вычитание минимумов по строке

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 14 0 0 0 0

Почти новая мин граница 79

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0 0

Новая мин граница 79

Результат вычитания минимумов по столбцам

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	63	INF	79	67	65	0
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(2:4)=19
(3:7)=63
(4:1)=0
(4:3)=6
(4:5)=9
(5:6)=13
(5:7)=0
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:19 63 9 13 9 6

Максимальная степень 0 находятся на позициях (3:7)

Граница у несодержащего ребро (1,2):86 у содержащего79

Нули на предыдущих этапах:(3:7) (1:2)

Начинаем разделение

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	63	INF	79	67	65	0
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

(3:7)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (3,7)

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	63	INF	79	67	65	INF
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Вычитание минимумов по строке

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	63	INF	79	67	65	INF
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 63 0 0 0 0

Почти новая мин граница 142

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0 0

Новая мин граница 142

Результат вычитания минимумов по столбцам

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	0	INF	16	4	2	INF
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(2:4)=19
(3:1)=2
(4:1)=0
(4:3)=6
(4:5)=4
(5:6)=2
(5:7)=23
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:19 2 6 23 9 6

Максимальная степень 0 находятся на позициях (5:7)

Удаление из матрицы 3:7

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	63	INF	79	67	65	0
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Результат удаления из матрицы 3:7

	1	3	4	5	6
2	INF	53	0	83	13
4	0	0	INF	0	34
5	69	60	97	INF	0
6	0	14	34	9	INF
7	0	6	6	44	22

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (3,7)

	1	3	4	5	6
2	INF	53	0	83	13
4	0	0	INF	0	34
5	69	60	97	INF	0
6	0	14	34	9	INF
7	0	INF	6	44	22

Вычитание минимумов по строке

	1	3	4	5	6
2	INF	53	0	83	13
4	0	0	INF	0	34
5	69	60	97	INF	0
6	0	14	34	9	INF
7	0	INF	6	44	22

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0

Почти новая мин граница 79

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0

Новая мин граница 79

Результат вычитания минимумов по столбцам

	1	3	4	5	6
2	INF	53	0	83	13
4	0	0	INF	0	34
5	69	60	97	INF	0
6	0	14	34	9	INF
7	0	INF	6	44	22

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(2:4)=19
(4:1)=0
(4:3)=14
(4:5)=9
(5:6)=73
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:19 14 73 9 6

Максимальная степень 0 находятся на позициях (5:6)

Граница у несодержащего ребро (3,7):142 у содержащего79

Нули на предыдущих этапах:(5:6) (3:7) (1:2)

Начинаем разделение

	1	3	4	5	6
2	INF	53	0	83	13
4	0	0	INF	0	34
5	69	60	97	INF	0
6	0	14	34	9	INF
7	0	INF	6	44	22

(5:6)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (5,6)

	1	3	4	5	6
2	INF	53	0	83	13
4	0	0	INF	0	34
5	69	60	97	INF	INF
6	0	14	34	9	INF
7	0	INF	6	44	22

Вычитание минимумов по строке

	1	3	4	5	6
2	INF	53	0	83	13
4	0	0	INF	0	34
5	69	60	97	INF	INF
6	0	14	34	9	INF
7	0	INF	6	44	22

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 60 0 0

Почти новая мин граница 139

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 13

Новая мин граница 152

Результат вычитания минимумов по столбцам

	1	3	4	5	6
2	INF	53	0	83	0
4	0	0	INF	0	21
5	9	0	37	INF	INF
6	0	14	34	9	INF
7	0	INF	6	44	9

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(2:4)=6
(2:6)=9
(4:1)=0
(4:3)=0
(4:5)=9
(5:3)=9
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:9 9 9 9 6

Максимальная степень 0 находятся на позициях (2:6)

Удаление из матрицы 5:6

	1	3	4	5	6
2	INF	53	0	83	13
4	0	0	INF	0	34
5	69	60	97	INF	0
6	0	14	34	9	INF
7	0	INF	6	44	22

Результат удаления из матрицы 5:6

	1	3	4	5
2	INF	53	0	83
4	0	0	INF	0
6	0	14	34	9
7	0	INF	6	44

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (5,6)

	1	3	4	5
2	INF	53	0	83
4	0	0	INF	0
6	0	14	34	INF
7	0	INF	6	44

Вычитание минимумов по строке

	1	3	4	5
2	INF	53	0	83
4	0	0	INF	0
6	0	14	34	INF
7	0	INF	6	44

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0

Почти новая мин граница 79

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0

Новая мин граница 79

Результат вычитания минимумов по столбцам

	1	3	4	5
2	INF	53	0	83
4	0	0	INF	0
6	0	14	34	INF
7	0	INF	6	44

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(2:4)=59
(4:1)=0
(4:3)=14
(4:5)=44
(6:1)=14
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:59 44 14 6

Максимальная степень 0 находятся на позициях (2:4)

Граница у несодержащего ребро (5,6):152 у содержащего79

Нули на предыдущих этапах:(2:4) (5:6) (3:7) (1:2)

Начинаем разделение

	1	3	4	5
2	INF	53	0	83
4	0	0	INF	0
6	0	14	34	INF
7	0	INF	6	44

(2:4)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (2,4)

	1	3	4	5
2	INF	53	INF	83
4	0	0	INF	0
6	0	14	34	INF
7	0	INF	6	44

Вычитание минимумов по строке

	1	3	4	5
2	INF	53	INF	83
4	0	0	INF	0
6	0	14	34	INF
7	0	INF	6	44

Нахождение минимальных по строкам

Мнимальные по строкам:53 0 0 0

Почти новая мин граница 132

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 6 0

Новая мин граница 138

Результат вычитания минимумов по столбцам

	1	3	4	5
2	INF	0	INF	30
4	0	0	INF	0
6	0	14	28	INF
7	0	INF	0	44

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(2:3)=30
(4:1)=0
(4:3)=0
(4:5)=30
(6:1)=14
(7:1)=0
(7:4)=28

Конец подсчета штрафов у нулей

Максимумы по строкам:30 30 14 28

Максимальная степень 0 находятся на позициях (2:3)

Удаление из матрицы 2:4

	1	3	4	5
2	INF	53	0	83
4	0	0	INF	0
6	0	14	34	INF
7	0	INF	6	44

Результат удаления из матрицы 2:4

	1	3	5
4	0	0	0
6	0	14	INF
7	0	INF	44

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (2,4)

	1	3	5
4	0	0	0
6	0	14	INF
7	0	INF	44

Вычитание минимумов по строке

	1	3	5
4	0	0	0
6	0	14	INF
7	0	INF	44

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0

Почти новая мин граница 79

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0

Новая мин граница 79

Результат вычитания минимумов по столбцам

	1	3	5
4	0	0	0
6	0	14	INF
7	0	INF	44

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(4:1)=0
(4:3)=14
(4:5)=44
(6:1)=14
(7:1)=44

Конец подсчета штрафов у нулей

Максимумы по строкам:44 14 44

Максимальная степень 0 находятся на позициях (4:5)

Граница у несодержащего ребро (2,4):138 у содержащего79

Нули на предыдущих этапах:(4:5) (2:4) (5:6) (3:7) (1:2)

Начинаем разделение

	1	3	5
4	0	0	0
6	0	14	INF
7	0	INF	44

(4:5)

Поиск циклов

Цикл найден. уничтожен [1][4]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (4,5)

	1	3	5
4	INF	0	INF
6	0	14	INF
7	0	INF	44

Вычитание минимумов по строке

	1	3	5
4	INF	0	INF
6	0	14	INF
7	0	INF	44

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0

Почти новая мин граница 79

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 44

Новая мин граница 123

Результат вычитания минимумов по столбцам

	1	3	5
4	INF	0	INF
6	0	14	INF
7	0	INF	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(4:3)=14
(6:1)=14
(7:1)=0
(7:5)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:14 14 0

Максимальная степень 0 находятся на позициях (4:3)

Удаление из матрицы 4:5

	1	3	5
4	0	0	0
6	0	14	INF
7	0	INF	44

Результат удаления из матрицы 4:5

	1	3
6	0	14
7	0	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (4,5)

	1	3
6	0	14
7	0	INF

Вычитание минимумов по строке

	1	3
6	0	14
7	0	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0

Почти новая мин граница 79

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 14

Новая мин граница 93

Результат вычитания минимумов по столбцам

	1	3
6	0	0
7	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(6:1)=0
(6:3)=0
(7:1)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0 0

Максимальная степень 0 находятся на позициях (6:1)

Граница у несодержащего ребро (4,5):123 у содержащего93

Нули на предыдущих этапах:(3:2) (1:2)

Начинаем разделение

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

(3:2)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (3,2)

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	77	INF	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

Вычитание минимумов по строке

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	77	INF	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 14 0 0 0 0

Почти новая мин граница 100

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 25 0 0 0 0 0

Новая мин граница 125

Результат вычитания минимумов по столбцам

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	63	INF	INF	79	67	65	0
4	0	47	0	INF	0	34	53
5	69	0	60	97	INF	0	0
6	0	57	14	34	9	INF	66
7	0	19	6	6	44	22	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:5)=8
(2:4)=7
(3:7)=63
(4:1)=0
(4:3)=6
(4:5)=0
(5:2)=19
(5:6)=13
(5:7)=0
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:8 7 63 6 19 9 6

Максимальная степень 0 находятся на позициях (3:7)

Удаление из матрицы 3:2

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

Результат удаления из матрицы 3:2

	1	3	4	5	6	7
1	INF	8	9	0	43	67
2	1	53	0	83	13	23
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (3,2)

	1	3	4	5	6	7
1	INF	8	9	0	43	67
2	1	INF	0	83	13	23
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Вычитание минимумов по строке

	1	3	4	5	6	7
1	INF	8	9	0	43	67
2	1	INF	0	83	13	23
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0 0

Почти новая мин граница 86

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0 0

Новая мин граница 86

Результат вычитания минимумов по столбцам

	1	3	4	5	6	7
1	INF	8	9	0	43	67
2	1	INF	0	83	13	23
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:5)=8
(2:4)=7
(4:1)=0
(4:3)=6
(4:5)=0
(5:6)=13
(5:7)=23
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:8 7 6 23 9 6

Максимальная степень 0 находятся на позициях (5:7)

Граница у несодержащего ребро (3,2):125 у содержащего86

Нули на предыдущих этапах:(5:7) (3:2) (1:2)

Начинаем разделение

	1	3	4	5	6	7
1	INF	8	9	0	43	67
2	1	INF	0	83	13	23
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

(5:7)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (5,7)

	1	3	4	5	6	7
1	INF	8	9	0	43	67
2	1	INF	0	83	13	23
4	0	0	INF	0	34	53
5	69	60	97	INF	0	INF
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Вычитание минимумов по строке

	1	3	4	5	6	7
1	INF	8	9	0	43	67
2	1	INF	0	83	13	23
4	0	0	INF	0	34	53
5	69	60	97	INF	0	INF
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0 0

Почти новая мин граница 86

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 0 23

Новая мин граница 109

Результат вычитания минимумов по столбцам

	1	3	4	5	6	7
1	INF	8	9	0	43	44
2	1	INF	0	83	13	0
4	0	0	INF	0	34	30
5	69	60	97	INF	0	INF
6	0	14	34	9	INF	43
7	0	6	6	44	22	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:5)=8
(2:4)=6
(2:7)=30
(4:1)=0
(4:3)=6
(4:5)=0
(5:6)=73
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:8 30 6 73 9 6

Максимальная степень 0 находятся на позициях (5:6)

Удаление из матрицы 5:7

	1	3	4	5	6	7
1	INF	8	9	0	43	67
2	1	INF	0	83	13	23
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Результат удаления из матрицы 5:7

	1	3	4	5	6
1	INF	8	9	0	43
2	1	INF	0	83	13
4	0	0	INF	0	34
6	0	14	34	9	INF
7	0	6	6	44	22

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (5,7)

	1	3	4	5	6
1	INF	8	9	0	43
2	1	INF	0	83	13
4	0	0	INF	0	34
6	0	14	34	9	INF
7	0	6	6	INF	22

Вычитание минимумов по строке

	1	3	4	5	6
1	INF	8	9	0	43
2	1	INF	0	83	13
4	0	0	INF	0	34
6	0	14	34	9	INF
7	0	6	6	INF	22

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0

Почти новая мин граница 86

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 13

Новая мин граница 99

Результат вычитания минимумов по столбцам

	1	3	4	5	6
1	INF	8	9	0	30
2	1	INF	0	83	0
4	0	0	INF	0	21
6	0	14	34	9	INF
7	0	6	6	INF	9

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:5)=8
(2:4)=6
(2:6)=9
(4:1)=0
(4:3)=6
(4:5)=0
(6:1)=9
(7:1)=6

Конец подсчета штрафов у нулей

Максимумы по строкам:8 9 6 9 6

Максимальная степень 0 находятся на позициях (2:6)

Граница у несодержащего ребро (5,7):109 у содержащего99

Нули на предыдущих этапах:(6:1) (4:5) (2:4) (5:6) (3:7) (1:2)

Начинаем разделение

	1	3
6	0	0
7	0	INF

(6:1)

Поиск циклов

Цикл найден. уничтожен [4][6]

Поиск циклов

Цикл найден. уничтожен [1][6]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (6,1)

	1	3
6	INF	0
7	0	INF

Вычитание минимумов по строке

	1	3
6	INF	0
7	0	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0

Почти новая мин граница 93

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0

Новая мин граница 93

Результат вычитания минимумов по столбцам

	1	3
6	INF	0
7	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(6:3)=0
(7:1)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0 0

Максимальная степень 0 находятся на позициях (6:3)

Удаление из матрицы 6:1

	1	3
6	0	0
7	0	INF

Результат удаления из матрицы 6:1

	3
7	INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (6,1)

	3
7	INF

Вычитание минимумов по строке

	3
7	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0

Почти новая мин граница 93

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0

Новая мин граница 93

Результат вычитания минимумов по столбцам

	3
7	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:

Конец подсчета штрафов у нулей

Максимумы по строкам:

Граница у несодержащего ребро (6,1):93 у содержащегоINF

Нули на предыдущих этапах:(6:3) (6:1) (4:5) (2:4) (5:6) (3:7) (1:2)

Начинаем разделение

	1	3
6	INF	0
7	0	INF

(6:3)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (6,3)

	1	3
6	INF	INF
7	0	INF

Вычитание минимумов по строке

	1	3
6	INF	INF
7	0	INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0

Почти новая мин граница 93

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0

Новая мин граница 93

Результат вычитания минимумов по столбцам

	1	3
6	INF	INF
7	0	INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(7:1)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0

Максимальная степень 0 находятся на позициях (7:1)

Удаление из матрицы 6:3

	1	3
6	INF	0
7	0	INF

Результат удаления из матрицы 6:3

	1
7	0

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (6,3)

	1
7	0

Вычитание минимумов по строке

	1
7	0

Нахождение минимальных по строкам

Мнимальные по строкам:0

Почти новая мин граница 93

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0

Новая мин граница 93

Результат вычитания минимумов по столбцам

	1
7	0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(7:1)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0

Максимальная степень 0 находятся на позициях (7:1)

Граница у несодержащего ребро (6,3):93 у содержащего93

Нули на предыдущих этапах:(7:1) (6:3) (6:1) (4:5) (2:4) (5:6) (3:7) (1:2)

В таблице всего один элемент

	1
7	0

добавили в путь 7:1

Нули на предыдущих этапах:(7:1) (6:3) (6:1) (4:5) (2:4) (5:6) (3:7) (1:2)

Метод ветвей и границ

Примеры из веба для сверки ответов:

Таблица длин маршрутов

Легенда узла: _{Номер шага обработки}(Строка:Колонка)_{Стоимость}

(Для подбробного решения выберите нужный этап на дереве)

Ответ: путь:6=>3=>7=>1=>2=>4=>5=>6 длина: 93

	1	2	3	4	5	6	7
1	INF	6	40	36	39	80	94
2	4	INF	61	3	98	26	26
3	81	4	INF	97	97	93	18
4	12	84	17	INF	24	56	65
5	69	25	65	97	INF	10	0
6	1	83	20	35	22	INF	67
7	12	56	23	18	68	44	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	3	4	5	6	7
2	1	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	6	40	36	39	80	94
2	4	INF	61	3	98	26	26
3	81	4	INF	97	97	93	18
4	12	84	17	INF	24	56	65
5	69	25	65	97	INF	10	0
6	1	83	20	35	22	INF	67
7	12	56	23	18	68	44	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	3	4	5	6	7
2	1	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

Метод ветвей и границ

Примеры из веба для сверки ответов:

Таблица длин маршрутов

Легенда узла: Номер шага обработки(Строка:Колонка)Стоимость

(Для подбробного решения выберите нужный этап на дереве)

Ответ: путь:6=>3=>7=>1=>2=>4=>5=>6 длина: 93

Легенда узла: _{Номер шага обработки}(Строка:Колонка)_{Стоимость}

	1	2	3	4	5	6	7
1	INF	6	40	36	39	80	94
2	4	INF	61	3	98	26	26
3	81	4	INF	97	97	93	18
4	12	84	17	INF	24	56	65
5	69	25	65	97	INF	10	0
6	1	83	20	35	22	INF	67
7	12	56	23	18	68	44	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	INF	8	9	0	43	67
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	2	3	4	5	6	7
1	INF	0	29	30	21	64	88
2	1	INF	53	0	83	13	23
3	77	0	INF	93	81	79	14
4	0	72	0	INF	0	34	53
5	69	25	60	97	INF	0	0
6	0	82	14	34	9	INF	66
7	0	44	6	6	44	22	INF

	1	3	4	5	6	7
2	1	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF

	1	3	4	5	6	7
2	INF	53	0	83	13	23
3	77	INF	93	81	79	14
4	0	0	INF	0	34	53
5	69	60	97	INF	0	0
6	0	14	34	9	INF	66
7	0	6	6	44	22	INF