分支定界法

阐述

分支定界是一类求解离散优化的方法。它将解空间表达为一棵树，然后对这棵树进行完整的搜索。但是，在探索某一个分支之前，会先试图对这个分支所能给出的解的上界或者下界作出预判，从而减少不必要的搜索。例如：

用分支定界法求解背包问题的时候，一个合理的上界是把问题放松为线性规划（可以用贪婪法直接求解）时所得到的解。