Описание метода ветвей и границ

Пусть х¹ – центр куба Х. Вычисляем и присваиваем это значение рекорду . Разбиваем куб Х ¹ⁱ со стороной ½ и вычисляем значения целевой функции в их центрах: , i= 1,…2ⁿ, обновляя по ходу вычислений значение рекорда . Проверяем выполнение условия для i=1,…,2ⁿ и отбрасываем соответствующие подкубы. Каждый из оставшихся разбиваем на 2ⁿ одинаковых подкубов Х^2ij со стороной ¼ и поступаем как прежде. На любом шаге у нас формируется множество К «кубиков» со сторонами 2^-l, l>=2, целое. Правило выбора очередного кубика для разбиения называется правилом ветвления – возможные варианты приводятся ниже. Кубики со стороной не больше исключаются из множества К – дробление кубика заканчивается. Также исключаются кубики, попавшие в множество (с индексом k – номером кубика) для текущего значения рекорда, - правило отсечения ветвей. Рекорд обновляется при получении меньшего значения целевой функции (правило получения границ, т.е. оценок). Значения целевой функции вычисляются в центре каждого нового подкубика, включаемого в К после разбиения выбранного для этого кубика. Алгоритм останавливается, когда К пусто.

Рис.2. Граф-дерево.

Указанная терминология и название метода определяются тем, что визуально данная схема перебора представляется в виде графа-дерева, корневая вершина которого соответствует кубу Х, вершины первого яруса – подкубам X^li, вершины второго яруса – кубикам X^2li, подсоединенным к своим порождающим вершинам X^li-го яруса, и т.д. (см. рис. 2). Если кубик исключается из К, его вершина закрывается – из нее не будут идти ветви на следующий ярус. Порядок закрытия вершины определяется правилом отсечения (своим для каждой массовой задачи), порядок раскрытия – правилом ветвления (своим для каждой индивидуальной задачи). Различают два вида правил ветвления по типу построения дерева решений (выбора вершин для раскрытия): «в ширину», когда сначала раскрываются все вершины одного яруса до перехода к следующему, и в «глубину» - всякий раз раскрывается лишь одна (обычно с лучшим значением рекорда) вершина на ярусе до конца ветви. На практике реализуют некоторую смесь, например, первое правило пока хватает машинной памяти (в К не слишком много элементов), затем переключаются на второе. Предпочтительность той или иной стратегии ветвления оценивается каждым вычислителем по-своему, исходя из главной задачи метода ветвей и границ – быстрее получить лучший рекорд, чтобы отсечь больше ветвей. Удачный выбор стратегии ветвления в МВГ (например, на основе имеющейся у вычислителя дополнительной информации или эвристических соображений об объекте) позволяет (хотя и не гарантированно) решать задачи большой размерности.

Отметим, что в худшем случае - не удается отбросить ни одной точки х – и приходим к полному перебору; т.е. указанная экспоненциальная оценка точна на классе всех липшицевых функций.