第六章 回溯算法
回溯算法
-
以深度优先的方式系统地搜索问题的解的方法称为回溯法。
-
可以系统地搜索一个问题的所有解或任意解。
-
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
-
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。
0 —1背包问题
假设背包容量C＝30，w＝{16，15，15}，v＝{45，25，25}
旅行商问题
在回溯法搜索解空间树时，通常采用两种策略（剪枝函数）避免无效搜索以提高回溯法的搜索效率：
- 用约束函数在扩展结点处剪去不满足约束条件的子树；
- 用限界函数剪去不能得到最优解的子树。
解0—1背包问题的回溯法用剪枝函数剪去导致不可行解的子树。
解旅行商问题的回溯算法中，如果从根结点到当前扩展结点的部分周游路线的费用已超过当前找到的最好周游路线费用，则以该结点为根的子树中不包括最优解，就可以剪枝。