Метод программирования и схем ветвей в процессах решения задач дискретной оптимизации (стр. 3 из 4)

Формально строится дерево вариантов, начиная от корня. В корне необходимо дать верхнюю и нижнюю оценки. Далее ветвимся. Чем меньший фрагмент дерева придется построить, тем успешнее сработал метод ветвей и границ.

Имеют место следующие определения:

Текущий рекорд – наибольшая из полученных в процессе реализации метода нижних оценок.

Вершина именуется мертвой, если верхняя оценка в ней не превышает текущего рекорда. Выполнять в ней дальнейшее ветвление бесполезно.

Терминальной называется вершина, в которой верхняя и нижняя оценки совпадают.

Вершина, ветвление в которой уже выполнено, называется закрытой.

Вершины, которые не являются мертвыми, терминальными или закрытыми, называются открытыми. Дальнейшее ветвление делаем в них.

Решение заканчивается тогда, когда в нашем дереве вариантов нет открытых вершин. Оптимальным решением будет текущий рекорд.

Верхняя оценка определяется при помощи «жадного» алгоритма.

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния методом выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность (последнее ребро, как правило, самое большое или близко к нему по длине).

Стратегия: «иди в ближайший (в который еще не входил) город». Рассмотрим для примера сеть на рис. 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.

●

Далее из корневой вершины начинаем ветвление по городам, в которые можем идти из первого: