产生式系统的搜索策略讲义课件18101.pptx

《产生式系统的搜索策略讲义课件18101.pptx》由会员分享，可在线阅读，更多相关《产生式系统的搜索策略讲义课件18101.pptx（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章产生式系统的搜索策略第三章产生式系统的搜索策略状态空间：由给定问题的所有可能的状态组状态空间：由给定问题的所有可能的状态组成的空间（相当于全集成的空间（相当于全集G）搜索空间：按某种策略在状态空间中选取的搜索空间：按某种策略在状态空间中选取的部分空间（部分空间（G的子集）的子集）解路径（解空间）：求解问题的一条有效路解路径（解空间）：求解问题的一条有效路径。径。搜索策略的基本思路：搜索空间必须包含解搜索策略的基本思路：搜索空间必须包含解路径，如果问题有解，且尽量缩小搜索空间。路径，如果问题有解，且尽量缩小搜索空间。搜索策略的评价准则：总体费用最低搜索策略的评价准则：总体费用最低3/30/

2、20231费用的划分：费用的划分：a 规则应用的费用：执行规则时所花的费规则应用的费用：执行规则时所花的费用用 b 控制费用：选择规则所花的费用。控制费用：选择规则所花的费用。3/30/20232第三章目录第三章目录3.1回溯策略回溯策略3.2 图搜索策略图搜索策略3.3 启发式图搜索策略启发式图搜索策略 1）A算法算法 2）爬山算法）爬山算法 3）分支界限算法）分支界限算法 4）动态规划算法）动态规划算法 5）A*算法算法3/30/20233 6）h函数与函数与A*的关系的关系 7）关于单调性限制）关于单调性限制 8）A*算法示例算法示例3/30/202343.1回溯算法回溯算法 3/30/

3、202353/30/20236例例 四皇后问题四皇后问题3/30/20237定义综合数据库：定义综合数据库：设：设：DATA=ij1=i,j=4,其中：其中：ij表示棋表示棋子所在行列子所在行列 如：如：24表示第二行第四列有一表示第二行第四列有一枚棋子枚棋子因为棋盘上因为棋盘上 可放入的棋子数为可放入的棋子数为04个个所以集合中元素数位所以集合中元素数位0 4个，即个，即length（DATA）=0 43/30/202383/30/202393/30/2023103/30/2023113/30/2023123/30/2023133/30/2023143.2图搜索策略图搜索策略3/30/202

4、315图搜索策略图搜索策略图搜索的实质是从问题空间中找出一张包含目标节点的子图搜索的实质是从问题空间中找出一张包含目标节点的子图。图。图搜索的结果：图搜索的结果：1，一个完整的搜索图，一个完整的搜索图G。2一个解路径，一个解路径，用指针表示的解路径。用指针表示的解路径。Procedure GraphSearch1 G=G0(G0=s),open=(s)/s:初始状态初始状态2 closed=()3Loop:if open=()then exit(fall)4 nfirst(open)remove(n,open),add(n,closed)5 if goal(n)then exit(succes

5、s)6mj expand(n),/mj不含不含n的先辈节点的先辈节点7 openadd(open，mj)/mj不在不在open，closed中中3/30/202316标记标记mj每个到每个到n节点指针节点指针确定是否需要修改已在确定是否需要修改已在open，closed中的每中的每个节点到个节点到n的指针的指针确定是否需要修改已在确定是否需要修改已在closed中的每个节点中的每个节点的后继节点原来的指针。的后继节点原来的指针。8按照某种方式排列按照某种方式排列open表中的节点，表中的节点，go loop3/30/2023173/30/2023183/30/202319深度优先算法深度优先算

6、法Procedrue depth-First-Search1 G=G0(G0=s),open=(s),closed=()/s:初始状态初始状态2 Loop:if open=()then exit(fall)3 nfirst(open)4 if goal(n)then exit(success)5remove(n,open),add(n,closed)6mj expand(n),/mj不含不含n的先辈节点的先辈节点7 openadd(open，mj)/mj不在不在open，closed中中标记标记mj每个到每个到n节点指针，按照节点深度递减顺节点指针，按照节点深度递减顺序排列序排列open中的节

7、点中的节点 8 go loop3/30/202320讨论讨论1：如果问题有解，有深度优先搜索算：如果问题有解，有深度优先搜索算法，是否能够找到解？法，是否能够找到解？不一定不一定.解空间是否有限？解空间是否有限？讨论讨论2：本算法的改进之处是：本算法的改进之处是open中节点按中节点按照深度优先排列，但是没有对深度加以控照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大制，可能造成搜索代价太大3/30/202321宽度优先算法宽度优先算法Procedrue breadth-First-Search1 G=G0(G0=s),open=(s),closed=()/s:初始状态初始状态2

8、Loop:if open=()then exit(fall)3 nfirst(open)4 if goal(n)then exit(success)5remove(n,open),add(n,closed)6mj expand(n),/mj不含不含n的先辈节点的先辈节点7 openadd(open，mj)/mj不在不在open，closed中中3/30/202322 标记每个到标记每个到n节点指针，按照节点深度节点指针，按照节点深度递增顺序排列递增顺序排列open中的节点中的节点 8 go loop 理论上可以利用宽度优先搜索能够找到解，理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。

9、如果问题有解的话。讨论：宽度优先算法和深度优先算法可能讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。息，所以称为无信息搜索策略。3/30/202323：宽度优先例题：宽度优先例题：由一张桌子由一张桌子T、三个积木、三个积木A、B、C组成一组成一个积木世界，初始状态是个积木世界，初始状态是A在在B上，上，B在桌在桌子上，子上，C在桌子上；目标状态是：在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图依次从上到下排列在桌子上。如图3/30/202324解：解：1）状态描述）状态描述（P1，P2，P

10、3）表示按）表示按A、B、C顺序依次分别在顺序依次分别在P1,P2,P3上其中上其中Pi是是积木或者桌子。初始状态时（积木或者桌子。初始状态时（B、T、T）,目标状态目标状态 可以表示（可以表示（B、C、T）2）定义操作）定义操作:move(x,y)表示将积木表示将积木x移到移到Y上上 ；约束条件约束条件:a X顶部必须是空的顶部必须是空的 b 如果如果Y是是积木，积木，Y的顶部必须是空的的顶部必须是空的 c 同一种状态出现不得多于一次。同一种状态出现不得多于一次。3/30/2023251）解题过程）解题过程 2）open表和表和closed表表3）节点样子画出整个图）节点样子画出整个图G 和

11、解路径和解路径4）程序何时结束）程序何时结束 5）改用深度优先如何？）改用深度优先如何？3/30/2023263.3启发式图搜索策略启发式图搜索策略基本概念基本概念启发式图搜索的实质是利用启发信息有目启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。的地进行搜索，减少搜索的盲目性。降低搜索空间降低搜索空间 找到最佳解找到最佳解启发式信息用于解决启发式信息用于解决open表中节点的排列表中节点的排列次序问题，方法是利用一个评价函数计算次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值表中节点的评价函数值，按照函数值从小到大排列所有节点。从小到大排列所有

12、节点。3/30/202327 评价函数的目的：把最有希望得到最佳解评价函数的目的：把最有希望得到最佳解或者解的排列在前面。或者解的排列在前面。路径路径：给定节点序列（：给定节点序列（n0，n1，nk）。）。如果该序列中的任一节点如果该序列中的任一节点ni-1都有后继节点都有后继节点ni，则该节点序列为从，则该节点序列为从n0到到nk的一条路径，的一条路径，路径长度为路径长度为K路径耗散值：路径耗散值等于该路径上所路径耗散值：路径耗散值等于该路径上所有相邻节点间耗散值的总和。有相邻节点间耗散值的总和。3/30/202328设：路径山任两点间的耗散值为才设：路径山任两点间的耗散值为才C(ni,nj

13、),则从则从ni到到nk的路径耗散值为的路径耗散值为C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路径耗散值：最佳路径上的实际耗散最佳路径耗散值：最佳路径上的实际耗散值，记为：值，记为：K(ni,nj).K(ni,nj)=g*(n)2)当当h=0且且g(n)=d(n)时，时，f(n)=d(n)既既宽度优先策略，宽度优先策略，d(n):节点深度。节点深度。3）h(n)称为启发函数。称为启发函数。3/30/2023313.1.1A算法算法1 G=G0(G0=s),open=(s),closed=()，f(s)=g(s)+h(s)/s:初始状态初始状态2 Loop:if open=()th

14、en exit(fall)3 nfirst(open)h()4 if goal(n)then exit(success)5remove(n,open),add(n,closed)6mj expand(n),/mj不含不含n的先辈节点的先辈节点 计算计算f(n,mi)=g(n,mi)+h(mi),(自自s经过经过n，mi 到目标到目标节点的耗散值节点的耗散值)3/30/202332openadd(open，mj)标记标记mj到到n的指针的指针(mj不在不在open，closed中中)if f(n,mk)f(mk)then f(mk)f(n,mk)标记标记mk到到n的指针的指针(mk在在open中

15、中)if f(n,mL)f(mL)then f(mL)f(n,mL)标记标记mL到到n的指针的指针(mL在在closed中中)add(mL,open),把把mL放回到放回到open中中7 Open中的节点按中的节点按f值升序排列值升序排列 8 go loop3/30/2023333/30/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个数码不在位。个数码不在位。3/30/2023

16、353/30/202336对于对于f(n)=g(n)+h(n),如果单独考虑如果单独考虑g(n)或者或者h(n),即，即，1)f(n)=g(n)只考虑搜索过的路径已经耗费只考虑搜索过的路径已经耗费的费用；的费用；/分支界限算法分支界限算法 2）f(n)=h(n)只考虑未来的发展趋势只考虑未来的发展趋势/爬山爬山算法算法那么可以得到两种特殊的算法：爬山算法和那么可以得到两种特殊的算法：爬山算法和分支界限算法。分支界限算法。3/30/2023373.3.2爬山算法爬山算法Procedure Hill _Climbing1 n=s2 Loop:if goal(n)then exit(success)

17、3mi expangd(n),计算每个计算每个h(mi)nextn h(mi)最小值的节点最小值的节点4 if h(n)h(nextn)then exit(fail)5 n nextn6go loop 优点，缺点优点，缺点3/30/2023383.3.3分支界限算法分支界限算法f(n)=g(n)Procedure Branch_Bound1 queue(s-s),g(s)=0 /queue中保存的是从中保存的是从s出出发的路径。发的路径。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH)/取第一条路径，及该路径的最后节

18、点取第一条路径，及该路径的最后节点n4 if goal(n)then exit(success)5 mj expand(n),计算计算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)/删除原来的路径，添加长度加一的路径。删除原来的路径，添加长度加一的路径。3/30/2023396 queue队列中分支按队列中分支按g值升序排列值升序排列7 GO LOOP例例 下图右八城市，城市间的耗散值已经给下图右八城市，城市间的耗散值已经给出，利用分支界限算法给出从出，利用分支界限算法给出从S到到t的最佳的最佳路径。路径。3/30/2023403/30/20234

19、13.3.4动态规划算法动态规划算法Procedure dynamic_Programming1 queue(s-s),g(s)=0 /queue中保存的是从中保存的是从s出出发的路径。发的路径。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH)/取第一条路径，及该路径的最后节点取第一条路径，及该路径的最后节点n4 if goal(n)then exit(success)5 mj expand(n),计算计算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)3/30/20234

20、2 /删除原来的路径，添加长度加一的路径。删除原来的路径，添加长度加一的路径。p6 仅保留仅保留queue中到达某一公共节点路径中中到达某一公共节点路径中耗散值最小的路径，余者删除；耗散值最小的路径，余者删除；queue队列队列中分支按中分支按g值升序排列值升序排列7 GO LOOP3/30/2023433/30/202344讨论讨论 a 动态规划与分支界限差别在于去掉动态规划与分支界限差别在于去掉公共路径的冗余部分，提高效率。公共路径的冗余部分，提高效率。b 如果问题空间是树结构，动态规划与分如果问题空间是树结构，动态规划与分支界限相同。因为对于树结构不存在到达支界限相同。因为对于树结构不存

21、在到达同一节点有多重路径的情况。同一节点有多重路径的情况。C动态规划动态规划 改进的代价。比如上例中，增改进的代价。比如上例中，增加一个城市。加一个城市。3/30/202345A算法总结算法总结1 初始状态，初始状态，open=（s）2 正常情况下（非成功非失败），取正常情况下（非成功非失败），取open中的第一个节点中的第一个节点n，将，将n由由open 转移到转移到closed。3 扩充节点扩充节点n，将新节点加入到，将新节点加入到open中中4修改某些节点的路径修改某些节点的路径5 open中节点按照升序排列中节点按照升序排列值得重视的一点：值得重视的一点：A算法失败的唯一原因是算法失败

22、的唯一原因是open表为空表为空3/30/202346思考题：图中：思考题：图中：s是起始点是起始点 t是目标节点；是目标节点；如果存在从如果存在从s到到t的一条最佳路径。而的一条最佳路径。而n是最是最佳路径上的一点。佳路径上的一点。1）f*(s)f*(n)f*(t)的关系的关系2）如果）如果f*(s)=10,g*(n)=4 问问h*(n)=?3/30/2023473.3.5 A*算法（最佳图搜索算法）算法（最佳图搜索算法）A*算法定义：算法定义：对于算法对于算法A，如果有，如果有h（n）h*（n）,即即h（n）以以h*（n）为上界，则称）为上界，则称 该算法称为该算法称为A*算法。算法。如果

23、令如果令h（n）=0，则满足，则满足h（n）h*（n）这就是分支界限算法这就是分支界限算法 和动态规划算法和动态规划算法。再令再令g(n)=d(n)(d(n)是节点深度）则是节点深度）则f(n)=d(n);A*算法就是宽度优先算法。宽度优先算法能找到最佳算法就是宽度优先算法。宽度优先算法能找到最佳解。解。例：例：第二章中八数码问题第二章中八数码问题 令令h(n)=w(n)=不在位数字个数。不在位数字个数。3/30/202348算法可采纳性：算法可采纳性：给定任意图，设存在从开始节点给定任意图，设存在从开始节点s到目标节点到目标节点t的路径。如果算法能够结束在的路径。如果算法能够结束在s到到t的

24、最佳路径的最佳路径上，则称该算法是可采纳的。上，则称该算法是可采纳的。A*是具有可采纳是具有可采纳性。性。定理定理1 对于有限图，如果从对于有限图，如果从s到到t存在路径，则存在路径，则A算法算法一定成功结束。一定成功结束。3/30/202349推论推论1.1 因为因为A*算法是算法是A算法的一个特例。所以在算法的一个特例。所以在有限图上如果如果从有限图上如果如果从s到到t存在路径，则存在路径，则A*算法一定成功结束。算法一定成功结束。定理定理2 对于无限图，如果存在对于无限图，如果存在s到到t路径，则路径，则A*算算法一定成功结束。法一定成功结束。3/30/202350推论推论2.1 ope

25、n表中任一满足表中任一满足f(n)f*(s)的节点的节点n最终最终都将被都将被A*选作扩展节点。选作扩展节点。定理定理3 如果存在节点如果存在节点s到目标节点到目标节点t路径，则路径，则A*算算法一定能找到最佳解结束。法一定能找到最佳解结束。推论推论3.1 A*选来扩展的节点都有选来扩展的节点都有f(n)f*(s)3/30/202351小结小结 1如果存在节点如果存在节点s到目标节点到目标节点t路径，则路径，则A*算算法一定能找到最佳解结束。法一定能找到最佳解结束。2 open表中所有满足表中所有满足f(n)f*(s)的节点的节点n最最终都将被终都将被A*选作扩展节点。选作扩展节点。3 A*选

26、来扩展的节点都有选来扩展的节点都有f(n)f*(s)4 f*(s)作为作为A*的一个衡量上限。的一个衡量上限。3/30/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有较多启发信息。有较多启发信息。讨论：启发信息与讨

27、论：启发信息与h函数值成正比。极端情况函数值成正比。极端情况下，完全没有启发信息时下，完全没有启发信息时h=0，则此时，则此时A*算算法就是宽度优先算法。法就是宽度优先算法。3/30/202353定理：定理：给定两个给定两个A*算法算法A1 和和A2 如果如果A2的启发式的启发式信息比信息比A1多，则在任何存在节点多，则在任何存在节点s到目标节到目标节点点t的路径上，搜索结束时，由的路径上，搜索结束时，由A2扩展的每扩展的每一个节点必定被一个节点必定被A1扩展。扩展。(A1扩展的节点多扩展的节点多)注意搜索空间小，不代表能够找到最佳解。注意搜索空间小，不代表能够找到最佳解。3/30/20235

28、4当当h=0时，除最下面一层节点外，所有节点都进入时，除最下面一层节点外，所有节点都进入closed表。求解路径如图红线所示。表。求解路径如图红线所示。当考虑到当考虑到h时，被扩充的节点只有时，被扩充的节点只有s、c、j，解路径，解路径相同相同3/30/2023553.37 h函数单调性限制函数单调性限制单调性限制的作用是：避免重复计算某些节单调性限制的作用是：避免重复计算某些节点的点的f值（主要对连通图而言）以便减少搜索值（主要对连通图而言）以便减少搜索代价。代价。单调性定义：给定一个启发函数单调性定义：给定一个启发函数h，如果对，如果对于所有节点于所有节点ni和和nj(nj是是ni的子节点

29、的子节点)，如果满，如果满足足 h(ni)-h(nj)c(ni,nj)h(t)=0,则称则称h满足单满足单调性限制。调性限制。上式可以写成h(ni)-h(nj)+c(ni,nj)可以理解为三角不等式。可以理解为三角不等式。3/30/202356定理定理5 如果好如果好h(n)满足单调性限制条件，则满足单调性限制条件，则A*算算法扩展了节点法扩展了节点n之后，就找到了到达节点之后，就找到了到达节点n的最佳路径，的最佳路径，即：如果即：如果A*选中节点选中节点n，在单调性限制条，在单调性限制条件下，有件下，有g(n)=g*(n)3/30/2023573.38A*算法示例算法示例迷宫问题迷宫问题给定

30、迷宫图如下，找出从入口到出口的最给定迷宫图如下，找出从入口到出口的最短路径。短路径。3/30/202358解解 1）综合数据库）综合数据库 定义定义 状态集：状态集：（x，y）1x，y4 其中（其中（x，y）表示任意节点的坐标）表示任意节点的坐标 所以问题表示为求解从（所以问题表示为求解从（1,1）到（）到（4,4）的）的最短路径。最短路径。2规则集（定义规则集（定义4条移动规则）条移动规则）右移右移R1：if（x，y）then（x+1，y）左移左移R2：if（x，y）then（x-1，y）3/30/202359上移上移R3：if（x，y）then（x+1，y+1）下移下移R4：if（x，y）

31、then（x+1，y-1）两种解法：宽度优先，设定两种解法：宽度优先，设定h(n)3/30/2023603/30/2023613）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

32、值相同，则深度优先，值相同，则深度优先，3/30/2023623/30/202363关于关于f函数值的意义的讨论函数值的意义的讨论为了调整为了调整g和和h在在h中的作用比例，中的作用比例，设设f=g+w*h1）令）令w=0 则则f=g，此时，此时，A*成为宽度优先算成为宽度优先算法。特点：可扩大搜索范围便于找到最佳法。特点：可扩大搜索范围便于找到最佳解，但是费用比较大。解，但是费用比较大。2）令）令w为一个大的整数，则加大了为一个大的整数，则加大了h在在f函数函数中的作用力度。其意义在于：不考虑到目中的作用力度。其意义在于：不考虑到目前已经前已经 消耗的费用，只关心当前节点到目消耗的费用，只关

33、心当前节点到目标节点剩余的搜索工作量。标节点剩余的搜索工作量。3/30/202364本章算法汇总本章算法汇总1.回溯策略回溯策略2.图搜索策略图搜索策略 A算法算法：h(n)=0 g(n)=-d(n)深度优先深度优先 F(n)=g(n)+h(n)g(n)=0 爬山算法爬山算法 h(n)=0 分支界限算法分支界限算法 各分支各分支 只保留一个只保留一个 动态规划算法动态规划算法 h(n)=0 g(n)=d(n)宽度优先算法宽度优先算法A*算法算法 。3/30/202365本章例题汇总本章例题汇总1.四皇后问题四皇后问题 回溯策略回溯策略2 积木世界问题积木世界问题 宽度优先宽度优先3 八数码问题八数码问题 A算法算法4 八城市八城市s-t 分支界限算法。分支界限算法。5 迷宫问题迷宫问题 A*算法算法3/30/202366本本章章结结束束！3/30/202367