|
Существует достаточно большой класс задач, в которых для нахождения оптимального решения необходимо перебрать все возможные варианты решений по какому-либо критерию. Однако такой прямой перебор может занять очень много времени. Например, для выбора оптимальной последовательности проведения маркетинговых исследований группой из т специалистов разного профиля в п объектах рынка необходимо перебрать большое множество вариантов. В задаче коммивояжера для формирования оптимального маршрута объезда п городов необходимо выбрать один лучший из (n -1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтоно-ва цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева — связного графа, не содержащего циклов и петель. Корень этого дерева объединяет все множество вариантов, а вершины дерева — это подмножества частично упорядоченных вариантов решений.
Вершина (i, j) соответствует подмножеству всех маршрутов, содержащих дугу (i,j), а вершина — подмножеству всех маршрутов, где эта дуга отсутствует.
Процесс разбиения на эти подмножества можно рассматривать как ветвление дерева. Поэтому метод называется методом поиска по дереву решений, или методом ветвей и границ.
Метод ветвей и границ представляет собой алгоритм направленного перебора множества вариантов решения задачи. Сущность этого метода состоит в том, что ветвятся от корня дерева не все вершины. В начале проводится оценка каждой вершины первого уровня, а затем ветвится та вершина, которая получает лучшую оценку (минимальную или максимальную) в соответствии с выбранным критерием. Однако вычислить точное значение критерия, не перебрав всех вариантов, невозможно. Чтобы избежать этой рутины, используют не точное значение критерия, а оценку снизу или сверху, которые называют нижней оценкой границы и верхней оценкой границы множества вариантов. При этом оценка вершины должна удовлетворять следующим требованиям:
1) оценка не должна быть больше (при минимизации) или меньше (при максимизации) минимального (максимального) значения функции для рассматриваемого множества;
2) оценка подмножества нижнего уровня не должна быть меньше (при минимизации) или больше (при максимизации) значения оценки подмножества более высокого уровня;
3) оценка единственного варианта решения на последнем уровне точно совпадает со значением критерия целевой функции решения.
Цель ветвления заключается в том, что процесс разбиения на подмножества позволяет получить подмножество, содержащее единственный маршрут. Пары городов (звенья) маршрута фиксируются при движении по дереву в обратном направлении к начальной вершине. На каждом шаге итерации на основе сравнения нижних границ подмножеств ветвление выполняется только из вершины, имеющей меньшее значение нижней границы.
Следует заметить, что оптимальный маршрут, представляющий собой гамильтонов цикл, можно найти, перебрав все возможные варианты. Однако с увеличением числа городов п количество возможных маршрутов (n - 1)! резко возрастает, поэтому вычислительные процедуры удобнее выполнять по методу ветвей и границ на компьютере.
Алгоритм решения задач методом ветвей и границ включает следующую последовательность.
1. Проводим операцию приведения матрицы расстояний по строкам и столбцам, находим нижнюю границу всего множества маршрутов.
2. Для каждой клетки dij = 0 заменяем поочередно нуль, находим сумму новых констант приведения: которые записываем в клетке в скобках рядом с нулем.
3. Выбираем дугу исключения (i,j) из множества по максимальной величине суммы констант приведения путем замены элемента матрицы dij . В результате будет образовано подмножество маршрутов {(i,j)}.
4. Приводим полученную матрицу расстояний и определяем нижнюю границу этого подмножества маршрутов H
5. Включаем дугу (i,y) в маршрут путем исключения i-й строки и j-го столбца из матрицы и замены симметричного элемента матрицы dji.
6. Приводим сокращенную матрицу и определяем нижнюю границу подмножества H .
7. Сравниваем нижние границы подмножеств {(i,j)} и { } и подвергаем подмножество, имеющее меньшее значение нижней границы, ветвлению.
8. Определяем гамильтонов цикл при получении матрицы 2x2.
|
