https://wiki.cvbbacm.com/ 2026-04-30T06:53:04+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-08-14T15:57:46+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%90%9C%E7%B4%A2:%E5%8F%8C%E5%90%91%E6%90%9C%E7%B4%A2&rev=1597391866&do=diff 双向搜索 简介&思想 在进行搜索的时候可以从某一个角度将搜索的状态减少或减小得到同样的状态的时间开销，从而减少了时间复杂度。 例题 世界冰球锦标赛 来源：洛谷 p4799 概述：共N $(1\le N\le40)$$2^20=1,048,576$ text/html 2020-08-20T19:33:53+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%90%9C%E7%B4%A2:%E6%A8%A1%E6%9D%BF&rev=1597923233&do=diff 简介&思想 例题 来源： 概述： 答案： ---------- 总结 text/html 2020-08-07T16:19:21+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%90%9C%E7%B4%A2:%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2&rev=1596788361&do=diff 记忆化搜索 简介&思想 在进行搜索的时候如果对某一个状态在不同的搜索过程中会搜索多次并且得到的结果只与状态本身的参数有关而与搜索过程无关，我们就可以用数组将第一次搜索这个状态所得到的结果储存，从而减小了复杂度。$(0\le i\ge K)$ text/html 2020-08-20T19:30:18+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%90%9C%E7%B4%A2:a&rev=1597923018&do=diff A* 简介&思想 通过估价函数预计搜索到的结点与终点的距离，以估价距离从小到大为顺序搜索终点，得到最短路，减少搜索时间。与dijkstra相似。 估价函数越大搜索越少，但估价函数小于等于真实距离时才能得到正确的结果，因此要注意估价函数的选取，可以调整估价函数的倍数。 text/html 2020-08-20T20:04:17+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%90%9C%E7%B4%A2:dlx&rev=1597925057&do=diff DLX（Dancing Links X 舞蹈链） 简介 求解精准覆盖问题：给定一个集合和若干个子集，选择若干个子集使得原集合中每一个元素出现且仅出现一次。 思路 用矩阵的方式存储子集：每一行代表一个子集，每一列代表原集合中的一个元素，某行某列用0和1代表这一个子集是否含有这一个元素。$\to$$\to$ text/html 2020-08-20T19:49:36+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%90%9C%E7%B4%A2:ida&rev=1597924176&do=diff IDA* 简介&思想 迭代加深：有时候广搜太多深搜也太多，主要在于枝数太多、深度太深，因此枚举深搜的深度并不断深搜。时间复杂度由于搜索树的性质只与最深一层有关。 IDA*：迭代加深+估价函数（估计深度）