分支定界法（分枝定界法）：一种用于求解整数规划与组合优化问题的算法框架。它把原问题不断“分支”成更小的子问题，并用可计算的“界（bound）”来判断某些分支不可能产生更优解，从而“剪枝”以减少搜索。
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.
分支定界法会探索一棵搜索树，并剪去那些“界”不可能优于当前已知最优解的子问题。
/ˌbræntʃ ən ˈbaʊnd/
该术语由两个常见动词短语组合而来：branch（“分支、分叉”）指把问题拆成多个子问题形成搜索树；bound（“界、上界/下界”）指通过计算上界或下界来判断某条分支是否值得继续搜索。作为方法名，它在运筹学、整数规划与计算机科学的优化领域中广泛使用。
Select Language