分支界限法
分支界限法（Branch and Bound）是一种通过剪枝来优化搜索的算法策略。
基本思想
先发现优化解的一个界限，接着剪枝那些未达到边界但已经超过界限的解。
实现步骤
- 使用爬山法等方法先快速确定一个较优方案（得到初始界限）
- 进行系统化的搜索
- 在搜索过程中，如果当前路径的代价已经超过已知最优解的代价，则剪枝（不再继续探索该路径）
- 不断更新界限，直到找到全局最优解
特点
- 能够保证找到全局最优解
- 通过剪枝提高效率
- 适用于组合优化问题（如旅行商问题、分配问题）
- 效率依赖于界限的紧密度
链接到
- 上一个知识点：5.5 Best-First搜索
- 下一个知识点：无（本章最后一个知识点）