第二章 产生式系统的搜索策略.doc

第二章 产生式系统的搜索策略 本章主要内容：l 回溯策略算法l 图的搜索策略*l 启发式图搜索（A算法*，爬山法，分支界限法，动态规划法*，A*算法*）（*为重点内容）无信息引导：不考虑知识，按事先排好的固定顺序，依次或随机调两种基本方式： 用规则（盲目）。有信息引导（启发式）：根据该领域知识（动态确定规则排序），优先调用较合适的规则。求任一解 的搜索策略 目前常用的策略：求最优解 的搜索策略 求与或关系组图的搜索策略21 回 溯 策 略呈递为性质1递为过程BACKTRACK例：四皇后问题 综合库：DATA=L（表），L的元素（ i ,j） 如 （12，24，31，43）规则集:if 1i4,且length(DATA)=i-1 then Append(DATA(i,j)。 共16条，Rij表示满足前提条件，在i,j处放一棋子。控制策略:按固定顺序R11 ,R12R43,R44调用BACKTRACK时，其搜索树见图2.3（共回溯22次，得到解组R12 ，R24，R31，R43）。控制策略：利用知识对规则排序（用对角线函数diag（i,j）计算过（i,j）点的对角线长度），得到规则序列R12，R13，R11 R14，R21 R24 R22 R23，R31 R34 R32 R33，R42R43R41R44。搜索图见图2.4（只回溯2次）。2.2 图搜索策略若控制系统保留所有规则应用后生成并连接起来的状态记录图，则称为使用了图搜索策略。术语回顾：节点深度：根节点为0，其它节点为父节点深度加1。 路径：若节点序列（n0，n1，ni，nk），每个ni都有一个后继节点ni+1，则该节点序列称为n0nk的一条路径。 路径耗散值：为路径上各节点间连线耗散值的总和。 C（ni，t）=C（ni，nj）+C（nj，t） nit的路径的耗散值。 扩展一个节点：对当前节点生成所有后继节点，并给出连接弧线的耗散。一般图搜索算法：P58 其中：G ： 搜索图 open ： 练扩展节点表 closed ： 已扩展节点表 mi ： 当前节点的子节点集（=mjmkml） mj ： open和closed中未出现过的子节点（新节点） 对于树不会出现如下 mk ： 已出现在open中的子节点 节点ml ： closed中的子节点简例：P59 例2.3无信息搜索过程1. 深度优先2.宽度优先2.4 启发式搜索过程搜索中，对open表进行排序，使最有希望通向目标节点的待扩展节点优先扩展。节点处在最优路径上的概率建立节点评价函数f：或节点与目标节点之间的距离或差异度量1. 启发式搜索算法A利用评价函数，评价节点通向t的希望程度，来排列open表节点。 f（n，mi）=g（n，mi）+h（mi） 其中：f（n，mi）：从S通过n，mi 到目标t的耗散估计； g（n，mi）：从S通过n到mi的耗散（能准确计算）； 越小，近路 h（mi） ：从mi 到目标节点的最小耗散估计。 越小离目标越近例：P65 八码问题： 设评价函数f（n）=d（n）+w（n）其中：f（n）：通向目标的耗散估计；越小越好好d（n）：当前节点深度；w（n）：不在位的牌数 演示一下演示：open：S(4) B(4) A(6) C(6) D(5) E(5) F(6) G(6) H(7) I(5) J(7)closed：S(4) B(4) D(5) E(5)mi：A(6) B(4) C(6) ， D(5) E(5) F(6) ， G(6) H(7) ， I(5) J(7) k L Mn： S(4) B(4) D(5) E(5)2. 爬山法：（前面讲过）这里简介算法3. 分支界限法优先扩展当前具有最小耗散值的分支路径的端节点n，评价函数 f（n）=g（n）。过程 BranchBound：（略）例：P68：图2.8的最短路径搜索（演示开头几步，直至t（13）位于Queue的最前端。）演示：Queue：s，A D，B D E A F B C E B t 0 3 4 7 8 6 9 10 11 11 12 13 13 Path： s，A D， E B D A F t 0 3 4 6 7 8 9 10 13 N：s，A D， E B D A F 0 3 4 6 7 8 9 10mi：s，A D， B D E A F B C E E B t 0 3 4 7 8 6 9 10 11 11 12 10 13 134. 动态规划法对分支界限法的改进：对上层搜索过的节点不再继续搜索。基本思想：求st的最优路径时，对某中间节点I，只考虑SI所有路径中耗散最小者，其余不必考虑。过程：Dynamicprogramming 介绍改进之处即可 图（2.10）5 最佳图搜索算法A* 重点算法在A算法中： 若使启发函数，则称为A*算法。：最短路径的耗散值。 其值未知定理涵义概括：定理1、2：对有限或无限图，若有路径存在，则A*算法一定成功。定理3：若存在的路径，则A*必能找到最佳解。定理4：对两个A*算法A1 和A2，若A2比A1有较多的启发信息（即），则A1 所扩展的节点至少和A2一样多。即“启发信息多的，扩展节点数愈少”。 例：P74最后一段+图2.11。6 A*算法应用举例（1） 八数码问题 （与P66比较一下）（2） 迷宫问题图2.15 求入口到出口的最短路径。 求：（1，1）（4，4）的最短路径问题： 规则：if（x，y） then （x+1，y） 东一步 then （x,y-1） 南 then (x-1,y) 西 then (x,y+1) 北空间状态图，图2.16（全搜索）A*算法： ，显然有，取则，设OPEN表中相等时深度优先，则得最佳路径：图2.17（1,1）(2,3)(3,4)(3,3)(4,3)(4,4)7 评价函数的启发能力一般，启发能力强，则搜索效率高例： 对图2.18的 八码问题取，是对节点n 中将牌排列顺序的计分总和 四周各将牌：其后继者与目标状态顺序一致为0，否则为2； 中心位置：无将牌为0，有将牌为1；，越小该节点越有希望。搜索图见2.18，得到18步的最优解。课后练习：画出的求问题搜索树。 课后练习 构造函数要考虑计算2值量不要过重。 可通过（是一个函数）来调节与的作用能力很大，过分强调启发分量；很小，突出宽度优先的特征。经验证明：使随节点深度反比变化，可提高搜索效率。 即在较浅处主要依靠启发分量；较深处，搜索渐宽，保证到达目标的某一路径被找到。2.5 搜索算法讨论1 弱方法 在搜索算法中引入启发信息，多数情况以较小的代价能找到解，但不能保证 任何情况下都能获得解（以前讲的都是）。但若引入较强的启发信息，会有很大改善，显示出“强”的作用。 例：用黄金分割法在a，b上求连续函数f 在何处取得极值及其大