知识卡片
限深搜索去重需保留剩余深度
深度优先搜索可使用栈保存待扩展状态,在深度上限内沿一条分支探索后回溯。对同一状态,较浅路径拥有更多剩余深度;若先从较深路径访问就永久标记为已访问,之后可能错误丢弃较浅路径,从而漏掉上限内的解。
可记录该状态已访问的最小深度,并在发现更浅路径时重新扩展;或使用当前路径上的循环检测,具体完整性取决于状态和成本约束。限深搜索找不到解只说明该限制下未找到,不证明全局无解。
184指出限深可控制探索范围;若实现保存全部闭合集,内存仍可能随访问状态数增长,而纯路径回溯的空间模型不同。
185的03324–03325从开放栈取状态后加入闭合集,但生成后继仅检查closed,尚未展开的重复状态可能同时进入open;而且首次深层访问会阻止之后更浅访问,可能漏掉限深解。初始状态等于目标会立即返回;代码先检测后继是否为目标再判断depthBound,边界语义需明确。
187以八数码例说明深层首次访问使浅层重访被闭合集抑制,甚至加大深度上限后仍可能找不到本可达到的解。03329–03332列出访问数和解长度,03334图及03328拟合仅描述实验范围;闭合集结构的查找成本也需计入。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 限深搜索去重需保留剩余深度
- · 使用环境
- · 解决方案
- · 分析
原书出处 · 4 处
- · 查看原书依据
最大搜索深度固定的情况下才具有可行性。深度优先搜索维护一个栈,保存未访问过的棋面状态。在每次迭代时,深度优先搜索从栈中弹出一个未访问的棋面状态,然后从这个棋面状态开始扩展,根据走法计算其后继棋面状态。如果达到了目标棋面状态,搜索终止。如果没有达到的话,任何在闭合集中的后继棋面状态都会被抛弃。剩余的未
- · 查看原书依据
控制对资源的使用。
- · 查看原书依据
闭合集的结构是一个散列表,可以高效地查询是否一个棋面状态已经访问,根据INode对象来计算散列函数的键值、每个棋面状态有一个叫做DepthTransition引用,记录(a)到达这个状态的走法,(b)之前状态,以及(c)从最初位置开始到此的深度。算法会多次复制一个棋面状态,用来尝试各种走法。 例7-
- · 查看原书依据
不恰当的搜索深度得不到解 考虑初始状态N2,搜索深度为25,在搜索20 441个棋面状态之后,我们仍然没有得到解。这怎么可能?因为深度优先搜索不会重复访问棋面状态。搜索可是能够在第3451个棋面状态时就能够找到解。 上图是在深度为25时得到的棋面状态,这个棋面状态只有3步就能够得到解。由于这个棋面状