Алгоритмические стратегии. Метод ветвей и границ (branch and bound)

Алгоритмические стратегии

Метод ветвей и границ (branch and bound)

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

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

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

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

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

Если такая информация доступна, мы можем сравнивать значение границы узла со значением наилучшего решения, полученного к этому моменту: если значения границы не лучше значения уже имеющегося наилучшего решения – т.е. не меньше в случае задачи минимизации или не больше в случае задачи минимизации, - то такой узел является бесперспективным и его обработка может быть завершена (иногда говорят, что эта ветвь обрезается), поскольку ни одно получаемое решение не может оказаться лучше того, что уже имеется. В этом заключается основная идея метода ветвей и границ.

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

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

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

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

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

Пример 1. Задача о назначениях. Имеется n работников, которым надо выполнить n заданий, по одному заданию каждый (т.е. каждому работнику назначается только одно задание и каждое задание назначается лишь одному человеку). Стоимость выполнения i-ым работником j-го задания известна и равна C(i, j) для всех пар i, j = 1,…n. Задача заключается в следующем: надо распределить задания между работниками таким образом, чтобы они были выполнены с наименьшей стоимостью. Если решать эту задачу методом исчерпывающего перебора, то количество вариантов будет n!.

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

Задачу можно сформулировать следующим образом: выбрать по одному элементу в каждой строке матрицы так, чтобы никакие два выбранных элемента не располагались в одном столбце, а общая сумма выбранных элементов была минимальной. Зад. 1 Зад. 2 Зад. 3 Зад. 4 9 2 7 8 Работник a 6 4 3 7 Работник b 5 8 1 8 Работник c 7 6 9 4 Работник d

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

Как найти нижнюю границу стоимости оптимального решения без реального решения задачи? Можно сделать это разными путями. Например, ясно, что стоимость любого решения, включая оптимальное, не может быть меньше суммы наименьших элементов в каждой из строк матрицы. Для приведенного примера эта сумма равна 2+3+1+4=10. Важно отметить, что это значение не является суммой ни одного из допустимых выборов (т.к. 3 и 1 находятся в одном столбце матрицы), это просто нижняя граница стоимости любого выбора, соответствующего ограничениям задачи.

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

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

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