Branch-and-bound

释义 Definition

分支定界法（分枝定界法）：一种用于求解整数规划与组合优化问题的算法框架。它把原问题不断“分支”成更小的子问题，并用可计算的“界（bound）”来判断某些分支不可能产生更优解，从而“剪枝”以减少搜索。

例句 Examples

We used branch-and-bound to solve the scheduling problem.
我们使用分支定界法来解决排程问题。

Branch-and-bound explores a search tree and prunes subproblems whose bounds cannot beat the best known solution.
分支定界法会探索一棵搜索树，并剪去那些“界”不可能优于当前已知最优解的子问题。

发音 Pronunciation (IPA)

/brnt n band/

词源 Etymology

该术语由两个常见动词短语组合而来：branch（“分支、分叉”）指把问题拆成多个子问题形成搜索树；bound（“界、上界/下界”）指通过计算上界或下界来判断某条分支是否值得继续搜索。作为方法名，它在运筹学、整数规划与计算机科学的优化领域中广泛使用。

相关词 Related Words

• Backtracking
• Pruning
• Optimization
• Integer Programming
• Combinatorial Optimization
• Search Tree
• Heuristic
• Constraint Programming

文学与著作中的出现 Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）
• Integer and Combinatorial Optimization（Nemhauser & Wolsey）
• Combinatorial Optimization: Algorithms and Complexity（Papadimitriou & Steiglitz）
• The Traveling Salesman Problem: A Computational Study（Applegate, Bixby, Chvátal, Cook）