ch3产生式系统的搜索策略

2019/9/71第三章产生式系统的搜索策略状态空间：由给定问题的所有可能的状态组成的空间（相当于全集G）搜索空间：按某种策略在状态空间中选取的部分空间（G的子集）解路径（解空间）：求解问题的一条有效路径。搜索策略的基本思路：搜索空间必须包含解路径，如果问题有解，且尽量缩小搜索空间。搜索策略的评价准则：总体费用最低2019/9/72费用的划分：a规则应用的费用：执行规则时所花的费用b控制费用：选择规则所花的费用。2019/9/73第三章目录3.1回溯策略3.2图搜索策略3.3启发式图搜索策略1）A算法2）爬山算法3）分支界限算法4）动态规划算法5）A*算法2019/9/746）h函数与A*的关系7）关于单调性限制8）A*算法示例2019/9/753.1回溯算法2019/9/762019/9/77例四皇后问题2019/9/78定义综合数据库：设：DATA={ij︱1=i,j=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子因为棋盘上可放入的棋子数为0～4个所以集合中元素数位0～4个，即length（DATA）=0～42019/9/792019/9/7102019/9/7112019/9/7122019/9/7132019/9/7142019/9/7153.2图搜索策略2019/9/716图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子图。图搜索的结果：1，一个完整的搜索图G。2一个解路径，用指针表示的解路径。ProcedureGraphSearch1G=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中2019/9/717标记mj每个到n节点指针确定是否需要修改已在open，closed中的每个节点到n的指针确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8按照某种方式排列open表中的节点，goloop2019/9/7182019/9/7192019/9/720深度优先算法Procedruedepth-First-Search1G=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中的节点8goloop2019/9/721讨论1：如果问题有解，有深度优先搜索算法，是否能够找到解？不一定.解空间是否有限？讨论2：本算法的改进之处是open中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大2019/9/722宽度优先算法Procedruebreadth-First-Search1G=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中2019/9/723标记每个到n节点指针，按照节点深度递增顺序排列open中的节点8goloop理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。2019/9/724：宽度优先例题：由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图2019/9/725解：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同一种状态出现不得多于一次。2019/9/7261）解题过程2）open表和closed表3）节点样子画出整个图G和解路径4）程序何时结束5）改用深度优先如何？2019/9/7273.3启发式图搜索策略基本概念启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。降低搜索空间找到最佳解启发式信息用于解决open表中节点的排列次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值从小到大排列所有节点。2019/9/728评价函数的目的：把最有希望得到最佳解或者解的排列在前面。路径：给定节点序列（n0，n1，…nk）。如果该序列中的任一节点ni-1都有后继节点ni，则该节点序列为从n0到nk的一条路径，路径长度为K路径耗散值：路径耗散值等于该路径上所有相邻节点间耗散值的总和。2019/9/729设：路径山任两点间的耗散值为才C(ni,nj),则从ni到nk的路径耗散值为C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路径耗散值：最佳路径上的实际耗散值，记为：K(ni,nj).K(ni,nj)=C(ni,nj)2019/9/730定义几个函数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的最佳路径的耗散值。2019/9/7314)评价函数：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)称为启发函数。2019/9/7323.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到目标节点的耗散值)2019/9/733open←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值升序排列8goloop2019/9/7342019/9/735例八数码问题令：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个数码不在位。2019/9/7362019/9/737对于f(n)=g(n)+h(n),如果单独考虑g(n)或者h(n),即，1)f(n)=g(n)只考虑搜索过的路径已经耗费的费用；//分支界限算法2）f(n)=h(n)只考虑未来的发展趋势//爬山算法那么可以得到两种特殊的算法：爬山算法和分支界限算法。2019/9/7383.3.2爬山算法ProcedureHill_Climbing1n=s2Loop:ifgoal(n)thenexit(success)3{mi}←expangd(n),计算每个h(mi)nextn←h(mi)最小值的节点4ifh(n)h(nextn)thenexit(fail)5n←nextn6goloop优点，缺点2019/9/7393.3.3分支界限算法f(n)=g(n)ProcedureBranch_Bound1queue(s-s),g(s)=0//queue中保存的是从s出发的路径。2Loop：ifqueue=0thenexit（fail）3path←FIRST(queue)，n←LAST(pATH)//取第一条路径，及该路径的最后节点n4ifgoal(n)thenexit(success)5{mj}←expand(n),计算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)//删除原来的路径，添加长度加一的路径。2019/9/7406queue队列中分支按g值升序排列7GOLOOP例下图右八城市，城市间的耗散值已经给出，利用分支界限算法给出从S到t的最佳路径。2019/9/7412019/9/7423.3.4动态规划算法Proceduredynamic_Programming1queue(s-s),g(s)=0//queue中保存的是从s出发的路径。2Loop：ifqueue=0thenexit（fail）3path←FIRST(queue)，n←LAST(pATH)//取第一条路径，及该路径的最后节点n4ifgoal(n)thenexit(success)5{mj}←expand(n),计算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)2019/9/743//删除原来的路径，添加长度加一的路径。6仅保留queue中到达某一公共节点路径中耗散值最小的路径，余者删除；queue队列中分支按g值升序排列7GOLOOP2019/9/7442019/9/745讨论a动态规划与分支界限差别在于去掉公共路径的冗余部分，提高效率。b如果问题空间是树结构，动态规划与分支界限相同。因为对于树结构不存在到达同一节点有多重路径的情况。C动态规划改进的代价。比如上例中，增加一个城市。2019/9/746A算法总结1初始状态，open=（s）2正常情况下（非成功非失败），取open中的第一个节点n，将n由open转移到closed。3扩充节点n，将新节点加入到open中4修改某些节点的路径5open中节点按照升序排列值得重视的一点：A算法失败的唯一原因是open表为空2019/9/747思考题：图中：s是起始点t是目标节点；如果存在从s到t的一条最佳路径。而n是最佳路径上的一点。1）f*(s)f*(n)f*(t)的关系2）如果f*(s)=10,g*(n)=4问h*(n)=?2019/9/7483.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