Метод ветвей и границ.

Пусть есть задача, имеющая решений: U = (u₁, ..., u_n). С каждым решением связан некоторый показатель , где - оценка эффективности решения. В гамильтоновом цикле в качестве эффективности выбирается длина цикла. Оптимальным будет решение, которое обеспечивает наименьшую из по всем : , т.е. будет минимальный гамильтонов цикл.

Пусть неизвестно точное значение , введём некоторую , которая называется оценкой снизу решения. По мере решения эта оценка может приближаться к .

Разобьём множество решений на два непересекающихся подмножества решений и : . В каждом из этих подмножеств решений есть свои оценки эффективности: - оценка эффективности подмножества решений ; - оценка эффективности подмножества решений ; - общая оценка эффективности.

Предположим, известны оценки снизу решений в подмножествах и : . Настоящее решение будет в том подмножестве, где оценка снизу будет меньшей. Это подмножество опять разбиваем на два подмножества и находим меньшую оценку. Делаем это до тех пор, пока не получим подмножество из одного решения.

Данный метод удобно иллюстрировать с помощью дерева решений:

Рисунок 4.24 – Нахождение минимальной оценки

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

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

4.6.5 Метод ветвей и границ в задаче о коммивояжёре

Показателем эффективности является длина гамильтонова цикла. При вычислении оценки снизу будем учитывать, что каждый гамильтонов цикл графа, представленного в виде матрицы смежности (расстояний), входит только по одному элементу из каждой строки и каждого столбца.

Поэтому, если все элементы каждой строки или столбца уменьшить на какое-то число, то сам гамильтонов цикл не изменится, а длина его уменьшится на это число. Это число принимаем за оценку снизу.

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

Длина оптимального маршрута отличается от длины маршрута в задаче с неприведённой матрицей на сумму констант приведения:
,

где: - константа приведения по строкам, определяется как (минимальный элемент в i – й строке);

- константа приведения по столбцам, определяется как (минимальный элемент в j – м столбце).

Длина маршрута: .

Исключение какой-либо дуги из маршрута означает замену длины данного маршрута на бесконечность: .

Включение дуги в маршрут приводит к исключению строки и столбца, а также, для предотвращения построения негамильтонового цикла, к исключению дуги : .

Выбор дуги . В оптимальный маршрут должны входить дуги, для которых в приведённой матрице смежности . Невключение этих дуг резко увеличивает оценку снизу. Константами приведения являются минимальные элементы в строке и столбце. После замены на бесконечность, сумма минимальных элементов строки и столбца будет минимальной.