1、2023-7-81第三章产生式系统的搜索策略第三章产生式系统的搜索策略 状态空间：由给定问题的所有可能的状态组状态空间：由给定问题的所有可能的状态组成的空间（相当于全集成的空间（相当于全集G）搜索空间：按某种策略在状态空间中选取的搜索空间：按某种策略在状态空间中选取的部分空间（部分空间（G的子集）的子集）解路径（解空间）：求解问题的一条有效路解路径（解空间）：求解问题的一条有效路径。径。搜索策略的基本思路：搜索空间必须包含解搜索策略的基本思路：搜索空间必须包含解路径，如果问题有解，且尽量缩小搜索空间。路径，如果问题有解，且尽量缩小搜索空间。搜索策略的评价准则：总体费用最低搜索策略的评价准则：总
2、体费用最低.2023-7-82 费用的划分：费用的划分：a 规则应用的费用：执行规则时所花的费规则应用的费用：执行规则时所花的费用用 b 控制费用：选择规则所花的费用。控制费用：选择规则所花的费用。.2023-7-83第三章目录第三章目录 3.1回溯策略回溯策略 3.2 图搜索策略图搜索策略 3.3 启发式图搜索策略启发式图搜索策略 1）A算法算法 2）爬山算法）爬山算法 3）分支界限算法）分支界限算法 4）动态规划算法）动态规划算法 5）A*算法算法.2023-7-84 6）h函数与函数与A*的关系的关系 7）关于单调性限制）关于单调性限制 8）A*算法示例算法示例.2023-7-853.1
3、回溯算法回溯算法 .2023-7-86.2023-7-87 例例 四皇后问题四皇后问题.2023-7-88 定义综合数据库：定义综合数据库：设：设：DATA=ij1=i,j=4,其中：其中：ij表示表示棋子所在行列棋子所在行列 如：如：24表示第二行第四列有表示第二行第四列有一枚棋子一枚棋子 因为棋盘上因为棋盘上 可放入的棋子数为可放入的棋子数为04个个 所以集合中元素数位所以集合中元素数位0 4个，即个，即length（DATA）=0 4.2023-7-89.2023-7-810.2023-7-811.2023-7-812.2023-7-813.2023-7-814.2023-7-8153.
4、2图搜索策略图搜索策略.2023-7-816图搜索策略图搜索策略 图搜索的实质是从问题空间中找出一张包含目标节点的子图搜索的实质是从问题空间中找出一张包含目标节点的子图。图。图搜索的结果：图搜索的结果：1，一个完整的搜索图，一个完整的搜索图G。2一个解路径，一个解路径，用指针表示的解路径。用指针表示的解路径。Procedure GraphSearch 1 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 g
5、oal(n)then exit(success)6mj expand(n),/mj不含不含n的先辈节点的先辈节点 7 openadd(open，mj)/mj不在不在open，closed中中.2023-7-817 标记标记mj每个到每个到n节点指针节点指针 确定是否需要修改已在确定是否需要修改已在open，closed中的每中的每个节点到个节点到n的指针的指针 确定是否需要修改已在确定是否需要修改已在closed中的每个节点中的每个节点的后继节点原来的指针。的后继节点原来的指针。8按照某种方式排列按照某种方式排列open表中的节点，表中的节点，go loop.2023-7-818.2023-7
6、-819.2023-7-820深度优先算法深度优先算法 Procedrue depth-First-Search 1 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节点指针，按照节点深
7、度递减顺节点指针，按照节点深度递减顺序排列序排列open中的节点中的节点 8 go loop.2023-7-821 讨论讨论1：如果问题有解，有深度优先搜索算：如果问题有解，有深度优先搜索算法，是否能够找到解？法，是否能够找到解？不一定不一定.解空间是否有限？解空间是否有限？讨论讨论2：本算法的改进之处是：本算法的改进之处是open中节点按中节点按照深度优先排列，但是没有对深度加以控照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大制，可能造成搜索代价太大.2023-7-822宽度优先算法宽度优先算法 Procedrue breadth-First-Search 1 G=G0(G0=
8、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中中.2023-7-823 标记每个到标记每个到n节点指针，按照节点深度节点指针，按照节点深度递增顺序排列递增顺序排列open中的节点中的节点 8 go loop 理论上可以利用宽度优先
9、搜索能够找到理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。解，如果问题有解的话。讨论：宽度优先算法和深度优先算法可能讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。息，所以称为无信息搜索策略。.2023-7-824：宽度优先例题：宽度优先例题：由一张桌子由一张桌子T、三个积木、三个积木A、B、C组成一组成一个积木世界，初始状态是个积木世界，初始状态是A在在B上，上，B在桌在桌子上，子上，C在桌子上；目标状态是：在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图依次从上到下排列在桌子上。
10、如图.2023-7-825 解：解：1）状态描述）状态描述（P1，P2，P3）表示按）表示按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 同一种状态出现不得多于一次。同一种状态出现不得多于一次。.2023-7-826 1）解题过程）解题过程 2）op
11、en表和表和closed表表 3）节点样子画出整个图）节点样子画出整个图G 和解路径和解路径 4）程序何时结束）程序何时结束 5）改用深度优先如何？）改用深度优先如何？.2023-7-8273.3启发式图搜索策略启发式图搜索策略 基本概念基本概念 启发式图搜索的实质是利用启发信息有目启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。的地进行搜索，减少搜索的盲目性。降低搜索空间降低搜索空间 找到最佳解找到最佳解 启发式信息用于解决启发式信息用于解决open表中节点的排列表中节点的排列次序问题，方法是利用一个评价函数计算次序问题，方法是利用一个评价函数计算open表中节点的评价函
12、数值，按照函数值表中节点的评价函数值，按照函数值从小到大排列所有节点。从小到大排列所有节点。.2023-7-828 评价函数的目的：把最有希望得到最佳解评价函数的目的：把最有希望得到最佳解或者解的排列在前面。或者解的排列在前面。p路径路径：给定节点序列（：给定节点序列（n0，n1，nk）。）。如果该序列中的任一节点如果该序列中的任一节点ni-1都有后继节点都有后继节点ni，则该节点序列为从，则该节点序列为从n0到到nk的一条路径，的一条路径，路径长度为路径长度为Kp路径耗散值：路径耗散值等于该路径上所路径耗散值：路径耗散值等于该路径上所有相邻节点间耗散值的总和。有相邻节点间耗散值的总和。.20
13、23-7-829 设：路径山任两点间的耗散值为才设：路径山任两点间的耗散值为才C(ni,nj),则从则从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)称为启发函数。称为启发函数。.2023-7-8323.1.1A算法算法 1 G=G0(G0=s),open=(s),closed=
14、()，f(s)=g(s)+h(s)/s:初始状态初始状态 2 Loop:if open=()then 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 到目标到目标节点的耗散值节点的耗散值).2023-7-833 openadd(open，mj)标记标记mj到到n的指针的指针(mj不在不在open，closed中中)if f(n,m
15、k)f(mk)then f(mk)f(n,mk)标记标记mk到到n的指针的指针(mk在在open中中)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 loop.2023-7-834.2023-7-835 例例 八数码问题八数码问题 令：令：g(n)=d(n)节点深度节点深度 h(n)=w(n)不在位的数码个数不在位的数码个数(启发启发函数函数)则则 f(n)=d(n)+w(n)如初始节点如初始节点s
16、的的f值值f(0)=d(0)+w(0)=0+4=4 有有4个数码不在位。个数码不在位。.2023-7-836.2023-7-837 对于对于f(n)=g(n)+h(n),如果单独考虑如果单独考虑g(n)或者或者h(n),即，即，1)f(n)=g(n)只考虑搜索过的路径已经耗费只考虑搜索过的路径已经耗费的费用；的费用；/分支界限算法分支界限算法 2）f(n)=h(n)只考虑未来的发展趋势只考虑未来的发展趋势/爬山爬山算法算法那么可以得到两种特殊的算法：爬山算法和那么可以得到两种特殊的算法：爬山算法和分支界限算法。分支界限算法。.2023-7-8383.3.2爬山算法爬山算法 Procedure
17、Hill _Climbing 1 n=s 2 Loop:if goal(n)then exit(success)3mi expangd(n),计算每个计算每个h(mi)nextn h(mi)最小值的节点最小值的节点 4 if h(n)h(nextn)then exit(fail)5 n nextn 6go loop 优点，缺点优点，缺点.2023-7-8393.3.3分支界限算法分支界限算法f(n)=g(n)Procedure Branch_Bound 1 queue(s-s),g(s)=0 /queue中保存的是从中保存的是从s出出发的路径。发的路径。2 Loop：ifqueue=0 the
18、n exit（fail）3 pathFIRST(queue)，n LAST(pATH)/取第一条路径，及该路径的最后节点取第一条路径，及该路径的最后节点n 4 if goal(n)then exit(success)5 mj expand(n),计算计算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue)/删除原来的路径，添加长度加一的路径。删除原来的路径，添加长度加一的路径。.2023-7-840 6 queue队列中分支按队列中分支按g值升序排列值升序排列 7 GO LOOP 例例 下图右八城市，城市间的耗散值已经给下图右八城市，城市间的耗散值已经给
19、出，利用分支界限算法给出从出，利用分支界限算法给出从S到到t的最佳的最佳路径。路径。.2023-7-841.2023-7-8423.3.4动态规划算法动态规划算法 Procedure dynamic_Programming 1 queue(s-s),g(s)=0 /queue中保存的是从中保存的是从s出出发的路径。发的路径。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH)/取第一条路径，及该路径的最后节点取第一条路径，及该路径的最后节点n 4 if goal(n)then exit(success)5 mj expa
20、nd(n),计算计算g(mj)=g(n,mj)remove(s-n,queue),add(s-mj,queue).2023-7-843 /删除原来的路径，添加长度加一的路径。删除原来的路径，添加长度加一的路径。p6 仅保留仅保留queue中到达某一公共节点路径中中到达某一公共节点路径中耗散值最小的路径，余者删除；耗散值最小的路径，余者删除；queue队列队列中分支按中分支按g值升序排列值升序排列 7 GO LOOP.2023-7-844.2023-7-845 讨论讨论 a 动态规划与分支界限差别在于去掉动态规划与分支界限差别在于去掉公共路径的冗余部分，提高效率。公共路径的冗余部分，提高效率。b
21、 如果问题空间是树结构，动态规划与分如果问题空间是树结构，动态规划与分支界限相同。因为对于树结构不存在到达支界限相同。因为对于树结构不存在到达同一节点有多重路径的情况。同一节点有多重路径的情况。C动态规划动态规划 改进的代价。比如上例中，增改进的代价。比如上例中，增加一个城市。加一个城市。.2023-7-846A算法总结算法总结 1 初始状态，初始状态，open=（s）2 正常情况下（非成功非失败），取正常情况下（非成功非失败），取open中的第一个节点中的第一个节点n，将，将n由由open 转移到转移到closed。3 扩充节点扩充节点n，将新节点加入到，将新节点加入到open中中 4修改某
22、些节点的路径修改某些节点的路径 5 open中节点按照升序排列中节点按照升序排列 值得重视的一点：值得重视的一点：A算法失败的唯一原因算法失败的唯一原因是是open表为空表为空.2023-7-847 思考题：图中：思考题：图中：s是起始点是起始点 t是目标节点；是目标节点；如果存在从如果存在从s到到t的一条最佳路径。而的一条最佳路径。而n是最是最佳路径上的一点。佳路径上的一点。1）f*(s)f*(n)f*(t)的关系的关系 2）如果）如果f*(s)=10,g*(n)=4 问问h*(n)=?.2023-7-8483.3.5 A*算法（最佳图搜索算法）算法（最佳图搜索算法）A*算法定义：算法定义：
23、对于算法对于算法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)=不在位数字个数。不在位数字个数。.2023-7-849 算法可采纳性：算法可
24、采纳性：给定任意图，设存在从开始节点给定任意图，设存在从开始节点s到目标节点到目标节点t的路径。如果算法能够结束在的路径。如果算法能够结束在s到到t的最佳路径的最佳路径上，则称该算法是可采纳的。上，则称该算法是可采纳的。A*是具有可采是具有可采纳性。纳性。定理定理1 对于有限图，如果从对于有限图，如果从s到到t存在路径，则存在路径，则A算法算法一定成功结束。一定成功结束。.2023-7-850 推论推论1.1 因为因为A*算法是算法是A算法的一个特例。所以在算法的一个特例。所以在有限图上如果如果从有限图上如果如果从s到到t存在路径，则存在路径，则A*算法一定成功结束。算法一定成功结束。定理定理
25、2 对于无限图，如果存在对于无限图，如果存在s到到t路径，则路径，则A*算算法一定成功结束。法一定成功结束。.2023-7-851推论推论2.1 open表中任一满足表中任一满足f(n)f*(s)的节点的节点n最终最终都将被都将被A*选作扩展节点。选作扩展节点。定理定理3 如果存在节点如果存在节点s到目标节点到目标节点t路径，则路径，则A*算算法一定能找到最佳解结束。法一定能找到最佳解结束。推论推论3.1 A*选来扩展的节点都有选来扩展的节点都有f(n)f*(s).2023-7-852 小结小结 1如果存在节点如果存在节点s到目标节点到目标节点t路径，则路径，则A*算算法一定能找到最佳解结束。
26、法一定能找到最佳解结束。2 open表中所有满足表中所有满足f(n)f*(s)的节点的节点n最最终都将被终都将被A*选作扩展节点。选作扩展节点。3 A*选来扩展的节点都有选来扩展的节点都有f(n)f*(s)4 f*(s)作为作为A*的一个衡量上限。的一个衡量上限。.2023-7-8533.3.6h函数和函数和A*算法的关系算法的关系 本节重点来讨论本节重点来讨论h函数（即启发信息量）对函数（即启发信息量）对A*算法搜索效率的影响总结。算法搜索效率的影响总结。定义：给定两个定义：给定两个A*算法算法A1 和和A2，都有，都有 f(n1)=g(n1)+h(n1)f(n2)=g(n2)+h(n2)如
27、果对于所有非目标节点如果对于所有非目标节点n，有，有h(n1)h(n2)则算法则算法A2 比算法比算法A1有较多启发信息。有较多启发信息。讨论：启发信息与讨论：启发信息与h函数值成正比。极端情函数值成正比。极端情况下，完全没有启发信息时况下，完全没有启发信息时h=0，则此时，则此时A*算法就是宽度优先算法。算法就是宽度优先算法。.2023-7-854 定理：定理：给定两个给定两个A*算法算法A1 和和A2 如果如果A2的启发式的启发式信息比信息比A1多，则在任何存在节点多，则在任何存在节点s到目标节到目标节点点t的路径上，搜索结束时，由的路径上，搜索结束时，由A2扩展的每扩展的每一个节点必定被
28、一个节点必定被A1扩展。扩展。(A1扩展的节点多扩展的节点多)注意搜索空间小，不代表能够找到最佳解。注意搜索空间小，不代表能够找到最佳解。.2023-7-855当当h=0时，除最下面一层节点外，所有节点都进入时，除最下面一层节点外，所有节点都进入closed表。求解路径如图红线所示。表。求解路径如图红线所示。当考虑到当考虑到h时，被扩充的节点只有时，被扩充的节点只有s、c、j，解路径，解路径相同相同.2023-7-8563.37 h函数单调性限制函数单调性限制 单调性限制的作用是：避免重复计算某些节单调性限制的作用是：避免重复计算某些节点的点的f值（主要对连通图而言）以便减少搜索值（主要对连通
29、图而言）以便减少搜索代价。代价。单调性定义：给定一个启发函数单调性定义：给定一个启发函数h，如果对，如果对于所有节点于所有节点ni和和nj(nj是是ni的子节点的子节点)，如果满，如果满足足 h(ni)-h(nj)c(ni,nj)h(t)=0,则称则称h满足单满足单调性限制。调性限制。上式可以写成h(ni)-h(nj)+c(ni,nj)可以理解为三角不等式。可以理解为三角不等式。.2023-7-857 定理定理5 如果好如果好h(n)满足单调性限制条件，则满足单调性限制条件，则A*算算法扩展了节点法扩展了节点n之后，就找到了到达节点之后，就找到了到达节点n的最佳路径，的最佳路径，即：如果即：如
30、果A*选中节点选中节点n，在单调性限制条，在单调性限制条件下，有件下，有g(n)=g*(n).2023-7-8583.38A*算法示例算法示例 迷宫问题迷宫问题 给定迷宫图如下，找出从入口到出口的最给定迷宫图如下，找出从入口到出口的最短路径。短路径。.2023-7-859 解解 1）综合数据库）综合数据库 定义定义 状态集：状态集：（x，y）1x，y4 其中（其中（x，y）表示任意节点的坐标）表示任意节点的坐标 所以问题表示为求解从（所以问题表示为求解从（1,1）到（）到（4,4）的）的最短路径。最短路径。2规则集（定义规则集（定义4条移动规则）条移动规则）右移右移R1：if（x，y）then
31、（x+1，y）左移左移R2：if（x，y）then（x-1，y）.2023-7-860 上移上移R3：if（x，y）then（x+1，y+1）下移下移R4：if（x，y）then（x+1，y-1）两种解法：宽度优先，设定两种解法：宽度优先，设定h(n).2023-7-861.2023-7-862 3）A*算法算法f函数定义函数定义f(n)=g(n)+h(n)设每一步的耗散值为设每一步的耗散值为1（单位耗散值）（单位耗散值）定义：定义：g(n=d(n)从初始节点从初始节点s到当前节点到当前节点n 的的搜索深度。搜索深度。h(n)=-xn +-yn 其中是（其中是（xg，yg）目标节点的坐标，）目
32、标节点的坐标，（xn，yn）是当前节点的坐标。）是当前节点的坐标。显然满足：显然满足：h(n)h*(n)4）Open表节点排序表节点排序 先按先按f值排序，如果值排序，如果f值相同，则深度优先，值相同，则深度优先，.2023-7-863.2023-7-864 关于关于f函数值的意义的讨论函数值的意义的讨论 为了调整为了调整g和和h在在h中的作用比例，中的作用比例，设设f=g+w*h1）令）令w=0 则则f=g，此时，此时，A*成为宽度优先算成为宽度优先算法。特点：可扩大搜索范围便于找到最佳法。特点：可扩大搜索范围便于找到最佳解，但是费用比较大。解，但是费用比较大。2）令）令w为一个大的整数，则
33、加大了为一个大的整数，则加大了h在在f函数函数中的作用力度。其意义在于：不考虑到目中的作用力度。其意义在于：不考虑到目前已经前已经 消耗的费用，只关心当前节点到目消耗的费用，只关心当前节点到目标节点剩余的搜索工作量。标节点剩余的搜索工作量。.2023-7-865本章算法汇总本章算法汇总 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*算法算法 。.2023-7-866本章例题汇总本章例题汇总 1.四皇后问题四皇后问题 回溯策略回溯策略 2 积木世界问题积木世界问题 宽度优先宽度优先 3 八数码问题八数码问题 A算法算法 4 八城市八城市s-t 分支界限算法。分支界限算法。5 迷宫问题迷宫问题 A*算法算法.2023-7-867本本章章结结束束！.我们正年轻，让努力变成常态，用逆袭创造传奇。变革 创新 共赢
