人工智能原理 第2章 搜索技术 （上）.

Presentation on theme: "人工智能原理 第2章 搜索技术 （上）."— Presentation transcript:

1 人工智能原理 第2章 搜索技术 （上）

2 第2章 搜索技术 本章内容 搜索与问题求解 2.2 无信息搜索策略 2.3 启发式搜索策略 2.4 局部搜索算法 2.5 约束满足问题 2.6 博弈搜索 参考书目 附录 A*算法可采纳性的证明

3 2.1 搜索与问题求解 2.1.1 问题与问题的解 2.1.2 问题实例 2.1.3 搜索策略
第2章 搜索技术 2.1 搜索与问题求解 问题与问题的解 问题实例 搜索策略

4 搜索与问题求解 问题求解过程是搜索答案(目标)的过程 / 所以问题求解技术也叫搜索技术—通过对状态空间的搜索而求解问题的技术
第2章 搜索技术 搜索与问题求解 问题求解过程是搜索答案(目标)的过程 / 所以问题求解技术也叫搜索技术—通过对状态空间的搜索而求解问题的技术 问题求解智能体是一种基于目标的智能体 在寻找到达目标的过程中，当智能体面对多个未知的选项时，首先检验各个不同的导致已知评价的状态的可能行动序列，然后选择最佳序列—这个过程就是搜索

5 2.1.1 问题与问题的解 问题可以形式化地定义为4个组成部分 智能体的初始状态(即搜索的开始)
第2章 搜索技术 2.1.1 问题与问题的解 问题可以形式化地定义为4个组成部分 智能体的初始状态(即搜索的开始) 后继函数—智能体采取的可能行动的描述，通常为<行动，后继状态> / 初始状态和后继函数隐含地定义了问题的状态空间 / 状态空间中的一条路径是通过行动序列连接起来的一个状态序列 目标测试—检查给定的状态是不是目标 路径耗散函数—每条路径都有一个数值化的耗散值，反映了性能度量 / 求解问题的代价

6 问题的解 问题的解就是初始状态到目标状态的路径 上述解题过程把解决一个问题的过程描述出来，称之为解题知识的过程性表示
第2章 搜索技术 问题的解 问题的解就是初始状态到目标状态的路径 解的优劣由路径耗散函数量度(代价) 最优解就是路径耗散函数值最小的路径 上述解题过程把解决一个问题的过程描述出来，称之为解题知识的过程性表示 过程性知识与陈述性知识相对 搜索过程解题的特点—没有直接的方法(公式)可以求解，而是一步一步的探索

7 状态空间 数据基：代表了所要解决的问题，有初始状态，可能有目标状态也可能没有
第2章 搜索技术 状态空间 数据基：代表了所要解决的问题，有初始状态，可能有目标状态也可能没有 状态空间：在解题过程中的每一时刻，数据基都处于一定的状态，数据基所有可能状态的集合称为状态空间 有向图：若把每个状态看成一个节点，则整个状态空间是一个有向图 / 该图不一定全连通，即从某些状态不一定能到达另外一些状态

8 第2章 搜索技术 问题的可解性 可解的：在每个连通部分，每个弧代表一个运算符，将状态改变 / 如果从代表初始状态的节点出发，有一条路径通向目标状态，则称此目标状态所代表的问题在当前初始状态下是可解的 搜索空间：在解题过程中达到过的所有状态的集合，称为搜索空间 不同于状态空间，搜索空间只是其中一部分 状态空间和搜索空间都属于过程性知识表示

9 2.1.2 问题实例 玩具问题 现实问题 八数码游戏(九宫图) 河内塔 八皇后问题 真空吸尘器世界 旅行商问题 超大规模集成电路的布局
第2章 搜索技术 2.1.2 问题实例 玩具问题 八数码游戏(九宫图) 河内塔 八皇后问题 真空吸尘器世界 现实问题 旅行商问题 超大规模集成电路的布局 自动装配排序 / 蛋白质设计 互联网搜索

10 八数码游戏 八数码游戏：1-8数字(棋子)/9个方格(棋盘格)/1个空格
第2章 搜索技术 八数码游戏 八数码游戏：1-8数字(棋子)/9个方格(棋盘格)/1个空格 可用如下形式的规则来表示数字通过空格进行移动：<a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9> 共24条规则=4角*2+4边*3+1中间*4 搜索顺序举例： (1)优先移动行数小的棋子(数字) (2)同一行中优先移动列数大的棋子 约束规则：不使离开既定位置的数字数增加

11 第2章 搜索技术 八数码游戏的搜索树 既定位置=终态

12 八数码问题形式化 初始状态 后继函数 目标测试 路径耗散函数 初始状态向量—规定向量中各分量对应的位置，各位置上的初始数字
第2章 搜索技术 八数码问题形式化 初始状态 初始状态向量—规定向量中各分量对应的位置，各位置上的初始数字 后继函数 移动规则—按照某条规则移动数字，将得到的新向量 目标测试 新向量是否是目标状态(也是向量形式) 路径耗散函数 每次移动代价为1

13 河内塔(1) 河内塔问题：n个大小不等的圆盘从一个柱子移到另一个柱子，共有3个柱子(n阶河内塔问题)
第2章 搜索技术 河内塔(1) 河内塔问题：n个大小不等的圆盘从一个柱子移到另一个柱子，共有3个柱子(n阶河内塔问题) 约束：从第1根柱子移动到第3根柱子上去，利用第2根柱子 / 每次移动1个盘子，且移动过程必须是小盘落大盘 描述：设每个状态为(a1, a2, a3, …, an), ai=1, 2, 3—表示第i个盘子在第1/2/3根柱子上

14 第2章 搜索技术 河内塔(2) 递归定义：{(a1, a2, a3, …, an)}为n阶河内塔的状态集合，则{(a1, a2, a3, …, an, 1), (a1, a2, a3, …, an, 2), (a1, a2, a3, …, an, 3)}是n+1阶河内塔的状态集合 1阶河内塔有3个状态，2阶河内塔有9个状态，n阶河内塔有3n个状态，给出1/2/3阶河内塔的状态图

15 第2章 搜索技术 河内塔问题图解

16 河内塔问题形式化 初始状态 后继函数 目标测试 路径耗散函数 初始状态向量—规定向量中各分量对应所有n个盘子，位置上数字代表3个柱子之一
第2章 搜索技术 河内塔问题形式化 初始状态 初始状态向量—规定向量中各分量对应所有n个盘子，位置上数字代表3个柱子之一 后继函数 移动规则—依据约束条件给出的各状态的后继状态 目标测试 新向量是否是目标状态(也是向量形式) 路径耗散函数 每移动一个盘子的代价为1

17 河内塔问题求解 求最短路径问题：状态图中从三角形1个顶点走到另一个顶点 结论： 求解过程—对状态空间的搜索—以2阶河内塔为例
第2章 搜索技术 河内塔问题求解 求最短路径问题：状态图中从三角形1个顶点走到另一个顶点 结论： (1)如果初始状态或目标状态在三角形顶点上，则最短路径唯一； (2)对于任意2个状态，最短求解路径至多为2条。(中国某大学研究生证明) 求解过程—对状态空间的搜索—以2阶河内塔为例

18 河内塔问题的搜索树 × × × × × × × × × × × × √ √ √ √ 第2章 搜索技术 1,1 2,1 3,1 1,1 3,1
2,3 2,2 1,1 2,1 3,2 3,3 × × × × √ √ 3,3 1,3 2,1 2,2 1,2 2,2 3,1 3,3 × × × × √ 2,3 3,3 1,2 1,1 √ 2,2 3,2 1,3 1,1

19 求解过程—树搜索 求解问题的过程使用搜索树形式 每个状态对应搜索树中一个节点 根节点对应于初始状态
第2章 搜索技术 求解过程—树搜索 求解问题的过程使用搜索树形式 每个状态对应搜索树中一个节点 根节点对应于初始状态 每次从搜索树的上层节点出发，根据约束条件进入下一个可能的状态，即展开新的一层树节点—节点扩展 节点展开的顺序即代表了不同的搜索策略 当展开的节点为目标状态时，就找到了问题的一个解

20 2.1.3 搜索策略 研究搜索过程考虑的若干问题 (1)有限搜索还是无限搜索 (2)已知目标还是未知目标 (3)目标或目标+路径
第2章 搜索技术 2.1.3 搜索策略 研究搜索过程考虑的若干问题 (1)有限搜索还是无限搜索 (2)已知目标还是未知目标 (3)目标或目标+路径 (4)有约束还是无约束 (5)数据驱动(向前搜索)还是目标驱动 (6)单向搜索还是双向搜索

21 搜索的分类 搜索过程的分类：状态空间搜索(图搜索方式)，问题空间搜索(层次方法)，博弈空间搜索 无信息搜索与启发式搜索
第2章 搜索技术 搜索的分类 搜索过程的分类：状态空间搜索(图搜索方式)，问题空间搜索(层次方法)，博弈空间搜索 无信息搜索与启发式搜索 启发式：利用中间信息改进控制策略 启发式：(1)任何有助于找到问题的解，但不能保证找到解的方法是启发式方法 (2)有助于加速求解过程和找到较优解的方法是启发式方法 启发式也叫启发函数

22 搜索算法的性能 4种途径来评价搜索算法的性能 完备性—当问题有解时，算法是否保证找到一个解
第2章 搜索技术 搜索算法的性能 4种途径来评价搜索算法的性能 完备性—当问题有解时，算法是否保证找到一个解 最优性—算法是否能找到一个最优解(路径耗散函数值最小的路径) 时间复杂性—找到一个解需要花费多少时间 空间复杂性—在搜索过程中需要占用多少内存

23 性能量度 时空复杂性的量度—由状态空间图的大小来衡量 / 相关度量如下： 分支因子 b (每次展开的平均节点个数) 目标节点的深度 d
第2章 搜索技术 性能量度 时空复杂性的量度—由状态空间图的大小来衡量 / 相关度量如下： 分支因子 b (每次展开的平均节点个数) 目标节点的深度 d 路径的最大长度 m 搜索深度限制 l 搜索耗散

24 第2章 搜索技术 2.2 无信息搜索策略 广度优先搜索 深度优先搜索和深度有限搜索 叠代深入深度优先搜索 无信息搜索策略性能比较 图搜索算法

25 盲目搜索策略 无信息搜索也称盲目搜索：没有任何附加信息，只有生成后继和区分目标与非目标状态 有5种盲目搜索策略 广度优先搜索 代价一致搜索
第2章 搜索技术 盲目搜索策略 无信息搜索也称盲目搜索：没有任何附加信息，只有生成后继和区分目标与非目标状态 有5种盲目搜索策略 广度优先搜索 代价一致搜索 深度优先搜索 深度有限搜索 迭代深入深度优先搜索

26 2.2.1 广度优先搜索 广度优先搜索过程： 广度优先搜索可以调用树搜索算法(Tree-Search)实现 首先扩展根节点
第2章 搜索技术 2.2.1 广度优先搜索 广度优先搜索过程： 首先扩展根节点 接着扩展根节点的所有后继节点 然后再扩展后继节点的后继，依此类推 在下一层任何节点扩展之前搜索树上的本层深度的所有节点都已经被扩展 广度优先搜索可以调用树搜索算法(Tree-Search)实现 其参数fringe(边缘/扩展分支)为先进先出队列FIFO

27 第2章 搜索技术 树搜索算法(1) function Tree-Search(problem,fringe) return solution /failure (initial fringe=empty, mode=FIFO) fringe←Insert(Make-Node(Initial-State[problem]),fringe) do while(1) if fringe=Empty then return failure node←Remove-First(fringe) if State[node]=Goal then return Solution(node) fringe←Insert-All(Expend(node,problem), fringe)

28 树搜索算法(2) 关键在于如何扩展节点 function Expend(node,problem) return set of nodes
第2章 搜索技术 树搜索算法(2) 关键在于如何扩展节点 function Expend(node,problem) return set of nodes successors←the empty set for each <action,result> in Successor-Find[problem] (State[node]) do s←new Node / State[s]←result Parent-Node[s]=node / Action[s]=action Path-Cost[s]=Path-Cost[node]+Step-Cost[node, action,s] Depth[s]←Depth[node]+1 add s to successors return successors

29 广度优先搜索的性能 在上述算法中，广度优先搜索以Tree-Search(problem,FIFO-Queue)调用树搜索算法
第2章 搜索技术 广度优先搜索的性能 在上述算法中，广度优先搜索以Tree-Search(problem,FIFO-Queue)调用树搜索算法 从4种度量来评价广度优先搜索： 完备性—总能找到一个解 如果每步扩展的耗散相同时，广度优先搜索能找到最优解 内存消耗是比执行时间消耗更大的问题 指数级的时间消耗(空间和时间消耗的例子参见p60图3.11)

30 2.2.2 深度优先搜索和深度有限搜索 深度优先搜索过程： 搜索算法参见深度有限搜索算法(l=∞)
第2章 搜索技术 2.2.2 深度优先搜索和深度有限搜索 深度优先搜索过程： 总是扩展搜索树的当前扩展分支(边缘)中最深的节点 搜索直接伸展到搜索树的最深层，直到那里的节点没有后继节点 那些没有后继节点的节点扩展完毕就从边缘中去掉 然后搜索算法回退下一个还有未扩展后继节点的上层节点继续扩展 搜索算法参见深度有限搜索算法(l=∞)

31 第2章 搜索技术 深度优先搜索的性能 深度优先搜索通过后进先出队列LIFO(栈)调用Tree-Search实现 / 通常使用递归函数实现，依次对当前节点的子节点调用该函数 性能： 内存需求少—如分支因子=b/最大深度=m的状态空间深度优先搜索只需要存储bm+1个节点(比较广度优先O(bd+1)) 不是完备的 / 不是最优的 最坏情况下时间复杂性也很高O(bm)

32 深度有限搜索 深度优先搜索的无边界问题可以通过提供一个预先设定的深度限制l来解决 深度=l的节点当作无后继节点看待
第2章 搜索技术 深度有限搜索 深度优先搜索的无边界问题可以通过提供一个预先设定的深度限制l来解决 深度=l的节点当作无后继节点看待 虽然解决了无限路径问题，但如果l<d则找不到解 如果选择d>l则深度优先搜索也不是最优的 时间复杂度O(bl) 空间复杂度O(bl) 深度优先搜索可看作是一种特例即l=∞

33 第2章 搜索技术 非递归的深度有限搜索算法 function Depth-Limited-Search(problem,fringe,limit) return solution/failure/cutoff fringe←Insert(Make-Node(Initial-State[problem]),fringe) (mode=LIFO) do while(1) if fringe=Empty then return failure node←Remove-First(fringe) if State[node]=Goal then return Solution(node) else if Depth[node]=limit then return cutoff else fringe←Insert-All(Expend (node, problem), fringe)

34 搜索步数的限制 上面算法中可能有两类失败 有时深度有限搜索基于问题本身的知识，如状态空间的直径即问题求解的最大步数
第2章 搜索技术 搜索步数的限制 上面算法中可能有两类失败 cutoff表示到达了有限深度而无解 failure表示一般的返回值无解 有时深度有限搜索基于问题本身的知识，如状态空间的直径即问题求解的最大步数 但对于大多数问题，不到问题解决时是无法知道求解步数的限制

35 2.2.3 叠代深入深度优先搜索 如果每次改变限制深度，多次调用深度有限搜索算法，就得到了叠代深入深度优先搜索算法
第2章 搜索技术 2.2.3 叠代深入深度优先搜索 如果每次改变限制深度，多次调用深度有限搜索算法，就得到了叠代深入深度优先搜索算法 其深度限制依次为0/1/2…这样，当搜索到达最浅的目标节点深度时就可以发现目标节点 这种搜索结合了广度优先和深度优先两种算法的优点(算法见p63) 分支因子有限时是完备的 / 路径耗散是节点深度的非递增函数时是最优的 空间需求为O(bd) / 时间复杂性为O(bd)

36 状态的生成 叠代深入搜索中因为多次重复搜索，因此部分状态被多次生成，看起来很浪费
第2章 搜索技术 状态的生成 叠代深入搜索中因为多次重复搜索，因此部分状态被多次生成，看起来很浪费 但是因为在分支因子比较平衡的搜索树中，多数节点都在最底层(即叶子节点)，所以上层节点的多次生成影响不是很大 / 与广度优先搜索相比，效率还是更高 一般来讲，当搜索空间很大而解的深度未知时，叠代深入搜索是一个首选的无信息搜索方法

37 第2章 搜索技术 2.2.4 无信息搜索策略比较 评价标准 广度优先 代价一致 深度优先 深度有限 叠代深入 双向搜索 是否完备 时间 空间 是否最优 是 A 是 A/B 否 否 是 A 是 A/D O(bd+1) O(bC/e) O(bm) O(bl) O(bd) O(bd/2) O(bd+1) O(bC/e) O(bm) O(bl) O(bd) O(bd/2) 是 C 是 否 否 是 C 是 C/D 关于A/B/C/D的解释：A—如果b有限则是完备的 / B—单步耗散≥e则是完备的 / C—如果单步耗散都是相同的则是最优的 / D—两个方向上都使用广度优先搜索

38 第2章 搜索技术 2.2.5 图搜索算法 已经看到搜索过程中会出现重复的状态扩展，应该避免 / 如果算法不检测重复状态的话，有可能使一个本来可解的问题变为不可解 检测就是把要扩展的节点与已扩展的节点进行比较，把遇到的相同状态去掉 所以要记录已经扩展的节点—引入两个表—存储已扩展的节点closed表和未扩展的节点open表(即前述fringe) 新算法称为图搜索算法

39 第2章 搜索技术 图搜索算法 function Graph-Search(problem,fringe) return solution or failure closed←empty set fringe←Insert(Make-Node(Initial-State[problem]),fringe) do while(1) if fringe=Empty then return failure node←Remove-First(fringe) if State[node]=Goal then return Solution(node) if State[node] !CLOSED then add State[node] to closed fringe←Insert-All(Expend(node,problem),fringe)

40 图搜索算法的性能 由树到图：存在不同分支节点的合并
第2章 搜索技术 图搜索算法的性能 由树到图：存在不同分支节点的合并 图搜索算法与树搜索算法比较：只是增加了对展开节点的判断，因此由不同的待扩展节点排列方式而形成的搜索策略(如广度优先和深度优先)的性能仍然同树搜索算法 对于含很多重复状态的问题，其搜索效率比树搜索算法有效很多 讨论参见p67

41 例子：“农夫过河”问题搜索 农夫过河问题 用向量<人,狼,羊,白菜>表示在河岸两边的情况 0表示此岸 / 1表示彼岸
第2章 搜索技术 例子：“农夫过河”问题搜索 农夫过河问题 用向量<人,狼,羊,白菜>表示在河岸两边的情况 0表示此岸 / 1表示彼岸 过河规则有8条(隐含了约束条件) 1 (0, *, *, *)→(1, *, *, *) / 2 (0, 0, *, *)→(1, 1, *, *) 3 (0, *, 0, *)→(1, *, 1, *) / 4 (0, *, *, 0)→(1, *, *, 1) 5 (1, *, *, *)→(0, *, *, *) / 6 (1, 1, *, *)→(0, 0, *, *) 7 (1, *, 1, *)→(0, *, 0, *) / 8 (1, *, *, 1)→(0, *, *, 0) *=0/1表示任意岸边但必须相同

42 “农夫过河”—广度优先搜索 × 第2章 搜索技术 closed表 <0 0 0 0> <1 0 1 0>
< > < > < > < > < > < > × 所用规则序列 3/5/2/7/4 所用规则序列 3/5/4/7/2 所用规则序列 3/5/2/7/4/5/3 所用规则序列 3/5/4/7/2/5/3

43 “农夫过河”—深度优先搜索 × 只使用一个搜索分支 / 所扩展的第一个节点是最新节点 第2章 搜索技术 closed表
< > < > < > < > < > < > × 只使用一个搜索分支 / 所扩展的第一个节点是最新节点 所用规则序列 3/5/2/7/4 所用规则序列 3/5/2/7/4/5/3

44 2.3 启发式搜索策略 2.3.1 贪婪最佳优先搜索 2.3.2 A*搜索 2.3.3 启发函数 2.3.4 联机搜索
第2章 搜索技术 2.3 启发式搜索策略 贪婪最佳优先搜索 A*搜索 启发函数 联机搜索

45 启发式搜索通用算法 启发式搜索也称有信息搜索，其通用算法称为最佳优先搜索(Best-First-Search)
第2章 搜索技术 启发式搜索通用算法 启发式搜索也称有信息搜索，其通用算法称为最佳优先搜索(Best-First-Search) 最佳优先搜索基于评价函数扩展节点—按照距离目标最短的评价值来扩展 并不是真正的最佳—只是表现得最佳/近似最佳 算法的关键因素是启发函数(Heuristic function)，记为f(n) / f(n)=从节点n到目标节点的最低耗散路径的耗散估计值 启发函数引导搜索两种方式—贪婪最佳优先搜索 / A*搜索(A*算法)

46 2.3.1 贪婪最佳优先搜索 贪婪最佳优先搜索的评价函数f(n)=h(n) 使用贪婪最佳优先搜索算法搜索从Arad到首都的行车最短路线
第2章 搜索技术 2.3.1 贪婪最佳优先搜索 贪婪最佳优先搜索的评价函数f(n)=h(n) 在贪婪最佳优先搜索中总是选择当前离目标最近(最小代价)的节点进行扩展(搜索) 局部最佳未必全局最佳—不是最优的(下例) 使用贪婪最佳优先搜索算法搜索从Arad到首都的行车最短路线 Arad的下一站有3个城市S(253)/T(329)/ Z(374) → 扩展Sibiu有3个城市F(176)/O(380) /R(193) → 扩展Fagaras直接可到目的地 然而实际不是最优的：S→F→B实际全长310 / S→RV→P→B实际全长278，多了32km

47 第2章 搜索技术 问题实例—Romania公路图

48 问题实例(1) 寻找从Arad到首都的行车最短路线 评价函数f(n)=h(n) 直线距离启发式hSLD 与实际距离相关但需另外给出，见下表
第2章 搜索技术 问题实例(1) 寻找从Arad到首都的行车最短路线 评价函数f(n)=h(n) 直线距离启发式hSLD 与实际距离相关但需另外给出，见下表 Arad 366 Mehadia 241 Bucharest Neamt 234 Craiova 160 Oradea 380 Dobreta 242 Pitesti 100 Eforie 161 Rimnicu Vilcea 193 Fagaras 176 Sibiu 253 Giurgiu 77 Timisoara 329 Hirsova 151 Urziceni 80 Iasi 226 Vaslui 199 Lugoj 244 Zerind 374

49 问题实例(2) 启发函数h(n)最小化会对错误的起点比较敏感 需要仔细检查重复状态，否则可能永远找不到解 与深度优先搜索类似，非最优、非完备
第2章 搜索技术 问题实例(2) 启发函数h(n)最小化会对错误的起点比较敏感 例子：地图中Iasi到Fagaras的行车路线(走入死路的可能) 需要仔细检查重复状态，否则可能永远找不到解 与深度优先搜索类似，非最优、非完备 最坏情况下时空复杂度都是O(bm) / m为最大搜索深度

50 2.3.2 A*搜索 A*搜索的评价函数为f(n)=g(h)+h(n) g(n)是从初始节点到该节点n的路径耗散
第2章 搜索技术 2.3.2 A*搜索 A*搜索的评价函数为f(n)=g(h)+h(n) g(n)是从初始节点到该节点n的路径耗散 h(n)是从节点n到目标节点的最低耗散路径的估计耗散值，称为启发式或启发函数 因此，f(n)=经过节点n、具有最低耗散值的解的估计耗散 找到g(n)+h(n)值最小的节点当然是合理的(参见书中p79图4.3对于地图的搜索) 若启发函数h(n)满足一定条件，则A*搜索是完备的和最优的

51 搜索算法的可采纳性 [定义]搜索算法的可采纳性(可采用性) (Hart, Nilsson, Raphel, 1968)
第2章 搜索技术 搜索算法的可采纳性 [定义]搜索算法的可采纳性(可采用性) (Hart, Nilsson, Raphel, 1968) 如果状态空间中的目标状态存在，并且从初始状态到目标状态有一条通路，而搜索算法一定能在有限步内终止并找到一个最优解(代价最低)，则这个状态空间搜索算法称为可采纳的 对于A*搜索来说，使用树搜索算法(Tree-Search)，则它是可采纳的 如果对启发函数h(n)作一定限制，则使用图搜索算法(Graph-Search)也是可采纳的

52 可采纳的启发函数 算法的可采纳性取决于启发函数的可采纳性 启发函数h(n)是可采纳的—h(n)从来不会过高地估计到达目标的耗散值
第2章 搜索技术 可采纳的启发函数 算法的可采纳性取决于启发函数的可采纳性 启发函数h(n)是可采纳的—h(n)从来不会过高地估计到达目标的耗散值 此即—h(n)满足h(n)≤h*(n)，h*(n)是从当前节点n到达目标的最低耗散值 此即—f(n)永远不会高估经过节点n的解的实际耗散—f(n)≤f*(n)，所以是最优解 如果h(n)是可采纳的，那么使用Tree-Search的A*算法是可采纳的(最优的) 自己尝试证明，参考附录证明过程

53 A*搜索的Tree-Search算法 第2章 搜索技术
function Tree-Search(problem,fringe) return solution or failure Select h(n) Make-Node(Initial-State[problem] & get their f(n) Insert(nodes, fringe) Sort(fringe, f(n)) do while(1) if fringe=Empty then return failure node←Remove-First(fringe) if State[node]=Goal then return Solution(node) Expend(node, problem) & get their f(n)

54 第2章 搜索技术 A*搜索的Graph-Search算法 如果A*搜索使用图搜索算法，则A*必然返回最优解的结论就不成立—原因是如果最优路径不是第一个生成的，可能因为有重复状态而被丢弃 解决方案： 1)修改Graph-Search算法使得能够进行比较，只丢弃耗散值大的路径 2)保证到达任何重复状态的最优路径总是第一条被追随的路径—要求h(n)保持一致性(单调性) 算法—请自行给出

55 第2章 搜索技术 h(n)的一致性(1) [定义]启发函数的一致性—如果对于每个节点n和通过任意行动a生成n的每个后继节点n’，从节点n到达目标节点的估计耗散值h(n)不大于从n到n’的单步耗散与从n’到目标节点的估计耗散值之和，则h(n)称为一致的 此即h(n)≤c(n,n’,a)+h(n’) / 是三角不等式的某种形式 每个一致的启发函数都是可采纳的 证明要点：h(n)≤c(n,n’,a)+h(n’), h(n)≤c*(n,n’,a)+h(n’) 可得h(n)–h*(n)≤h(n’)–h*(n’) 目标节点h(T)=h*(T)=0回退可得任意节点h(n)≤h*(n)

56 h(n)的一致性(2) 通常我们选择的启发函数h(n)都满足一致性要求(因而必定是可采纳的) 关于一致性的结论：
第2章 搜索技术 h(n)的一致性(2) 通常我们选择的启发函数h(n)都满足一致性要求(因而必定是可采纳的) 关于一致性的结论： 如果h(n)是一致的，那么使用Graph-Search的A*算法是最优的 附录证明似乎没有利用此条件 如果h(n)是一致的，那么沿着任何路径的f(n)值是非递减的(由一致性定义可得) f(n)耗散值沿着任何路径都是非递减的结论允许在状态空间中画出等值线(见下图)

57 第2章 搜索技术 道路里程的等值线 Z T L M D C G U O N I V H E 420 A 380 B F P R S 400

58 A*搜索节点的扩展 A*搜索由初始节点出发开始搜索，以同心带状增长f(n)耗散值的方式扩展节点 如果C*是最优解路径的耗散值，则有以下结论：
第2章 搜索技术 A*搜索节点的扩展 A*搜索由初始节点出发开始搜索，以同心带状增长f(n)耗散值的方式扩展节点 如果h(n)=0则为代价一致搜索(只按g(n)值排序)则同心带为“圆型”，使用启发函数则同心带向目标节点方向拉伸 如果C*是最优解路径的耗散值，则有以下结论： A*算法扩展所有f(n)≤C*的节点 A*算法在到达目标节点之前可能会扩展一些正好处于“目标等值线”上的节点 A*算法不扩展f(n)>C*的节点(均被剪枝)

59 A*算法的性质(1) A*算法是完备的—如果解存在，就一定能找到 / 因为找到解只要有限步
第2章 搜索技术 A*算法的性质(1) A*算法是完备的—如果解存在，就一定能找到 / 因为找到解只要有限步 A*算法是最优的—即可采纳的(一个普遍采用的证明见附录) A*算法对于任何给定的启发函数都是效率最优的 / 没有任何其他算法扩展的节点少于A*算法 但是，A*算法对于多数问题来说，搜索空间处于目标等值线内的节点数量是求解路径长度的指数级

60 A*算法的性质(2) 如果要求不以指数级增长，则启发函数需要满足条件
第2章 搜索技术 A*算法的性质(2) 如果要求不以指数级增长，则启发函数需要满足条件 对于几乎所有的启发函数来说，偏差至少都是与路径耗散成正比的，而不是路径耗散的对数 / 所以，在实际应用中，往往不是坚持找到最优解，而是采用以下两种方式： 使用A*算法的变种算法快速找到非最优解 设计准确而非严格可采纳的启发函数

61 A*算法在空间方面的改进 A*算法在内存中保留所有生成的节点，消耗极大—因而对于许多大规模问题时不实用的 A*算法要减少对内存的需求—改进
第2章 搜索技术 A*算法在空间方面的改进 A*算法在内存中保留所有生成的节点，消耗极大—因而对于许多大规模问题时不实用的 A*算法要减少对内存的需求—改进 递归最佳优先搜索RBFS—模仿标准的最佳优先搜索的递归算法，只是用线性存储空间 如果h(n)是可采纳的，则RBFS最优 MA*(存储限制A*)和SMA*(简化的MA*)—充分利用可用的内存 SMA*的思想—当内存放满时，就丢弃最差的一个子节点而加入新节点 如果任何最优解是可到达的，则SMA*是最优的

62 2.3.3 启发函数 A*搜索的关键就是设计可采纳的或者一致的(单调的)启发函数 例子—八数码问题 关于八数码问题的一些数据：
第2章 搜索技术 2.3.3 启发函数 A*搜索的关键就是设计可采纳的或者一致的(单调的)启发函数 如何评价启发函数 / 如何设计启发函数 例子—八数码问题 关于八数码问题的一些数据： 随机产生的八数码游戏的平均解的步数=22 分支因子约为3 穷举搜索(盲目搜索)考虑的状态个数322≈3.1*1010 实际可到达的不同状态个数9!/2=181440

63 八数码问题的启发函数 启发函数的核心—决不高估到达目标的步数 / 对于八数码问题的常用候选：
第2章 搜索技术 八数码问题的启发函数 启发函数的核心—决不高估到达目标的步数 / 对于八数码问题的常用候选： h1(n)=不在位棋子数—这是一个可采纳的启发函数，因为要把“不在位”的棋子都移动到正确位置上，每个错位的棋子至少要移动一次 / 所以有h1(n)≤h*(n) h2(n)=所有棋子到达其目标位置的距离和—计算水平距离(曼哈顿距离) / 该函数也是可采纳的，因为到达其目标位置至少要移动这些距离长度

64 启发函数精确度对算法性能的影响 刻画启发函数质量的一个度量是有效分支因子b*
第2章 搜索技术 启发函数精确度对算法性能的影响 刻画启发函数质量的一个度量是有效分支因子b* b*是深度为d的一致搜索树为了能够包括N(生成的总节点数)+1个节点所必需的分支因子 N+1=1+b*+(b*)2+……+(b*)d 例如：52个节点在第5层找到解，则b*=1.92 有效分支因子可以根据问题实例发生变化，但是在足够难的问题中是稳定的 / 因此小规模实验中测得b*值可以为启发函数的总体有效性提供指导

65 八数码问题启发函数的比较 良好设计的启发函数使b*值接近1，允许对大规模的问题进行求解
第2章 搜索技术 八数码问题启发函数的比较 良好设计的启发函数使b*值接近1，允许对大规模的问题进行求解 启发函数越接近于真实最优解的值，则相应的搜索算法效率越高 / 显然此时有—如果h1(n)≤h2(n)，则h2(n)优于h1(n) (此时h2(n)信息量比h1(n)多) p85页给出了八数码问题的启发函数h1/h2的比较数据 “优于”的含义—使用h2的算法不会比使用h1的算法扩展更多的节点

66 如何设计启发函数 A*搜索的关键如何找到是一个合适的启发函数 寻找策略：
第2章 搜索技术 如何设计启发函数 A*搜索的关键如何找到是一个合适的启发函数 寻找策略： 从松弛问题中获得—松弛问题的最优解的耗散是原问题的一个可采纳的启发函数 从给定问题子问题的解耗散中获得—建立模式数据库，存储每个可能子问题实例 从经验中学习—使用归纳学习算法，使用相关状态特征来预测

67 松弛问题最优解作为启发函数 松弛问题—降低了行动限制的问题 松弛问题的最优解耗散是原问题的一个可采纳的启发函数 第2章 搜索技术
根据定义，原始问题的最优解也是该松弛问题的解，其耗散不低于松弛问题的最优解 松弛问题的最优解是确切耗散，一定满足三角不等式，因而是单调的，所以作为启发函数一定是可采纳的 如果问题定义通过形式化语言描述，则自动地构造其松弛问题是可能的 / 例子—八数码问题

68 子问题的解耗散作为启发函数 子问题的最优解耗散是完整问题的耗散下界 建立模式数据库—存储每个可能子问题实例的精确解耗散
第2章 搜索技术 子问题的解耗散作为启发函数 子问题的最优解耗散是完整问题的耗散下界 建立模式数据库—存储每个可能子问题实例的精确解耗散 从目标状态向后搜索并记录下每个子问题模式的耗散，存储于数据库 搜索中遇到的每个完整状态通过在数据库中查找出相应子问题布局而设计出一个可采纳的启发函数 对于八数码问题，这样的启发函数要比曼哈顿距离精确得多(具体数值见p87)

69 从经验中学习启发函数 从实例中学习—每个实例包含了解路径上的各状态及其到达解的耗散 每个最优解实例提供了可学习h(n)的实例
第2章 搜索技术 从经验中学习启发函数 从实例中学习—每个实例包含了解路径上的各状态及其到达解的耗散 每个最优解实例提供了可学习h(n)的实例 收集实际解消耗的统计数据，以此产生可预测其他状态解消耗的启发函数h(n) 使用归纳学习方法 八数码问题的讨论(p87)

70 A*搜索的例子(1) 积木块移动游戏 初始状态： 目标状态： 移动规则： (1)积木移到空格/代价=1
第2章 搜索技术 A*搜索的例子(1) 积木块移动游戏 初始状态： 目标状态： 移动规则： (1)积木移到空格/代价=1 (2)积木跨越1个积木移到空格/代价=1 (3)积木跨越2个积木移到空格/代价=2

71 A*搜索的例子(2) A*搜索：至少代价=每个W左边B的个数(B到W右边的必须跨越W的代价) 搜索过程中括号里的数字分别为h/g值
第2章 搜索技术 A*搜索的例子(2) A*搜索：至少代价=每个W左边B的个数(B到W右边的必须跨越W的代价) 令h(n)=至少代价，则h(n)≤h*(n) 且满足单调性 h(ni) ≤ h(ni+1)+g(ni+1)-g(ni) (实际是=) g(n)=到达当前状态实际付出的代价 搜索过程中括号里的数字分别为h/g值

72 第2章 搜索技术 A*搜索的例子(3)

73 2.3.4 联机搜索 脱机搜索—不需感知，只要计算 联机搜索—必须通过行动/观察与计算交叉进行才能决定下一步搜索
第2章 搜索技术 2.3.4 联机搜索 脱机搜索—不需感知，只要计算 例子：简单游戏，通过有限的规则作用即可推算出目标所在 联机搜索—必须通过行动/观察与计算交叉进行才能决定下一步搜索 两种情况：环境未知—只有行动才能得知如何正确走向目标 / 环境空间过大—虽然理论上已知，但是实际不可计算(如棋类比赛)

74 例子：迷宫问题 G 如左图所示，联机搜索问题只能通过行动来解决，因为障碍是不能事先预知的 S 3 2 智能体初始位置在S，其已知信息为： 1
第2章 搜索技术 例子：迷宫问题 如左图所示，联机搜索问题只能通过行动来解决，因为障碍是不能事先预知的 智能体初始位置在S，其已知信息为： ACTION(s)—状态S下的行动列表 c(s,a,s’)—通过行动a从s状态到达s’状态 Goal-Test(s) / G目标位置 G S 3 2 1 智能体可使用曼哈顿距离启发式

75 竞争率(1) 代价—智能体实际走过的路经总耗散 理想耗散—没有无用搜索步骤的走过路径耗散/也就是应该走过路径的耗散 竞争率—代价÷理想耗散
第2章 搜索技术 竞争率(1) 代价—智能体实际走过的路经总耗散 理想耗散—没有无用搜索步骤的走过路径耗散/也就是应该走过路径的耗散 竞争率—代价÷理想耗散 该值要尽可能地小

76 竞争率(2) 影响竞争率的因素，使其无穷大 没有算法能够在所有的状态空间中避免死路(p98图4.19a)
第2章 搜索技术 竞争率(2) 影响竞争率的因素，使其无穷大 行动不可逆—进入一个不可到达目标的状态又不可回溯 没有算法能够在所有的状态空间中避免死路(p98图4.19a) 因此，通常需要假设状态空间是可安全探索的—具有可逆的状态空间 / 从每个可达状态出发都有可达的目标状态 不过，在可逆状态空间中，因为对手的存在，也会出现无界竞争率的情况(p98图4.19b)

77 联机搜索智能体 联机搜索智能体需要行动和感知，然后扩展当前状态的环境地图 区别：联机—规划与行动交叉 / 脱机—只要规划
第2章 搜索技术 联机搜索智能体 联机搜索智能体需要行动和感知，然后扩展当前状态的环境地图 区别：联机—规划与行动交叉 / 脱机—只要规划 例子：A*搜索在不同子空间节点的跳跃式扩展，模拟而非实际行动 / 联机算法只扩展目前实际占据的节点—采用深度优先搜索 联机搜索必须维护一个回溯表