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

《第二章产生式系统的搜索策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二章产生式系统的搜索策略本章主要内容：•回溯策略算法•图的搜索策略*•启发式图搜索（A算法；爬山法，分支界限法，动态规划法；A*算法*）（*为重点内容）「无信息引导：不考虑知识，按事先排好的固定顺序，依次或随机调两种基本方式：<用规则（盲目）。I有信息引导（启发式）：根据该领域知识（动态确定规则排序），优先调用较合适的规则。r求任一解的搜索策略｛IT前常用的策略求最优解的搜索策略£I求与或关系组图的搜索策略2.1回溯策略呈递为性质1.递为过程BACKTRACK规则集:iflWiW4,且length（DATA）=i-lthenAppend（DATA（i,j））o共16条,Rij表

2、示满足前提条件,在i,j处放一棋子。控制策略①:按固定顺序R11,R12……R.!3,Rm调用BACKTRACK时,其搜索树见图2.3（共回溯22次，得到解组R】2,R-24,氐,R13）o控制策略②：利用知识对规则排序（用对角线函数diag（i,j）计算过（i,j）点的对角线长度），得到规则序列R12，R13,RllR14,R2IR24R22R23,1?31&4&2&3,R42R43R41R44O搜索图见图2.4（只M溯2次）。2.2图搜索策略若控制系统保留所有规则应用后牛成并连接起來的状态记录图，则称为使川了图搜索策略。术语回顾：①节点深度：根节点为0,其它节点为父节点深度加

3、1。②路径：若节点序列（n°,ni,…，m,…，nQ,每个ni都有一个后继节点n.u,则该节点序列称为no—nk的一条路径。②路径耗散值：为路径上各节点间连线耗散值的总和。C(m,t)=C(rii,n_i)+C(n.,,t)可rii—t的路径的耗散值。③扩展一个节点：对当前节点生成所冇后继节点，并给出连接弧线的耗散。一般图搜索算法：P58其中：G:搜索图open:练扩展节点表closed:已扩展节点表伽}:当询节点的子节点集(={mj}U{mk}U{mi))mj:open^11closed中耒出现过的子节点(新节点)mk:已出现在open中的子节点mi:closed中的子节点简例

4、：P59-例2.3无信息搜索过程1.深度优先2.宽度优先2.4启发式搜索过程搜索屮，对open表进行排序，使最有希望通向目标节点的待扩展节点优先扩展。厂①节点处在最优路径上的概率建立节点评价函数f：yj或②节点与目标节点Z间的距离或差异度量1.启发式搜索算法A利用评价函数，评价节点通向t的希望程度，来排列open表节点。f(n,mj)=g(n,mJ+h(mj)其中：f(n,mj)：从S通过n,mi到

5、=

6、标t的耗散估计；g

7、评价两数f(n)=d(n)+w(n)其中:f(n)：通向Fl标的耗散估计；越小越好好d(n)：当前节点深度;演示一下w(n)：不在位的牌数演示:2.爬山法:(前面讲过)这里简介算法M3.分支界限法优先扩展当前具有最小耗散值的分支路径的端节点n,评价苗数f(n)=g(n)o过程Branch一Bound：(略)例：P68：图2$的最短路径搜索(演示开头儿步，直至t(13)位于Queue的最前端。)演示：Queue：s,AD,BDEAFBCEB0347869101111121313Path：BDA§t03467891013N：s,AD,EBDAF034678910{mj)：s,AD,B

8、DEAFBcEEBt03478691()1111121013134.动态规划法对分支界限法的改进：对上层搜索过的节点不再继续搜索。基木思想：求s—t的最优路径时，对某屮间节点I,只考虑S—I所有路径屮耗散最小者，其余不必考虑。介绍改进Z处即可过程:Dynamic一programming图(210)巫点算法5最佳图搜索算法A*在A算法中：若使启发函数h(n)

9、,若A?比街有较多的启发信息(即/22(h)>/2i(h)),例：P74最后一段+图2.11。6A*算法应用举例(1)八数码问题283123164t8475768(2)迷宫问题图2.15求入口到出口的最短路径。则A.所扩展的节点至少和A?—样多。即“启发信息多的，扩展节点数愈少”。(与P66比较一下)1)-(4,4)的最短路径问题:求：(1,规则：if(x,y)then(x+1,y)then(x,y~l)then(x-1,y)then(x,y+1)东一步南西北空间状态图，图2.1