 |
Задача коммивояжера методом ветвей и границ
|
|
|
|
Другим алгоритмом решения задачи коммивояжера является метод ветвей и границ. В сущности, это некоторая модификация полного перебора решений, оптимизируемая за счет того, что по определенным признакам отсекаются неоптимальные множества перебора.
Формально строится дерево вариантов, начиная от корня. В корне необходимо дать верхнюю и нижнюю оценки. Далее ветвимся. Чем меньший фрагмент дерева придется построить, тем успешнее сработал метод ветвей и границ.
Имеют место следующие определения:
Текущий рекорд – наибольшая из полученных в процессе реализации метода нижних оценок.
Вершина именуется мертвой, если верхняя оценка в ней не превышает текущего рекорда. Выполнять в ней дальнейшее ветвление бесполезно.
Терминальной называется вершина, в которой верхняя и нижняя оценки совпадают.
Вершина, ветвление в которой уже выполнено, называется закрытой.
Вершины, которые не являются мертвыми, терминальными или закрытыми, называются открытыми. Дальнейшее ветвление делаем в них.
Решение заканчивается тогда, когда в нашем дереве вариантов нет открытых вершин. Оптимальным решением будет текущий рекорд.
Верхняя оценка определяется при помощи «жадного» алгоритма.
Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния методом выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность (последнее ребро, как правило, самое большое или близко к нему по длине).
Стратегия: «иди в ближайший (в который еще не входил) город». Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди вы ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.
|
|
|
Чтобы вычислить нижнюю оценку, сначала суммируем минимальные элементы по строкам и по столбцам, а затем из полученных сумм выбираем наибольшую, но надо учитывать конфликт.
Пример 2.1 Решить методом ветвей и границ задачу коммивояжера, определяемую матрицей:
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
|
|
|
●
 | |||
 | |||
|
 | ||||||||
| ||||||||
 | ||||||||
 | ||||||||
| ||||||||
В результате решения задачи, дальше ветвиться нам не куда. Запишем оптимальный маршрут коммивояжера:
1 ® 2 ® 5 ® 4 ® 3®1
Таким образом, задача решена.
Заключение
Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.
Реальные прикладные задачи дискретной оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.
|
|
|
