CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

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

CVBB ACM Team

用户工具

站点工具

页面工具