第5章 搜索技术课件.ppt
《第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个位置上摆放空
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第5章 搜索技术课件 搜索 技术 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-2137931.html