第5章搜索求解策略介绍ppt课件.ppt
《第5章搜索求解策略介绍ppt课件.ppt》由会员分享,可在线阅读,更多相关《第5章搜索求解策略介绍ppt课件.ppt(74页珍藏版)》请在三一办公上搜索。
1、第 5 章 搜索求解策略,教材: 王万良人工智能及其应用(第2版) 高等教育出版社,2008. 6,2,第5章 搜索求解策略,5.1 搜索的概念5.2 状态空间的搜索策略5.3 盲目的图搜索策略5.4 启发式图搜索策略5.5 与/或图搜索策略,3,第5章 搜索求解策略,5.1 搜索的概念5.2 状态空间知识表示方法5.3 盲目的图搜索策略5.4 启发式图搜索策略5.5 与/或图搜索策略,4,5.1 搜索的概念,问题求解:问题的表示。 选择一种相对合适的求解方法。问题求解的基本方法:搜索法、归约法、归结法、推理法及产生式等。,5,5.1 搜索的概念,5.1.1 搜索的基本问题与主要过程5.1.2
2、 搜索策略,6,5.1.1 搜索的基本问题与主要过程,搜索中需要解决的基本问题:(1)是否一定能找到一个解。(2)是否终止运行或是否会陷入一个死循环。(3)找到的解是否是最佳解。(4)时间与空间复杂性如何。,7,5.1.1 搜索的基本问题与主要过程,搜索的主要过程:(1) 从初始或目的状态出发,并将它作为当前状态。(2) 扫描操作算子集,将适用当前状态的一些操作算子作用于当前状态而得到新的状态,并建立指向其父结点的指针 。(3) 检查所生成的新状态是否满足结束状态,如果满足,则得到问题的一个解,并可沿着有关指针从结束状态反向到达开始状态,给出一解答路径;否则,将新状态作为当前状态,返回第(2)
3、步再进行搜索。,8,5.1.2 搜索策略,1. 搜索方向: (1) 数据驱动:从初始状态出发的正向搜索。,正向搜索从问题给出的条件(一个用于状态转换的操作算子集合)出发。,逆向搜索:先从想达到的目的入手,看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。,(2) 目的驱动:从目的状态出发的逆向搜索。,9,5.1.2 搜索策略,1. 搜索方向: (3) 双向搜索,双向搜索:从开始状态出发作正向搜索,同时又从目的状态出发作逆向搜索,直到两条路径在中间的某处汇合为止。,10,5.1.2 搜索策略,2. 盲目搜索与启发式搜索:(1)盲目搜索:在不具有对特定问题的任何有关信息的条件下
4、,按固定的步骤(依次或随机调用操作算子)进行的搜索。 (2)启发式搜索:考虑特定问题领域可应用的知识,动态地确定调用操作算子的步骤,优先选择较适合的操作算子,尽量减少不必要的搜索,以求尽快地到达结束状态。,11,第5章 搜索求解策略,5.1 搜索的概念5.2 状态空间知识表示方法5.3 盲目的图搜索策略5.4 启发式图搜索策略5.5 与/或图搜索策略,12,5.2 状态空间知识表示方法,5.2.1 状态空间表示法5.2.2 状态空间的图描述,13,5.2.1 状态空间表示法,状态:表示系统状态、事实等叙述型知识的一组变量或数组:,操作:表示引起状态变化的过程型知识的一组关 系或函数:,T,14
5、,5.2.1 状态空间表示法,状态空间:利用状态变量和操作符号,表示系统或问题的有关知识的符号体系,状态空间是一个四元组:,:状态集合。 :操作算子的集合。 :包含问题的初始状态是 的非空子集。 :若干具体状态或满足某些性质的路径信息描述。,15,5.2.1 状态空间表示法,求解路径:从 结点到 结点的路径。,:状态空间的一个解。,状态空间的一个解:一个有限的操作算子序列。,16,例1 八数码问题的状态空间。,5.2.1 状态空间表示法,状态集 :所有摆法,操作算子:,将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right,17,5.2.2 状态空间的图描述,状态空间的
6、有向图描述,18,5.2.2 状态空间的图描述,八数码状态空间图,19,例2 旅行商问题(traveling salesman problem, TSP)或邮递员路径问题。,5.2.2 状态空间的图描述,可能路径:费用为375的路径(A,B,C,D,E,A),20,5.2.2 状态空间的图描述,21,第5章 搜索求解策略,5.1 搜索的概念5.2 状态空间知识表示方法5.3 盲目的图搜索策略5.4 启发式图搜索策略5.5 与/或图搜索策略,22,5.3 盲目的图搜索策略,5.3.1 回溯策略5.3.2 宽度优先搜索策略5.3.3 深度优先搜索策略,23,5.3.1 回溯策略,带回溯策略的搜索:
7、 从初始状态出发,不停地、试探性地寻找路径,直到它到达目的或“不可解结点”,即“死胡同”为止。若它遇到不可解结点就回溯到路径中最近的父结点上,查看该结点是否还有其他的子结点未被扩展。若有,则沿这些子结点继续搜索;如果找到目标,就成功退出搜索,返回解题路径。,24,递归过程:,5.3.1 回溯策略,Step Track (DataList):Data:= First(DataList);if Member(Data, Tail(DataList) then return FAIL; *回老路退回if Goal(Data) then return NIL; *达到目的地成功返回if DeadEnd
8、(Data) then return FAIL; *达到不合理状态,退出if Length(DataList) Bound then return FAIL; *已到深度限制,退回Rules:= AppRules(Data); *得出可应用的规则集Loop:if Null(Rules) then return FAIL; *进入死胡同,退回R:= First(Rules); *取出第一条可用规则Rules:= Tail(Rules); Newdata:= Gen(R,Data); *运用规则,生成新状态NewDataList:= Cons(Newdata, DataList);Path:= B
9、ack Track(NewDataList); *递归If Path:= FAIL then go loop else return Cons(R, Path);,25,5.3.1 回溯策略,回溯搜索示意图,26,5.3.1 回溯策略,回溯搜索的算法(1) PS(path states)表:保存当前搜索路径上的状态。如果找到了目的,PS就是解路径上的状态有序集。 (2) NPS(new path states)表:新的路径状态表。它包含了等待搜索的状态,其后裔状态还未被搜索到,即未被生成扩展 。(3) NSS(no solvable states)表:不可解状态集,列出了找不到解题路径的状态。
10、如果在搜索中扩展出的状态是它的元素,则可立即将之排除,不必沿该状态继续搜索。,27,5.3.1 回溯策略,Function backtrack:begin PS:= Start; NPS:= Start; NSS:= ; CS:= Start; *初始化 while NPS do begin if CS=目的状态 then return(PS); *成功,返回解题路径 if CS没有子状态(不包括PS,NPS和NSS中已有的状态) then begin while((PS非空) and (CS=PS中的第一个元素))do begin 将CS加入NSS *标明此状态不可解 从PS中删除第一个元素
11、CS *回溯 从NPS中删除第一个元素CS; CS:= NPS中的第一个元素;,28,5.3.1 回溯策略,end; 将CS加入PS; endelse begin 将CS子状态(不包括PS、NPS和NSS中已有的)加入NPS; CS:= NPS中第一个元素; 将CS加入到PS; end end; return FAIL; end.,29,回溯搜索示意图的回溯轨迹: 初值:PS=A; NPS=A; NSS= ; CS=A。,5.3.1 回溯策略,30,5.3.1 回溯策略,图搜索算法(深度优先、宽度优先、最好优先搜索等)的回溯思想:,(1)用未处理状态表(NPS)使算法能返回(回溯)到其 中任一
12、状态。 (2)用一张“死胡同”状态表(NSS)来避免算法重新搜索 无解的路径。 (3)在PS 表中记录当前搜索路径的状态,当满足目的时可 以将它作为结果返回。 (4)为避免陷入死循环必须对新生成的子状态进行检查, 看它是否在该三张表中 。,31,5.3.2 宽度优先搜索策略,open表(NPS表):已经生成出来但其子状态未被搜索的状态。closed表( PS表和NSS表的合并):记录了已被生成扩展过的状态。,宽度优先搜索法中状态的搜索次序,32,5.3.2 宽度优先搜索策略,Procedure breadth_first_searchbeginopen:= start; closed:= *初
13、始化while open do begin 从open表中删除第一个状态,称之为n; 将n放入closed表中; if n = 目的状态 then return (success); 生成n的所有子状态; 从n的子状态中删除已在open或closed表中出现的状态; 将n的其余子状态,按生成的次序加入到open表的后段。 end; end;,open表:队列结构,即先进先出(FIFO)的数据结构,33,例3 通过搬动积木块,希望从初始状态达到一个目的状态,即三块积木堆叠在一起。,5.3.2 宽度优先搜索策略,34,操作算子为MOVE(X,Y):把积木X搬到Y(积木或桌面)上面。,5.3.2 宽



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 搜索 求解 策略 介绍 ppt 课件

链接地址:https://www.31ppt.com/p-1430418.html