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

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

Согласно основополагающим работам1,2 важнейшими принципами метода ветвей и границ, позволяющими для широкого класса дискретных задач существенно уменьшить объем перебора, являются следующие принципы:

  • 1) задание структурной схемы дерева вариантов на основе определения числа возможных значений для каждого из компонентов вектора альтернатив;
  • 2) задание системы нумерации вершин на дереве вариантов с целью установления соответствия между комбинациями альтернатив и результатами решения задач;
  • 3) задание стратегии ветвления перспективных вершин при поиске оптимального решения на дереве вариантов;
  • 4) задание способа вычисления оптимистической оценки перспективности вершин (нижняя граница при решении задачи на минимум или верхняя граница при решении задачи на максимум) путем сведения основной задачи к более простым частным подзадачам.

Обратите внимание!

Признаками классификации алгоритмов, созданных на основе метода ветвей и границ, являются:

  • • структурная схема дерева вариантов;
  • • система нумерации вершин;
  • • стратегия ветвления дерева вариантов;
  • • способ вычисления оптимистической оценки перспективности вершин на дереве вариантов.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >