深度优先搜索的优化技巧
作者：
威子
,
2021-12-18 11:32:30
,
所有人可见
,
阅读 843
1.优化搜索顺序
在一些搜索问题中,搜索树的各个层次,各个分支之间的顺序不是固定的,
不同的搜索顺序会产生不同的搜索树形态,其规模大小也相差甚远
(例如排序会影响子树的形态变化)
2.排除等效冗余
在搜索过程中,如果我们能够判定从搜索树的当前结点上沿着几条不同分支到达的子树是等效的，
那么只需要对其中的一条分支执行搜索。
(例如:组合和排序)
3.可行性剪枝
在搜索过程中，及时对当前状态进行检查,如果发现分支已经无法到达递归边界，就执行回溯。
这就好比我们在道路上行走时,远远看到前方是死胡同，就应该立即折返绕路，而不是走到路的尽头在返回。
某些题目条件的范围限制是一个区间,此时可行性剪纸也被称为“上下界剪枝”
4.最优化剪枝
在最优化问题的搜索过程中如果当前花费的代价已经超过当前搜到的最优解,
那么无论采取多么优秀的策略到达递归边界,都不可能更新答案。此时可以停止对当前分支的搜索，执行回溯。
5.记忆化
可以记录每个状态的搜索结果,在重复遍历一个状态时直接检索并返回。
这好比我们对图进行深度优先遍历时，标记一个节点是否已经被访问过。
(可以理解为每种情况只搜索一次,记忆化的加强版就可以理解为动态规划)
so NB
你又上电脑课摸鱼了
NB
NB
太夸张了吧
NB
NB
NB
NB
ccccccccccorz
NB
orz tql %%% sto
NB
老张张好腻害也！！！
超厉害的拉？？？
NB
NB