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

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

	1	2	3	4	5	6
1	INF	88	97	75	64	27
2	46	INF	38	87	60	83
3	6	30	INF	74	92	72
4	19	50	12	INF	86	61
5	85	87	90	14	INF	79
6	76	71	7	80	5	INF

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

Мнимальные по строкам:27 38 6 12 14 5

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

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

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

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

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

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

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

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

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

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

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

Максимумы по строкам:82 8 14 7 97 24

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

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

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

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

(5:4)

Поиск циклов

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

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

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	INF	INF	65
6	71	42	2	75	0	INF

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

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	INF	INF	65
6	71	42	2	75	0	INF

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	6
1	INF	37	70	0	37	0
2	8	INF	0	1	22	45
3	0	0	INF	20	86	66
4	7	14	0	INF	74	49
5	22	0	27	INF	INF	16
6	71	42	2	27	0	INF

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

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

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

Максимумы по строкам:16 1 7 7 16 24

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

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

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

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

	1	2	3	5	6
1	INF	37	70	37	0
2	8	INF	0	22	45
3	0	0	INF	86	66
4	7	14	0	74	49
6	71	42	2	0	INF

Поиск циклов

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

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

	1	2	3	5	6
1	INF	37	70	37	0
2	8	INF	0	22	45
3	0	0	INF	86	66
4	7	14	0	INF	49
6	71	42	2	0	INF

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

	1	2	3	5	6
1	INF	37	70	37	0
2	8	INF	0	22	45
3	0	0	INF	86	66
4	7	14	0	INF	49
6	71	42	2	0	INF

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

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

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

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

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

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

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

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

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

	1	2	3	5	6
1	INF	37	70	37	0
2	8	INF	0	22	45
3	0	0	INF	86	66
4	7	14	0	INF	49
6	71	42	2	0	INF

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

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

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

Максимумы по строкам:82 8 14 7 24

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

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

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

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

	1	2	3	5	6
1	INF	37	70	37	0
2	8	INF	0	22	45
3	0	0	INF	86	66
4	7	14	0	INF	49
6	71	42	2	0	INF

(1:6)

Поиск циклов

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

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

	1	2	3	5	6
1	INF	37	70	37	INF
2	8	INF	0	22	45
3	0	0	INF	86	66
4	7	14	0	INF	49
6	71	42	2	0	INF

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

	1	2	3	5	6
1	INF	37	70	37	INF
2	8	INF	0	22	45
3	0	0	INF	86	66
4	7	14	0	INF	49
6	71	42	2	0	INF

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

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

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

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

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

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

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

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

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

	1	2	3	5	6
1	INF	0	33	0	INF
2	8	INF	0	22	0
3	0	0	INF	86	21
4	7	14	0	INF	4
6	71	42	2	0	INF

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

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

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

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

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

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

	1	2	3	5	6
1	INF	37	70	37	0
2	8	INF	0	22	45
3	0	0	INF	86	66
4	7	14	0	INF	49
6	71	42	2	0	INF

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

	1	2	3	5
2	8	INF	0	22
3	0	0	INF	86
4	7	14	0	INF
6	71	42	2	0

Поиск циклов

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

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

	1	2	3	5
2	8	INF	0	22
3	0	0	INF	86
4	7	14	0	INF
6	INF	42	2	0

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

	1	2	3	5
2	8	INF	0	22
3	0	0	INF	86
4	7	14	0	INF
6	INF	42	2	0

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

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

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

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

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

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

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

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

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

	1	2	3	5
2	8	INF	0	22
3	0	0	INF	86
4	7	14	0	INF
6	INF	42	2	0

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

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

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

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

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

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

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

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

	1	2	3	5
2	8	INF	0	22
3	0	0	INF	86
4	7	14	0	INF
6	INF	42	2	0

(6:5)

Поиск циклов

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

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

	1	2	3	5
2	8	INF	0	22
3	0	0	INF	86
4	7	14	0	INF
6	INF	42	2	INF

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

	1	2	3	5
2	8	INF	0	22
3	0	0	INF	86
4	7	14	0	INF
6	INF	42	2	INF

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

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

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

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

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

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

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

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

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

	1	2	3	5
2	8	INF	0	0
3	0	0	INF	64
4	7	14	0	INF
6	INF	40	0	INF

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

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

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

Максимумы по строкам:64 14 7 40

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

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

	1	2	3	5
2	8	INF	0	22
3	0	0	INF	86
4	7	14	0	INF
6	INF	42	2	0

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

	1	2	3
2	8	INF	0
3	0	0	INF
4	7	14	0

Поиск циклов

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

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

	1	2	3
2	8	INF	0
3	0	0	INF
4	7	14	0

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

	1	2	3
2	8	INF	0
3	0	0	INF
4	7	14	0

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

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

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

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

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

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

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

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

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

	1	2	3
2	8	INF	0
3	0	0	INF
4	7	14	0

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

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

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

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

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

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

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

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

	1	2	3
2	8	INF	0
3	0	0	INF
4	7	14	0

(3:2)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

	1	2	3
2	8	INF	0
3	0	INF	INF
4	INF	14	0

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

	1	2	3
2	8	INF	0
3	0	INF	INF
4	INF	14	0

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

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

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

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

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

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

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

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

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

	1	2	3
2	8	INF	0
3	0	INF	INF
4	INF	0	0

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

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

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

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

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

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

	1	2	3
2	8	INF	0
3	0	0	INF
4	7	14	0

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

	1	3
2	8	0
4	7	0

Поиск циклов

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

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

	1	3
2	8	INF
4	INF	0

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

	1	3
2	8	INF
4	INF	0

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

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

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

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

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

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

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

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

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

	1	3
2	0	INF
4	INF	0

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

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

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

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

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

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

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

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

	1	3
2	0	INF
4	INF	0

(2:1)

Поиск циклов

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

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

	1	3
2	INF	INF
4	INF	0

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

	1	3
2	INF	INF
4	INF	0

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

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

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

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

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

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

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

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

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

	1	3
2	INF	INF
4	INF	0

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

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

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

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

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

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

	1	3
2	0	INF
4	INF	0

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

	3
4	0

Поиск циклов

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

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

	3
4	0

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

	3
4	0

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

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

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

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

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

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

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

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

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

	3
4	0

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

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

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

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

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

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

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

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

	3
4	0

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

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

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

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

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

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

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

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

	1	2	3	4	5	6
1	INF	88	97	75	64	27
2	46	INF	38	87	60	83
3	6	30	INF	74	92	72
4	19	50	12	INF	86	61
5	85	87	90	14	INF	79
6	76	71	7	80	5	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	INF	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	INF	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	0	37	0
2	8	INF	0	1	22	45
3	0	0	INF	20	86	66
4	7	14	0	INF	74	49
5	22	0	27	INF	INF	16
6	71	42	2	27	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	88	97	75	64	27
2	46	INF	38	87	60	83
3	6	30	INF	74	92	72
4	19	50	12	INF	86	61
5	85	87	90	14	INF	79
6	76	71	7	80	5	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	INF	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	INF	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	0	37	0
2	8	INF	0	1	22	45
3	0	0	INF	20	86	66
4	7	14	0	INF	74	49
5	22	0	27	INF	INF	16
6	71	42	2	27	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

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

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

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

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

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

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

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

	1	2	3	4	5	6
1	INF	88	97	75	64	27
2	46	INF	38	87	60	83
3	6	30	INF	74	92	72
4	19	50	12	INF	86	61
5	85	87	90	14	INF	79
6	76	71	7	80	5	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	INF	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	INF	INF	65
6	71	42	2	75	0	INF

	1	2	3	4	5	6
1	INF	37	70	0	37	0
2	8	INF	0	1	22	45
3	0	0	INF	20	86	66
4	7	14	0	INF	74	49
5	22	0	27	INF	INF	16
6	71	42	2	27	0	INF

	1	2	3	4	5	6
1	INF	37	70	48	37	0
2	8	INF	0	49	22	45
3	0	0	INF	68	86	66
4	7	14	0	INF	74	49
5	71	49	76	0	INF	65
6	71	42	2	75	0	INF