爆搜 & 模拟专题
即为那些没有多少思维难度， 但实现起来非常复杂的题目。
- eg1: NOIP2003 提高组 侦探推理
Solution : 搜索哪些话为真，哪些为假， 并根据矛盾关系剪枝。
- eg2: [NOIP2015 提高组] 斗地主
Solution : 模拟+搜索, 先计算一张,两张,三张,四张的牌各有几张， 再进行搜索。
- eg3:[SCOI2005] 骑士精神
Solution : 采用迭代加深搜索， 即限定深度的dfs， 若超过限定步数则直接返回， 若搜不到解则增加限定深度， 直到找到一组解。
但是这还不够， 我们需要一点优化。可以对搜索中的每个状态设计一个估价函数来衡量状态优劣。若当前步数+估价最少步数 >= 当前答案 则直接剪枝。(类似A*算法)。
关于A*：
- 概述：采用广度优先搜索策略,在搜索过程中使用启发函数（即上文中的估价函数）,即有大致方向的向前进虽然目标有时候不是很明确。
- 核心：启发函数。
- 应用：可用于优化bfs，当前步数+估计步数越小， 则该状态越有潜力， 用优先队列存储状态， 每次取最有潜力的状态进行拓展。
书接上文， 我们将A* 与迭代加深结合起来， 就成为了传说中的 IDA* 。
设当前限定深度为$d$， 若当前步数 + 估价步数 > $d$则可以直接剪枝。
剪枝技巧：
-
- 优化搜索顺序（先大后小）
-
- 避免重复搜索（记忆化）
-
- 前瞻性预测（A*）
eg1: 小木棍
eg2: 八数码难题
eg3: 生日蛋糕
小组成员：邵品渊，邵品砚，蒋佳成，顾天泽