Алгоритмы

Branch & Bound: Умный перебор

Цели урока

  • Понимать разницу между Backtracking и Branch & Bound
  • Вычислять границы для отсечения (bounds)
  • Реализовать B&B для Knapsack
  • Понимать B&B для TSP
  • Выбирать стратегию обхода дерева

Предварительные знания

  • Backtracking
  • Динамическое программирование
  • Жадные алгоритмы
  • Backtracking
  • DP
  • Greedy

Когда обычный перебор невозможен из-за размера, а DP не применим - Branch & Bound приходит на помощь. Это основа коммерческих солверов для Integer Programming (CPLEX, Gurobi). Компании экономят миллионы долларов на оптимизации логистики с помощью B&B.

  • CPLEX, Gurobi: коммерческие оптимизаторы
  • Логистика: маршрутизация, scheduling
  • Авиация: crew scheduling, flight planning
  • Производство: cutting stock, bin packing

Лэнд и Дойг: рождение метода ветвей и границ

Метод придумали британские экономистки Айлса Лэнд и Элисон Дойг из Лондонской школы экономики. В 1960 году они опубликовали статью 'An Automatic Method of Solving Discrete Programming Problems' в журнале Econometrica, где описали систематический перебор для задач целочисленного программирования с отсечением бесперспективных ветвей. Сам термин 'branch and bound' закрепился позже, в 1963 году, после работы Джона Литтла и соавторов, применивших метод к задаче коммивояжёра. С тех пор B&B стал ядром коммерческих решателей целочисленного программирования, таких как CPLEX и Gurobi.

Идея: границы отсечения

**Branch & Bound** - метод полного перебора с интеллектуальным отсечением. Если знаем, что ветвь не даст лучшего решения - не исследуем её.

**Ключевые компоненты:**

  1. **Branching**: разбиение задачи на подзадачи (ветвление)
  2. **Bounding**: вычисление границ (нижней/верхней) для подзадачи
  3. **Pruning**: отсечение ветвей, которые не могут улучшить текущий лучший результат

**Применяется для:** задач оптимизации (минимизация/максимизация), особенно NP-hard: TSP, Knapsack, Integer Linear Programming.

Чем Branch & Bound отличается от обычного Backtracking?

Bounding: вычисление границ

**Граница (bound)** - оценка лучшего возможного решения в поддереве.

**Качество границы критично!**

**Способы получения границ:**

  • **Релаксация**: ослабляем ограничения (fractional вместо integer)
  • **Жадная эвристика**: быстрое приближённое решение
  • **LP релаксация**: решаем линейную программу
  • **Lagrangian релаксация**: штрафы вместо ограничений

Для задачи минимизации, когда отсекаем ветвь?

Пример: 0/1 Knapsack

**0/1 Knapsack через Branch & Bound.** Граница - fractional knapsack (жадное решение).

**Сложность:** в худшем случае O(2^n), но на практике отсечения дают огромное ускорение. Для "хороших" инстансов - почти линейно от размера итогового дерева.

Почему fractional knapsack даёт верхнюю границу для 0/1 knapsack?

Пример: TSP (Коммивояжёр)

**TSP - классическая задача для Branch & Bound.** Нижняя граница через MST или assignment problem.

**Более сильные границы для TSP:**

  • **1-tree bound**: MST + два минимальных ребра из стартовой вершины
  • **Assignment problem**: решаем задачу о назначениях (Hungarian algorithm)
  • **Held-Karp bound**: Lagrangian relaxation, очень сильная граница

Почему TSP использует НИЖНЮЮ границу, а Knapsack - ВЕРХНЮЮ?

Стратегии обхода

**Порядок обхода дерева влияет на эффективность.**

**Дополнительные оптимизации:**

  • **Variable ordering**: выбор переменной для ветвления (most constrained first)
  • **Symmetry breaking**: избегаем симметричных решений
  • **Dominance rules**: отсекаем доминируемые узлы
  • **Preprocessing**: упрощаем задачу до запуска
  • **Warm start**: начинаем с хорошего приближённого решения

**На практике:** хорошая начальная эвристика + best-first + качественные границы = решение NP-hard задач среднего размера за секунды.

Какая стратегия обхода требует меньше всего памяти?

Branch & Bound

  • Branching: разбиение на подзадачи
  • Bounding: оценка границ оптимума
  • Pruning: отсечение неперспективных ветвей
  • Качество границы критично для эффективности
  • Best-first vs Depth-first: баланс памяти и скорости

Связанные темы

Branch & Bound связан с другими методами оптимизации.

  • Backtracking — B&B - расширение с bounds
  • Greedy — Используется для начальных решений
  • Approximation — Альтернатива для больших задач

Связанные уроки

  • alg-22-backtracking — Branch and bound - backtracking с отсекающими границами
  • alg-20-greedy — Жадные оценки дают функцию границы
  • alg-34-approximation — Когда B and B медленный, приближаем с гарантиями
  • la-09-systems — Решатели целочисленного программирования используют branch and bound
  • ml-01-intro
Branch & Bound: Умный перебор

0

1

Войти