知识卡片
搜索从状态与合法转移建模
以初始状态为根、合法操作为边,按需生成后继状态;状态空间很大时无需预先展开全部节点。单主体搜索寻找通往目标的动作序列;交替对抗博弈还必须考虑对手可能选择的回应。
同一状态可能由多条路径到达,树形展开会重复计算;能否合并或缓存取决于状态是否完整记录轮次、历史与规则。
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)领域的先驱们经常需要解决一些没有已知解法的问题。解决这些问题的常用方法就是将这些问题转化为一个(巨大)图的搜索问题。我们之所以花了一整章讲述此问题,就是因为它非常重要,可以解决大量的问题。然而,要确保真地没有其他可替代的计算方法存在!你可以使用寻径方法来将一个无序数组作为起