回溯法与分支定界法

回溯法和分支定界法是系统搜索范式，它们将候选解决方案空间探索为一棵树，通过剪除无法导向有效或最优解的子树，使得原本指数级的搜索在实践中变得可行。

Definition

回溯法是对部分候选解树的深度优先搜索，一旦部分候选解无法完成为有效解，即剪除该分支；分支定界法在此基础上增加了目标值的数值界限，以便丢弃其最佳可能值无法超越当前最优解的分支。

Scope

本主题涵盖围绕搜索树组织的穷举搜索技术：回溯法（一旦部分候选方案违反约束即放弃）和分支定界法（利用可实现目标值的界限来剪除优化中的子树）。它包括约束满足问题示例（N皇后问题、图着色、数独）和组合优化问题示例（旅行商问题、整数规划），并讨论了尽管在最坏情况下成本呈指数级，但这些方法对于NP-hard问题为何仍有价值。

Core questions

• 如何将问题的解空间建模为部分赋值的搜索树？
• 哪些约束检查允许回溯法提前剪除不可行分支？
• 如何计算上下界以在优化中剪除分支？
• 分支和定界顺序如何影响实际性能？
• 尽管在最坏情况下呈指数级，为何这些方法仍用于NP-hard问题？

Key concepts

• 搜索树
• 深度优先探索
• 约束传播
• 剪枝
• 定界函数
• 当前最优解
• N皇后问题
• 整数规划松弛

Key theories

搜索树的剪枝

这两种范式都将候选解组织成一棵树并进行深度优先探索；正确性源于穷举性，而效率则源于剪除那些被证明不可能包含有效或改进解的子树。

分支定界法中的定界函数

分支定界法维护迄今为止找到的最佳解，以及每个子树中可达到的最佳值的界限（例如，LP松弛）；当子树的界限无法改进当前最优解时，该子树将被丢弃。

Clinical relevance

分支定界法是运筹学中精确组合优化的支柱，包括用于调度、路由和规划的整数和混合整数规划求解器。回溯法是约束求解器、SAT式搜索、谜题求解器和解析器的基础，在这些领域中，带剪枝的系统搜索是获得精确答案的实用途径。

History

回溯法在20世纪50年代和60年代被系统化为一种通用技术，其中Golomb和Baumert的描述尤为著名。分支定界法由Ailsa Land和Alison Doig于1960年为整数线性规划引入，此后成为组合优化的核心，为现代混合整数规划求解器提供了动力。

Key figures

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

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

回溯法和分支定界法有什么区别？

回溯法通常用于可行性问题和约束满足问题，并剪除违反约束的分支。分支定界法针对优化问题，并额外使用数值界限进行剪枝，丢弃任何其最佳可能目标值无法超越已找到的最佳解的子树。

如果这些方法在最坏情况下是指数级的，为什么还要使用它们？

对于NP-hard问题，目前尚无已知的多项式精确算法，但有效的剪枝通常能在实际实例中消除绝大部分搜索树，因此分支定界法和回溯法求解器通常能比其最坏情况界限所暗示的更快地找到可证明的最优解。