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

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

Если алгоритм поиска с возвратом направлен на поиск первого или всех решений для заданного N, то метод ветвей и границ направлен на оптимизацию решения (поиск максимального или минимального решения или в зависимости от критерия оптимальности).

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

1 этап: В матрице стоимости ищутся сначала минимальные элементы в каждой строке и производится вычитание.

S =

Получаем:

Запоминаем h₁= h₂= h₃= h₄=1, h₅=2

Затем производится поиск минимальных элементов в каждом столбце и снова производится вычитание:

h₆= h₇= h₈= h₉=0, h₁₀=1

Получаем: = - приведенная матрица.

Определим сумму всех h_i:

H_i=

H_i является нижней границей стоимости каждого тура для данной вершины графа.

2 этап: В приведенной матрице находим базовый путь в результате поиска строки с номером i, имеющей не менее двух стоимостей, не равных ¥. Среди набора элементов выбираем в качестве базы с наименьшим индексом.

После выбора базы приводим ветвления в графе, т. е. осуществляем построение двух матриц L и R.

Для нашего случая в качестве кандидатов на базовый элемент используются элементы приведенной матрицы R=0:

(S₁₂,, S₂₁, S₃₄,, S₃₅,, S₄₃,, S₅₃)

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

Пример:

S₁₂=1+1=2

S₂₁=1+1=2

S₃₄=1

S₃₅=1

S₄₃=1

S₅₃=1

В качестве базы берем S₁₂, строим для него L и R.

L получается приравниванием к ¥ всех элементов, стоящих в той же строке и в том же столбце, что и базовый элемент, а также асимметричный ему элемент по индексу.

Т. о. асимметричный базе элемент - S_21.

- вершина L первого уровня.

Рассматриваем L₁ в качестве исходной, выполняем приведение и поиск базового элемента для получения матриц L₂ и R₂.

Результат:

h₂₅=h₃₁=1

H₂=1+1=2

H₂=H₁+H₂=7+2=9

H₂ – нижняя граница стоимости каждого тура наследия этой вершины.

Получаем матрицы L₂ и R₂ описанным выше способом и повторяем этот процесс до тех пор, пока не будут достигнуты листья дерева.

Для листа дерева, соответствующего какому-либо туру, в матрице есть только один элемент в каждой строке и в каждом столбце, неравный ¥.

(S₂₅,, S₃₁, S₃₄,, S₃₅,, S₄₃,, S₅₃)

S₂₅ – база, S₅₂ - ¥; H₃=H₂+1=9+1=10

Т. о. листок дерева будет иметь вид:

L₅=

C₁₂,, C₂₅, C₅₄,,C₄₃,, C₃₁ из первого во второй

2®5 5®4 4®3 3®1 город.

С=1+3+3+1+2=10

Принимаем С за минимум, возвращаемся на 1 шаг назад (в L₄) и вычисляем матрицу R₅ (2 тур).

Ветви не имеет смысла исследовать, если нижняя граница для всех туров в данной передаче превышает стоимость наилучшего тура (минимума) в данный момент.

Матрицу R получают из исходной заменой базового элемента на ¥, после чего повторяют процедуру поиска так же, как и для левой матрицы L, выбирая новый базовый элемент.

R₁:C₁₂=¥; S®; (C₁₂,, C₂₁, C₃₄,,C₃₅,, C₄₃,,C₅₃,)

C₂₁®2

Заменяем на ¥

Дата добавления: 2014-01-07