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

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

	1	2	3	4	5	6	7
1	INF	75	43	13	61	40	96
2	23	INF	89	45	29	95	27
3	76	97	INF	97	49	81	50
4	68	37	88	INF	47	44	40
5	3	35	28	0	INF	5	24
6	0	44	62	73	26	INF	71
7	39	10	84	39	73	4	INF

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

Мнимальные по строкам:13 23 49 37 0 0 4

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

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

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

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

Максимумы по строкам:2 3 6 8 2 26 11

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

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

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

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

(6:1)

Поиск циклов

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

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

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

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

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	18	8	47	0	INF	44
7	35	6	52	35	69	0	INF

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

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

	2	3	4	5	6	7
1	62	2	0	48	27	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

Поиск циклов

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

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

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

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

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

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

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

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

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

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

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

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

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

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

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	35	19	3	69	0
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

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

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

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

Максимумы по строкам:2 3 3 8 2 11

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

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

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

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

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	35	19	3	69	0
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

(7:6)

Поиск циклов

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

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

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	35	19	3	69	0
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	INF	INF

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

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	35	19	3	69	0
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	INF	INF

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

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

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

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

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

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

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

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

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

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	35	19	3	64	0
3	48	INF	48	0	27	0
4	0	23	INF	10	2	2
5	35	0	0	INF	0	23
7	0	46	29	63	INF	INF

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

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

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

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

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

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

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	35	19	3	69	0
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

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

	2	3	4	5	7
1	62	2	0	48	82
2	INF	35	19	3	0
3	48	INF	48	0	0
4	0	23	INF	10	2
5	35	0	0	INF	23

Поиск циклов

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

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

	2	3	4	5	7
1	62	2	0	48	82
2	INF	35	19	3	0
3	48	INF	48	0	0
4	0	23	INF	10	2
5	35	0	0	INF	23

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

	2	3	4	5	7
1	62	2	0	48	82
2	INF	35	19	3	0
3	48	INF	48	0	0
4	0	23	INF	10	2
5	35	0	0	INF	23

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

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

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

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

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

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

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

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

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

	2	3	4	5	7
1	62	2	0	48	82
2	INF	35	19	3	0
3	48	INF	48	0	0
4	0	23	INF	10	2
5	35	0	0	INF	23

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

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

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

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

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

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

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

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

	2	3	4	5	7
1	62	2	0	48	82
2	INF	35	19	3	0
3	48	INF	48	0	0
4	0	23	INF	10	2
5	35	0	0	INF	23

(4:2)

Поиск циклов

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

Поиск циклов

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

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

	2	3	4	5	7
1	62	2	0	48	INF
2	INF	35	19	3	0
3	48	INF	48	0	0
4	INF	23	INF	10	2
5	35	0	0	INF	23

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

	2	3	4	5	7
1	62	2	0	48	INF
2	INF	35	19	3	0
3	48	INF	48	0	0
4	INF	23	INF	10	2
5	35	0	0	INF	23

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

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

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

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

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

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

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

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

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

	2	3	4	5	7
1	27	2	0	48	INF
2	INF	35	19	3	0
3	13	INF	48	0	0
4	INF	21	INF	8	0
5	0	0	0	INF	23

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

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

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

Максимумы по строкам:2 3 3 8 13

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

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

	2	3	4	5	7
1	62	2	0	48	82
2	INF	35	19	3	0
3	48	INF	48	0	0
4	0	23	INF	10	2
5	35	0	0	INF	23

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

	3	4	5	7
1	2	0	48	82
2	35	19	3	0
3	INF	48	0	0
5	0	0	INF	23

Поиск циклов

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

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

	3	4	5	7
1	2	0	48	INF
2	35	INF	3	0
3	INF	48	0	0
5	0	0	INF	23

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

	3	4	5	7
1	2	0	48	INF
2	35	INF	3	0
3	INF	48	0	0
5	0	0	INF	23

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

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

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

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

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

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

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

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

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

	3	4	5	7
1	2	0	48	INF
2	35	INF	3	0
3	INF	48	0	0
5	0	0	INF	23

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

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

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

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

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

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

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

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

	3	4	5	7
1	2	0	48	INF
2	35	INF	3	0
3	INF	48	0	0
5	0	0	INF	23

(2:7)

Поиск циклов

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

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

	3	4	5	7
1	2	0	48	INF
2	35	INF	3	INF
3	INF	48	0	0
5	0	0	INF	23

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

	3	4	5	7
1	2	0	48	INF
2	35	INF	3	INF
3	INF	48	0	0
5	0	0	INF	23

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

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

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

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

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

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

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

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

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

	3	4	5	7
1	2	0	48	INF
2	32	INF	0	INF
3	INF	48	0	0
5	0	0	INF	23

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

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

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

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

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

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

	3	4	5	7
1	2	0	48	INF
2	35	INF	3	0
3	INF	48	0	0
5	0	0	INF	23

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

	3	4	5
1	2	0	48
3	INF	48	0
5	0	0	INF

Поиск циклов

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

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

	3	4	5
1	2	0	48
3	INF	48	0
5	0	0	INF

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

	3	4	5
1	2	0	48
3	INF	48	0
5	0	0	INF

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

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

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

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

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

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

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

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

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

	3	4	5
1	2	0	48
3	INF	48	0
5	0	0	INF

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

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

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

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

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

Граница у несодержащего ребро (2,7):161 у содержащего158

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

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

	3	4	5
1	2	0	48
3	INF	48	0
5	0	0	INF

(3:5)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

	3	4	5
1	2	INF	48
3	INF	48	INF
5	0	0	INF

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

	3	4	5
1	2	INF	48
3	INF	48	INF
5	0	0	INF

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

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

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

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

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

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

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

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

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

	3	4	5
1	0	INF	0
3	INF	0	INF
5	0	0	INF

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

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

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

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

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

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

	3	4	5
1	2	0	48
3	INF	48	0
5	0	0	INF

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

	3	4
1	2	0
5	0	0

Поиск циклов

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

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

	3	4
1	2	INF
5	INF	0

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

	3	4
1	2	INF
5	INF	0

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

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

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

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

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

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

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

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

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

	3	4
1	0	INF
5	INF	0

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

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

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

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

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

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

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

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

	3	4
1	0	INF
5	INF	0

(1:3)

Поиск циклов

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

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

	3	4
1	INF	INF
5	INF	0

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

	3	4
1	INF	INF
5	INF	0

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

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

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

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

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

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

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

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

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

	3	4
1	INF	INF
5	INF	0

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

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

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

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

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

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

	3	4
1	0	INF
5	INF	0

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

	4
5	0

Поиск циклов

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

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

	4
5	0

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

	4
5	0

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

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

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

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

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

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

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

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

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

	4
5	0

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

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

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

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

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

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

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

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

	4
5	0

добавили в путь 5:4

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	75	43	13	61	40	96
2	23	INF	89	45	29	95	27
3	76	97	INF	97	49	81	50
4	68	37	88	INF	47	44	40
5	3	35	28	0	INF	5	24
6	0	44	62	73	26	INF	71
7	39	10	84	39	73	4	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	18	8	47	0	INF	44
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	27	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	75	43	13	61	40	96
2	23	INF	89	45	29	95	27
3	76	97	INF	97	49	81	50
4	68	37	88	INF	47	44	40
5	3	35	28	0	INF	5	24
6	0	44	62	73	26	INF	71
7	39	10	84	39	73	4	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	18	8	47	0	INF	44
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	27	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	75	43	13	61	40	96
2	23	INF	89	45	29	95	27
3	76	97	INF	97	49	81	50
4	68	37	88	INF	47	44	40
5	3	35	28	0	INF	5	24
6	0	44	62	73	26	INF	71
7	39	10	84	39	73	4	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	INF	18	8	47	0	INF	44
7	35	6	52	35	69	0	INF

	1	2	3	4	5	6	7
1	INF	62	2	0	48	27	82
2	0	INF	38	22	6	72	3
3	27	48	INF	48	0	32	0
4	31	0	23	INF	10	7	2
5	3	35	0	0	INF	5	23
6	0	44	34	73	26	INF	70
7	35	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	27	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF

	2	3	4	5	6	7
1	62	2	0	48	INF	82
2	INF	38	22	6	72	3
3	48	INF	48	0	32	0
4	0	23	INF	10	7	2
5	35	0	0	INF	5	23
7	6	52	35	69	0	INF