知识卡片

普通读书笔记卡 · 5654.d.1.f.4.n.3 · 生成模型:未记录

限深搜索去重需保留剩余深度

理解等级:中级

深度优先搜索可使用栈保存待扩展状态,在深度上限内沿一条分支探索后回溯。对同一状态,较浅路径拥有更多剩余深度;若先从较深路径访问就永久标记为已访问,之后可能错误丢弃较浅路径,从而漏掉上限内的解。

可记录该状态已访问的最小深度,并在发现更浅路径时重新扩展;或使用当前路径上的循环检测,具体完整性取决于状态和成本约束。限深搜索找不到解只说明该限制下未找到,不证明全局无解。

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步就能够得到解。由于这个棋面状

    参考来源

    - 位置:《算法技术手册》第7章《深度优先搜索》(spine1592;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1555.html;u182-ch07-004)。 - 结论依据:182全文、03322伪代码与03323搜索树实读;深度去重问题由图搜索推导。 - 原始内容:最大搜索深度固定的情况下才具有可行性。深度优先搜索维护一个栈,保存未访问过的棋面状态。在每次迭代时,深度优先搜索从栈中弹出一个未访问的棋面状态,然后从这个棋面状态开始扩展,根据走法计算其后继棋面状态。如果达到了目标棋面状态,搜索终止。如果没有达到的话,任何在闭合集中的后继棋面状态都会被抛弃。剩余的未 - 位置:《算法技术手册》第7章《使用环境》(spine1593;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1556.html;u184-ch07-004)。 - 结论依据:184指出限深可控制探索范围;若实现保存全部闭合集,内存仍可能随访问状态数增长,而纯路径回溯的空间模型不同。 - 原始内容:控制对资源的使用。 - 位置:《算法技术手册》第7章《解决方案》(spine1594;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1557.html;u185-ch07-004)。 - 结论依据:185的03324–03325从开放栈取状态后加入闭合集,但生成后继仅检查closed,尚未展开的重复状态可能同时进入open;而且首次深层访问会阻止之后更浅访问,可能漏掉限深解。初始状态等于目标会立即返回;代码先检测后继是否为目标再判断depthBound,边界语义需明确。 - 原始内容:闭合集的结构是一个散列表,可以高效地查询是否一个棋面状态已经访问,根据INode对象来计算散列函数的键值、每个棋面状态有一个叫做DepthTransition引用,记录(a)到达这个状态的走法,(b)之前状态,以及(c)从最初位置开始到此的深度。算法会多次复制一个棋面状态,用来尝试各种走法。 例7- - 位置:《算法技术手册》第7章《分析》(spine1596;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1559.html;u187-ch07-004)。 - 结论依据:187以八数码例说明深层首次访问使浅层重访被闭合集抑制,甚至加大深度上限后仍可能找不到本可达到的解。03329–03332列出访问数和解长度,03334图及03328拟合仅描述实验范围;闭合集结构的查找成本也需计入。 - 原始内容:不恰当的搜索深度得不到解 考虑初始状态N2,搜索深度为25,在搜索20 441个棋面状态之后,我们仍然没有得到解。这怎么可能?因为深度优先搜索不会重复访问棋面状态。搜索可是能够在第3451个棋面状态时就能够找到解。 上图是在深度为25时得到的棋面状态,这个棋面状态只有3步就能够得到解。由于这个棋面状