《第5章 搜索技术课件.ppt》由会员分享，可在线阅读，更多相关《第5章 搜索技术课件.ppt（55页珍藏版）》请在三一办公上搜索。
1、第五章 搜索技术,1、明晰问题如何表示,2、选择相对合适的求解方法,搜索中需要解决的基本问题：,01,02,03,04,找到的解是否是最佳解,是否会终止运行/陷入一个死循环,是否一定能找到一个解,时间与空间复杂性如何,搜索过程：,6,(1)数据驱动：从初始状态（问题给出的条件）出发的正向搜索,(2)目的驱动：从目的状态出发的逆向搜索,从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。,(3)双向搜索,搜索策略（按方向）,搜索策略（按信息运用度）,（1）盲目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。
2、,（2）启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。,8,状态：表示系统状态、事实等叙述型知识的一组变量或数组：,操作：表示引起状态变化的过程型知识的一组关系或函数：,T,图搜索策略,状态空间：利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组：,状态集合,操作算子的集合,若干具体状态或满足某些性质的路径信息描述,包含问题的初始状态是 的非空子集,9,求解路径：从 结点到 结点的路径。,：状态空间的一个解,状态空间的一个解：一个有限的操作算子序列。,图搜索策略,10
3、,例5.1 八数码问题的状态空间。,状态集：所有摆法,操作算子：,将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right,图搜索策略,11,八数码状态空间图,图搜索策略,12,状态空间的有向图描述,图搜索策略,13,例5.2 旅行商问题（traveling salesman problem,TSP）或邮递员路径问题。,可能路径：费用为375的路径（A，B，C，D，E，A）,图搜索策略,14,图搜索策略,16,U 1.回溯策略U 2.宽度优先搜索策略U 3.深度优先搜索策略,盲目搜索,17,带回溯策略的搜索：从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或“不可
4、解结点”，即“死胡同”为止。若它遇到不可解结点就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。,盲目搜索（回溯策略）,18,回溯搜索示意图,盲目搜索（回溯策略）,19,回溯搜索的算法(1)PS（path states）表：保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。(2)NPS（new path states）表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展。(3)NSS（no solvable states）表：不可解状态集，列出了找不
5、到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。,盲目搜索（回溯策略）,20,图搜索算法的回溯思想：,（1）用未处理状态表（NPS）使算法能返回（回溯）到其 中任一状态。（2）用一张“死胡同”状态表（NSS）来避免算法重新搜索 无解的路径。（3）在PS 表中记录当前搜索路径的状态，当满足目的时可 以将它作为结果返回。（4）为避免陷入死循环必须对新生成的子状态进行检查，看它是否在该三张表中。,盲目搜索（回溯策略）,21,Fopen表（NPS表）：已经生成出来但其子状态未被搜索的状态。Fclosed表（PS表和NSS表的合并）：记录了已被生成扩展过的状
6、态。,宽度优先搜索法中状态的搜索次序,盲目搜索（宽度优先策略）,22,例5.3 通过搬动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起。,盲目搜索（宽度优先策略）,23,操作算子为MOVE（X，Y）：把积木X搬到Y（积木或桌面）上面。,MOVE（A，Table）：“搬动积木A到桌面上”。,操作算子可运用的先决条件：（1）被搬动积木的顶部必须为空。（2）如果 Y 是积木，则积木 Y 的顶部也必须为空。（3）同一状态下，运用操作算子的次数不得多于一次。,盲目搜索（宽度优先策略）,24,盲目搜索（宽度优先策略）,25,盲目搜索（深度优先策略）,26,Q 在深度优先搜索中，当搜索到某一个
7、状态时，它所有的子状态以及子状态的后裔状态都必须先于该状态的兄弟状态被搜索。Q 为了保证找到解，应选择合适的深度限制值，或采取不断加大深度限制值的办法，反复搜索，直到找到解。,盲目搜索（深度优先策略）,Q 深度优先搜索并不能保证第一次搜索到的某个状态时的路径是到这个状态的最短路径。Q 对任何状态而言，以后的搜索有可能找到另一条通向它的路径。如果路径的长度对解题很关键的话，当算法多次搜索到同一个状态时，它应该保留最短路径。,27,例5.4 卒子穿阵问题，要求一卒子从顶部通过下图所示的阵列到达底部。卒子行进中不可进入到代表敌兵驻守的区域（标注1），并不准后退。假定深度限制值为5。,阵列图,盲目搜索
8、（深度优先策略）,28,S0,S1(1,1),S2(1,2),S3(2,2),S4(2,1),S5(3,1),S6(3,2),S7(2,3),S8(2,1),S9(3,1),S10(1,3),S18(1,4),S11(1,2),S14(1,4),S12(2,2),S15(2,4),S13(2,3),S16(3,4),S17(4,4),open表：S17、S18closed表：S0S16,卒子穿阵的深度优先搜索树,30,N“启发”（heuristic）：关于发现和发明操作算子及搜索方法的研究。,三、启发式搜索,启发式策略：利用与问题有关的启发信息进行搜索。,O 启发式:在状态空间搜索中，启发式被
9、定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径。,31,（1）一个问题由于在问题陈述和数据获取方面固有的模糊性，导致它没有一个确定的解。,三、启发式搜索,（2）虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。,适用范围：,局限性：,启发（猜想）根据经验和直觉判断，可能得到的是次优解，也可能一无所获。,32,例5.5 一字棋。在九宫棋盘上，从空棋盘开始，双方轮流在棋盘上摆各自的棋子或（每次一枚），谁先取得三子一线（一行、一列或一条对角线）的结果就取胜。,和 在棋盘中不同位置对应的棋局就是问题空间中的不同状态。9个位置上摆放空
10、，有 39 种棋局。可能的走法：。,三、启发式搜索,33,三、启发式搜索,O赢的概率：8-5=3,O赢的概率：8-6=2,O赢的概率：8-4=4,一字棋：9！，西洋跳棋：1078，国际象棋：10120，围棋：10761。假设每步可以搜索一个棋局，用极限并行速度（10-104年/步）来处理，搜索一遍国际象棋的全部棋局也得1016年即1亿亿年才可以算完！,34,启发式搜索下缩减的状态空间,三、启发式搜索,最佳走步,35,36,评估函数：估计待搜索结点的“有希望”程度，并依次给它们排定次序（在open表中）。,：从初始结点经过 结点到达目的结点的路径的最小代 价估计值,一般地，在 中，的比重越大，越
11、倾向于宽度优先搜索方式，而 的比重越大，表示启发性能越强。,三、启发式搜索,：从初始结点到 结点的实际代价估计值,：从 结点到目的结点的最佳路径估计代价值,37,open表：保留所有已生成而未扩展的状态。closed表：记录已扩展过的状态。进入open表的状态是根据其估值的大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态加以扩展。,三、启发式搜索,设计评估函数的目标：利用有限的信息作出一个较精确的评估函数,启发式图搜索法的基本特点：寻找并设计一个与问题有关的 及构出，然后以 的大小来排列待扩展状态的次序，每次选择 值最小者进行扩展。,A算法（基于评估函数的加权启发式图搜索算
12、法）,实现步骤,2、若open表为空，则搜索失败，退出,3、移出open表中第一个节点N放入closed表中，并顺序编号n,4、若目标结点把附有 的初始,则搜索成功，结束,5、若N不可扩展，则转步骤2,6、扩展N，生成一组附有 的子结点，对这组子结点进行处理：考察是否有已在open或closed表中存在的结点。若有则再考察其中有无N的先辈结点，有则删除，同时考虑是否修改表中结点及其后裔指针和 的值为其余子结点配上指向N的返回指针后放入open表中，并排序，转步骤2,1、把附有 放入open表,39,A算法描述,procedure heuristic_searchopen：=start；clos
13、ed：=；f(s)：=g(s)+h(s)；*初始化while open dobegin从open表中删除第一个状态，称之为n；if n=目的状态then return(success)；生成n的所有子状态；if n没有任何子状态then continue；for n的每个子状态docase子状态is not already on open表or closed表；begin计算该子状态的估价函数值；将该子状态加到open表中；end；,40,5.4.3 A搜索算法,case子状态is already on open表：if该子状态是沿着一条比在open表已有的更短路径而到达then 记录更短路径
14、走向及其估价函数值；case子状态is already on closed表：if该子状态是沿着一条比在closed表已有的更短路径而到达thenbegin将该子状态从closed表移到open表中；记录更短路径走向及其估价函数值；end；case end；将n放入closed表中；根据估价函数值，从小到大重新排列open表；end；*open表中结点已耗尽return(failure)；end.,41,每次重复时，A搜索算法从open表中取出第一个状态，如果该状态满足目的条件，则算法返回到该状态的搜索路径。如果open表的第一个状态不是目的状态，则算法利用与之相匹配的一系列操作算子进行相应的
15、操作来产生它的子状态。如果某个子状态已在open表（或closed表）中出现过，即该状态再一次被发现时，则通过刷新它的祖先状态的历史记录，使算法极有可能找到到达目的状态的更短的路径接着，A搜索算法open表中每个状态的估价函数值，按照值的大小重新排序，将值最小的状态放在表头，使其第一个被扩展。,三、启发式搜索,42,三、启发式搜索,43,例5.7 利用A搜索算法求解八数码问题的搜索树，其评估函数定义为：状态的深度，每步为单位代价。：以“不在位”的数码数作为启发信息的度量。,三、启发式搜索-A算法,44,45,open表和closed表内状态排列的变化情况,三、启发式搜索,46,如果某一问题有解
16、，那么利用A*搜索算法对该问题进行搜索则一定能搜索到解，并且一定能搜索到最优的解而结束。,三、启发式搜索-A*算法,定义：h*(n)为状态n到目的状态的最优路径的代价，则当A算法的启发函数h(n)小于等于h*(n)，即满足h(n)h*(n)，对所有结点n,47,1.可采纳性 当一个搜索算法在最短路径存在时能保证在有限步内找到它，就称它是可采纳的。,A*搜索算法的特性,所有的A*算法都是可采纳的。,最优评估函数：,f*(n)：起点出发通过n状态而到达目的状态的最佳路径的总代价值g*(n)：起点到n状态的最短路径代价值h*(n)：n状态到目的状态的最短路径的代价值,48,2.单调性 在整个搜索空间
17、都是局部可采纳的。一个状态和任一个子状态之间的差由该状态与其子状态之间的实际代价所限定。,A*搜索算法的特性,如果某一启发函数满足：对所有状态ni和nj，其中nj是ni的后裔，满足，其中cost(ni,nj)是从ni到nj的实际代价。目的状态的启发函数值为0或则称该启发函数h(n)是单调的。,49,3.信息性 在两个A*启发策略的 中，如果对搜索空间中的任一状态n都有，就称策略 具有更多的信息性。,A*搜索算法的特性,信息性越多，所搜索的状态数就越少，但所需要的计算时间越多。,1914,世上第一个计算机游戏,1952,世界上第一个跳棋程序,1979,西洋双陆棋程序,1997,“深蓝”PK卡斯帕
18、罗夫,2006,浪潮天梭PK许银川,2011,Watson上场危险边缘,四、博弈搜索,2016,AlhoGoPK李世石,2017,Master、Zero,-剪枝算法,蒙特卡洛树搜索+信心上限决策,深度学习+增强学习,+,=,1.蒙特卡洛树搜索过程选择：以当前棋局为根节点，自上而下地选择一个落子点；扩展：向选定的节点添加一个或多个子节点；模拟：对扩展出的节点用蒙特卡罗方法进行模拟；回传：根据模拟结果依次向上更新祖先节点的估计值。,存在不足：1、选择范围是全体可下子点；2、每次模拟必须一下到底，完成整局模拟直到知道分出胜负为止。,信心上限决策1、优先选择到目前为止胜率最大的节点；2、优先选择到目前为止模you拟次数较少的节点,：节点j目前的收益（比如获胜概率）；n：是目前为止的总的模拟次数；：是节点j目前的模拟次数；c：是加权系数,经常不断地学习,你就什么都知道。你知道得越多,你就越有力量Study Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be,写在最后,感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings,结束语,讲师：XXXXXX XX年XX月XX日,
