1. 优化搜索顺序
1. 搜索树中,各个层次、各个分支之间的顺序不是固定的。不同搜索顺序会产生不同的搜索树状态。
如:按照权值排序、优先选择最少的。
2. 排除等效冗余
1. 沿不同分支到达的子树是等效的。
2. 避免混淆“层次”和“分支”,避免遍历若干颗覆盖同一状态空间的等效搜索树。
3. 可行性剪枝
1. 搜索过程中,及时对当前状态进行检查,若无法到达递归边界,就执行回溯。
2. 某些题目条件的范围限制是一个区间,此时也被称为“上下界剪枝”。
4. 最优性剪枝
1. 在最优化问题的搜索过程中,如果当前花费的代价已经超过了当前搜到的最优解,执行回溯。
5. 记忆化
1. 记录每个状态的搜索结果,在重复遍历一个状态时直接检索并返回。就好比对图进行深度优先遍历时,标记一个节点是否已经被访问过。