<<
>>

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

Этот метод применяется для решения задач коммивояжера и по назначению.

Задача коммивояжера:

Пусть задана матрица С=|| Cij || расстояний между городами. Если от некоторой строки i или некоторого столбца j вычесть минимальный из них, то получим матрицу, у которой в каждой строке и в каждом столбце будет хотя бы один нулевой элемент.

Такая матрица называется приведенной, а процесс получения нулей – приведением. Сумма вычитаемых в процессе приведения элементов называется приводящей const обозначается hk, где к – порядковый номер приведения.

Для описания процедуры ветвления используем геометрическую интерпретацию метода. Разбиение множества всех циклов на не пересекаемые подмножества будет изображать дерево с вершинами, состоящими из пар допустимых(i,j) и запрещенных (i,j) городов.

Пара (i,j) содержит все маршруты, которые позволяют переход из города i в j(i,j) – все маршруты, запрещающие переход

из города i в j. Пара (к,l) – содержит все маршруты, в которых разрешен переход не только с к в l, но из i в j.

Обозначим вершину, из которой осуществляется ветвление, k,l k,lчерез х. Вершину, которая наиболее вероятно принадлежит

перспективной ветви, обозначим через y, а запрещенную вершину через y. Поставим в соответствие вершине х сумму приводящих констант, которая представляет ее нижнюю

границу w(x). Процесс ветвления опишем следующим образом: процесс выбора пары городов для ветвления как игру 2-х лиц.

Игрок y имеет преимущество: он может выбирать любую еще не выбранную пару городов для ветвления. Стремясь построить цикл минимальной длины, он должен из исходной матрицы выбрать те пары городов, которым соответствуют минимальные элементы(в приведенной матрице это нулевые элементы).

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

Неоднозначность выбора пары затрудняет процесс игрока y. Поэтому для выбора однозначной стратегии он накладывает ограничивающие факторы для игрока y : если y для объезда выбирает пару городов (i,j), то y должен выехать из любого города, но не в j и въехать в любой город, но не из i. Y ÷ (i,j).

Игрок y будет стремиться выбрать такой допустимый переезд, чтобы суммарный путь был минимальным. Поэтому в строке i приведенной матрицы он выбирает тот город (исключая j), которому соответствует минимальное расстояние. А в столбце j – город (исключая i), которому соответствует минимальный элемент.

Зная о стратегии y , игрок y выбирает из всех допустимых пар городов ту пару, у которой будет наибольшее расстояние. Алгоритм метода

1. Осуществить приведение исходной матрицы С=|| Cij || по строкам. В результате чего получить С’=|| C’ij ||. C’ij = Cij – min Cij

j

2. Осуществить приведение матрицы С’ по столбцам и получить матрицу Ск = || Cкij ||. Cкij = C’ij – min C’ij

i n n

3. Вычислить сумму приводящих констант: hk = ∑ min Cij + ∑ min C’ij

i=1 j j=1 i

Cумма приводящих констант на 1 этапе приведения h’ является нижней границей для множества Х. W(x) = h1 .

4. Выбрать претендентов для ветвления в множество y. Это будут все пары городов (i=1,n) , (j=1,n), (i≠j), для которых сij =0.

5. Для выделенных претендентов подсчитываем величину Qij: Qij = min C’ij + min C’ij

j’≠j i’≠i

min C’ij - в строке i выбирается тот город, исключая j, которому соответствует минимальное j’≠j расстояние приведенной матрицы.

min C’ij – в столбце j выбирается тот город, исключая i, которому соответствует минимальный i’≠i элемент.

6. Из подсчитанных Qij выбрать максимальное: Qkl = max Qij.

7. Пару городов (k,l) включить в множество y (она же является запретной для y).

8. Подсчитать оценку для множества y. Она будет равна ранее произведенным затратам и величине Qkl. W(k,l) = W(x) + Qkl.

9. Из каждого города можно выехать только 1 раз, поэтому из дальнейшего рассмотрения исключить строку к. В каждый город можно въехать только 1 раз, поэтому исключить столбец l. Чтобы избежать замкнутых подциклов, запретить переезд из города l в город к. То есть соответствующему элементу присвоить ∞. Сlk=∞.

10. Полученная усеченная матрица содержит 2 допустимые пары городов, которые являются замыкающими для некоторого цикла без петель. Поэтому на данном шаге проверяется размерность матрицы. Если она 2х2, то перейти к пункту 12, в противном случае – к пункту 11.

11. Проверить, является ли полученная матрица приведенной, если да, то оценка для множества y равна оценке того множества, из которого она получена. W(Ym) = W(Ym-1). Если нет, то осуществить приведение полученной матрицы и подсчитать сумму приводящих констант hk. Тогда оценка для множества y будет равна: W(Ym) = W(Ym-1) + hk.

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

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

<< | >>
Источник: Ответы - Исследование операций и методы оптимизаций. 2016

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