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