Алгоритм метода ветвей и границ

Этап 0. Вычисление первоначальной оценки.

Полагаем ξ (0,1) = h + H.

Этап 1. Ветвление.

Пусть построено подмножество X (k,t) и вычислена оценка ξ (k,t). Этому подмножеству соответствует приведенная матрица С'' (k,t).

Пусть построено подмножество X (k,t) и вычислена оценка ξ (k,t). Этому подмножеству соответствует приведенная матрица С'' (k,t).

Подмножество X (k,t) разбиваем на два подмножества X (k+ 1 ,m+ 1), X (k+ 1 ,m+ 2), где m – последний порядковый номер в уровне на момент разбиения.

В подмножество X (k+ 1 ,m+ 1) будет входить множество всех маршрутов, содержащих путь из города p в город q.

В подмножество X (k+ 1 ,m+ 2) будет входить множество всех маршрутов, не содержащих путь из города p в город q.

Переход p → q, включенный в подмножество X (k+ 1 ,m+ 1), должен характеризоваться минимальными (нулевыми) затратами. Если таких переходов несколько, то среди нулевых элементов приведенной матрицы выбирается такой переход, чтобы в подмножество X (k+ 1 ,m+ 2) попали варианты с наибольшими затратами.

Первое слагаемое в сумме характеризует минимальные затраты на выход из города p (переход p → q запрещен), а второе минимальные затраты на вход в город q при том же условии.

Этап 2. Пересчет оценок.

Матрицу С (k+ 1 ,m+ 1) получаем из матрицы С'' (k,t) вычеркиванием строки p и столбца q, полагаем c_qp = ∞, делая невозможным обратный переход q → p. Производим процедуру приведения к матрице С'' (k+ 1 ,m+ 1), вычисляя h_i и H_j, и считаем оценку ξ (k+ 1 ,m+ 1) = ξ (k,t) + h + H.

Чтобы получить матрицу С (k+ 1 ,m+ 2) в матрице С'' (k,t) полагаем c_pq = ∞, запрещая переход p → q. Производим процедуру приведения к матрице С'' (k+ 1 ,m+ 2), вычисляя h_i и H_j, и считаем оценку ξ (k+ 1 ,m+ 2) = ξ (k,r) + h + H.

Этап 3. Отбрасывание вариантов.

Отбрасывание вариантов осуществляется по минимальной оценке или по достижению предельного решения (когда дальнейшее разбиение невозможно).

Если предельное решение не достигнуто, то среди «конечных» оценок ξ (i,j) выбираем минимальную. Она соответствует подмножеству X (i,j), переходим к Этапу1, где подмножество X (k,t) становится подмножеством X (i,j).

Пример. Решить задачу коммивояжера для шести городов (n=5) методом ветвей и границ при заданной матрице расстояний:

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

Как видно максимум достигается в двух клетках (1,2) и (5,3). Выберем одну из них – клетку (1,2) и разобьем множество Х (0,1) на подмножества Х (1,1) и Х (1,2).

Подмножество Х (1,1) содержит условие из города 1 идти в город 2. Ему соответствует матрица С (1,1), которая получается из матрицы расстояний С'' (0,1) удалением строки 1 и столбца 2, а также, для запрета малых циклов, изменением на ∞ значения клетки (2,1).

Вычтем h_i из каждого элемента c_ij, соответствующей строки. Получим матрицу С' (1,2). Теперь вычислим H_j.

Вычтем H_i из каждого элемента, соответствующего столбца.

После приведения получим матрицу С'' (1,2).

Шаг 2.

Минимальная оценка ξ (1,1), поэтому разбиваем множество Х (1,1). Определим клетку (p,q). Найдем суммы минимумов для клеток с нулевыми значениями:

Максимальная сумма соответствует клетке (5,3). Относительно нее производим разбиение множества Х (1,1) на подмножества Х (2,1) и Х (2,2).

Подмножество Х (2,1) содержит условие из города 5 идти в город 3. Ему соответствует матрица С (2,1), которая получается из матрицы расстояний С'' (1,1) удалением строки 5 и столбца 3, а также изменением на ∞ значения клетки (3,5), для запрета малых циклов.

Для этой таблицы все h_i и H_j равны 0, поэтому оценка останется прежней ξ (2,1)= ξ (1,1)=16, а матрица С'' (2,1) примет следующий вид:

Оценка ξ(2,2)= ξ (1,1)+4+1=16+5=21.

Достраиваем дерево разбиения:

Шаг 3.

Минимальная оценка ξ (2,1), поэтому разбиваем множество Х (2,1). Определим клетку (p,q). Найдем суммы минимумов для клеток с нулевыми значениями:

Как видно, максимум достигается в двух клетках (2,5) и (4,0). Выберем одну из них – клетку (2,5) и разобьем множество Х (2,1) на подмножества Х (3,1) и Х (3,2).

Подмножество Х (3,1) содержит условие из города 2 идти в город 5. Ему соответствует матрица С (3,1), которая получается из матрицы расстояний С'' (2,1) удалением строки 2 и столбца 5.

Вычтем h_i из каждого элемента c_ij, соответствующей строки. Получим матрицу С' (3,2). Теперь вычислим H_j.

Шаг 4.

Минимальная оценка ξ (3,1), поэтому разбиваем множество Х (3,1) Определим клетку (p,q), относительно которой будем проводить разбиение:

Максимальная сумма соответствует клетке (4,0). Относительно нее производим разбиение множества Х (3,1) на подмножества Х (4,1) и Х (4,2).

Подмножество Х (4,1) содержит условие из города 4 идти в город 0. Ему соответствует матрица С (4,1), которая получается из матрицы расстояний С'' (3,1) удалением строки 4 и столбца 0, а также, для запрета малых циклов, изменением на ∞ значения клетки (0,4).

Вычислим коэффициенты приведения h_i и H_j:

Достраиваем дерево разбиения:

Шаг 5.

Минимальная оценка ξ (4,1), Для подмножества Х (4,1) имеем:

Т.е. остаются переходы из 0 в 1 и из 3 в 4. Добавим эти переходы к переходам, полученным при движении по дереву от вершины до подмножества Х(4,1), и получим цикл 0 → 1 → 2 → 5 → 3 → 4 → 0, длина которого равна 16. Т.к. все остальные оценки ξ для концевых вершин больше 16, то этот цикл оптимальный.

Ответ: оптимальный путь 0→1→2→5→3→4→0, его длина 16.

Поиск по сайту: