双向搜索

upd on 9-24:添加了 P3230 [HNOI2013] 比赛。

upd on 10-9:添加了 P10488 Booksort。

注意,双向搜索有两种:https://oi-wiki.org/search/bidirectional/

由于 ivyjiao 很菜,若有错误,敬请指正。

双向搜索题目的一般特征:

  1. 如果给定起点和终点的状态,且符合以上两条,一般是双向同时搜索。

如果你发现了其他双向搜索题欢迎私信添加。

upd 2024-1-11:觉得之前的操作很唐氏,清除了更新记录并删掉了 14 道题目。

meet-in-middle:

我习惯称它为双向深搜。

做法:先搜一半记录结果,再搜另一半匹配结果。

搜索树示意图如下:

模板题 P4799 [CEOI2015 Day2] 世界冰球锦标赛

双向同时搜索:

我习惯称它为双向广搜。

做法:当给定初始状态和目标状态时,可以采用双向广搜的做法。如果发现搜索的两端相遇了,那么可以认为是获得了可行解。然而这种题目很少,因为很少有出题人会把俩状态贴你脸上摆明双向广搜。

搜索树示意图如下:

模板题 P1379 八数码难题


  1. P1466 - [USACO2.2] Subset Sums
  2. P5194 - [USACO05DEC] Scales S
  3. SP739 - NEG2 - The Moronic Cowmpouter
  4. P1032 - [NOIP 2002 提高组] 字串变换(疑似错题)
  5. P1379 - 八数码难题
  6. P4799 - [CEOI 2015] 世界冰球锦标赛 (Day2)
  7. P5691 - [NOI2001] 方程的解数
  8. P10488 - [BAPC 2006 资格赛] Booksort
  9. CF285D - Permutation Sum
  10. CF888E - Maximum Subsequence
  11. AT_abc184_f - [ABC184F] Programming Contest
  12. AT_abc271_f - [ABC271F] XOR on Grid Path
  13. AT_indeednow_2015_quala_4 - パズル
  14. P1225 - [CEOI 1999] 黑白棋游戏
  15. P1778 - [ICPC 2007 Tokyo R] 万圣节后的早晨
  16. P1949 - [NOI2001] 聪明的打字员
  17. P2324 - [SCOI2005] 骑士精神
  18. P2962 - [USACO09NOV] Lights G
  19. P3067 - [USACO12OPEN] Balanced Cow Subsets G
  20. P3154 - [CQOI2009] 循环赛
  21. P3230 - [HNOI2013] 比赛
  22. P4289 - [HAOI2008] 移动玩具
  23. P5507 - 机关
  24. P8187 - [USACO22FEB] Robot Instructions S
  25. P8817 - [CSP-S 2022] 假期计划
  26. P9234 - [蓝桥杯 2023 省 A] 买瓜
  27. CF525E - Anya and Cubes
  28. CF585D - Lizard Era: Beginning
  29. CF1006F - Xor-Paths
  30. AT_abc300_g - [ABC300G] P-smooth number
  31. UVA1601 - 万圣节后的早晨 The Morning after Halloween
  32. UVA1326 - Jurassic Remains
  33. CF912E - Prime Gift
  34. CF1257F - Make Them Similar
  35. CF1767E - Algebra Flash
  36. SP11469 - SUBSET - Balanced Cow Subsets
  37. P6871 - [COCI 2013/2014 #6] HASH
  38. SP12323 - NAKANJ - Minimum Knight moves !!!