ch3产生式系统的搜索策略

第三章产生式系统的搜索战略形状空间：由给定问题的一切能够的形状组成的空间〔相当于选集G〕搜索空间：按某种战略在形状空间中选取的部分空间〔G的子集〕解途径〔解空间〕：求解问题的一条有效途径。搜索战略的根本思绪：搜索空间必需包含解途径，假设问题有解，且尽量减少搜索空间。搜索战略的评价准那么：总体费用最低1/24/20241费用的划分：a规那么运用的费用：执行规那么时所花的费用b控制费用：选择规那么所花的费用。1/24/20242第三章目录3.1回溯战略3.2图搜索战略3.3启发式图搜索战略1〕A算法2〕爬山算法3〕分支界限算法4〕动态规划算法5〕A*算法1/24/202436〕h函数与A*的关系7〕关于单调性限制8〕A*算法例如1/24/202443.1回溯算法1/24/202451/24/20246例四皇后问题1/24/20247定义综合数据库：设：DATA={ij︱1<=i,j<=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子由于棋盘上可放入的棋子数为0～4个所以集合中元素数位0～4个，即length〔DATA〕=0～41/24/202481/24/202491/24/2024101/24/2024111/24/2024121/24/2024131/24/2024143.2图搜索战略1/24/202415图搜索战略图搜索的本质是从问题空间中找出一张包含目的节点的子图。图搜索的结果：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中1/24/202416标志mj每个到n节点指针确定能否需求修正已在open，closed中的每个节点到n的指针确定能否需求修正已在closed中的每个节点的后继节点原来的指针。8按照某种方式陈列open表中的节点，goloop1/24/2024171/24/2024181/24/202419深度优先算法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中的节点8goloop1/24/202420讨论1：假设问题有解，有深度优先搜索算法，能否可以找到解？不一定.解空间能否有限？讨论2：本算法的改良之处是open中节点按照深度优先陈列，但是没有对深度加以控制，能够呵斥搜索代价太大1/24/202421宽度优先算法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中1/24/202422

标志每个到n节点指针，按照节点深度递增顺序陈列open中的节点8goloop实际上可以利用宽度优先搜索可以找到解，假设问题有解的话。讨论：宽度优先算法和深度优先算法能够出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索战略。1/24/202423：宽度优先例题：由一张桌子T、三个积木A、B、C组成一个积木世界，初始形状是A在B上，B在桌子上，C在桌子上；目的形状是：A、B、C依次从上到下陈列在桌子上。如图1/24/202424解：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同一种形状出现不得多于一次。1/24/2024251〕解题过程2〕open表和closed表3〕节点样子画出整个图G和解途径4〕程序何时终了5〕改用深度优先如何？1/24/2024263.3启发式图搜索战略根本概念启发式图搜索的本质是利用启发信息有目的地进展搜索，减少搜索的盲目性。降低搜索空间找到最正确解启发式信息用于处理open表中节点的陈列次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值从小到大陈列一切节点。1/24/202427评价函数的目的：把最有希望得到最正确解或者解的陈列在前面。途径：给定节点序列〔n0，n1，…nk〕。假设该序列中的任一节点ni-1都有后继节点ni，那么该节点序列为从n0到nk的一条途径，途径长度为K途径耗散值：途径耗散值等于该途径上一切相邻节点间耗散值的总和。1/24/202428设：途径山任两点间的耗散值为才C(ni,nj),那么从ni到nk的途径耗散值为C(ni,nj)=C(ni,nj)+C(nj,nk)最正确途径耗散值：最正确途径上的实践耗散值，记为：K(ni,nj).K(ni,nj)<=C(ni,nj)1/24/202429定义几个函数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的最正确途径的耗散值。1/24/2024304)评价函数：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)称为启发函数。1/24/2024313.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到目的节点的耗散值)1/24/202432open←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值升序陈列8goloop1/24/2024331/24/202434例八数码问题令：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个数码不在位。1/24/2024351/24/202436对于f(n)=g(n)+h(n),假设单独思索g(n)或者h(n),即，1)f(n)=g(n)只思索搜索过的途径曾经耗费的费用；//分支界限算法2〕f(n)=h(n)只思索未来的开展趋势//爬山算法那么可以得到两种特殊的算法：爬山算法和分支界限算法。1/24/2024373.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优点，缺陷1/24/2024383.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)//删除原来的途径，添加长度加一的途径。1/24/2024396queue队列中分支按g值升序陈列7GOLOOP例以下图右八城市，城市间的耗散值曾经给出，利用分支界限算法给出从S到t的最正确途径。1/24/2024401/24/2024413.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)1/24/202442//删除原来的途径，添加长度加一的途径。6仅保管queue中到达某一公共节点途径中耗散值最小的途径，余者删除；queue队列中分支按g值升序陈列7GOLOOP1/24/2024431/24/202444讨论a动态规划与分支界限差别在于去掉公共途径的冗余部分，提高效率。b假设问题空间是树构造，动态规划与分支界限一样。由于对于树构造不存在到达同一节点有多重途径的情况。C动态规划改良的代价。比如上例中，添加一个城市。1/24/202445A算法总结1初始形状，open=〔s〕2正常情况下〔非胜利非失败〕，取open中的第一个节点n，将n由open转移到closed。3扩展节点n，将新节点参与到open中4修正某些节点的途径5open中节点按照升序陈列值得注重的一点：A算法失败的独一缘由是open表为空1/24/202446思索题：图中：s是起始点t是目的节点；假设存在从s到t的一条最正确途径。而n是最正确途径上的一点。1〕f*(s)f*(n)f*(t)的关系2〕假设f*(s)=10,g*(n)=4问h*(n)=?1/24/2024473.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)=不在位数字个数。1/24/202448算法可采用性：给定恣意图，设存在从开场节点s到目的节点t的途径。假设算法可以终了在s到t的最正确途径上，那么称该算法是可采用的。A*是具有可采用性。定理1对于有限图，假设从s到t存在途径，那么A算法一定胜利终了。1/24/202449推论1.1由于A*算法是A算法的一个特例。所以在有限图上假设假设从s到t存在途径，那么A*算法一定胜利终了。定理2对于无限图，假设存在s到t途径，那么A*算法一定胜利终了。1/24/202450推论2.1open表中任一满足f(n)≦f*(s)的节点n最终都将被A*选作扩展节点。定理3假设存在节点s到目的节点t途径，那么A*算法一定能找到最正确解终了。推论3.1A*选来扩展的节点都有f(n)≦f*(s)1/24/202451小结1假设存在节点s到目的节点t途径，那么A*算法一定能找到最正确解终了。2open表中一切满足f(n)≦f*(s)的节点n最终都将被A*选作扩展节点。3A*选来扩展的节点都有f(n)≦f*(s)4f*(s)作为A*的一个衡量上限。1/24/2024523.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*算法就是宽度优先算法。1/24/202453定理：给定两个A*算法A1和A2假设A2的启发式信息比A1多，那么在任何存在节点s到目的节点t的途径上，搜索终了时，由A2扩展的每一个节点必定被A1扩展。(A1扩展的节点多)留意搜索空间小，不代表可以找到最正确解。1/24/202454当h=0时，除最下面一层节点外，一切节点都进入closed表。求解途径如图红线所示。当思索到h时，被扩展的节点只需s、c、j，解途径一样1/24/2024553.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)可以了解为三角不等式。1/24/202456定理5假设好h(n)满足单调性限制条件，那么A*算法扩展了节点n之后，就找到了到达节点n的最正确途径，即：假设A*选中节点n，在单调性限制条件下，有g(n)=g*(n)1/24/2024573.38A*算法例如迷宫问题给定迷宫图如下，找出从入口到出口的最短途径。1/24/202458解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〕1/24/202459上移R3：if〔x，y〕then〔x+1，y+1〕下移R4：if〔x，y〕then〔x+1，y-1〕两种解法：宽度优先，设定h(n)1/24/2024601/24/2024613〕A*算法f函数定义f(n)=g(n)+h(n)设每一步的耗散