======深度优先搜索及其优化====== 大家都会 =====原理===== 深度优先搜索也就是DFS，俗称一条路走到黑，是暴力的好帮手。\\ 基本原理是找到一个没有访问过的节点，继续访问其一个子节点，不断往深处走，直到没有子节点（碰壁）后回退到上一个节点，访问它没有访问过的另一个子节点。\\ 这样的操作可以把所有的节点按“深度优先”原则全部访问到，所以称为“深度优先搜索”。\\ 如果用函数来实现的话会自然地形成一个栈的结构（与[[2020-2021:teams:no_morning_training:weekly:宽度优先搜索及其优化|宽度优先搜索]]的队列相比较）\\ =====例题===== 只要你想的话每道题都是例题\\ 经典例题有八皇后、全排列等。\\ =====优化===== 这是重点。\\ 搜索是万能的，但是只有搜索是万万不能的。\\ 这里列几个目前我所知道的优化方法。\\ ====剪枝==== 这个其实也比较基础，自己写DFS的时候自然而然可能就无师自通了。\\ 大概就是把那些一看就不对的搜索方向直接剪掉。\\ 关键是判断剪掉哪些。\\ 例题以后补一下摸了 ====贪心==== 也叫基于贪心的启发式搜索。\\ 就是在选择子节点的时候进行一些排序。\\ 比较复杂点的就是[[A*算法]]\\ ====深度限制==== 字面意思，对深搜的深度加上一些限制，对于特定的题可以有效避免深得离谱的情况。