Метод ветвей и границ. 03 Метод ветвей и границ. Лекция 3 Метод ветвей и границ
 Скачать 0.81 Mb.
|
|
Модуль 1. Полный перебор Лекция 3 Метод ветвей и границ. 2 План лекции ● Метод ветвей и границ – Общий принцип – МВГ для задачи коммивояжёра ● Варианты ветвления ● Варианты оценки ● Задание 3. 3 Метод ветвей и границ ● Предназначен в первую очередь для решения NP-трудных оптимизационных задач. ● Сочетание двух операций: – Ветвление. – Оценка верхней/нижней границы и «отсечение» неперспективной ветви. 4 Метод ветвей и границ ● Ветвление – Всё множество допустимых решений S(x) последовательно делится на подмножества: – Подмножества рекурсивно делятся дальше: – Для разделения множества решений на подмножества обычно последовательно накладывают условия/ограничения, которым должны удовлетворять решения из заданного подмножества. 5 Метод ветвей и границ Примеры ограничений для задачи коммивояжёра ● По принципу «содержит» / «не содержит» указанные дуги (алгоритм Литтла). Выбрать дугу e E и разделить S(x) на два подмножества: S {e} (x) = {Z : e Z} и S {e} (x) = {Z : e Z}. Потом выбираем другую дугу и аналогичным образом делим S {e} (x) и S {e} (x) на более мелкие подмножества. 6 Метод ветвей и границ 7 Метод ветвей и границ Примеры ограничений для задачи коммивояжёра ● Частичный путь Фиксируем фрагмент цикла — какие вершины цикл проходит последовательно друг за другом. Стартовая вершина всегда фиксирована: «1». Поэтому разделяем все возможные циклы на подмножества, содержащие фрагменты: «1,2», «1,3»,..., «1,n». Потом делим множество «1,2»: «1,2,3», «1,2,4», …, «1,2,n». 8 Метод ветвей и границ 9 Метод ветвей и границ Принцип отсечения неперспективных ветвей: ● Вычисляем оценку («границу») стоимости решений, входящих в анализируемое подмножество. Для задач минимизации вычисляем оценку снизу, для максимизации — оценку сверху. ● Сравниваем оценку со стоимостью рекордного (наилучшего на данный момент) решения. Если оценка хуже (для минимизации — выше, для максимизации — меньше), чем рекордное решение — данное подмножество далее не анализируем. Важно иметь в виду: на вычисление оценки также тратится время, и важно соблюдать баланс между качеством оценки и сложностью её вычисления. Возможный вариант: применять разные оценки на разных уровнях «дерева перебора»: на верхних уровнях более сложные, но более точные, на низших уровнях — менее точные, но более быстрые (подумайте — почему так?). 10 Метод ветвей и границ Варианты вычисления границ (оценка снизу) для задачи коммивояжёра: (1) Выбрать минимальную стоимость дуги (ещё не включённой в цикл), умножить на количество ещё не пройденных вершин графа и прибавить стоимости дуг, уже включённых в цикл. c' = c(a,b)+c(b,d)+3*c(a,c) 11 Метод ветвей и границ Варианты вычисления границ (оценка снизу) для задачи коммивояжёра: (2) Для каждой вершины найти две инцидентные ей дуги наименьшей стоимости (обязательно включая дуги, уже вошедшие в цикл — если такие есть) и взять их среднее арифметическое. В качестве оценки использовать сумму этих средних 12 Задание 3 Разработать программу решения задачи коммивояжёра. ● Дано: – Граф (неориентированный или ориентированный). ● Необходимо: – Найти точное решение ЗК перебором обобщённых слов. – Найти точное решение ЗК перебором перестановок. – Найти точное решение методом ветвей и границ. Принцип ветвления: по вашему желанию. Расчёт границы: по вашему желанию. – Для каждого метода рассчитать время и количество вызовов метода Process() либо метода расчёта границы. 13 Задание 3 Формат входного файла: аналогичен формату для задания 2, но для каждого ребра в строке указано: начало, конец, стоимость. 5 8 1 2 3 1 3 4 1 5 7 2 3 4 2 4 6 3 4 5 3 5 8 4 5 6 Оптимальное решение: 25. |