ch3产生式系统的搜索策略

第三章产生式系统的搜索策略状态空间：由给定问题的所有可能的状态组成的空间（相当于全集G）搜索空间：按某种策略在状态空间中选取的部分空间（G的子集）解路径（解空间）：求解问题的一条有效路径。搜索策略的基本思路：搜索空间必须包含解路径，如果问题有解，且尽量缩小搜索空间。搜索策略的评价准则：总体费用最低9/16/20231费用的划分：a规则应用的费用：执行规则时所花的费用b控制费用：选择规则所花的费用。9/16/20232第三章目录3.1回溯策略3.2图搜索策略3.3启发式图搜索策略1）A算法2）爬山算法3）分支界限算法4）动态规划算法5）A*算法9/16/202336）h函数与A*的关系7）关于单调性限制8）A*算法示例9/16/202343.1回溯算法9/16/202359/16/20236例四皇后问题9/16/20237定义综合数据库：设：DATA={ij︱1<=i,j<=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子因为棋盘上可放入的棋子数为0～4个所以集合中元素数位0～4个，即length（DATA）=0～49/16/202389/16/202399/16/2023109/16/2023119/16/2023129/16/2023139/16/2023143.2图搜索策略9/16/202315图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子图。图搜索的结果：1，一个完整的搜索图G。2一个解路径，用指针表示的解路径。ProcedureGraphSearch1G=G0(G0=s),open=(s)//s:初始状态2closed=()3Loop:ifopen=()thenexit(fall)4n←first(open)remove(n,open),add(n,closed)5ifgoal(n)thenexit(success)6{mj}←expand(n),//mj不含n的先辈节点7open←add(open，mj)//mj不在open，closed中9/16/202316标记mj每个到n节点指针确定是否需要修改已在open，closed中的每个节点到n的指针确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8按照某种方式排列open表中的节点，goloop9/16/2023179/16/2023189/16/202319深度优先算法Procedruedepth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始状态2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先辈节点7open←add(open，mj)//mj不在open，closed中标记mj每个到n节点指针，按照节点深度递减顺序排列open中的节点8goloop9/16/202320讨论1：如果问题有解，有深度优先搜索算法，是否能够找到解？不一定.解空间是否有限？讨论2：本算法的改进之处是open中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大9/16/202321宽度优先算法Procedruebreadth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始状态2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先辈节点7open←add(open，mj)//mj不在open，closed中9/16/202322

标记每个到n节点指针，按照节点深度递增顺序排列open中的节点8goloop理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。9/16/202323：宽度优先例题：由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图9/16/202324解：1）状态描述（P1，P2，P3）表示按A、B、C顺序依次分别在P1,P2,P3上其中Pi是积木或者桌子。初始状态时（B、T、T）,目标状态可以表示（B、C、T）2）定义操作:move(x,y)表示将积木x移到Y上；约束条件:aX顶部必须是空的b如果Y是积木，Y的顶部必须是空的c同一种状态出现不得多于一次。9/16/2023251）解题过程2）open表和closed表3）节点样子画出整个图G和解路径4）程序何时结束5）改用深度优先如何？9/16/2023263.3启发式图搜索策略基本概念启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。降低搜索空间找到最佳解启发式信息用于解决open表中节点的排列次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值从小到大排列所有节点。9/16/202327评价函数的目的：把最有希望得到最佳解或者解的排列在前面。路径：给定节点序列（n0，n1，…nk）。如果该序列中的任一节点ni-1都有后继节点ni，则该节点序列为从n0到nk的一条路径，路径长度为K路径耗散值：路径耗散值等于该路径上所有相邻节点间耗散值的总和。9/16/202328设：路径山任两点间的耗散值为才C(ni,nj),则从ni到nk的路径耗散值为C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路径耗散值：最佳路径上的实际耗散值，记为：K(ni,nj).K(ni,nj)<=C(ni,nj)9/16/202329定义几个函数1）g*(n)=k(s,n):从初始节点s到当前节点n的最佳路径的耗散值。2)h*(n)=k(n,t):从当前节点n到目标节点t的最佳路径的好三者。3)f*(n)=g*(n)+h*(n):从初始节点s通过当前节点n到目标节点t的最佳路径的耗散值。9/16/2023304)评价函数：f(n)=g(n)+h(n),其中f，g，h分别是f*，g*，h*的估计值。通常约定:f(n)按照升序排列。讨论：有上述定义，得:1)g(n)>=g*(n)2)当h=0且g(n)=d(n)时，f(n)=d(n)既宽度优先策略，d(n):节点深度。3）h(n)称为启发函数。9/16/2023313.1.1A算法1G=G0(G0=s),open=(s),closed=()，f(s)=g(s)+h(s)//s:初始状态2Loop:ifopen=()thenexit(fall)3n←first(open)h()4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先辈节点计算f(n,mi)=g(n,mi)+h(mi),(自s经过n，mi到目标节点的耗散值)9/16/202332open←add(open，mj)标记mj到n的指针(mj不在open，closed中)iff(n,mk)<f(mk)thenf(mk)←f(n,mk)标记mk到n的指针(mk在open中)iff(n,mL)<f(mL)thenf(mL)←f(n,mL)标记mL到n的指针(mL在closed中)

add(mL,open),把mL放回到open中7Open中的节点按f值升序排列8goloop9/16/2023339/16/202334例八数码问题令：g(n)=d(n)节点深度h(n)=w(n)不在位的数码个数(启发函数)则f(n)=d(n)+w(n)如初始节点s的f值f(0)=d(0)+w(0)=0+4=4有4个数码不在位。9/16/2023359/16/202336对于f(n)=g(n)+h(n),如果单独考虑g(n)或者h(n),即，1)f(n)=g(n)只考虑搜索过的路径已经耗费的费用；//分支界限算法2）f(n)=h(n)只考虑未来的发展趋势//爬山算法那么可以得到两种特殊的算法：爬山算法和分支界限算法。9/16/2023373.3.2爬山算法ProcedureHill_Climbing1n=s2Loop:ifgoal(n)thenexit(success)3{mi}←expangd(n),计算每个h(mi)nextn←h(mi)最小值的节点4ifh(n)<h(nextn)thenexit(fail)5n←nextn6goloop优点，缺点9/16/2023383.3.3分支界限算法f(n)=g(n)ProcedureBranch_Bound1queue(s-s),g(s)=0//queue中保存的是从s出发的路径。2Loop：ifqueue=0thenexit（fail）3path←FIRST(queue)，n←LAST(pATH)//取第一条路径，及该路径的最后节点n4ifgoal(n)thenexit(success)5{mj}←expand(n),计算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)//删除原来的路径，添加长度加一的路径。9/16/2023396queue队列中分支按g值升序排列7GOLOOP例下图右八城市，城市间的耗散值已经给出，利用分支界限算法给出从S到t的最佳路径。9/16/2023409/16/2023413.3.4动态规划算法Proceduredynamic_Programming1queue(s-s),g(s)=0//queue中保存的是从s出发的路径。2Loop：ifqueue=0thenexit（fail）3path←FIRST(queue)，n←LAST(pATH)//取第一条路径，及该路径的最后节点n4ifgoal(n)thenexit(success)5{mj}←expand(n),计算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)9/16/202342//删除原来的路径，添加长度加一的路径。6仅保留queue中到达某一公共节点路径中耗散值最小的路径，余者删除；queue队列中分支按g值升序排列7GOLOOP9/16/2023439/16/202344讨论a动态规划与分支界限差别在于去掉公共路径的冗余部分，提高效率。b如果问题空间是树结构，动态规划与分支界限相同。因为对于树结构不存在到达同一节点有多重路径的情况。C动态规划改进的代价。比如上例中，增加一个城市。9/16/202345A算法总结1初始状态，open=（s）2正常情况下（非成功非失败），取open中的第一个节点n，将n由open转移到closed。3扩充节点n，将新节点加入到open中4修改某些节点的路径5open中节点按照升序排列值得重视的一点：A算法失败的唯一原因是open表为空9/16/202346思考题：图中：s是起始点t是目标节点；如果存在从s到t的一条最佳路径。而n是最佳路径上的一点。1）f*(s)f*(n)f*(t)的关系2）如果f*(s)=10,g*(n)=4问h*(n)=?9/16/2023473.3.5A*算法（最佳图搜索算法）A*算法定义：对于算法A，如果有h（n）≤h*（n）,即h（n）以h*（n）为上界，则称该算法称为A*算法。如果令h（n）=0，则满足h（n）≤h*（n）

这就是分支界限算法和动态规划算法。再令g(n)=d(n)(d(n)是节点深度）则f(n)=d(n);A*算法就是宽度优先算法。宽度优先算法能找到最佳解。例：第二章中八数码问题令h(n)=w(n)=不在位数字个数。9/16/202348算法可采纳性：给定任意图，设存在从开始节点s到目标节点t的路径。如果算法能够结束在s到t的最佳路径上，则称该算法是可采纳的。A*是具有可采纳性。定理1对于有限图，如果从s到t存在路径，则A算法一定成功结束。9/16/202349推论1.1因为A*算法是A算法的一个特例。所以在有限图上如果如果从s到t存在路径，则A*算法一定成功结束。定理2对于无限图，如果存在s到t路径，则A*算法一定成功结束。9/16/202350推论2.1open表中任一满足f(n)≦f*(s)的节点n最终都将被A*选作扩展节点。定理3如果存在节点s到目标节点t路径，则A*算法一定能找到最佳解结束。推论3.1A*选来扩展的节点都有f(n)≦f*(s)9/16/202351小结1如果存在节点s到目标节点t路径，则A*算法一定能找到最佳解结束。2open表中所有满足f(n)≦f*(s)的节点n最终都将被A*选作扩展节点。3A*选来扩展的节点都有f(n)≦f*(s)4f*(s)作为A*的一个衡量上限。9/16/2023523.3.6h函数和A*算法的关系本节重点来讨论h函数（即启发信息量）对A*算法搜索效率的影响总结。定义：给定两个A*算法A1和A2，都有f(n1)=g(n1)+h(n1)f(n2)=g(n2)+h(n2)如果对于所有非目标节点n，有h(n1)<h(n2)则算法A2比算法A1有较多启发信息。讨论：启发信息与h函数值成正比。极端情况下，完全没有启发信息时h=0，则此时A*算法就是宽度优先算法。9/16/202353定理：给定两个A*算法A1和A2如果A2的启发式信息比A1多，则在任何存在节点s到目标节点t的路径上，搜索结束时，由A2扩展的每一个节点必定被A1扩展。(A1扩展的节点多)

注意搜索空间小，不代表能够找到最佳解。9/16/202354当h=0时，除最下面一层节点外，所有节点都进入closed表。求解路径如图红线所示。当考虑到h时，被扩充的节点只有s、c、j，解路径相同9/16/2023553.37h函数单调性限制单调性限制的作用是：避免重复计算某些节点的f值（主要对连通图而言）以便减少搜索代价。单调性定义：给定一个启发函数h，如果对于所有节点ni和nj(nj是ni的子节点)，如果满足h(ni)-h(nj)≤c(ni,nj)h(t)=0,则称h满足单调性限制。

上式可以写成h(ni)-≤h(nj)+c(ni,nj)可以理解为三角不等式。

9/16/202356定理5如果好h(n)满足单调性限制条件，则A*算法扩展了节点n之后，就找到了到达节点n的最佳路径，即：如果A*选中节点n，在单调性限制条件下，有g(n)=g*(n)9/16/2023573.38A*算法示例迷宫问题给定迷宫图如下，找出从入口到出口的最短路径。9/16/202358解1）综合数据库定义状态集：{（x，y）∣1≤x，y≤4}其中（x，y）表示任意节点的坐标所以问题表示为求解从（1,1）到（4,4）的最短路径。2规则集（定义4条移动规则）右移R1：if（x，y）then（x+1，y）左移R2：if（x，y）then（x-1，y）9/16/202359上移R3：if（x，y）then（x+1，y+1）下移R4：if（x，y）then（x+1，y-1）两种解法：宽度优先，设定h(n)9/16/2023609/16/2023613）A*算法f函数定义f(n)=g(n)+h(n)设每一步的耗散值为1（