人工智能 一般搜索原理课件.ppt
《人工智能 一般搜索原理课件.ppt》由会员分享,可在线阅读,更多相关《人工智能 一般搜索原理课件.ppt(94页珍藏版)》请在三一办公上搜索。
1、1,2022/12/11,搜索技术,问题提出:有了知识表示方法之后,就需要有解决问题的方法,也就是搜索技术。所谓搜索,就是寻找一条从初始问题到问题解的路径本章内容:搜索技术有许多种,本章介绍一些早期的、比较简单的搜索原理:1,盲目搜索;2,启发式搜索;3,消解原理;4,通用问题求解技术关键问题:如何利用知识,尽可能有效地找到问题的解(最佳解)。,第三章 一般搜索原理,2,2022/12/11,一般搜索原理,搜索策略可分为三大类不可撤回方式、回朔方式、图搜索方式不可撤回方式:每一次搜索时,利用局部知识根据最优评价,选出下一状态,选定后不能撤回,只能继续回朔方式:在搜索过程中,有时会发现所选的路径
2、不适合找到目标,这时允许退回去另选一条路径。图搜索方式:如果把问题求解过程用图来表示。节点代表问题的状态,弧代表状态变化的方向,则搜索就变成对图进行从初始节点开始,到目标节点路径的搜索。,第三章 一般搜索原理 3.1盲目搜索,3,2022/12/11,回溯搜索策略,例:皇后问题,第三章 一般搜索原理 3.1盲目搜索,4,2022/12/11,( ),皇后问题搜索过程(一),第三章 一般搜索原理 3.1盲目搜索,5,2022/12/11,Q,皇后问题搜索过程(二),第三章 一般搜索原理 3.1盲目搜索,6,2022/12/11,皇后问题搜索过程(三),第三章 一般搜索原理 3.1盲目搜索,7,2
3、022/12/11,Q,皇后问题搜索过程(四),第三章 一般搜索原理 3.1盲目搜索,8,2022/12/11,皇后问题搜索过程(五),第三章 一般搜索原理 3.1盲目搜索,9,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程(六),10,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程(七),11,2022/12/11,Q,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程(八),12,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程(九),13,2022/12/11,Q,第三章 一般搜索原理 3.1盲目
4、搜索,皇后问题搜索过程(十),14,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程(十一),15,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程(十二),16,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程(十三),17,2022/12/11,递归的思想,第三章 一般搜索原理 3.1盲目搜索,18,2022/12/11,一个递归的例子,int ListLenght(LIST *pList)if (pList = NULL) return 0;else return ListLength(pList-nex
5、t)+1;,第三章 一般搜索原理 3.1盲目搜索,19,2022/12/11,回溯搜索算法说明,BACKTRACK(DATA)DATA:当前状态。返回值:从当前状态到目标状态的路径(以规则表的形式表示)或FAIL。,第三章 一般搜索原理 3.1盲目搜索,20,2022/12/11,回溯搜索算法(一),递归过程BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);,第三章 一般搜索原理 3.1盲目搜索,TERM: 找目标DEADEND: 状态不合法,无
6、法继续搜索APPRULES: 取可应用规则集,21,2022/12/11,回溯搜索算法(二),4, LOOP: IF NULL(RULES) RETURN FAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R, DATA);8, PATH:=BACKTRACK(RDATA);9, IF PATH=FAIL GO LOOP;10, RETURN CONS(R, PATH);,第三章 一般搜索原理 3.1盲目搜索,TAIL: 删除头条规则GEN: 调用规则作用于当前状态CONS: 获取解路径规则表,22,2022/12/11,存
7、在问题及解决办法,问题:深度问题:如果深度太深死循环问题: 如果状态出现重复解决办法:对搜索深度加以限制记录从初始状态到当前状态的路径,第三章 一般搜索原理 3.1盲目搜索,23,2022/12/11,增加约束后的回溯搜索算法,BACKTRACK1(DATALIST)DATALIST:从初始到当前的状态表(逆向)返回值:从当前状态到目标状态的路径(以规则表的形式表示)或FAIL。,第三章 一般搜索原理 3.1盲目搜索,24,2022/12/11,增加约束后的回溯搜索算法(一),1, DATA:=FIRST(DATALIST)2, IF MENBER(DATA, TAIL(DATALIST) R
8、ETURN FAIL;3, IF TERM(DATA) RETURN NIL;4, IF DEADEND(DATA) RETURN FAIL;5, IF LENGTH(DATALIST)BOUND RETURN FAIL;,第三章 一般搜索原理 3.1盲目搜索,25,2022/12/11,增加约束后的回溯搜索算法(二),6, RULES:=APPRULES(DATA);7, LOOP: IF NULL(RULES) RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);,第三章 一般搜索原理 3.1盲目搜索,26,2022/12/11,增加约束后
9、的回溯搜索算法(三),10,RDATA:=GEN(R, DATA);11,RDATALIST:=CONS(RDATA, DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);,第三章 一般搜索原理 3.1盲目搜索,27,2022/12/11,一些深入的问题,失败原因分析、多步回溯,第三章 一般搜索原理 3.1盲目搜索,28,2022/12/11,一些深入问题(续),回溯搜索中知识的利用基本思想:尽可能选取划去对角线上位置数最少的。,第三章 一般搜索原理 3.1盲目搜索,29,
10、2022/12/11,模式导向搜索,这个算法是将递归搜索应用到谓词演算的通用搜索算法要判断一个谓词表达式是某个断言集合的逻辑结论首先谓词表达式作为目标,使用合一来选择能与其后件匹配的蕴涵式并把得到的置换运用于该蕴涵式的前件这个前件成了新的目标称其为子目标应用递归搜索解这个子目标如果与事实相匹配,则搜索结实,第三章 一般搜索原理 3.1盲目搜索,30,2022/12/11,模式导向搜索算法描述一,Function pattern_search(current_goal)begin if current_goal is in closed then return FAIL else put cur
11、rent_goal into closed while every rule and facts do begin case current_goal 与事实合一return SUCCESS,第三章 一般搜索原理 3.1盲目搜索,31,2022/12/11,模式导向搜索算法描述二,current_goal 是合取式 beginfor every合取项item do ret = pattern_search(item) if ret = FAIL then return FAIL end current_goal 与规则的后件合一 begin 对前件q应用对应的合一置换 ret = patter
12、n_search(q) if ret = FAIL then return FAIL else SUCCESS end end return FAIL end,第三章 一般搜索原理 3.1盲目搜索,32,2022/12/11,图搜索策略,图搜索策略就是在图中寻找从起始点到目标点的路径的方法图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0,然后逐步扩展节点,直到将目标点扩展到搜索图里为止。扩展的过程就是搜索的过程扩展节点的方法不同,就意味着搜索的方法不同,也就是搜索的路径不同。,第三章 一般搜索原理 3.1盲目搜索,33,2022/12/11,图搜索策略图示,S0,Sg,第三章
13、一般搜索原理 3.1盲目搜索,34,2022/12/11,节点扩展,扩展一个节点生成出该节点的所有后继节点,并给出它们之间的代价值。这一过程称为“扩展一个节点”。,第三章 一般搜索原理 3.1盲目搜索,35,2022/12/11,路径,路径设一节点序列为(n0, n1,nk),对于i = 1k,若节点ni-1具有一个后继节点ni,则该序列称为从n0到nk的路径。路径的代价值一条路径的代价值等于连接这条路径各节点间所有代价值的总和。用C(ni, nj)表示从ni到nj的路径的代价值。,第三章 一般搜索原理 3.1盲目搜索,36,2022/12/11,节点深度,节点深度:根节点深度=0其它节点深度
14、=父节点深度+1,0,1,2,3,第三章 一般搜索原理 3.1盲目搜索,37,2022/12/11,图搜索的一般过程,第三章 一般搜索原理 3.1盲目搜索,38,2022/12/11,图搜索过程说明,我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构OPEN表中的节点都是搜索树的端节点,即至今尚未被选作为扩展的节点CLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点,或者是搜索树的非端节点重排OPEN表,实际上就是在选择搜索顺序,也就是扩展的节点的顺序。,第三章 一般搜索原理 3.1盲目搜索,39,2022/12/11,节点类型说明,.,mj,第三章 一般搜索原理 3.
15、1盲目搜索,扩展的节点OPEN表没有的部分,扩展的节点在已在close表中的部分,扩展的节点已在OPEN表中的部分,选定的扩展节点,40,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示(一),现要扩展它,41,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示(二),修改父子关系,现要扩展它,42,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示(三),修改父子关系,修改父子关系,43,2022/12/11,盲目搜索概述,盲目搜索也叫无信息搜索盲目搜索实际上是对解空间的遍历盲目搜索包括有:宽度优先搜索:搜索以接
16、近起始节点的程度依次扩展节点,在对下一层搜索前,必须搜索完本层的所有节点。深度优先搜索:搜索首先扩展最新产生的节点。等代价搜索:搜索沿最小代价节点进行扩展。,第三章 一般搜索原理 3.1盲目搜索,44,2022/12/11,宽度优先搜索,第三章 一般搜索原理 3.1盲目搜索,45,2022/12/11,目标,2 31 8 47 6 5,1,2,5,6,7,3,8,4,第三章 一般搜索原理 3.1盲目搜索,八数码难题的宽度优先搜索树,按上下左右序走步,46,2022/12/11,宽度优先搜索的性质,当问题有解时,一定能找到解当问题为单位代价值,且问题有解时,一定能找到最优解方法与问题无关,具有通
17、用性效率较低属于图搜索方法,第三章 一般搜索原理 3.1盲目搜索,47,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,深度优先搜索,48,2022/12/11,2 31 8 47 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,。,第三章 一般搜索原理 3.1盲目搜索,八数码难题的深度优先搜索树,49,2022/12/11,深度优先搜索的性质,一般不能保证找到最优解当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制最坏情况时,搜索空间等同于穷举是一个通用的与问题无关的方法,第三章 一般搜索原理 3.1盲目搜索,50,2022/12/11,第三章 一般搜
18、索原理 3.1盲目搜索,等代价搜索,51,2022/12/11,什么是启发式搜索,盲目搜索的效率低,耗费过多的计算时间和空间,容易产生组合爆炸。利用知识来引导搜索,达到减少搜索范围,降低问题复杂度的目的。对搜索产生帮助的信息称为启发信息,第三章 一般搜索原理 3.2启发式搜索,52,2022/12/11,启发式信息对搜索方法的影响,启发信息的多少用启发信息强度来表示不同的启发信息对搜索方法带来不同的影响:强:降低搜索工作量,但可能导致找不到最优解弱:一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解,第三章 一般搜索原理 3.2启发式搜索,53,2022/12/11,启发式搜索类
19、型,启发信息按用途可分为3类:用于决定要扩展的下一个节点(这个节点称为最有希望的节点),以免像在宽度优先或深度优先搜索中那样盲目地扩展在扩展一个节点的过程中,用于决定要生成哪些其后继节点,以免盲目地生成所有节点。用于决定哪些节点应从搜索树中抛弃或修剪。用来估算节点希望程度的方法为估价函数,第三章 一般搜索原理 3.2启发式搜索,54,2022/12/11,对启发式搜索的认识,有些启发信息能够大大减少搜索工作量,但不能保证能够得到最小代价路径我们往往希望获得路径代价和求该路径所需的搜索代价的综合为最小由于计算综合代价很困难,因此,比较两种方法的优劣,依赖使用的经验使用估价函数实际是对OPEN表进
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 一般搜索原理课件 一般 搜索 原理 课件
链接地址:https://www.31ppt.com/p-1621989.html