В4 и 5 Решение задач о рюкзаке и коммивояжера методом ветвей и границ.

1) Разбиваем множество X на два подмножества 1 X и 2 X, находим на каждом из них границу 1 f и 2 f;2) Выбираем множество, на котором оценка минимальна, разбиваем его на два подмножества 3 X и 4 X (этот процесс называется ветвлением), находим на каждом из них границу 3 f и 4 f (при этом само это множество исключается из списка подмножеств); 3) На каждом шаге мы имеем разбиение исходного множества X на конечное число подмножеств для каждого из которых известна граница целевой функции f. Повторяем пункт 2 до тех пор, пока в каком-то из получающихся подмножеств не найдется настоящий минимум (подмножество будет иметь настолько небольшой размер, что нахождение минимума будет не очень сложной задачей). Такой минимум тоже является оценкой для множества, только в отличие от остальных данная оценка является точной; 4) Отбрасываем те подмножества из нашего списка, граница у которых не меньше, чем значение функции f в найденной точке 5) Если после этого список подмножеств окажется пустым, найденная точка и является решением задачи. Если нет, продолжаем алгоритм с пункта 2, до тех пор, пока мы либо не отбросим все подмножества как не перспективные, либо не найдем другую точку, в которой значение функции f еще меньше. При воплощении этого алгоритма часто используется дерево вариантов. Вершинам данного дерева соответствуют множества X, 1 X, 2 X, …, nX и их оценки. Из каждой вершины-множества дуги ведут к его подмножествам, получающимся при ветвлении. Если у вершины (множества) имеется точная оценка, такую вершину помечаем звездочкой (в этой вершине далее ветвление не происходит, а ее оценка используется для прекращения ветвления в тех вершинах, у которых оценки больше). Примерный вид дерева вариантов представлен на рисунке 4.1. Таким образом, для того, чтобы решать задачу методом ветвей и границ, необходимо:1. Предложить метод ветвления, т.е. разбиения множества всех вариантов X на подмножества;2. Для каждого из подмножеств, получающихся при ветвлении указать способ для вычисления границы (оценки целевой функции на данном подмножестве).

Отметим, что эффективность применения метода ветвей и границ зави-сит от того, насколько трудоемким является процесс вычисления оценок, и насколько точными являются оценки, получаемые на каждом шаге. Для об-легчения этого процесса обычно ветвление организуют так, чтобы нахождение оценки для всего множества и для его подмножеств было однотипным. Желательно также, чтобы точность находимых оценок повышалась с уменьшением размеров подмножеств. Оценить достоинства и трудности ме-тода ветвей и границ можно только при рассмотрении конкретных задач.

Постановка задачи о коммивояжере. Имеется n городов. Расстояния между любой па-рой городов известны и составляют Если прямого маршрута между городами i и j не существует, то .Расстояния между городами удобно записывать в виде матрицы (таблица 5.1), где .

Коммивояжер, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них один, и только один раз, и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы наименьшей.

Если городам поставить в соответствие вершины графа, а соединяющим их дорогам – дуги, то в терминах теории графов задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает c конечной. Здесь под длиной контура понимают не количество дуг, входящих в контур, а сумму их длин.

Алгоритм решения: 1. Приводим матрицу расстояний по строкам и столбцам. Находим нижнюю границу всего множества маршрутов: . 2. Каждый нуль в приведенной матрице условно заменяем на ∞ и на-ходим сумму констант приведения . Значения записываем в соответствующие клетки рядом с нулями. 3. Априорно исключаем из гамильтонова контура ту дугу (i j), для которой сумма констант приведения максимальна исключение дуги (i j) достигается заменой элемента в матрице расстояний на ∞. В результате исключения дуги (i, j) будет образовано подмножество гамильтоновых контуров . 4. Приводим полученную матрицу расстояний и определяем нижнюю границу подмножества гамильтоновых контуров . 5. Априорно включаем дугу (i j) в гамильтонов контур, что ведет к исключению в матрице, полученной после выполнения пункта 2, i -й строки j -го столбца. Заменяем один из элементов матрицы на (в простейшем случае симметричный), чтобы не допустить образования негамильтонова контура.

6. Приводим сокращенную матрицу и находим нижнюю границу подмножества маршрутов . 7. Проверяем размерность сокращенной матрицы. Если сокращенная матрица размерности 2x2, то переходим к выполнению пункта 9; если же размерность матрицы больше, чем 2x2, то – к пункту 8. 8. Сравниваем нижние границы подмножеств гамильтоновых контуров и переходим к выполнению п. 2. При этом, если , то разбиению подлежит подмножество (дальнейшему анализу подвергается матрица, полученная в результате последнего выполнения пункта 4). Если же разбиению подлежит подмножество (дальнейшему анализу подвергается матрица, полученная после последнего выполнения пункта 6). Разбиение множества гамильтоновых контуров на подмножества сопровождаем построением дерева (рисунок 3, практическое занятие 5). 9. Определяем гамильтонов контур и его длину. 10. Сравниваем длину полученного контура с нижними границами оборванных ветвей. Если длина гамильтонова контура не превышает нижних границ оборванных ветвей дерева, то задача решена. Если же длина контура больше нижней границы некоторых ветвей, то, действуя по алгоритму, развиваем эти ветви до тех пор, пока не получим маршрута с меньшей длиной или не убедимся, что его не существует.