第2章_基于状态空间图表示的搜索搜索技术(新)__.ppt

第2章基于图的知识表示与图搜索技术 2020 2 4 人工智能 2 第2章基于图的知识表示与图搜索技术 2 1概述2 2状态空间图表示2 3状态空间图的盲目搜索2 4状态空间图的启发式搜索2 5与或图表示及搜索技术2 6博弈树及搜索技术 2020 2 4 人工智能 3 2 1概述 2 1 1知识与问题求解框架2 1 2知识表示2 1 3图搜索技术 2020 2 4 人工智能 4 2 1 1知识与问题求解框架 1 1 知识的定义心理学 个体通过与环境相互作用后获得的信息及其组织 费根鲍姆 知识是经过消减 塑造 解释和转换的信息 博恩斯坦 Bernstein 知识是由特定领域的描述 关系和过程组成的 概括地说 知识是高度组织起来的信息集团 是人们在长期的生活和社会实践中 科学研究和科学实验中积累起来的经验或对客观世界规律的认识等 2 1 1知识与问题求解框架 2 2 知识的分类 1 从应用领域来划分常识性知识领域 专业 性知识 2 从在问题求解中的作用来划分叙述性知识过程性知识控制性知识 3 从确定性来划分确定性知识非确定性知识 4 从知识的表现形式来划分 可分为文字 符号 声音 图形 图像等 2020 2 4 人工智能 5 2 1 1知识与问题求解框架 3 3 问题求解框架问题 是指事件或事物的已知或当前状态与目标状态之间有差异 问题求解 是指在一定的控制策略下 通过一系列的操作或运算来改变问题的状态 使之与目标状态接近或一致 例如 李明在北京 他要去西安 办事 又如 博弈问题 问题的求解框架 1 叙述性知识 描述问题的状态有关的各种知识 2 过程性知识 描述状态之间的变换关系的各种知识 3 控制性知识 描述如何在当前状态下选择合适操作的知识 2020 2 4 人工智能 6 2020 2 4 人工智能 7 2 1 2知识表示 1 知识表示 就是研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识 包括构成问题求解框架的全部知识 常用的知识表示形式状态空间图与或图谓词逻辑产生式框架语义网络 2 1 2知识表示 2 2020 2 4 人工智能 8 例2 1麦卡赛问题 在一个2n 2n的方格棋盘中 去掉对角的两个方格 如图 a 问能否将它全部划成若干1 2的小长方块 目标状态 初始状态 可达状态 同构问题 同态问题 2020 2 4 人工智能 9 2 1 3图搜索技术 1 1 搜索搜索 简单地说就是 寻找 目的是找到问题的解 在问题求解过程中 待求解的问题被抽象成一定空间上的图 搜索过程就是从图中初始节点出发 沿着与之相连的边试探着前进 寻找目标节点或可解节点的过程 2 搜索树搜索过程中经过 考察过 的节点和边 按原图的连接关系 便会构成一个树型的有向图 称为搜索树 搜索树是一个搜索过程的搜索轨迹 或称之为搜索空间 2 1 3图搜索技术 2 2020 2 4 人工智能 10 图2 2搜索空间示意图 问题的状态空间 搜索空间及解的示意图 2 1 3图搜索技术 3 3 搜索策略搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点 盲目搜索 无向导的搜索 也称穷举搜索 启发式搜索 利用 启发性信息 作为导航的搜索过程 对于较大或无限状态空间问题 盲目搜索效率太低 所以在实际当中往往是不可行的 启发式搜索广泛地应用于实际问题求解中 如博弈 机器学习 数据挖掘 智能检索等 2020 2 4 人工智能 11 2020 2 4 人工智能 12 2 2状态空间图表示 2 2 1状态空间图2 2 2隐式状态空间图 2020 2 4 人工智能 13 2 2 1状态空间图 1 1 状态状态对应叙述性知识 描述一个问题在开始 结束或中间的某一时刻所处的状况或状态 通常引进一组变量 表示与问题状态相关的各种要素 并用这组变量所构成的多元组来表示状态 状态在状态图中表示为节点 2020 2 4 人工智能 14 2 2 1状态空间图 2 2 操作操作对应过程性知识 即状态转换规则 描述状态之间的关系 描述一个操作要包含两个部分条件 指明被作用的状态要满足的约束条件动作 指明一个操作对状态的分量所做的改变 操作的表示形式可以是一个机械性的步骤 过程 规则或算子 操作在状态图中表示为边 在程序中 状态转换规则可用数据对 条件语句 规则 函数 过程等表示 如 如果室内温度低于26度 则关闭空调 2020 2 4 人工智能 15 2 2 1状态空间图 3 3 状态空间图问题的状态空间图是一个描述该问题全部可能的状态及相互关系的图 如考虑操作的代价 状态空间图就是一个赋值有向图 状态空间常记为三元组 S 初始状态的集合F 操作的集合G 目标状态的集合 由问题的状态空间表示就可以构造出状态空间图 2 2 1状态空间图 4 4 求解在状态空间表示法中 问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题 也就是寻找操作序列的问题 状态空间的解为三元组Qs 某个初始状态Qg 某个目标状态a 把Qs变换成Qg的有限的操作序列状态转换图 2020 2 4 人工智能 16 2020 2 4 人工智能 17 例2 2翻转钱币问题 1 三枚钱币处于反 正 反状态 每次只许翻动一枚钱币 问连续翻动三次后 能否出现全正或全反状态 初始状态Qs 目标状态集合 Q0 Q7 例2 2翻转钱币问题 2 引入一个三元组 q0 q1 q2 来描述总状态 钱币正面为0 反面为1 全部可能的状态为 Q0 0 0 0 Q1 0 0 1 Q2 0 1 0 Q3 0 1 1 Q4 1 0 0 Q5 1 0 1 Q6 1 1 0 Q7 1 1 1 翻动钱币的操作抽象为改变上述状态的算子 即F a b c a 把钱币q0翻转一次b 把钱币q1翻转一次c 把钱币q2翻转一次问题的状态空间为 2020 2 4 人工智能 18 例2 2翻转钱币问题 4 3 状态空间图问题的状态空间为 2020 2 4 人工智能 19 构造状态空间图 aabababaabbbbcccbcccb 2020 2 4 人工智能 20 例2 3修道士和野人问题 1 在河的左岸有三个修道士 三个野人和一条船 修道士们想用这条船将所有的人都运过河去 但受到以下条件的限制 1 修道士和野人都会划船 但船一次最多只能运两个人 2 在任何岸边野人数目都不得超过修道士 否则修道士就会被野人吃掉 假定野人会服从任何一种过河安排 试规划出一种确保修道士安全过河方案 2020 2 4 人工智能 21 例2 3修道士和野人问题 2 1 问题的状态可以用一个三元数组来描述 S m c b m 左岸的修道士数c 左岸的野人数b 左岸的船数右岸的状态不必标出 因为 右岸的修道士数m 3 m右岸的野人数c 3 c右岸的船数b 1 b 2020 2 4 人工智能 22 例2 3修道士和野人问题 3 2020 2 4 人工智能 23 例2 3修道士和野人问题 4 2 操作集F p01 p10 p11 p02 p20 q01 q10 q11 q02 q20 例2 3修道士和野人问题 5 3 状态空间给出状态和操作的描述之后 该问题的状态空间是 S0 P01 P10 P11 P02 P20 Q01 Q10 Q11 Q02 Q20 S31 2020 2 4 人工智能 25 例2 3修道士和野人问题 6 4 状态空间图 四条S0到S31长度相等的最短路径 对应的操作序列就是该问题的四个最优解 2020 2 4 人工智能 26 2 2 2隐式状态空间图 显式状态空间图 表示了问题所有可能的状态及状态之间的关系 这种表示方式称为显式状态空间图 或称为状态空间图的显示表示 隐式状态空间图 利用有关状态描述和状态转换 操作 的知识定义的状态空间图 在计算机中仅存储描述问题状态及操作的有关知识 包括该问题的各状态分量的取值情况 分量之间的约束条件 开始状态 终止状态 以及全部操作的条件和动作等 隐式状态空间图也称为是状态空间图的隐式表示或隐式图 重排九宫问题的隐式图描述为 1 有关状态的知识 状态S的定义 S X0 X1 X2 X3 X4 X5 X6 X7 X8 其中 Xi 0 1 2 3 4 5 6 7 8 且 初始状态 S0 0 1 2 3 5 6 4 7 8 目标状态 Sg 0 1 2 3 4 5 6 7 8 重排九宫问题的状态表示 例2 4重排九宫问题 八数码问题 例2 4重排九宫问题 2 2 有关操作的知识 规则 0组规则R1 X0 0 X2 n X0 n X2 0 R2 X0 0 X4 n X0 n X4 0 R3 X0 0 X6 n X0 n X6 0 R4 X0 0 X8 n X0 n X8 0 1组规则R5 X1 0 X2 n X1 n X2 0 R6 X1 0 X8 n X1 n X8 0 8组规则 R22 X8 0 X1 n X8 n X1 0 R23 X8 0 X0 n X8 n X0 0 R24 X8 0 X7 n X8 n X7 0 例2 4重排九宫问题 3 八数码的状态图可表示为 S0 r1 r2 r24 Sg 八数码问题状态图仅给出了初始节点和目标节点 其余节点需用状态转换规则来产生 类似于这样表示的状态图称为隐式状态图 或者说状态图的隐式表示 例2 4重排九宫问题 4 3 隐式图搜索初始状态S 0 1 2 3 5 6 4 7 8 满足条件X0 0 故可以使用第0组的四条规则 如果选择规则R1 则状态转换为 S1 2 1 0 3 5 6 4 7 8 2020 2 4 人工智能 31 例2 5旅行商问题 TSP 1 设有n个互相可直达的城市 某推销商准备从其中的A城出发 周游各城市一遍 最后又回到A城 要求为该推销商规划一条最短的旅行路线 1 状态描述 该问题的状态为以A打头城市序列 AA1 Ai Aj A 其中 A Ai Aj A 为城市名 1 i j n 1 Aj A Ai A 1 n 1 当i j时 Ai Aj 当且仅当 n 1时 A A 初始状态 A 1终止状态 AA1A2 A n 1 例2 5旅行商问题 TSP 2 2 操作描述 状态转换规则 规则1 如果 AA1 Ai Aj 且 n 但A 则置 A 即没遍历完时 在城市序列中添加一个没有到过的城市 规则2 如果 n 置 A 即从当前城市返回A城 3 隐式图搜索对于有A B C D四个城市所组成的连通城市网 初始状态 A 1 满足规则1 则操作的结果为 AB 或 AC 或 AD 继续使用规则1 直到生成包含四个城市的序列出现 再使用规则2 2020 2 4 人工智能 32 补充例二阶梵塔问题 1 有三个杆 一号杆有A B两个金盘 A小于B 要求将A B移至三号杆 每次只可移动一个盘子 任何时刻B不能在A上 1 有关状态的知识 用二元组 SA SB 表示状态 SA表示A所在杆号 SB表示B所在杆号 其中 SA SB 1 2 3 则全部状态如下 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 初始状态为 1 1 终止状态为 3 3 2020 2 4 人工智能 33 B A A A A A B A B B B B B 补充例二阶梵塔问题 2 2020 2 4 人工智能 34 2 有关操作的知识 规则 A i j 表示金盘A从第i号杆移到j号杆 B i j 表示金盘B从第i号杆移到j号杆 其中 i j 1 2 3 但i j 全部操作为 A 1 2 A 1 3 A 2 1 A 2 3 A 3 1 A 3 2 B 1 2 B 1 3 B 2 1 B 2 3 B 3 1 B 3 2 分析每个操作的条件和动作 得到下表 补充例二阶梵塔问题 3 2020 2 4 人工智能 35 补充例二阶梵塔问题 4 2020 2 4 人工智能 36 补充例二阶梵塔问题 5 3 状态空间图 1 1 2 1 3 1 2 3 3 3 1 3 3 2 1 2 2 2 A 1 2 A 1 3 B 1 2 A 3 2 A 1 2 B 3 2 A 3 1 B 1 3 A 2 3 2020 2 4 人工智能 37 2 3状态空间图的盲目搜索 盲目搜索 搜索时不参考与具体待求解问题相关的任何信息 只是按预先设定的顺序逐个考察节点 盲目搜索与问题无关 具有通用性 算法中使用的数据结构 OPEN表 专门登记已经生成但还没有考察的节点 即待考察节点 CLOSED表 用来记录考察过的节点以及节点之间的关系 如每个节点指向父节点的编号 返回指针 CLOSED表中存放的就是一定搜索策略下的搜索树 2020 2 4 人工智能 38 OPEN表 CLOSED表 2020 2 4 人工智能 39 2 3状态空间图的盲目搜索 2 3 1广度优先搜索2 3 2深度优先搜索 2020 2 4 人工智能 40 2 3 1广度优先搜索 1 广度优先搜索 A ed 基本思想 广度优先搜索是严格按节点在树中的出现位置一层一层向下的搜索过程 通过将OPEN表设计为一个队列来实现 将新生成的子节点放在OPEN表的后面 保证先生成的节点先考察 广度优先搜索算法 步1把初始节点S0放入OPEN表中 步2若OPEN表为空 则搜索失败 退出 步3否则 取OPEN表中第一个节点N放在CLOSED表中 并冠以顺序编号n 步4若节点N为目标节点 则搜索成功 利用CLOSED表中的返回指针找出S0到N的路径即为所求解 退出 步5若N不可扩展 转步2 步6否则 扩展N 将其所有子节点配上指向N的返回指针放入OPEN表的尾部 转步2 2 3 1广度优先搜索 2 2020 2 4 人工智能 42 例2 6使用广度优先搜索算法求解重排九宫问题 八数码广度优先搜索 2020 2 4 人工智能 43 2 3 1广度优先搜索 广度优先搜索的特点 广度优先中OPEN表是一个队列 CLOSED表是一个顺序表 表中各节点按顺序编号 正被考察的节点在表中编号最大 广度优先搜索又称为宽度优先或横向搜索 广度优先策略是完备的 即如果问题的解存在 则它一定可以找到解 并且找到的解还是最优解 广度优先搜索策略与问题无关 具有通用性 缺点搜索效率低 2020 2 4 人工智能 44 2 3 2深度优先搜索 1 深度优先搜索的基本思想 深度优先搜索是一种一直向下的搜索过程 它优先在自己的子节点集合中选择下一个被考察的节点 不断向纵深方向前进 直到到达叶子节点或受到深度限制时 才返回到上一级节点沿另一方向继续前进 深度优先搜索算法 与广度优先搜索策略的唯一不同点就是OPEN表被设计成后进先出的栈 新生成的子节点放在OPEN表的前面 后生成的节点优先被考察 深度优先搜索算法只需将宽度优先搜索算法步6修改为 步6否则 扩展N 将其所有子节点配上指向N的指针放入OPEN表的首部 转步2 例2 7使用深度优先搜索算法求解重排九宫问题 12384576 3 12384576 12384576 12843765 12385746 2 12384765 5 2020 2 4 人工智能 46 2 3 2深度优先搜索 深度优先搜索的特点 OPEN表为一个堆栈 深度优先又称纵向搜索 一般不能保证找到最优解 如下图所示 图2 13深度优先搜索不具有完备性示意图 2020 2 4 人工智能 47 1 有界深度优先搜索 Acd 为克服深度优先搜索的不足 可以对其深度进行限制深度界限的选择很重要dm若太小 则达不到解的深度 得不到解 若太大 既浪费了计算机的存储空间与时间 又降低了搜索效率 由于解的路径长度事先难以预料 所以要恰当地给出dm的值是比较困难的 即使能求出解 它也不一定是最优解 2 可变界深度优先搜索算法 1 当在dm界限之内找不到解时 可以将深度界限dm不断扩大 每次增加一个深度增量 d 直到找到解 或者搜索完整棵树 这样算法的完备性得到了保证 称为可变界深度优先搜索算法 或迭代加深搜索 当 d 1时 算法开始蜕变为广度优先搜索算法 2 可变界深度优先搜索算法 2 迭代加深搜索过程 步1把初始节点S0放入OPEN表中 置S0的深度d S0 0 dm为任意初值 步2若OPEN表为空 则考查CLOSED表是否有待扩展节点 若无 则问题无解 退出 若有 则取出CLOSED表中待扩展节点放入到OPEN表中 令dm dm d 2 可变界深度优先搜索算法 3 步3取OPEN表中第一个节点N放在CLOSED表中 并冠以编号n 步4若节点N为目标节点 成功退出 步5若N的深度d N dm 深度限制值 则标N为待扩展节点 则转步2 步6N无子节点 则转步2 步7扩展N 将其所有子节点Ni配上指向N的指针放入OPEN首部 置d Ni d N 1 转步2 3 可采纳的有界深度优先搜索算法 1 问题 当 d 1时 是否能保证找到最优解 2020 2 4 人工智能 53 3 可采纳的有界深度优先搜索算法 2 步1把初始节点S0放入OPEN表中 置d S0 0 dm dm0 G NULL 步2若OPEN表为空 则考察CLOSED表是否有待扩展节点 1 若无待扩展节点 则判断G表是否为空 若为空 搜索失败 退出 否则 取出G表最后面的节点Sg Sg即为所求最优解 搜索成功 退出 2 若有待扩展节点 则取出CLOSED表中待扩展节点放入到OPEN表中 令dm dm d 转步2 3 可采纳的有界深度优先搜索算法 3 步3取OPEN表中首部的节点N放在CLOSED表中 并冠以顺序编号n 步4若d N dm 则标N为待扩展节点 转步2 步5若N是目标节点Sg 则令dm d Sg 1 把Sg放到G表的尾部 转步2 步6若N不可扩展 则转步2 步7否则 扩展N 将其所有子节点Ni配上指向N的返回指针放入OPEN表首部 置d Ni d N 1 转步2 2020 2 4 人工智能 54 2 4状态空间图的启发式搜索 1 1 启发性知识与启发函数启发性知识就是与被求解问题自身特性相关的知识 包括被求解问题的解的特性 解的分布规律和在实际当中求解此类问题的经验 技巧等 对应于问题求解框架中的控制性知识 启发函数要实现启发式搜索 需要把启发性知识形式化 即用一定的函数表示出来 通过函数计算来评价每种选择的价值大小 用以指导搜索过程 这样的函数称为启发函数 2020 2 4 人工智能 55 2020 2 4 人工智能 56 2 4状态空间图的启发式搜索 2 2 启发函数的设计在实际设计过程中 启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数 通常记为h x 启发函数可以是 1 一个节点到目标节点的某种距离或差异的量度 2 一个节点处在最佳路径上的概率 3 根据主观经验的主观打分等 2020 2 4 人工智能 57 2 4状态空间图的启发式搜索 3 2 4 1启发式搜索算法2 4 2启发式搜索的A算法和A 算法2 4 3A 算法在游戏中的应用 2020 2 4 人工智能 58 2 4 1启发式搜索算法 1 启发式搜索用启发函数来导航 其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程 并且由启发函数值来确定节点的扩展顺序 按选择范围不同 启发式搜索分为 全局择优搜索局部择优搜索 2020 2 4 人工智能 59 2 4 1启发式搜索算法 2 1 全局择优搜索基本思想 在OPEN表中保留所有已生成而未考察的节点 并用启发函数h x 对它们全部进行估价 从中选出最优节点进行扩展 而不管这个节点出现在搜索树的什么地方 2 4 1启发式搜索算法 3 全局择优搜索算法 步1把初始节点S0放入OPEN表中 计算h S0 步2若OPEN表为空 则搜索失败 退出 步3否则 移出OPEN表中第一个节点N放入CLOSED表中 并冠以序号n 步4若目标节点Sg N 则搜索成功 利用CLOSED表中的返回指针找出S0到N的路径即为所求解 退出 步5若N不可扩展 则转步2 步6否则 扩展N 计算N的每个子节点x的函数值 并将N所有子节点x配以指向N的返回指针后放入OPEN表中 依据启发函数对节点的计算 再对OPEN表中所有节点按其启发函数值的大小以升序排列 转步2 2020 2 4 人工智能 60 2 4 1启发式搜索算法 4 2 局部择优搜索基本思想 局部择优搜索是在启发性知识导航下的深度优先搜索 在OPEN表中保留所有已生成而未考察的节点 对其中新生成的每个子节点x计算启发函数 从全部子节点中选出最优节点进行扩展 其选择下一个要考察节点的范围是刚刚生成的全部子节点 局部择优搜索算法 与全局择优搜索算法的区别仅在步6 步6否则 扩展N 计算N的每个子节点x的函数值 并将N的所有子节点x配以指向节点N的指针后 将全部子节点按启发函数值升序排列后放入OPEN表的首部 转步2 2020 2 4 人工智能 61 2 4 2启发式搜索的A算法和A 算法 1 启发函数是对当前节点到达目标节点未来可能要付出的代价的估计 在全局择优和局部择优搜索算法中 都没有考虑从初始节点到当前节点已经付出的实际代价 在很多实际问题中 已经付出的实际代价是必须考虑的 如TSP问题等 将两者同时考虑 用于指导搜索的算法称为A算法和A 算法 2020 2 4 人工智能 63 2 4 2启发式搜索的A算法和A 算法 2 1 A算法估价函数f x 为了防止在单独利用启发函数的时候误入歧途 将启发函数h x 与代价函数g x 相结合 即初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值总和 f x g x h x g x 代价函数 初始节点S0到达节点x处已付出的代价 有利于搜索纵向发展 提高搜索效率 但影响完备性 h x 启发函数 节点x到达目标节点Sg的接近程度估计值有利于搜索横向发展 提高搜索的完备性 但影响搜索效率 2 4 2启发式搜索的A算法和A 算法 3 代价g x 的计算g x 表示从初始节点S0到节点x的代价 g S0 0g xj g xi c xi xj 其中 c xi xj 表示父节点xi到子节点xj的代价 A D C E B 4 6 4 3 3 2 3 2 3 4 6 2 3 4 4 6 3 2 C1 B1 D1 D2 E1 C2 E2 D3 C3 B2 E4 E3 6 B3 2020 2 4 人工智能 64 2 4 2启发式搜索的A算法和A 算法 4 对估价函数f x g x h x 令其中的h x 0时 这时得到的是代价树的非启发式搜索算法 按对节点的考察范围不同 可分为两种搜索策略 分支界限法将全局择优搜索算法中的h x 替换为g x 即可得到分支界限搜索算法 瞎子爬山法将局部择优搜索算法中的h x 替换为g x 即可得到瞎子爬山搜索算法 2020 2 4 人工智能 65 2020 2 4 人工智能 66 2 4 2启发式搜索的A算法和A 算法 5 步1把附有f S0 的初始节点S0放入OPEN表中 步2若OPEN表为空 则搜索失败 退出 步3否则 移出OPEN表中第一个节点N放入CLOSED表中 并冠以顺序编号n 步4若目标节点Sg N 则搜索成功 利用CLOSED表中的返回指针找出S0到N的路径即为所求解 退出 步5若N不可扩展 则转步2 2 4 2启发式搜索的A算法和A 算法 6 步6否则 扩展N 生成一组子节点xi 计算f xi 并对这组节点xi作如下处理 1 若xi是N的先辈节点 则删除之 2 若xi存在于OPEN或CLOSED表中 也删除之 但表明此时存在两条初始节点S0到xi的路径 如果新路径较短 则修改xi节点的返回指针 指向N 并修改xi及其后裔节点和f值 同时若xi存在于CLOSED表中 则将其移出放入OPEN表重新考察 3 对其余子节点配上指向N的返回指针放入OPEN表 步7对OPEN表中所有节点按f值以升序排列 转步2 2020 2 4 人工智能 67 2020 2 4 人工智能 68 2 4 2启发式搜索的A算法和A 算法 7 对步6的1 的说明 2 4 2启发式搜索的A算法和A 算法 8 对步6的2 的说明 2020 2 4 人工智能 69 2 4 2启发式搜索的A算法和A 算法 9 树式搜索例对于已存在于OPEN表中的节点 如果有的话 也删除之 删除之前要比较其返回初始节点的新路径与原路径 如果新路径短 则修改这些节点在OPEN表中的原返回指针 使其沿原路径返回 Path1 Path2 S0 m n P 先扩展 后扩展 P在n之前已是某一节点m的后继 如图所示 说明从S0 P至少有两条路 这时有两种情况 f Path2 f Path1 当前路径较好 要修改P的指针 使其指向n 即搜索之后的最佳路径 否则 原路径好 2020 2 4 人工智能 70 2 4 2启发式搜索的A算法和A 算法 10 对已存在于CLOSED表的节点 作与 2 同样的处理 并将其移出CLOSED表 放入OPEN表中重新扩展 S0 过去生成P的路径 现在生成P的路径 过去对Ps的最优路径 Ps P m n k a P在n之前已是某一节点m的后继 所以需要做如同 2 同样的处理 如图右部所示 b P在Closed表中 说明P的后继也在n之前已经生成 称为Ps 对Ps而言同样可能由于n P这一路径的加入 又必须比较多条路径之后而取代价小的一条 如图左部所示 2020 2 4 人工智能 71 2 4 2启发式搜索的A算法和A 算法 11 f x g x h x 探讨九宫重排问题的估价函数的设计过程 g x 对某一确定的节点 是确定的值 h x 不同的问题启发函数的定义不同 相同的问题也可以定义出不同的启发函数 衡量h x 优劣的标准是看其是否能够准确反映出节点x到达目标的难易程度 距离 估价函数定义探讨 2020 2 4 人工智能 72 2 4 2启发式搜索的A算法和A 算法 12 2020 2 4 人工智能 73 估价函数f x g x h x 因素1格局中将牌是否在家 g x 用节点深度d x 来衡量 如何定义 h x 用x的格局与目标节点格局相比 不在家的将牌数目w x 来衡量 例2 8A算法在重排九宫问题中的应用 2 3 8 5 3 3 4 1 12384576 2 12384765 0 1 扩展顺序 f x 值 14832765 14832765 3 4 4 14283765 12843765 3 4 12843765 12843765 4 2 6 12384765 7 2 5 5 6 7 14283765 14283576 1 扩展顺序 f2 x 值 14832765 14832765 4 5 13482765 6 3 6 13824765 5 13482576 7 9 81432765 7 34182765 13478265 8 8 4 7 8 10 13824765 5 11 12843765 14286375 14283765 7 8 8 12384765 5 12 8 13824765 2 4 2启发式搜索的A算法和A 算法 15 81263754 a 问题 是否对于所有的节点w x 都能反映出从x节点变化到目标节点的难易程度 到目标的距离 w a 7w b 6 从w x 值看a格局离目标格局更远 a格局真的比b格局距离目标更远吗 81263754 a 81263754 12863754 12863754 12863754 12386754 12386475 12386475 w a 7 实际距离为8 1 2 3 4 5 6 7 8 2020 2 4 人工智能 77 28143765 28143765 81243765 81243765 81243765 28146375 81324765 81324765 13824765 13824765 12384765 81324765 w b 6 实际距离为11 1 2 3 4 5 6 7 8 9 10 11 2020 2 4 人工智能 78 2 4 2启发式搜索的A算法和A 算法 18 81263754 a 28146375 b 考虑因素2 定义h x p x p x 是x格局中每个将牌离家 Sg中的位置 的最短距离 不论路上是否放有其他将牌 的总和 0 2 1 1 1 1 1 1 p a 8 0 2 1 2 2 1 0 1 p b 9 反映出a比b更容易到达目标格局 实际距离为8 实际距离为11 2020 2 4 人工智能 79 1 扩展顺序 f3 x 值 14832765 14832765 7 7 13482765 7 2 3 13824765 5 13482576 7 4 13824765 5 5 12384765 5 6 8 13824765 2020 2 4 人工智能 80 2 4 2启发式搜索的A算法和A 算法 20 因素3格局中将牌回家的顺序 81263754 28146375 b a 因素4中心位置是否有将牌 沿着周围非中心方格上依顺时针检查x格局中的每一个将牌 如果其后紧跟着的将牌正好是目标格局中该将牌的后续者 该将牌得0分 否则得2分 在正中方格上有将牌得1分 否则得0分 综合因素3和因素4的值 记为s x 2020 2 4 人工智能 81 2 3 8 5 22 25 30 10 12384576 18 12384765 7 1 扩展顺序 f4 x 值 14832765 14832765 22 28 4 14283765 12843765 16 30 12843765 12843765 17 16 6 12384765 7 2020 2 4 人工智能 82 2020 2 4 人工智能 83 2 4 2启发式搜索的A算法和A 算法 22 对A算法再限制其估价函数中的启发函数h x 满足 对所有的节点x均有 h x h x 其中h x 是从节点x到目标节点的最小代价 这就称为A 算法 A 算法也称为最佳图搜索算法 利用A 算法 如果问题存在最优解 就保证能找到最优解 2 4 2启发式搜索的A算法和A 算法 23 例2 9修道士和野人问题 在河的左岸有五个修道士 五个野人和一条船 修道士们想用这条船将所有的人都运过河去 但受到以下条件的限制 1 修道士和野人都会划船 但船一次最多只能运三个人 2 在任何岸边及船上野人数目都不得超过修道士 否则修道士就会被野人吃掉 假定野人会服从任何一种过河安排 试规划出一种确保修道士安全过河方案 请定义启发函数 并给出相应的搜索树 2020 2 4 人工智能 84 2 4 2启发式搜索的A算法和A 算法 24 解 先建立问题的状态空间 问题的状态可以用一个三元数组来描述 S m c b m 左岸的修道士数c 左岸的野人数b 左岸的船数初始状态为 5 5 1 终止状态为 0 0 0 合法的操作只有使状态如下转换 从平衡状态 m c 转换为修道士扎堆 m 0或m 5 从平衡状态 m c 转换为平衡状态 m c 从扎堆状态 m 0或m 5 转换为平衡状态 m c 2020 2 4 人工智能 85 2 4 2启发式搜索的A算法和A 算法 25 定义启发函数 若满足h n h n 即满足A 条件的 启发函数1 h n 0 启发函数2 h n M C 对状态 1 1 1 启发函数2不满足h n h n 提示 不考虑限制条件的运送次数一定小于有限制条件的运送次数 2020 2 4 人工智能 86 2 4 2启发式搜索的A算法和A 算法 26 先考虑船在左岸的情况 如果不考虑限制条件 至少需要 m c 3 2 2 1化简后为 m c 3 2 2 1大于等于m n 2再考虑船在右岸的情况 同样不考虑限制条件 船在右岸 需要一个人将船运往左岸 因此 对于状态 m c 0 需要的摆渡数 相当于船在左岸的 m 1 c 1 或 m c 1 1 所以需要的最少摆渡数为 m c 1 2 1 m c综合条件 需要的最少摆渡数为m c 2b 2020 2 4 人工智能 87 扩展顺序 h x 及f x 值 2020 2 4 人工智能 88 0 4 1 15 h 2f 10 0 5 1 h 3f 11 0 3 1 h 1f 11 0 2 0 h 2f 11 2020 2 4 人工智能 89 2020 2 4 人工智能 90 2 4 3A 算法在游戏中的应用 1 启发式算法逐渐发展成为路径搜索算法的核心 除了A 算法以外 国内外研究者还在此基础上逐渐发展了许多其它智能算法 包括IDA 算法 D 算法等 它们的基本原理都借鉴了A 算法中的估价函数思想 目前 游戏业界的标准是使用A 算法或IDA 算法 A 算法一般要快一些 而IDA 算法则比A 算法要使用更少的内存 2 4 3A 算法在游戏中的应用 2 如果游戏仅仅要求出从点A到达点B的一条最短路径的话 那么使用A 算法 将h x 设计为对A点到B点的最短路径的估计就可以完成此任务 然而 真实游戏中往往还要考虑路上的障碍物 或者在从点A到点B的途中避免被看到或被射击到 以及敌方的位置和火力线等 在游戏设计中 使用A 算法寻找路径时 启发函数h x 的设计还需要考虑更多的因素 如路径的距离 途中的障碍物 地形允许的行走速度 是否敌人视线与火力之下的位置 敌我双方暴露的时间和次数 敌方的威胁是否动态的 有掩护物和隐身处的路径等因素 2 4 3A 算法在游戏中的应用 3 比如 对那些暴露在敌方火力侦查或是覆盖之下的位置增加其代价值 使得A 算法生成一条尽量避免敌人侦查或射击的路径 如果敌方的飞机处于被我方地对空导弹防御的区域 那么 同样暴露20秒 是一次暴露20秒 还是分四次暴露 一次暴露5秒 显然对我方来说代价是不一样的 另外 敌方的威胁是静态的或动态的 估价函数值计算出来也应该不同 当然 考虑更多的因素一定会增加代价计算量 所以 在实际当中 使用A 算法进行游戏设计时 还需要在获得战术能力和所付出的计算量之间做出权衡 2020 2 4 人工智能 93 2 5与或图表示及搜索技术 2 5 1与或图表示2 5 2与或树的盲目搜索2 5 3与或树的启发式搜索 问题分解 在问题求解过程中 常常将一个复杂的问题P分解为一组子问题 当这些子问题全部可解时 原问题P可解 任何一个子问题无解时 都将导致原问题P无解 即一个问题与一组子问题的 与 等价 如 保送研究生的条件是每门课程成绩都在85分以上 问题变换 有时将一个复杂的问题P变换为与之等价的一组子问题 其中任何一个子问题可解时 原问题P可解 全部子问题无解时 原问题P无解 即一个问题与一组子问题的 或 等价 如 保送研究生的条件中 要求英语成绩是通过六级考试 或者通过GRE考试 与或图 将问题对应节点 分解或变换关系对应边 这样 就可以将一个问题求解过程中的分解和变换过程表示为一棵与或图 与状态空间图的意义不同 这里的与或图对应的是问题空间图 2020 2 4 人工智能 94 2 5 1与或图表示 1 与或图的概念来源于问题求解中的分解和变换一个复杂的问题P常常可以分解为与之等价的一组子问题P1 P2 Pn 当这些问题全部可解时 问题可解 任何一个子问题无解时 都将导致原问题P无解 即一个问题与一组子问题的与等价 一个复杂的问题P常常可以分别变换为与之等价的一组子问题P1 P2 Pn 其中任何一个子问题可解时 问题可解 全部子问题无解时 原问题P无解 即一个问题与一组子问题的或等价 2 5 1与或图表示 2 例2 10猴子摘香蕉问题房间内有一只猴子位于A处 有一只箱子位于B处 还有一架梯子位于C处 A到B的距离与A到C是距离相同 梯子和箱子的重量相同 屋顶上D处挂着一串香蕉 猴子爬到梯子上或箱子上都能摘到香蕉 2020 2 4 人工智能 96 2 5 1与或图表示 3 2020 2 4 人工智能 97 定义五个动作 f1 x y 表示猴子从x处走到y处 f2 x y 表示猴子推箱子从x处走到y处 f3 x y 表示猴子搬梯子从x处走到y处 f4 表示登上箱子 f5 表示登上梯子 f6 表示摘到香蕉 则猴子摘香蕉问题的分解变换过程可用如下与或图表示 2020 2 4 人工智能 98 2 5 1与或图表示 4 例2 11证明四边形全等 分析 连接BD B D 原来问题可以分解为两个子问题 Q1 证明 ABC A B C Q2 证明 BCD B C D 原来问题可以分为两个子问题解决 2 5 1与或图表示 5 问题Q1还可以再被分解为 Q11 证明AB A B Q12 证明AD A D Q13 证明 A A 或Q11 证明AB A B Q12 证明AD A D Q13 证明BD B D 问题Q2还可以再被分解为 Q21 证明BC B C Q22 证明CD C D Q23 证明 C C 或Q21 证明BC B C Q22 证明CD C D Q23 证明BD B D 2020 2 4 人工智能 100 2 5 1与或图表示 5 将原问题用图的形式表示如下 弧线表示所连边为 与 的关系 不带弧线的边为或关系 2 5 1与或图表示 6 例2 12梵塔问题 有1 2 3号杆 1号杆自上而下串着从小到大的n个金盘 要把1号杆上的n个金盘移到3号杆上 移动金盘的规则是 一次只能移一个金盘 移动的过程中不允许大盘压在小盘上 2020 2 4 人工智能 101 2 5 1与或图表示 6 1 1 1 3 3 3 1 1 1 1 1 3 1 2 3 1 2 2 3 2 2 3 2 1 3 3 1 3 3 3 1 1 3 1 2 3 3 2 1 3 3 1 1 1 1 1 2 2 1 2 2 3 2 2 3 2 2 3 3 3 三阶梵塔问题的与或树 2020 2 4 人工智能 103 2 5 1与或图表示 7 与或图的几个概念 直接可解的问题称为本原问题 本原问题对应的节点称为终止节点 无子节点的节点称为端节点 子节点为与关系 则该节点为与节点 子节点为或关系 则该节点为或节点 与或图一般表示问题的变换过程 就是从原问题出发 运用某些规则不断的进行问题的分解 得到与分支 和变换 得到或分支 而得到一个与或图 与或图的节点一般代表问题 整个图就表示问题空间 2020 2 4 人工智能 104 2 5 1与或图表示 8 与或图也可以用三元组表示 Q0 F Qn Q0表示初始问题F表示问题变换规则集Qn表示本原问题集 2 5 1与或图表示 9 节点的可解性判别 1 终止节点是可解节点 2 一个与节点可解 当且仅当其全部子节点可解 3 一个或节点可解 只要其子节点至少有一个可解 4 非终止节点的端节点是不可解节点 5 一个与节点不可解 只要其子节点至少有一个不可解 6 一个或节点不可解 当且仅当其全部子节点不可解 与或树的解树 由能判别 标记 根节点是可解节点的全部节点和边所组成的子树 2 5 1与或图表示 10 四边形相等问题分解树 2020 2 4 人工智能 106 2020 2 4 人工智能 107 2 5 2与或树的盲目搜索 1 与或树搜索与状态树搜索的不同之处在于 1 搜索过程中包含可解性标记过程 一旦生成已知可解或不可解的节点 需要向上标记其先辈节点的可解性 当根节点的可解性得到标记后 搜索终止 根据根节点的可解性返回解树或证明问题无解 2 包含从OPEN表中删除 具有可解或不可解先辈节点 的节点的过程 因为先辈节点的可解性或不可解性一旦确定之后 就不需要再通过其他子节点对它进行标记 2 5 2与或树的盲目搜索 2 2020 2 4 人工智能 108 2020 2 4 人工智能 109 2 5 2与或树的盲目搜索 3 1 广度优先搜索算法 步1把初始节点S0放入OPEN表 步2把OPEN表中的第一个节点 记为节点N 取出放入CLOSED表 并冠以编号n 步3如果节点n可扩展 则作下列工作 1 扩展节点N 将其子节点放入OPEN表尾部 并为每个子节点配置指向父节点的指针 以备标示过程中使用 2 考查这些节点中是否有终止节点 若有 将它们放入CLOSED表 标示这些节点为可解节点 并用可解标示过程对其先辈节点中的可解节点进行标示 如果S0也被标示为可解节点 就得到解树 搜索成功 退出 3 若S0不能确定为可解节点 则从OPEN表中删除具有可解先辈节点 转步2 2020 2 4 人工智能 110 2 5 2与或树的盲目搜索 4 步4如果节点N不可扩展 则作如下工作 1 标示节点N为不可解节点 2 应用不可解节点标示过程对节点N的先辈节点中不可解的节点进行标示 如果初始节点S0也被标示为不可解节点 则搜索失败 退出搜索过程 3 如果不能确定S0为不可解节点 则从OPEN表中删去具有不可解先辈的节点 转步2 例2 13与或树的广度优先搜索 与或树如下图 2020 2 4 人工智能 111 2 5 2与或树的盲目搜索 4 a 与或树 b 解树 广度优先搜索序列为 A B C F D I E K G L M 2020 2 4 人工智能 112 2 与或树的深度优先搜索策略 将与或树的广度优先搜索算法的步3中 1 做如下修改 步3如果节点N可扩展 则做下列工作 1 扩展节点N 将其子节点放入OPEN表首部 并为每个子节点配置指向父节点N的返回指针 深度优先的搜索序列为 A C F G M L 2020 2 4 人工智能 113 2 5 3与或树的启发式搜索 与或树的启发式搜索也叫有序搜索 其困难是 在与或树的搜索过程中 搜索树的生长方向是从根节点开始 自上而下进行的 而与或树的解树是由终止节点 可解节点 自下而上进行标记的 有代价时 代价的计算也是自下而上进行的 在搜索没到达终止节点和端节点之前 无法知道根节点和中间节点的实际代价 在与或树的搜索过程中 代价的计算方向与搜索树的生长方向相反 1 解树的代价 与或树中解树的代价是从树叶开始自下而上逐层计算的 用个g x 表示节点x的代价 c x y 表示节点x到其自节点y的代价 解树代价的计算如下 1 若x是终止节点 则g x 0 2 若x是或节点 则3 若x是与节点 则有两种计算法则 和代价法则 最大代价法则 比如 某一系统A有三个子系统 三个子系统相互独立 并行开发与串行开发分别采用最大代价法则与和代价法则 例2 15与或树的代价计算 有代价的与或树如图2 32a所示 解 它有两个解树分别为2 32b和c所示 见书本p49 按最大代价计算解树的代价分别为7和6 按和代价计算解树代价分别为10和8 2020 2 4 人工智能 116 2 希望树 有序搜索思路 为求得最小代价解树 每次在确定要扩展的节点时 只能是先往前多看几步 利用启发信息 通过对更深层节点代价的估计 计算 估计 扩展一个节点可能要付出的代价 然后 选择代价最小的节点进行扩展 1 按扩展深度扩展节点 得到新的子节点x 用估价函数来计算x的代价称为x的估计值 2 向上倒推计算x的父节点及先辈节点y的代价 称为y的倒推值 并用y的倒推值代替y原来的估计值 3 重复步 1 2 直到扩展到终止节点或端节点 能够标记初始节点的可解性为止 不断用节点的倒推值代替其估计值的依据是 越接近终止节点 估计越准确 希望树 有序搜索的目的是求最优解树 因此 要求在搜索过程中 按照估价函数 任一时刻求出的部分解树都是代价最小的 为此 每次挑选欲扩展的节点都应该挑选最有希望成为最优解树一部分的节点 有这些节点极其先辈节点所构成的与或树是最优解树的近根部分 成为希望树 或希望解树 2020