剪枝¶
可行性剪枝¶
可行性剪枝的思想较为简单，就是如果当前状态已经无法搜索成功的解了，那么我们就退出搜索。这种剪枝方法在之前的代码里面很常见，比如全排列问题当中判断一个数是否已经选过了，迷宫问题当中判断是否已经走出了迷宫边界。
使用可行性剪枝需要仔细看题，知道答案需要满足什么条件，然后再在搜索函数里面添加特判，把不合法的状态全部都去掉。注意别把可以产生答案的状态剪掉了。
最优化剪枝¶
最优化剪枝的思想就是如果当前状态可以搜出解，但是不可能比当前的最优解更优了，那么就退出搜索。例如在迷宫问题当中，第一次遇到的格子必然是最优的，那么之前就已经遇到过的格子就不用搜索了。
另一种题目是判断是否有解，那么广度优先搜索可以直接 return，但是深度优先搜索里面就必须判断当前是否已经有解了，如果是的话就可以不用继续搜索了。
迷宫问题里面的 dfs 代码就有个缺陷：可能会死循环，因为我们没有标记格子的最小距离。（注意这里需要标记最小距离，因为 dfs 不想 bfs 那样是一层一层搜的，后面到达的状态可能会比前面的更优）。因此我们只需要加入最小距离数组就可以避免死循环的问题了，但是我们仍然无法保证复杂度，因为一个格子不一定只会遍历一次。所以那题就是一道必须使用广搜的题目了。