Метод программирования и схем ветвей в процессах решения задач дискретной оптимизации
В*({2, 4}, 3) = min [B*({2}, 4) + s43; B*({4}, 2) + s23] = min(6 + 4; 9 + 5 )= 10;
В*({3, 4}, 2}) = min [B*({3}, 4) + s42; B*({4}, 3) + s32] = min(4 + 5; 8 + 2)= 9;
В*({2, 3, 4}, 1) = min [B*({2, 3}, 4) + s41; B*({2, 4}, 3) + s31; B*({3, 4}, 2) + s21;] = min (7 + 1; 10 +6; 9 + 2 ) = 8.
Итак, оптимальное значение критерия в рассматриваемом примере равно 8.
Выполненные выделения позволяют определить оптимальный маршрут. Он следующий:
1 ® 3 ® 2 ® 4 ® 1.
4. Задача коммивояжера методом ветвей и границ
Другим алгоритмом решения задачи коммивояжера является метод ветвей и границ. В сущности, это некоторая модификация полного перебора решений, оптимизируемая за счет того, что по определенным признакам отсекаются неоптимальные множества перебора.
Формально строится дерево вариантов, начиная от корня. В корне необходимо дать верхнюю и нижнюю оценки. Далее ветвимся. Чем меньший фрагмент дерева придется построить, тем успешнее сработал метод ветвей и границ.
Имеют место следующие определения:
Текущий рекорд – наибольшая из полученных в процессе реализации метода нижних оценок.
Вершина именуется мертвой, если верхняя оценка в ней не превышает текущего рекорда. Выполнять в ней дальнейшее ветвление бесполезно.
Терминальной называется вершина, в которой верхняя и нижняя оценки совпадают.
Вершина, ветвление в которой уже выполнено, называется закрытой.
Вершины, которые не являются мертвыми, терминальными или закрытыми, называются открытыми. Дальнейшее ветвление делаем в них.
Решение заканчивается тогда, когда в нашем дереве вариантов нет открытых вершин. Оптимальным решением будет текущий рекорд.
Верхняя оценка определяется при помощи «жадного» алгоритма.

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния методом выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность (последнее ребро, как правило, самое большое или близко к нему по длине).
Стратегия: «иди в ближайший (в который еще не входил) город». Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди вы ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.
Чтобы вычислить нижнюю оценку, сначала суммируем минимальные элементы по строкам и по столбцам, а затем из полученных сумм выбираем наибольшую, но надо учитывать конфликт.
Пример 2.1 Решить методом ветвей и границ задачу коммивояжера, определяемую матрицей:

Вычисляем верхнюю и нижнюю оценки в корне:
Верхнюю оценку подсчитываем, пользуясь, так называемым, «жадным» алгоритмом: каждый переход делаем из текущего в ближайший город. Получаем маршрут:
1 ® 2 ® 4 ® 3 ® 5 ®1
Суммарная стоимость данного маршрута равна 12, она определяет верхнюю оценку в корне.
Чтобы вычислить нижнюю оценку, сначала суммируем минимальные элементы по строкам и по столбцам, а затем из полученных сумм выбираем наибольшую:
По строкам: 2 + 1 + 2 + 2 + 2 = 9
По столбцам: 2 + 2 + 3 + 1 + 2 = 10
Выбираем максимум из значений и выбираем 10.
Проанализируем столбцы: можем сдвинуться на 2 (конфликт). Отсюда нижний предел равен 10 + 2 = 12.
●![]()
Далее
из корневой
вершины начинаем
ветвление по
городам, в которые
можем идти из
первого:
![]()

![]()
![]()
●
![]()
![]()
![]()
Далее подсчитываем верхние и нижние оценки для новых вершин:
1 – 2: Верхняя оценка («жадный алгоритм»), определяемая суммарной
стоимостью данного маршрута 1 ® 2 ® 4 ® 3 ® 5 ®1 равна 13. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что идем из 1го города во 2й. Она совпадает с нижней оценкой в корне и равна 12.
1 – 3: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 3 ® 2 ® 5 ® 4®1, равна 16. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что из 1го города идем в 3й. Она равна 2+2+4+ 1+2 = 11 и плюс 2 с учетом конфликта. Итого получаем 13.
1 – 4: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 4 ® 2 ®5® 3 ® 1 равна 24. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что идем из 1го города в 4й. Она равна 18.
1 – 5: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 5 ® 4 ®2® 3 ® 1 равна 23. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что идем из 1го города в 5й. И она равна 16
![]()
![]()

![]()
![]()
![]()
![]()
●
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
Проанализируем полученные результаты. Текущий рекорд равен 12.
Переход в вершины 3, 4 и 5 дает ухудшение критерия, поэтому данные вершины именуются мертвыми и ветвление из них далее бессмысленно. Дальше будем ветвиться во 2 и 3 вершинах.
1 – 2 – 3: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 2 ® 3 ® 4 ® 5 ®1 равна 19. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что идем из 1го города во 2й, из 2го в 3й. Она равна 14.
1 – 2 – 4: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 2 ® 4 ® 3 ® 5®1, равна 13. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что из 1го города идем в 2й, из 2го в 4й. Она равна 13.
1 – 2 – 5: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 2 ® 5 ® 4 ® 3®1, равна 16. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что из 1го города идем в 2й, из 2го в 5й. Она равна 12.
![]()
![]()
![]()
![]()



![]()
![]()
![]()
![]()
![]()
![]()
●
![]()
![]()

![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()

![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
Проанализируем полученные результаты. Переход в вершины 3 и 4 дает ухудшение критерия, поэтому данные вершины именуются мертвыми и ветвление из них далее бессмысленно. Дальше будем ветвиться в 5й вершине.
1 – 2 – 5–3: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 2 ® 5 ® 3 ® 4®1, равна 17. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что из 1го города идем в 2 ® 5® 3. Она равна 15.
1 – 2 – 5–4: Верхняя оценка («жадный алгоритм»), определяемая суммарной стоимостью данного маршрута 1 ® 2 ® 5 ® 4 ® 3®1, равна 16. Нижняя оценка определяется суммой минимальных элементов строк с учетом того, что из 1го города идем в 2й, из 2го в 5й. Она равна 13.
13/12
![]()
![]()


![]()
![]()
![]()
![]()
![]()
●
![]()
