知识的状态空间表示法及搜索问题讨论ppt课件

知识的状态空间表示法 计算机科学技术学院陈峰 1课前思考 人类的思维过程 可以看作是一个搜索的过程 某个方案所用的步骤是否最少 也就是说它是最优的吗 如果不是 如何才能找到最优的方案 在计算机上又如何实现这样的搜索 这些问题实际上就是本章我们要介绍的搜索问题 2学习目标 掌握回溯搜索算法 深度优先搜索算法 宽度优先搜索算法和A搜索算法 对典型问题 掌握启发式函数的定义方法 3学习指南 了解算法的每一个过程和细节问题 掌握一些重要的定理和结论 在有条件的情况下 程序实现每一个算法 求解一些典型的问题 4难重点 回溯搜索算法 算法及其性质 改进的 算法 5知识点 本章所要的讨论的问题如下 有哪些常用的搜索算法 问题有解时能否找到解 找到的解是最佳的吗 什么情况下可以找到最佳解 求解的效率如何 3 1状态空间表示知识 一 状态空间表示知识要点1 状态状态 State 用于描述叙述性知识的一组变量或数组 也可以说成是描述问题求解过程中任意时刻的数据结构 通常表示成 Q q1 q2 qn 当给每一个分量以确定的值时 就得到一个具体的状态 每一个状态都是一个结点 节点 实际上任何一种类型的数据结构都可以用来描述状态 只要它有利于问题求解 就可以选用 2 操作 规则或算符 操作 Operator 是把问题从一种状态变成为另一种状态的手段 当对一个问题状态使用某个可用操作时 它将引起该状态中某一些分量发生变化 从而使问题由一个具体状态变成另一个具体状态 操作可以是一个机械步骤 一个运算 一条规则或一个过程 操作可理解为状态集合上的一个函数 它描述了状态之间的关系 通常可表示为 F f1 f2 fm 3 1状态空间表示知识 续 3 状态空间状态空间 StateSpace 是由问题的全部及一切可用算符 操作 所构成的集合称为问题的状态空间 用三元组表示为 Qs F Qg Qs 初始状态 Qg 目标状态 F 操作 或规则 4 状态空间 转换 图状态空间也可以用一个赋值的有向图来表示 该有向图称为状态空间图 在状态空间图中包含了操作和状态之间的转换关系 节点表示问题的状态 有向边表示操作 3 1状态空间表示知识 续 二 状态图搜索1 搜索方式用计算机来实现状态图的搜索 有两种最基本的方式 树式搜索和线式搜索 2 搜索策略大体可分为盲目搜索和启发式 heuristic 搜索两大类 3 1状态空间表示知识 续 搜索空间示意图 例3 1钱币翻转问题设有三枚硬币 其初始状态为 反 正 反 允许每次翻转一个硬币 只翻一个硬币 必须翻一个硬币 必须连翻三次 问是否可以达到目标状态 正 正 正 或 反 反 反 问题求解过程如下 用数组表示的话 显然每一硬币需占一维空间 则用三维数组状态变量表示这个知识 Q q1 q2 q3 取q 0表示钱币的正面q 1表示钱币的反面 3 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 引入操作 f1 把q1翻一面 f2 把q2翻一面 f3 把q3翻一面 显然 F f1 f2 f3 目标状态 找到的答案 Qg 0 0 0 或 1 1 1 3 1状态空间表示知识 续 3 1状态空间表示知识 续 例3 2分油问题 有两只空油瓶 容量分别为8斤和6斤 另有一个大油桶 里面有足够的油 我们可以任意从油桶中取出油灌满某一油瓶 也可以把某瓶中的油全部倒回油桶 两个油瓶之间可以互相灌 问如何在8斤油瓶中精确的得到4斤油 3 1状态空间表示知识 续 问题的求解显然用2维数组或状态空间描述比较合适 第一位表示8斤油瓶油量 第二位表示6斤油瓶油量 构成整数序列偶 E S E 0 1 2 3 4 5 6 7 8 表示8斤油瓶中含有的油量 S 0 1 2 3 4 5 6 表示6斤油瓶中含有的油量 总结出如下分油操作规则 3 1状态空间表示知识 续 f1 8斤油瓶不满时装满 E S 且E0 0 S f4 6斤油瓶不空时倒空 E S 且S 0 E 0 f5 8斤油瓶内油全部装入6斤油瓶内 E S E 0且E S 6 0 E S f6 6斤油瓶内油全部装入8斤油瓶内 E S S 0且E S 8 E S 0 f7 用6斤油瓶内油去灌满8斤油瓶 E S 且E 8且E S 8 8 E S 8 f8 用8斤油瓶内油去灌满6斤油瓶 E S 且S 6且E S 6 E S 6 6 3 2搜索问题讨论 1 求任一解路的搜索策略回溯法 Backtracking 爬山法 HillClimbing 宽度优先法 Breadth first 深度优先法 Depth first 限定范围搜索法 BeamSearch 好的优先法 Best first 2 求最佳解路的搜索策略大英博物馆法 BritishMuseum 分枝界限法 BranchandBound 动态规划法 DynamicProgramming 最佳图搜索法 A 3 求与或关系解图的搜索法一般与或图搜索法 AO 极小极大法 Minimax 剪枝法 Alpha betaPruning 启发式剪枝法 HeuristicPruning 3 3图搜索 用计算机进行状态空间问题求解的基本思路 首先把问题的初始状态 即初结点 作为当前状态 选择合适的算符对其进行操作 生成一组子状态 然后检查目标状态是否在其中出现 若出现 则搜索成功 若不出现 则按某种搜索策略从已生成的状态中再选一个状态作为当前状态 重复上述过程 直到目标状态出现 或者不在有可供操作的状态为止 一 显示图与隐式图1 显式图 显式存储 把与问题有关的全部状态空间以及相应的有关知识 叙述性知识 过程性知识 控制性知识 都直接存入知识库 称为显式图 或 显式存贮 2 隐式图 隐式存贮 只存贮与问题有关的部分知识 存贮的状态由初始状态开始运用相应的知识 逐步生成所需的部分状态空间 通过搜索推理 逐渐转移到要求的目标状态 只需在知识库中存贮局部的状态空间 称为 隐式图 或 隐式存贮 通常采用隐式图进行解题 搜索推理 3 3图搜索 续 二 隐式图 求解问题的一般过程open表 用于存放刚生成的结点closed表 用于存放将要扩展或者已扩展的结点 3 3图搜索 续 open表 closed表 搜索过程如下 1 把初始结点s0放入open表中 2 检查open表是否为空 若空 问题无解 退出 3 把open表中的第一个结点取出放入closed表中 并证实该结点为n结点 4 考察结点n为是否为目标结点 若是 退出 5 扩展结点n 生成一组子结点 把其中不是先辈的那些结点加入open表的尾部 并配以指向父结点的指针 6 按某种搜索策略对open表中的结点进行排序7 转入第2步 3 3图搜索 续 一般的图搜索算法 1 G G0 G0 s OPEN s 2 CLOSED 3 LOOP IFOPEN THENEXIT FAIL 4 n FIRST OPEN REMOVE n OPEN ADD n CLOSED 5 IFGOAL n THENEXIT SUCCESS 6 EXPAND n mi G ADD mi G 一般的图搜索算法 续 7 标记和修改指针 ADD mi OPEN 并标记mi到n的指针 计算是否要修改mk ml到n的指针 计算是否修改ml到其后续节点的指针 8 对OPEN中的节点按某种原则重新排序 9 GOLOOP 一些基本概念 节点深度根节点深度 0其它节点深度 父节点深度 1路径设一节点序列为 n0 n1 nk 对于i 1 k 若节点ni 1具有一个后续节点ni 则该序列称为从n0到nk的路径 路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和 用C ni nj 表示从ni到nj的路径的耗散值 扩展一个节点生成该节点的所有后续节点 并给出它们之间的耗散值 这一过程称为 扩展一个节点 三 广度优先搜索流程图广度优先搜索的含义 在对第n层结点没有搜索考察完之前 不对第n 1层结点进行搜索 但在隐式图优先搜索中是讲 从初始结点s0开始 按生成规则逐步生成下一级各子结点 在检查同级子结点同时 生成下级子结点并放在open表的末尾 而后再检查下一个同级结点 如不是目标结点 则按规则生成下级子结点 并放在open表末尾 如此下去 直到找到目标为止 3 3图搜索 续 广度优先搜索算法流程 G G0 G0 s OPEN s CLOSED LOOP IFOPEN THENEXIT FAIL n FIRST OPEN IFGOAL n THENEXIT SUCCESS REMOVE n OPEN ADD n CLOSED 3 3图搜索 续 EXPAND n mi G ADD mi G IF目标在 mi 中 THENEXIT SUCCESS ADD OPEN mj 并标记到n的指针 GOLOOP 3 3图搜索 续 宽度优先搜索示例 8数码问题的宽度优先搜索树 广度优先搜索的性质 当问题有解时 一定能找到解当问题为单位耗散值时 且问题有解时 一定能找到最优解方法与问题无关 具有通用性效率较低属于图搜索方法 3 3图搜索 续 四 深度优先搜索流程从初始结点s0开始 按生成规则逐步生成下一级各子结点 在检查同级子结点同时 生成下级子结点并放在open表的首部 而后再检查下一个同级结点 如不是目标结点 则按规则生成下级子结点 并放在open表首部 如此下去 直到找到目标为止 3 3图搜索 续 深度优先搜索 1 G G0 G0 s OPEN s CLOSED 2 LOOP IFOPEN THENEXIT FAIL 3 n FIRST OPEN 4 IFGOAL n THENEXIT SUCCESS 5 REMOVE n OPEN ADD n CLOSED 6 IFDEPTH n DmGOLOOP 7 EXPAND n mi G ADD mi G 8 IF目标在 mi 中THENEXIT SUCCESS 9 ADD mi OPEN 并标记mj到n指针 10 将mi重排序到open表头部 11 GOLOOP 目标 深度优先搜索性质 一般不能保证找到最优解当深度限制不合理时 可能找不到解 可以将算法改为可变深度限制最坏情况时 搜索空间等于穷举与回溯法的差别 图搜索是一个通用的与问题无关的方法 3 4回溯策略 所谓回溯策略 简单地说是这样一种策略 首先将规则给出一个固定的排序 在搜索时 对当前状态 搜索开始时 当前状态是初始状态 依次检测每一条规则 在当前状态未使用过的规则中找到第一条可触发规则 被应用于当前状态 得到的新状态重新设置为当前状态 并重复以上搜索 如果当前状态无规则可用 或者所有规则已经被试探用过仍未找到问题的解 则将当前状态的前一个状态 即直接生成该状态的状态 设置为当前状态 重复以上搜索 直到找到问题的解 或者试探了所有可能后仍找不到问题的解为止 一个递归的例子 Intabc intn abc m 递归的思想 从前有座山 从前有座山 从前有座山 从前有座山 八数码游戏回溯控制方式 新生成的状态在通向初始状态的路径上已出现过 从初始状态开始 应用的规则数目达到所规定的数目之后还未找到目标状态 这一组规则的数目实际上就是搜索 对当前状态 再没有可应用的规则 回溯搜索算法 BACKTRACK DATA 功能 如果从当前状态DATA到目标状态有路径存在 则返回以规则序列表示的从DATA到目标状态的路径 以规则表的形式表示 如果从当前状态DATA到目标状态没有路径存在 则返回FAIL 回溯搜索算法 递归过程BACKTRACK DATA IFTERM DATA RETURNNIL TERM取真即找到目标 则过程返回空表NIL IFDEADEND DATA RETURNFAIL DEADEND取真 即该状态不合法 则过程返回FAIL 必须回溯 RULES APPRULES DATA APPRULES计算DATA的可应用规则集 依某种原则 任意排列或按启发式准则 排列后赋给RULES LOOP IFNULL RULES RETURNFAIL NULL取真 即规则用完未找到目标 过程返回FAIL 必须回溯 R FIRST RULES 取头条可应用规则 回溯搜索算法 RULES TAIL RULES 删去头条规则 减少可应用规则表的长度 RDATA GEN R DATA 调用规则R作用于当前状态 生成新状态 PATH BACKTRACK RDATA 对新状态递归调用本过程 IFPATH FAIL GOLOOP 当PATH FAIL时 递归调用失败 则转移调用另一规则进行测试 RETURNCONS R PATH 过程返回解路径规则表 或局部解路径子表 回溯搜索算法 BACKTRACK1 DATALIST DATALIST 从初始到当前的状态表 逆向 返回值 同前面的算法一样 是以规则序列表示的路径表 当求解成功时 或者是FAIL 当求解失败时 回溯搜索算法 续 DATA FIRST DATALIST 设置DATA为当前状态 IFMEMBER DATA TAIL DATALIST RETURNFAIL TAIL是取尾操作 表示取表DATALIST中除了第一个元素以外的所有元素 如果DATA在TAIL DATALIST 中存在 则表示有环路出现 过程返回FAIL 必须回溯 IFTERM DATA RETURNNIL TERM取真即找到目标 则过程返回空表NIL IFDEADEND DATA RETURNFAIL DEADEND取真 即该状态不合法 则过程返回FAIL 必须回溯 回溯搜索算法 续 IFLENGTH DATALIST BOUND RETURNFAIL LENGTH计算DATALIST的长度 即搜索的深度 当搜索深度大于给定值BOUND时 则过程返回FAIL 必须回溯 RULES APPRULES DATA APPRULES计算DATA的可应用规则集 依某种原则 任意排列或按启发式准则排列 排列后赋给RULES LOOP IFNULL RULES RETURNFAIL NULL取真 即规则用完未找到目标 过程返回FAIL 必须回溯 R FIRST RULES 取头条可应用规则 RULES TAIL RULES 删去头条规则 减少可应用规则表的长度 回溯搜索算法 续 RDATA GEN R DATA 调用规则R作用于当前状态 生成新状态 RDATALIST CONS RDATA DATALIST 将新状态加入到表DATALIST中 PATH BACKTRACK1 RDATALIST 递归调用本过程 IFPATH FAIL GOLO0P 当PATH FAIL时 递归调用失败 则转移调用另一规则进行测试 RETURNCONS R PATH 过程返回解路径规则表 或局部解路径子表 2 1回溯策略 BacktrackingStrategies 例 四皇后问题 存在问题及解决办法 问题 深度问题死循环问题解决办法 对搜索深度加以限制记录从初始状态到当前状态的路径 一些深入的问题 失败原因分析 多步回溯 一些深入的问题 续 回溯搜索中知识的利用基本思想 以皇后问题为例 尽可能选取划去对角线上位置数最少的 3 5状态空间的与 或树表示法 1 分解 与树 把一个复杂的问题变成简单的子问题 各子问题又可以化成更为简单的子问题 重复此过程 直到不能分解为止 然后对各子问题求解 最后把各子问题复合起来就是问题的解 2 等价变换 或树 通过同结构的等价变换或同态的等价变换把问题分解成比较容易解的子问题 P1 P2 P3任何一个子问题有解 则问题P就可解 称P1 P2 P3之间存在 或 的关系 节点P成为 或 节点 由P1 P2 P3 P之间构成的树为 或 树 3 5状态空间的与 或树表示法 续 几个概念 1 父问题 子问题 问题空间是由一个个问题组成的空间 在问题求解中 用一个节点代表一个问题 若节点A有一边通向B 则表示A的解决有赖于B的解决 A称为父问题 B称为子问题 2 本原问题 不能再分解或变换 而且直接可解的子问题 3 端节点与终止节点 没有子节点的节点 本原问题对应的节点是终止节点 注意 终止节点一定是端节点 但端节点不一定是终止节点 3 5状态空间的与 或树表示法 续 与或图的搜索 基本概念 与或图是一个超图 节点间通过连接符连接 K 连接符 可解节点 终节点是可解节点 若非终节点有 或 子节点时 当且仅当其子节点至少有一能解 该非终节点才可解 若非终节点有 与 子节点时 当且仅当其子节点均能解 该非终节点才可解 不可解节点 没有后裔的非终节点是不可解节点 若非终节点有 或 子节点时 当且仅当所有子节点均不能解时 该非终节点才不可解 若非终节点有 与 子节点时 当至少有一子节点不能解时 该非终节点才不可解 与 或 树的搜索过程 1 把初始节点S0放入OPEN表 2 移出OPEN表的第一个节点N放入CLOSED表 并冠以序号n 3 若节点N可扩展 则做下列工作 1 扩展N 将其子节点配上指向父节点的指针后放入OPEN表 2 考察这些子节点中是否有终止节点 3 删去OPEN表中那些具有可解先辈的节点 因为其先辈节点已经可解 故已无再考察该节点的必要 转步骤2 4 若N不可扩展 则做下列工作 1 标记N为不可解节点 然后由它的不可解返回推断其先辈节点的可解性 并对其中的不可解节点进行标记 如果初始节点S0也被标记为不可解节点 则搜索失败 退出 2 删去OPEN表中那些具有不可解先辈的节点 因为其先辈节点已不可解 故已无再考察这些节点的必要 转步骤2 与状态图搜索一样 搜索成功后 解树已经记录在CLOSED表中 这时需按指向父节点的指针找出整个解树 例3 9三阶梵塔问题设有A B C三个金片 盘 以及三个钢针 盘按自上而下从小到大的顺序穿在1号钢针上 要求将它们全部移到3号钢针上 规则 一次只能搬移一个金片 任何时刻都不能把大的金片压在小的金片上 2号钢针作为过渡使用 解法1 用状态转换图法 用三维状态空间来表示知识或过程 i j k i表示C片所钢针号 j表示B片所在钢针号 k表示A中所在钢针号 显然 组成的状态空间有27个 3 3 3 S0 1 1 1 S1 1 1 2 S2 1 1 3 S3 1 2 1 S4 1 2 2 S5 1 2 3 S6 1 3 1 S7 1 3 2 S8 1 3 3 S9 2 1 1 S10 2 1 2 S11 2 1 3 S12 2 2 1 S13 2 2 2 S14 2 2 3 S15 2 3 1 S16 2 3 2 S17 2 3 3 S18 3 1 1 S19 3 1 2 S20 3 1 3 S21 3 2 1 S22 3 2 2 S23 3 2 3 S24 3 3 1 S25 3 3 2 S26 3 3 3 依题意规则可用18个状态空间表示算子 A B C A 1 2 表示从1号针移到2号针 以下类推 A盘共有6种搬移规则 A 1 3 A 2 1 A 3 1 A 3 2 B 1 2 B 1 3 B 3 1 B 3 2 C 1 2 C 1 3 C 3 1 C 3 2 解法2 用 与 或 树解题为把3个金片移到3号针可分解成如下步骤 1 把A B金片移到2号针问题 双片移动问题 2 把C片移到3号针问题 终止节点 单片移动 3 把A B金片移到3号针问题 双片移动问题 用 表示状态变换 则由 博弈树的搜索 博弈问题 双人一人一步双方信息完备零和 分钱币问题 中国象棋问题 每个势态有40种不同的走法 如果一盘棋双方平均走50步 则搜索的位置有 402 50 10160 即深度达100层 总节点数约为10161个 假设一毫微秒走一步 约需10145年 结论 不可能穷举 极小极大过程 一字棋 在九宫格棋盘上 两位选手轮流在棋盘上摆各自的棋子 每次一枚 谁先取得三子一线的结果就取胜 设程序方MAX的棋子用 表示 对手MIN的棋子用 表示 MAX先走 静态估计函数f p 规定如下 若p对任何一方来说都不是获胜的格局 则f p 所有空格都放上MAX的棋子之后 MAX的三子成线 行 列 对角 的总 所有空格都放上MIN的棋子之后 MIN的三子成线 行 列 对角 的总数 若p是MAX获胜的格局 则f p 若p是MIN获胜的格局 则f p 一字棋第一阶段搜索树 一字棋第二阶段搜索树 一字棋第三阶段搜索树 搜索过程 MAX节点的 值为当前子节点的最大倒推值MIN节点的 值为当前子节点的最小倒推值剪枝的条件 任何MAX节点n的 值 它先辈节点的 值 则n以下的分值可以停止搜索 并令节点n的倒推值为 这种剪枝称为 剪枝 任何MIN节点n的 值 它先辈节点的 值 则n以下的分值可以停止搜索 并令节点n的倒推值为 这种剪枝称为 剪枝 一字棋第一阶段 剪枝方法 搜索过程的博弈树 3 7启发式搜索 启发式图搜索 利用知识来引导搜索 以达到减少搜索范围 降低问题复杂度的目的启发信息的强度强 降低搜索工作量 但可能导致找不到最优解弱 一般导致工作量加大 极限情况下变为盲目搜索 但可能可以找到最优解 希望 引入启发知识 在保证找到最佳解的情况下 尽可能减少搜索范围 提高搜索效率基本思想 定义一个评价函数f 对当前的搜索状态进行评估 找出一个最有希望的节点来扩展 启发式搜索算法A A算法 评价函数的格式 f n g n h n f n 评价函数h n 启发函数 符号的意义 g n 从s到n的最短路径的耗散值h n 从n到g的最短路径的耗散值f n g n h n 从s经过n到g的最短路径的耗散值g n h n f n 分别是g n h n f n 的估计值 A算法 1 OPEN s f s g s h s 2 LOOP IFOPEN THENEXIT FAIL 3 n FIRST OPEN 4 IFGOAL n THENEXIT SUCCESS 5 扩展结点n 生成出不是n祖先的后继结点集 mi 计算f n mi g n mi h mi 6 若mi没有在OPEN表和CLOSED表中出现过 则ADD mi OPEN 7 若mi在OPEN表中有重复结点k 且g mi g k 则REMOVE k OPEN ADD mi OPEN A算法 续 8 若mi在CLOSED表中有重复结点k 且g mi g k 则 1 CLOSED表的结点k改为结点mi 2 按后继元表 修改结点k的所有在OPEN表和CLOSED表中的后裔的g f值 9 OPEN中的节点按f值从小到大排序 10 GOLOOP 一个A算法的例子 定义评价函数 f n g n h n g n 为初始节点到当前节点的耗散值h n 为当前节点 不在位 的将牌数 h计算举例 h n 4 2 最佳图搜索算法A A 算法 在A算法中如果满足条件h n h n 则A算法称为A 算法 A 条件举例 8数码问题h1 n 不在位 的将牌数h2 n 将牌 不在位 的距离和 h1 n 4h2 n 5 A 算法的性质 A 算法的假设设ni nj是任意两个节点 有 C ni nj 其中 为大于0的常数几个等式f s f t h s g t f n 其中s是初始节点 t是目标节点 n是s到t的最佳路径上的节点 A 算法的性质 续1 定理1 对有限图 如果从初始节点s到目标节点t有路径存在 则算法A一定成功结束 引理2 1对无限图 若有从初始节点S到目标节点t的路径 则A 不结束时 在OPEN表中即使最小的一个f值也将增到任意大 或有f n f s A 算法的性质 续3 引理2 2A 结束前 OPEN表中必存在一个节点n n在最佳路径上且满足f n f s f n g n h n g n h n g n h n f n f s A 算法的性质 续3 定理2对无限图 若从初始节点s到目标节点t有路径存在 则A 一定成功结束证明 引理2 1 A 如果不结束 则OPEN中所有的n有f n f s 引理2 2 在A结束前 必存在节点n 使得f n f s 所以 如果A 不结束 将导致矛盾 A 算法的性质 续4 推论2 1 OPEN表上任意一具有f n f s 的节点n 最终将被A 选作扩展节点由定理2 知A 一定结束 由A 的结束条件 OPEN表中f t 最小时才结束 而f t f t f s 所以f n f s 的n均被扩展 得证 A 算法的性质 续5 定理3 可采纳性定理 若存在从初始节点s到目标节点t有路径 则A 必能找到最佳解结束 可采纳性的证明 由定理1 2知A 一定找到一条路径结束设找到的路径s t不是最佳的 t为目标 则 f t g t f s 由引理2 2知结束前OPEN中存在f n f s 的节点n 所以f n f s f t 因此A 应选择n扩展 而不是t 而假设A 选择t结束矛盾 得证 注意 A 的结束条件 A 算法的性质 续6 推论3 1A 选择扩展的任一节点n 有f n f s 由引理2 2知在A 结束前 OPEN中存在节点n f n f s 设此时A 选择n扩展 如果n n 则f n f s 得证 如果n n 由于A 选择n扩展 而不是n 所以有f n f n f s 得证 A 算法的性质 续7 定理4 设对同一问题定义了两个A 算法A1和A2 若A2比A1有较多的启发信息 即对所有非目标节点有h2 n h1 n 则在一条从s到t的路径的隐含图上 搜索结束时 由A2所扩展的每一个节点 也必定由A1所扩展 即A1所扩展的节点数至少和A2一样多 简写 如果h2 n h1 n 目标节点除外 则A1扩展的节点数 A2扩展的节点数 A 算法的性质 续7 注意 在定理4中 评价指标是 扩展的节点数 也就是说 同一个节点无论被扩展多少次 都只计算一次 定理4的证明 使用数学归纳法 对节点的深度进行归纳 1 当d n 0时 即只有一个节点 显然定理成立 2 设d n k时 定理成立 归纳假设 3 当d n k 1时 用反证法 设存在一个深度为k 1的节点n 被A2扩展 但没有被A1扩展 而由假设 A1扩展了n的父节点 即n已经被生成了 因此当A1结束时 n将被保留在OPEN中 定理4的证明 续 n没有被A1选择扩展 有f1 n f s 即g1 n h1 n f s 所以h1 n f s g1 n 1 另一方面A2扩展了n 有f2 n f s 即g2 n h2 n f s 所以h2 n f s g2 n 2 由于d k时 A2扩展的节点 A1也一定扩展 故有g1 n g2 n 因A1扩展的节点数可能较多 所以h1 n f s g1 n f s g2 n 3 比较式 2 3 可得 至少在节点n上有h1 n h2 n 这与定理的前提条件矛盾 因此存在节点n的假设不成立 证毕 对h的评价方法 平均分叉数 设共扩展了d层节点 共搜索了N个节点 则 其中b 称为平均分叉数b 越好 说明h效果越好实验表明 b 是一个比较稳定的常数 同一问题基本不随问题规模变化 对h的评价举例 例 数码问题 随机产生若干初始状态使用h1 d 14 N 539 b 1 44d 20 N 7276 b 1 47使用h2 d 14 N 113 b 1 23d