深度优先搜索(DFS)的剪枝方式

作者： 作者的头像   小小_88 ,  2022-01-08 14:22:25 ,  所有人可见 ,  阅读 424

2


1

优化搜索顺序

  • 大部分情况下，应该优先搜索分支较少的节点

排除等效冗余

  • 在不需要考虑顺序的情况下，用组合的方式进行搜索

可行性剪枝

  • 如果发现当前分支再继续搜已经不会有合法结果，及时跳出分支

最优性剪枝

  • 如果发现当前搜索到的结果已经是最优解，不可能有更好的结果，及时停止搜索

记忆化搜索(DP)

  • 常结合DP使用，在DFS问题中不多见

0 评论