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

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

Definition

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

Scope

Эта тема охватывает методы исчерпывающего поиска, организованные вокруг дерева поиска: метод отката (backtracking), который отбрасывает частичные кандидаты, как только они нарушают ограничение, и метод ветвей и границ (branch and bound), который использует границы для наилучшего достижимого значения целевой функции для отсечения поддеревьев при оптимизации. Включает примеры задач удовлетворения ограничений (задача о N ферзях, раскраска графа, Судоку) и примеры задач комбинаторной оптимизации (задача коммивояжера, целочисленное программирование), а также обсуждается, почему эти методы остаются ценными для NP-трудных задач, несмотря на экспоненциальную сложность в худшем случае.

Core questions

• Как пространство решений задачи моделируется в виде дерева поиска частичных присваиваний?
• Какие проверки ограничений позволяют методу отката рано отсекать невыполнимые ветви?
• Как вычисляются нижние и верхние границы для отсечения ветвей при оптимизации?
• Как порядок ветвления и оценки влияет на практическую производительность?
• Почему эти методы используются для NP-трудных задач, несмотря на экспоненциальную сложность в худшем случае?

Key concepts

• дерево поиска
• поиск в глубину
• распространение ограничений
• отсечение
• функции оценки
• текущее лучшее решение
• задача о N ферзях
• релаксация целочисленного программирования

Key theories

Отсечение дерева поиска

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

Оценочные функции в методе ветвей и границ

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

Clinical relevance

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

History

Метод отката был систематизирован как общая техника в 1950-х и 1960-х годах, в частности, описан Голомбом и Баумертом. Метод ветвей и границ был введен Эйлсой Лэнд и Элисон Дойг в 1960 году для целочисленного линейного программирования и с тех пор стал центральным в комбинаторной оптимизации, обеспечивая работу современных решателей смешанного целочисленного программирования.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

В чем разница между методом отката и методом ветвей и границ?

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

Если эти методы экспоненциальны в худшем случае, почему их используют?

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