【算法2-5】进阶搜索

搜索算法可以枚举所有可能的结果,找到最优结果或者统计符合要求的结果数量。我们在《基础篇》中介绍了搜索算法,包括深度优先搜索(DFS)和广度优先搜索(BFS)。在搜索的过程中,每个过程都有若干决策,所以搜索是一类时空开销都极大的枚举算法,其时间复杂度往往是指数或者是阶乘级别的。

为了使运行速度快一点,在这一章将介绍一些更优秀的搜索策略,也许可以帮助我们通过更 多的测试点。然而,就算是用上了这些策略,这些搜索算法的时间复杂度往往还是指数级别的。当实在没能想出更好的解法时,可以考虑使用搜索算法来通过一些数据规模较小的测试点。

该题单内容将继续改进。

对应进阶篇第 4 章。


  1. P1036 - [NOIP 2002 普及组] 选数
  2. P1433 - 吃奶酪
  3. P1120 - [CERC 1995] 小木棍
  4. P1763 - 埃及分数
  5. CF525E - Anya and Cubes
  6. P1379 - 八数码难题
  7. P5507 - 机关
  8. P2324 - [SCOI2005] 骑士精神
  9. P1074 - [NOIP 2009 提高组] 靶形数独
  10. P1312 - [NOIP 2011 提高组] Mayan 游戏
  11. P3959 - [NOIP 2017 提高组] 宝藏
  12. P2960 - [USACO09OCT] Invasion of the Milkweed G
  13. CF912E - Prime Gift
  14. P4799 - [CEOI 2015] 世界冰球锦标赛 (Day2)
  15. P1078 - [NOIP 2012 普及组] 文化之旅(疑似错题)