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

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

	1	2	3	4	5	6	7
1	INF	6	91	79	15	3	46
2	10	INF	57	84	68	39	53
3	21	88	INF	54	3	29	1
4	79	75	8	INF	74	54	15
5	11	99	91	74	INF	29	9
6	65	76	22	66	53	INF	33
7	91	44	29	91	14	11	INF

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

Мнимальные по строкам:3 10 1 8 9 22 11

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

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

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

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

Максимумы по строкам:30 31 1 7 2 9 1

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

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

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

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

(2:1)

Поиск циклов

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

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

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

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

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	18	1	27	0	14
3	18	84	INF	9	0	28	0
4	69	64	0	INF	64	46	7
5	0	87	82	21	INF	20	0
6	41	51	0	0	29	INF	11
7	78	30	18	36	1	0	INF

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

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

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

Максимумы по строкам:30 1 1 7 18 1 1

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

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

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

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

	2	3	4	5	6	7
1	0	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

Поиск циклов

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

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

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

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

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

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

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

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

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

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

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

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

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

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

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	54	INF	9	0	28	0
4	34	0	INF	64	46	7
5	57	82	21	INF	20	0
6	21	0	0	29	INF	11
7	0	18	36	1	0	INF

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

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

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

Максимумы по строкам:10 1 7 20 9 21

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

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

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

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

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	54	INF	9	0	28	0
4	34	0	INF	64	46	7
5	57	82	21	INF	20	0
6	21	0	0	29	INF	11
7	0	18	36	1	0	INF

(7:2)

Поиск циклов

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

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

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	54	INF	9	0	28	0
4	34	0	INF	64	46	7
5	57	82	21	INF	20	0
6	21	0	0	29	INF	11
7	INF	18	36	1	0	INF

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

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	54	INF	9	0	28	0
4	34	0	INF	64	46	7
5	57	82	21	INF	20	0
6	21	0	0	29	INF	11
7	INF	18	36	1	0	INF

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

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

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

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

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

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

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

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

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

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	33	INF	9	0	28	0
4	13	0	INF	64	46	7
5	36	82	21	INF	20	0
6	0	0	0	29	INF	11
7	INF	18	36	1	0	INF

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

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

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

Максимумы по строкам:10 1 7 20 13 1

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

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

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	54	INF	9	0	28	0
4	34	0	INF	64	46	7
5	57	82	21	INF	20	0
6	21	0	0	29	INF	11
7	0	18	36	1	0	INF

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

	3	4	5	6	7
1	88	32	10	0	43
3	INF	9	0	28	0
4	0	INF	64	46	7
5	82	21	INF	20	0
6	0	0	29	INF	11

Поиск циклов

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

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

	3	4	5	6	7
1	88	32	10	0	43
3	INF	9	0	28	0
4	0	INF	64	46	7
5	82	21	INF	20	0
6	0	0	29	INF	11

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

	3	4	5	6	7
1	88	32	10	0	43
3	INF	9	0	28	0
4	0	INF	64	46	7
5	82	21	INF	20	0
6	0	0	29	INF	11

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

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

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

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

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

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

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

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

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

	3	4	5	6	7
1	88	32	10	0	43
3	INF	9	0	28	0
4	0	INF	64	46	7
5	82	21	INF	20	0
6	0	0	29	INF	11

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

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

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

Максимумы по строкам:30 10 7 20 9

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

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

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

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

	3	4	5	6	7
1	88	32	10	0	43
3	INF	9	0	28	0
4	0	INF	64	46	7
5	82	21	INF	20	0
6	0	0	29	INF	11

(1:6)

Поиск циклов

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

Поиск циклов

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

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

	3	4	5	6	7
1	88	32	10	INF	INF
3	INF	9	0	28	0
4	0	INF	64	46	7
5	82	21	INF	20	0
6	0	0	29	INF	11

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

	3	4	5	6	7
1	88	32	10	INF	INF
3	INF	9	0	28	0
4	0	INF	64	46	7
5	82	21	INF	20	0
6	0	0	29	INF	11

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

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

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

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

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

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

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

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

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

	3	4	5	6	7
1	78	22	0	INF	INF
3	INF	9	0	8	0
4	0	INF	64	26	7
5	82	21	INF	0	0
6	0	0	29	INF	11

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

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

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

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

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

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

	3	4	5	6	7
1	88	32	10	0	43
3	INF	9	0	28	0
4	0	INF	64	46	7
5	82	21	INF	20	0
6	0	0	29	INF	11

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

	3	4	5	7
3	INF	9	0	0
4	0	INF	64	7
5	82	21	INF	0
6	0	0	29	11

Поиск циклов

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

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

	3	4	5	7
3	INF	9	0	0
4	0	INF	64	7
5	82	21	INF	0
6	0	0	29	11

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

	3	4	5	7
3	INF	9	0	0
4	0	INF	64	7
5	82	21	INF	0
6	0	0	29	11

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

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

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

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

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

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

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

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

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

	3	4	5	7
3	INF	9	0	0
4	0	INF	64	7
5	82	21	INF	0
6	0	0	29	11

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

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

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

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

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

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

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

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

	3	4	5	7
3	INF	9	0	0
4	0	INF	64	7
5	82	21	INF	0
6	0	0	29	11

(3:5)

Поиск циклов

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

Поиск циклов

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

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

	3	4	5	7
3	INF	9	INF	0
4	0	INF	64	7
5	82	21	INF	0
6	0	0	29	INF

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

	3	4	5	7
3	INF	9	INF	0
4	0	INF	64	7
5	82	21	INF	0
6	0	0	29	INF

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

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

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

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

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

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

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

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

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

	3	4	5	7
3	INF	9	INF	0
4	0	INF	35	7
5	82	21	INF	0
6	0	0	0	INF

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

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

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

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

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

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

	3	4	5	7
3	INF	9	0	0
4	0	INF	64	7
5	82	21	INF	0
6	0	0	29	11

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

	3	4	7
4	0	INF	7
5	82	21	0
6	0	0	11

Поиск циклов

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

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

	3	4	7
4	0	INF	7
5	INF	21	0
6	0	0	INF

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

	3	4	7
4	0	INF	7
5	INF	21	0
6	0	0	INF

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

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

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

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

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

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

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

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

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

	3	4	7
4	0	INF	7
5	INF	21	0
6	0	0	INF

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

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

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

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

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

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

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

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

	3	4	7
4	0	INF	7
5	INF	21	0
6	0	0	INF

(5:7)

Поиск циклов

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

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

	3	4	7
4	0	INF	7
5	INF	21	INF
6	0	0	INF

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

	3	4	7
4	0	INF	7
5	INF	21	INF
6	0	0	INF

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

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

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

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

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

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

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

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

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

	3	4	7
4	0	INF	0
5	INF	0	INF
6	0	0	INF

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

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

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

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

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

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

	3	4	7
4	0	INF	7
5	INF	21	0
6	0	0	INF

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

	3	4
4	0	INF
6	0	0

Поиск циклов

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

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

	3	4
4	0	INF
6	0	0

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

	3	4
4	0	INF
6	0	0

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

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

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

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

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

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

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

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

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

	3	4
4	0	INF
6	0	0

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

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

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

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

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

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

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

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

	3	4
4	0	INF
6	0	0

(4:3)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

	3	4
4	INF	INF
6	INF	0

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

	3	4
4	INF	INF
6	INF	0

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

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

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

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

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

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

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

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

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

	3	4
4	INF	INF
6	INF	0

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

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

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

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

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

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

	3	4
4	0	INF
6	0	0

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

	4
6	0

Поиск циклов

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

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

	4
6	0

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

	4
6	0

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

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

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

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

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

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

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

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

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

	4
6	0

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

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

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

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

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

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

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

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

	4
6	0

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

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	6	91	79	15	3	46
2	10	INF	57	84	68	39	53
3	21	88	INF	54	3	29	1
4	79	75	8	INF	74	54	15
5	11	99	91	74	INF	29	9
6	65	76	22	66	53	INF	33
7	91	44	29	91	14	11	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	18	1	27	0	14
3	18	84	INF	9	0	28	0
4	69	64	0	INF	64	46	7
5	0	87	82	21	INF	20	0
6	41	51	0	0	29	INF	11
7	78	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	2	3	4	5	6	7
1	0	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	6	91	79	15	3	46
2	10	INF	57	84	68	39	53
3	21	88	INF	54	3	29	1
4	79	75	8	INF	74	54	15
5	11	99	91	74	INF	29	9
6	65	76	22	66	53	INF	33
7	91	44	29	91	14	11	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	18	1	27	0	14
3	18	84	INF	9	0	28	0
4	69	64	0	INF	64	46	7
5	0	87	82	21	INF	20	0
6	41	51	0	0	29	INF	11
7	78	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	2	3	4	5	6	7
1	0	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

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

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

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

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

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

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

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

	1	2	3	4	5	6	7
1	INF	6	91	79	15	3	46
2	10	INF	57	84	68	39	53
3	21	88	INF	54	3	29	1
4	79	75	8	INF	74	54	15
5	11	99	91	74	INF	29	9
6	65	76	22	66	53	INF	33
7	91	44	29	91	14	11	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	INF	INF	18	1	27	0	14
3	18	84	INF	9	0	28	0
4	69	64	0	INF	64	46	7
5	0	87	82	21	INF	20	0
6	41	51	0	0	29	INF	11
7	78	30	18	36	1	0	INF

	1	2	3	4	5	6	7
1	INF	0	88	32	10	0	43
2	0	INF	47	30	56	29	43
3	20	84	INF	9	0	28	0
4	71	64	0	INF	64	46	7
5	2	87	82	21	INF	20	0
6	43	51	0	0	29	INF	11
7	80	30	18	36	1	0	INF

	2	3	4	5	6	7
1	0	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF

	2	3	4	5	6	7
1	INF	88	32	10	0	43
3	84	INF	9	0	28	0
4	64	0	INF	64	46	7
5	87	82	21	INF	20	0
6	51	0	0	29	INF	11
7	30	18	36	1	0	INF