知识卡片

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

搜索从状态与合法转移建模

理解等级:中级

以初始状态为根、合法操作为边,按需生成后继状态;状态空间很大时无需预先展开全部节点。单主体搜索寻找通往目标的动作序列;交替对抗博弈还必须考虑对手可能选择的回应。

同一状态可能由多条路径到达,树形展开会重复计算;能否合并或缓存取决于状态是否完整记录轮次、历史与规则。

179以八数码的格局为状态、相邻滑动为动作,前驱链还原动作序列。树形展开不自动防止重复:不同动作序列可能到达同一局面,需明确开放集和闭合集的去重策略,以及状态键是否覆盖影响后续行动的全部信息。

181的Tiny-Puzzle用两个非负整数作状态,每次增加其中一个;不同动作顺序可抵达相同状态,说明去重必须根据状态而非路径文本决定。状态空间无限时,搜索终止与完整性需额外条件。

183指出输出可以是走法序列或存在性;复杂度记号应区分分支因子 b 与最大深度 d,原文把两者都写成d。

202列出迭代加深、状态缓存、层次化和内存限制等思路。缓存剪枝须记录与未来搜索相关的状态、剩余深度和成本;直接丢弃节点或做层次近似可能改变完整性或最优性,需按具体算法分析。

303的03470汇总搜索算法;解空间搜索可能指数增长,若已知排序、图或动态规划等直接方法,应比较其约束和成本。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 6 处

    • · 查看原书依据

      状态树的通用结构。状态树的根节点表示初始状态,边表示两个状态之间可以转换。 在树中进行搜索是非常有挑战性的,因为所有的状态并不会完全计算出来,要知道,状态的数目可是爆炸性增长的。在跳棋游戏中,有大约5×1020个不同的棋盘状态(Schaeffer,2007)。因此这样的树将会在搜索时按需逐步构造。两

    • · 查看原书依据

      八数码游戏是在一个3×3的网格上,放着8个小方块,分别标上1~8,有一个空的格子没有方块。这个空格周围(水平的或者垂直的)方块可以移动到这里,方块原有位置形成一个新的空格。这个游戏的目标就是从一个初始状态开始,移动空格周围的方块,达到目标状态。如图7-3所示。这种游戏不存在对手玩家,但是玩家的行为和

    • · 查看原书依据

      搜索空间事实上可能是一个图,而不是一棵树,因为到达同一个状态可能有多种走法。即便这样,我们也在一个类似于树而不是图的结构上使用寻路算法,并且评价线性的走法序列。 我们假设存在这样一个问题,我们叫它Tiny-Puzzle,作为深度优先搜索,广度优先搜索以及A*搜索的伪代码所描述的例子。在Tiny-Pu

    • · 查看原书依据

      走法的序列,表示从初始状态到目标状态的路径(或者只是输出是否存在一个解)。 假设 为了分析方便,我们假设d为深度优先搜索的最大深度,d为搜索树的分支因子。

    • · 查看原书依据

      转移表 为了避免重复计算,程序员可以对局面状态进行散列,在一个转移表中存储路径长度。如果状态在后面的搜索中会出现,而且当前深度大于先前的深度,那么搜索将会终止。这种方法能够避免搜索一棵低效的子树。 层次化 如果局面状态能够层次化地表示,那么我们可以重新构建一下搜索空间。层次化寻路A*(HPA*)就应

    • · 查看原书依据

      使用搜索 人工智能(AI)领域的先驱们经常需要解决一些没有已知解法的问题。解决这些问题的常用方法就是将这些问题转化为一个(巨大)图的搜索问题。我们之所以花了一整章讲述此问题,就是因为它非常重要,可以解决大量的问题。然而,要确保真地没有其他可替代的计算方法存在!你可以使用寻径方法来将一个无序数组作为起

    参考来源

    - 位置:《算法技术手册》第7章《概述》(spine1588;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1551.html;u177-ch07-001)。 - 结论依据:177全文实读。 - 原始内容:状态树的通用结构。状态树的根节点表示初始状态,边表示两个状态之间可以转换。 在树中进行搜索是非常有挑战性的,因为所有的状态并不会完全计算出来,要知道,状态的数目可是爆炸性增长的。在跳棋游戏中,有大约5×1020个不同的棋盘状态(Schaeffer,2007)。因此这样的树将会在搜索时按需逐步构造。两 - 位置:《算法技术手册》第7章《搜索树》(spine1589;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1552.html;u179-ch07-001)。 - 结论依据:179以八数码的格局为状态、相邻滑动为动作,前驱链还原动作序列。树形展开不自动防止重复:不同动作序列可能到达同一局面,需明确开放集和闭合集的去重策略,以及状态键是否覆盖影响后续行动的全部信息。 - 原始内容:八数码游戏是在一个3×3的网格上,放着8个小方块,分别标上1~8,有一个空的格子没有方块。这个空格周围(水平的或者垂直的)方块可以移动到这里,方块原有位置形成一个新的空格。这个游戏的目标就是从一个初始状态开始,移动空格周围的方块,达到目标状态。如图7-3所示。这种游戏不存在对手玩家,但是玩家的行为和 - 位置:《算法技术手册》第7章《假设》(spine1591;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1554.html;u181-ch07-001)。 - 结论依据:181的Tiny-Puzzle用两个非负整数作状态,每次增加其中一个;不同动作顺序可抵达相同状态,说明去重必须根据状态而非路径文本决定。状态空间无限时,搜索终止与完整性需额外条件。 - 原始内容:搜索空间事实上可能是一个图,而不是一棵树,因为到达同一个状态可能有多种走法。即便这样,我们也在一个类似于树而不是图的结构上使用寻路算法,并且评价线性的走法序列。 我们假设存在这样一个问题,我们叫它Tiny-Puzzle,作为深度优先搜索,广度优先搜索以及A*搜索的伪代码所描述的例子。在Tiny-Pu - 位置:《算法技术手册》第7章《输入/输出》(spine1592;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1555.html;u183-ch07-001)。 - 结论依据:183指出输出可以是走法序列或存在性;复杂度记号应区分分支因子 b 与最大深度 d,原文把两者都写成d。 - 原始内容:走法的序列,表示从初始状态到目标状态的路径(或者只是输出是否存在一个解)。 假设 为了分析方便,我们假设d为深度优先搜索的最大深度,d为搜索树的分支因子。 - 位置:《算法技术手册》第7章《相关算法》(spine1609;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1572.html;u202-ch07-001)。 - 结论依据:202列出迭代加深、状态缓存、层次化和内存限制等思路。缓存剪枝须记录与未来搜索相关的状态、剩余深度和成本;直接丢弃节点或做层次近似可能改变完整性或最优性,需按具体算法分析。 - 原始内容:转移表 为了避免重复计算,程序员可以对局面状态进行散列,在一个转移表中存储路径长度。如果状态在后面的搜索中会出现,而且当前深度大于先前的深度,那么搜索将会终止。这种方法能够避免搜索一棵低效的子树。 层次化 如果局面状态能够层次化地表示,那么我们可以重新构建一下搜索空间。层次化寻路A*(HPA*)就应 - 位置:《算法技术手册》第11章《原则:如果没有显而易见的解法,使用搜索》(spine1690;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1652.html;u303-ch07-001)。 - 结论依据:303的03470汇总搜索算法;解空间搜索可能指数增长,若已知排序、图或动态规划等直接方法,应比较其约束和成本。 - 原始内容:使用搜索 人工智能(AI)领域的先驱们经常需要解决一些没有已知解法的问题。解决这些问题的常用方法就是将这些问题转化为一个(巨大)图的搜索问题。我们之所以花了一整章讲述此问题,就是因为它非常重要,可以解决大量的问题。然而,要确保真地没有其他可替代的计算方法存在!你可以使用寻径方法来将一个无序数组作为起