算法提高课汇总

$DFS$ 剪枝

按$dfs$搜索顺序连接节点可以构成一颗$dfs$搜索树.

什么是剪枝

一般来说, 从根节点到叶子节点的路径对应一个方案. 而剪枝意味着算法在到达叶子节点之前,
可以推出从当前节点到叶子节点对应方案不合法/不是最优解, 从而可以提前结束, 以优化搜索时间.

常用剪枝方式

1. 优化搜索顺序 — 一般情况下, 应优先搜索分支较少的节点.

其原因可以考虑一个假想例子, 若从根到叶子节点路径上只有4个节点, 考虑两种情况.

若首先搜索分支较多的节点, 搜索树可能是(灰色节点表示被剪枝节点):

而如果首先考虑分支较少的节点, 搜索树可能是:

同样是到达第3个节点返回(剪枝), 分支较少的搜索树剪枝效果更好(只需要搜索一条路径即可返回).

1. 删除等效冗余 — 不重复搜索效果相同的方案.

一般常见于对于组合问题, 规定搜索顺序以防止重复搜索同一集合(变为排列问题).

1. 可行性剪枝 — 当前路径不合法, 提前退出.

2. 最优性剪枝 — 当前路径已经不可能更新最优解, 提前返回.

3. 记忆化搜索 — 常见于可以用$DP$求解的问题.