ch3产生式系统的搜索策略课件

ch3产生式系统的搜索策略2022/12/26ch3产生式系统的搜索策略ch3产生式系统的搜索策略2022/12/26ch3产生式系1费用的划分：a规则应用的费用：执行规则时所花的费用b控制费用：选择规则所花的费用。2022/12/26ch3产生式系统的搜索策略2费用的划分：2022/12/26ch3产生式系统的搜索策略2第三章目录3.1回溯策略3.2图搜索策略3.3启发式图搜索策略1）A算法2）爬山算法3）分支界限算法4）动态规划算法5）A*算法2022/12/26ch3产生式系统的搜索策略3第三章目录3.1回溯策略2022/12/26ch3产生式系统6）h函数与A*的关系7）关于单调性限制8）A*算法示例2022/12/26ch3产生式系统的搜索策略46）h函数与A*的关系2022/12/26ch3产3.1回溯算法2022/12/26ch3产生式系统的搜索策略53.1回溯算法2022/12/26ch3产生式系统的搜索2022/12/26ch3产生式系统的搜索策略62022/12/26ch3产生式系统的搜索策略6例四皇后问题2022/12/26ch3产生式系统的搜索策略7例四皇后问题2022/12/26ch3产生式系统的搜索策略定义综合数据库：设：DATA={ij︱1<=i,j<=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子因为棋盘上可放入的棋子数为0～4个所以集合中元素数位0～4个，即length（DATA）=0～42022/12/26ch3产生式系统的搜索策略8定义综合数据库：2022/12/26ch3产生式系统的搜索策2022/12/26ch3产生式系统的搜索策略92022/12/26ch3产生式系统的搜索策略92022/12/26ch3产生式系统的搜索策略102022/12/26ch3产生式系统的搜索策略102022/12/26ch3产生式系统的搜索策略112022/12/26ch3产生式系统的搜索策略112022/12/26ch3产生式系统的搜索策略122022/12/26ch3产生式系统的搜索策略122022/12/26ch3产生式系统的搜索策略132022/12/26ch3产生式系统的搜索策略132022/12/26ch3产生式系统的搜索策略142022/12/26ch3产生式系统的搜索策略143.2图搜索策略2022/12/26ch3产生式系统的搜索策略153.2图搜索策略2022/12/26ch3产生式系统的搜索策图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子图。图搜索的结果：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中2022/12/26ch3产生式系统的搜索策略16图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子标记mj每个到n节点指针确定是否需要修改已在open，closed中的每个节点到n的指针确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8按照某种方式排列open表中的节点，goloop2022/12/26ch3产生式系统的搜索策略17标记mj每个到n节点指针2022/12/26ch3产生式系统2022/12/26ch3产生式系统的搜索策略182022/12/26ch3产生式系统的搜索策略182022/12/26ch3产生式系统的搜索策略192022/12/26ch3产生式系统的搜索策略19深度优先算法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中的节点8goloop2022/12/26ch3产生式系统的搜索策略20深度优先算法Procedruedepth-First-Se讨论1：如果问题有解，有深度优先搜索算法，是否能够找到解？不一定.解空间是否有限？讨论2：本算法的改进之处是open中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大2022/12/26ch3产生式系统的搜索策略21讨论1：如果问题有解，有深度优先搜索算法，是否能够找到解？2宽度优先算法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中2022/12/26ch3产生式系统的搜索策略22宽度优先算法Procedruebreadth-First-

标记每个到n节点指针，按照节点深度递增顺序排列open中的节点8goloop理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。2022/12/26ch3产生式系统的搜索策略23标记每个到n节点指针，按照节点深度递增顺序排列：宽度优先例题：由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图2022/12/26ch3产生式系统的搜索策略24：宽度优先例题：2022/12/26ch3产生式系统的搜索策解：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同一种状态出现不得多于一次。2022/12/26ch3产生式系统的搜索策略25解：1）状态描述（P1，P2，P3）表示按A、B、C顺序依次1）解题过程2）open表和closed表3）节点样子画出整个图G和解路径4）程序何时结束5）改用深度优先如何？2022/12/26ch3产生式系统的搜索策略261）解题过程2）open表和closed表2022/12/3.3启发式图搜索策略基本概念启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。降低搜索空间找到最佳解启发式信息用于解决open表中节点的排列次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值从小到大排列所有节点。2022/12/26ch3产生式系统的搜索策略273.3启发式图搜索策略基本概念2022/12/26ch3产生评价函数的目的：把最有希望得到最佳解或者解的排列在前面。路径：给定节点序列（n0，n1，…nk）。如果该序列中的任一节点ni-1都有后继节点ni，则该节点序列为从n0到nk的一条路径，路径长度为K路径耗散值：路径耗散值等于该路径上所有相邻节点间耗散值的总和。2022/12/26ch3产生式系统的搜索策略28评价函数的目的：把最有希望得到最佳解或者解的排列设：路径山任两点间的耗散值为才C(ni,nj),则从ni到nk的路径耗散值为C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路径耗散值：最佳路径上的实际耗散值，记为：K(ni,nj).K(ni,nj)<=C(ni,nj)2022/12/26ch3产生式系统的搜索策略29设：路径山任两点间的耗散值为才C(ni,nj),则从ni到n定义几个函数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的最佳路径的耗散值。2022/12/26ch3产生式系统的搜索策略30定义几个函数2022/12/26ch3产生式系统的搜索策略34)评价函数：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)称为启发函数。2022/12/26ch3产生式系统的搜索策略314)评价函数：f(n)=g(n)+h(n),其中f，g，h分3.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到目标节点的耗散值)2022/12/26ch3产生式系统的搜索策略323.1.1A算法1G=G0(G0=s),open=(s),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值升序排列8goloop2022/12/26ch3产生式系统的搜索策略33open←add(open，mj)标记mj到n的指针(m2022/12/26ch3产生式系统的搜索策略342022/12/26ch3产生式系统的搜索策略34例八数码问题令：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个数码不在位。2022/12/26ch3产生式系统的搜索策略35例八数码问题2022/12/26ch3产生式系统的搜索策2022/12/26ch3产生式系统的搜索策略362022/12/26ch3产生式系统的搜索策略36对于f(n)=g(n)+h(n),如果单独考虑g(n)或者h(n),即，1)f(n)=g(n)只考虑搜索过的路径已经耗费的费用；//分支界限算法2）f(n)=h(n)只考虑未来的发展趋势//爬山算法那么可以得到两种特殊的算法：爬山算法和分支界限算法。2022/12/26ch3产生式系统的搜索策略37对于f(n)=g(n)+h(n),如果单独考虑g(n)或者h3.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优点，缺点2022/12/26ch3产生式系统的搜索策略383.3.2爬山算法ProcedureHill_Climb3.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)//删除原来的路径，添加长度加一的路径。2022/12/26ch3产生式系统的搜索策略393.3.3分支界限算法f(n)=g(n)Procedure6queue队列中分支按g值升序排列7GOLOOP例下图右八城市，城市间的耗散值已经给出，利用分支界限算法给出从S到t的最佳路径。2022/12/26ch3产生式系统的搜索策略406queue队列中分支按g值升序排列2022/12/26c2022/12/26ch3产生式系统的搜索策略412022/12/26ch3产生式系统的搜索策略413.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)2022/12/26ch3产生式系统的搜索策略423.3.4动态规划算法Proceduredynamic_P//删除原来的路径，添加长度加一的路径。6仅保留queue中到达某一公共节点路径中耗散值最小的路径，余者删除；queue队列中分支按g值升序排列7GOLOOP2022/12/26ch3产生式系统的搜索策略43//删除原来的路径，添加长度加一的路径。2022/2022/12/26ch3产生式系统的搜索策略442022/12/26ch3产生式系统的搜索策略44讨论a动态规划与分支界限差别在于去掉公共路径的冗余部分，提高效率。b如果问题空间是树结构，动态规划与分支界限相同。因为对于树结构不存在到达同一节点有多重路径的情况。C动态规划改进的代价。比如上例中，增加一个城市。2022/12/26ch3产生式系统的搜索策略45讨论a动态规划与分支界限差别在于去掉公共路径的冗余部分，A算法总结1初始状态，open=（s）2正常情况下（非成功非失败），取open中的第一个节点n，将n由open转移到closed。3扩充节点n，将新节点加入到open中4修改某些节点的路径5open中节点按照升序排列值得重视的一点：A算法失败的唯一原因是open表为空2022/12/26ch3产生式系统的搜索策略46A算法总结1初始状态，open=（s）2022/12/26思考题：图中：s是起始点t是目标节点；如果存在从s到t的一条最佳路径。而n是最佳路径上的一点。1）f*(s)f*(n)f*(t)的关系2）如果f*(s)=10,g*(n)=4问h*(n)=?2022/12/26ch3产生式系统的搜索策略47思考题：图中：s是起始点t是目标节点；如果存在从s到t的3.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)=不在位数字个数。2022/12/26ch3产生式系统的搜索策略483.3.5A*算法（最佳图搜索算法）A*算法定义：20算法可采纳性：给定任意图，设存在从开始节点s到目标节点t的路径。如果算法能够结束在s到t的最佳路径上，则称该算法是可采纳的。A*是具有可采纳性。定理1对于有限图，如果从s到t存在路径，则A算法一定成功结束。2022/12/26ch3产生式系统的搜索策略49算法可采纳性：2022/12/26ch3产生式系统的搜索策略推论1.1因为A*算法是A算法的一个特例。所以在有限图上如果如果从s到t存在路径，则A*算法一定成功结束。定理2对于无限图，如果存在s到t路径，则A*算法一定成功结束。2022/12/26ch3产生式系统的搜索策略50推论1.12022/12/26ch3产生式系统的搜索策略5推论2.1open表中任一满足f(n)≦f*(s)的节点n最终都将被A*选作扩展节点。定理3如果存在节点s到目标节点t路径，则A*算法一定能找到最佳解结束。推论3.1A*选来扩展的节点都有f(n)≦f*(s)2022/12/26ch3产生式系统的搜索策略51推论2.12022/12/26ch3产生式系统的搜索策略51小结1如果存在节点s到目标节点t路径，则A*算法一定能找到最佳解结束。2open表中所有满足f(n)≦f*(s)的节点n最终都将被A*选作扩展节点。3A*选来扩展的节点都有f(n)≦f*(s)4f*(s)作为A*的一个衡量上限。2022/12/26ch3产生式系统的搜索策略52小结2022/12/26ch3产生式系统的搜索策略523.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*算法就是宽度优先算法。2022/12/26ch3产生式系统的搜索策略533.3.6h函数和A*算法的关系本节重点来讨论h函数（即启发定理：给定两个A*算法A1和A2如果A2的启发式信息比A1多，则在任何存在节点s到目标节点t的路径上，搜索结束时，由A2扩展的每一个节点必定被A1扩展。(A1扩展的节点多)

注意搜索空间小，不代表能够找到最佳解。2022/12/26ch3产生式系统的搜索策略54定理：2022/12/26ch3产生式系统的搜索策略54当h=0时，除最下面一层节点外，所有节点都进入closed表。求解路径如图红线所示。当考虑到h时，被扩充的节点只有s、c、j，解路径相同2022/12/26ch3产生式系统的搜索策略55当h=0时，除最下面一层节点外，所有节点都进入closed表3.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)可以理解为三角不等式。

2022/12/26ch3产生式系统的搜索策略563.37h函数单调性限制单调性限制的作用是：避免重复计算某定理5如果好h(n)满足单调性限制条件，则A*算法扩展了节点n之后，就找到了到达节点n的最佳路径，即：如果A*选中节点n，在单调性限制条件下，有g(n)=g*(n)2022/12/26ch3产生式系统的搜索策略57定理52022/12/26ch3产生式系统的搜索策略573.38A*算法示例迷宫问题给定迷宫图如下，找出从入口到出口的最短路径。2022/12/26ch3产生式系统的搜索策略583.38A*算法示例迷宫问题2022/12/26ch3产生式解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）2022/12/26ch3产生式系统的搜索策略59解1）综合数据库2022/12/26ch3产生式系统的搜上移R3：if（x，y）then（x+1，y+1）下移R4：if（x，y）then（x+1，y-1）两种解法：宽度优先，设定h(n)2022/12/26ch3产生式系统的搜索策略60上移R3：if（x，y）then（x+1，y+1）2022022/12/26ch3产生式系统的搜索策略612022/12/26ch3产生式系统的搜索策略613）A*算法f函数定义f(n)=g(n)+h(n)设每一步的耗散值为1（单位耗散值）定义：g(n=d(n)从初始节点s到当前节点n的搜索深度。h(n)=∣-xn∣+∣-yn∣其中是（xg，yg）目标节点的坐标，（xn，yn）是当前节点的坐标。显然满足：h(n)≤h*(n)4）Open表节点排序先按f值排序，如果f值相同，则深度优先，2022/12/26ch3产生式系统的搜索策略623）A*算法f函数定义f(n)=g(n)+h(n)2022/2022/12/26ch3产生式系统的搜索策略632022/12/26ch3产生式系统的搜索策略63关于f函数值的意义的讨论为了调整g和h在h中的作用比例，设f=g+w*h1）令w=0则f=g，此时，A*成为宽度优先算法。特点：可扩大搜索范围便于找到最佳解，但是费用比较大。2）令w为一个大的整数，则加大了h在f函数中的作用力度。其意义在于：不考虑到目前已经消耗的费用，只关心当前节点到目标节点剩余的搜索工作量。2022/12/26ch3产生式系统的搜索策略64关于f函数值的意义的讨论2022/12/26ch3产生式系统本章算法汇总1.回溯策略2.图搜索策略

A算法：h(n)=0g(n)=-d(n)深度优先

F(n)=g(n)+h(n)g(n)=0爬山算法

h(n)=0分支界限算法各分支只保留一个动态规划算法h(n)=0g(n)=d(n)宽度优先算法A*算法。。。。。。。2022/12/26ch3产生式系统的搜索策略65本章算法汇总1.回溯策略2022/12/26ch3产生式系统本章例题汇总1.四皇后问题回溯策略2积木世界问题宽度优先3八数码问题A算法4八城市s-t分支界限算法。5迷宫问题A*算法2022/12/26ch3产生式系统的搜索策略66本章例题汇总1.四皇后问题回溯策略2022/1演讲完毕，谢谢听讲!再见，seeyouagain2022/12/26ch3产生式系统的搜索策略演讲完毕，谢谢听讲!再见，seeyouagain202267ch3产生式系统的搜索策略2022/12/26ch3产生式系统的搜索策略ch3产生式系统的搜索策略2022/12/26ch3产生式系68费用的划分：a规则应用的费用：执行规则时所花的费用b控制费用：选择规则所花的费用。2022/12/26ch3产生式系统的搜索策略69费用的划分：2022/12/26ch3产生式系统的搜索策略2第三章目录3.1回溯策略3.2图搜索策略3.3启发式图搜索策略1）A算法2）爬山算法3）分支界限算法4）动态规划算法5）A*算法2022/12/26ch3产生式系统的搜索策略70第三章目录3.1回溯策略2022/12/26ch3产生式系统6）h函数与A*的关系7）关于单调性限制8）A*算法示例2022/12/26ch3产生式系统的搜索策略716）h函数与A*的关系2022/12/26ch3产3.1回溯算法2022/12/26ch3产生式系统的搜索策略723.1回溯算法2022/12/26ch3产生式系统的搜索2022/12/26ch3产生式系统的搜索策略732022/12/26ch3产生式系统的搜索策略6例四皇后问题2022/12/26ch3产生式系统的搜索策略74例四皇后问题2022/12/26ch3产生式系统的搜索策略定义综合数据库：设：DATA={ij︱1<=i,j<=4},其中：ij表示棋子所在行列如：24表示第二行第四列有一枚棋子因为棋盘上可放入的棋子数为0～4个所以集合中元素数位0～4个，即length（DATA）=0～42022/12/26ch3产生式系统的搜索策略75定义综合数据库：2022/12/26ch3产生式系统的搜索策2022/12/26ch3产生式系统的搜索策略762022/12/26ch3产生式系统的搜索策略92022/12/26ch3产生式系统的搜索策略772022/12/26ch3产生式系统的搜索策略102022/12/26ch3产生式系统的搜索策略782022/12/26ch3产生式系统的搜索策略112022/12/26ch3产生式系统的搜索策略792022/12/26ch3产生式系统的搜索策略122022/12/26ch3产生式系统的搜索策略802022/12/26ch3产生式系统的搜索策略132022/12/26ch3产生式系统的搜索策略812022/12/26ch3产生式系统的搜索策略143.2图搜索策略2022/12/26ch3产生式系统的搜索策略823.2图搜索策略2022/12/26ch3产生式系统的搜索策图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子图。图搜索的结果：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中2022/12/26ch3产生式系统的搜索策略83图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子标记mj每个到n节点指针确定是否需要修改已在open，closed中的每个节点到n的指针确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8按照某种方式排列open表中的节点，goloop2022/12/26ch3产生式系统的搜索策略84标记mj每个到n节点指针2022/12/26ch3产生式系统2022/12/26ch3产生式系统的搜索策略852022/12/26ch3产生式系统的搜索策略182022/12/26ch3产生式系统的搜索策略862022/12/26ch3产生式系统的搜索策略19深度优先算法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中的节点8goloop2022/12/26ch3产生式系统的搜索策略87深度优先算法Procedruedepth-First-Se讨论1：如果问题有解，有深度优先搜索算法，是否能够找到解？不一定.解空间是否有限？讨论2：本算法的改进之处是open中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大2022/12/26ch3产生式系统的搜索策略88讨论1：如果问题有解，有深度优先搜索算法，是否能够找到解？2宽度优先算法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中2022/12/26ch3产生式系统的搜索策略89宽度优先算法Procedruebreadth-First-

标记每个到n节点指针，按照节点深度递增顺序排列open中的节点8goloop理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。2022/12/26ch3产生式系统的搜索策略90标记每个到n节点指针，按照节点深度递增顺序排列：宽度优先例题：由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图2022/12/26ch3产生式系统的搜索策略91：宽度优先例题：2022/12/26ch3产生式系统的搜索策解：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同一种状态出现不得多于一次。2022/12/26ch3产生式系统的搜索策略92解：1）状态描述（P1，P2，P3）表示按A、B、C顺序依次1）解题过程2）open表和closed表3）节点样子画出整个图G和解路径4）程序何时结束5）改用深度优先如何？2022/12/26ch3产生式系统的搜索策略931）解题过程2）open表和closed表2022/12/3.3启发式图搜索策略基本概念启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。降低搜索空间找到最佳解启发式信息用于解决open表中节点的排列次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值从小到大排列所有节点。2022/12/26ch3产生式系统的搜索策略943.3启发式图搜索策略基本概念2022/12/26ch3产生评价函数的目的：把最有希望得到最佳解或者解的排列在前面。路径：给定节点序列（n0，n1，…nk）。如果该序列中的任一节点ni-1都有后继节点ni，则该节点序列为从n0到nk的一条路径，路径长度为K路径耗散值：路径耗散值等于该路径上所有相邻节点间耗散值的总和。2022/12/26ch3产生式系统的搜索策略95评价函数的目的：把最有希望得到最佳解或者解的排列设：路径山任两点间的耗散值为才C(ni,nj),则从ni到nk的路径耗散值为C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路径耗散值：最佳路径上的实际耗散值，记为：K(ni,nj).K(ni,nj)<=C(ni,nj)2022/12/26ch3产生式系统的搜索策略96设：路径山任两点间的耗散值为才C(ni,nj),则从ni到n定义几个函数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的最佳路径的耗散值。2022/12/26ch3产生式系统的搜索策略97定义几个函数2022/12/26ch3产生式系统的搜索策略34)评价函数：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)称为启发函数。2022/12/26ch3产生式系统的搜索策略984)评价函数：f(n)=g(n)+h(n),其中f，g，h分3.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到目标节点的耗散值)2022/12/26ch3产生式系统的搜索策略993.1.1A算法1G=G0(G0=s),open=(s),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值升序排列8goloop2022/12/26ch3产生式系统的搜索策略100open←add(open，mj)标记mj到n的指针(m2022/12/26ch3产生式系统的搜索策略1012022/12/26ch3产生式系统的搜索策略34例八数码问题令：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个数码不在位。2022/12/26ch3产生式系统的搜索策略102例八数码问题2022/12/26ch3产生式系统的搜索策2022/12/26ch3产生式系统的搜索策略1032022/12/26ch3产生式系统的搜索策略36对于f(n)=g(n)+h(n),如果单独考虑g(n)或者h(n),即，1)f(n)=g(n)只考虑搜索过的路径已经耗费的费用；//分支界限算法2）f(n)=h(n)只考虑未来的发展趋势//爬山算法那么可以得到两种特殊的算法：爬山算法和分支界限算法。2022/12/26ch3产生式系统的搜索策略104对于f(n)=g(n)+h(n),如果单独考虑g(n)或者h3.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优点，缺点2022/12/26ch3产生式系统的搜索策略1053.3.2爬山算法ProcedureHill_Climb3.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)//删除原来的路径，添加长度加一的路径。2022/12/26ch3产生式系统的搜索策略1063.3.3分支界限算法f(n)=g(n)Procedure6queue队列中分支按g值升序排列7GOLOOP例下图右八城市，城市间的耗散值已经给出，利用分支界限算法给出从S到t的最佳路径。2022/12/26ch3产生式系统的搜索策略1076queue队列中分支按g值升序排列2022/12/26c2022/12/26ch3产生式系统的搜索策略1082022/12/26ch3产生式系统的搜索策略413.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)2022/12/26ch3产生式系统的搜索策略1093.3.4动态规划算法Proceduredynamic_P//删除原来的路径，添加长度加一的路径。6仅保留queue中到达某一公共节点路径中耗散值最小的路径，余者删除；queue队列中分支按g值升序排列7GOLOOP2022/12/26ch3产生式系统的搜索策略110//删除原来的路径，添加长度加一的路径。2022/2022/12/26ch3产生式系统的搜索策略1112022/12/26ch3产生式系统的搜索策略44讨论a动态规划与分支界限差别在于去掉公共路径的冗余部分，提高效率。b如果问题空间是树结构，动态规划与分支界限相同。因为对于树结构不存在到达同一节点有多重路径的情况。C动态规划改进的代价。比如上例中，增加一个城市。2022/12/26ch3产生式系统的搜索策略112讨论a动态规划与分支界限差别在于去掉公共路径的冗余部分，A算法总结1初始状态，open=（s）2正常情况下（非成功非失败），取open中的第一个节点n，将n由open转移到closed。3扩充节点n，将新节点加入到open中4修改某些节点的路径5open中节点按照升序排列值得重视的一点：A算法失败的唯一原因是open表为空2022/12/26ch3产生式系统的搜索策略113A算法总结1初始状态，open=（s）2022/12/26思考题：图中：s是起始点t是目标节点；如果存在从s到t的一条最佳路径。而n是最佳路径上的一点。1）f*(s)f*(n)f*(t)的关系2）如果f*(s)=10,g*(n)=4问h*(n)=?2022/12/26ch3产生式系统的搜索策略114思考题：图中：s是起始点t是目标节点；如果存在从s到t的3.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)=不在位数字个数。2022/12/26ch3产生式系统的搜索策略1153.3.5A*算法（最佳图搜索算法）A*算法定义：20算法可采纳性：给定任意图，设存在从开始节点s到目标节点t的路径。如果算法能够结束在s到t的最佳路径上，则称该算法是可采纳的。A*是具有可采纳性。定理1对于有限图，如果从s到t存在路径，则A算法一定成功结束。2022/12/26ch3产生式系统的搜索策略116算法可采纳性：2022/12/26ch3产生式系统的搜索策略推论1.1因为A*算法是A算法的一个特例。所以在有限图上如果如果从s到t存在路径，则A*算法一定成功结束。定理2对于无限图，如果存在s到t路径，则A*算法一定成功结束。2022/12/26ch3产生式系统的搜索策略117推论1.12022/12/26ch3产生式系统的搜索策略5推论2.1open表中任一满足f(n)≦f*(s)的节点n最终都将被A*选作扩展节点。定理3如果存在节点s到目标节点t路径，则A*算法一定能找到最佳解结束。推论3.1A*选来扩展的节点都有f(n)≦f*(s)2022/12/26ch3产生式系统的搜索策略118推论2.12022/12/26ch3产生式系统的搜索策略51小结1如果存在节点s到目标节点t路径，则A*算法一定能找到最佳解结束。2open表中所有满足f(n)≦f*(s)的节点n最终都将被A*选作扩展节点。3A*选来扩展的节点都有f(n)≦f*(s)4f*(s)作为A*的一个衡量上限。2022/12/26ch3产生式系统的搜索策略119小结2022/12/26ch3产生式系统的搜索策略523.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*算法就是宽度优先算法。2022/12/26ch3产生式系统的搜索策略1203.3.6h函数和A*算法的关系本节重点来讨论h函数（即启发定理：给定两个A*算法A1和A2如果A2的启发式信息比A1多，则在任何存在节点s到目标节点t的路径上，搜索结束时，由A2扩展的每一个节点必定被A1扩展。(A1扩展的节点多)

注意搜索空间小，不代表能够找到最佳解。2022/12/26ch3产生式系统的搜索策略121定理：2022/1