《搜索技术》PPT课件

《《搜索技术》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章搜索技术第一节引言一、搜索对于无成熟方法可用的问题求解，必须一步步地摸索求解，这种问题求解过程就是搜索。注：搜索技术是人工智能的核心技术之一。二、研究和选用搜索算法的原则1、有限搜索还是无限搜索？若搜索空间有限，则任何一种穷举算法均能完成任务。第三章搜索技术第一节引言二、研究和选用搜索算法的原则2、搜索空间是静态的还是动态生成的？在人工智能中，搜索的对象(常称状态)是在搜索过程中逐步生成的，需将搜索对象的生成和评估的代价计算在内。对于一般搜索，搜索空间基本是静态的，或表或数组或数据库。3、已知目标还是未知目标？4、只要目标还是也要路

2、径？路径是解题过程中应用的操作序列。第三章搜索技术第一节引言二、研究和选用搜索算法的原则5、状态空间搜索还是问题空间搜索？在解题过程中的每一时刻，所要解决的问题均处于一定的状态，搜索过程只是将一个状态变成另一个状态(如，一盘棋局变成另一盘棋局)，则称为状态空间搜索。若搜索的对象是问题，搜索的原则是把一个复杂的问题化为一组比较简单的子问题(如把一个复杂的下棋策略分为几个子策略)，则称为问题空间搜索。注：问题空间搜索常常比状态空间搜索有效，但算法要复杂些。第三章搜索技术第一节引言二、研究和选用搜索算法的原则6、有约束还是无约束？问题空间搜索时

3、，若子问题间互相无约束关系，则求接比较简单，否则，一般需要回溯，即，放弃已解决的子问题，走回头路，寻找新的解法。7、数据驱动还是目标驱动？数据驱动是向前搜索，目标驱动是向后搜索。8、单向搜索还是双向搜索？第三章搜索技术第一节引言二、研究和选用搜索算法的原则9、盲目搜索还是启发式搜索？按照预定的控制策略实行搜索，在搜索过程中获取的中间信息不用来改进控制策略，称为盲目搜索，反之，称为启发式搜索。注：关于“启发式”，可有两种看法：1)任何有助于找到问题的解，但不能保证找到解的方法均是启发式方法；2)有助于加速求解过程和找到较优解的方法是启发式方

4、法。第三章搜索技术第一节引言二、研究和选用搜索算法的原则10、有对手搜索还是无对手搜索？若有两个控制源均能改变同一状态空间，并且任何一方向目标前进时，另一方均试图将它从目标拉开，则称为有对手搜索，通常称为博弈搜索。注：博弈搜索算法可以看成是一种特殊的问题空间搜索。第三章搜索技术第一节引言三、一般搜索方法分类1、盲目搜索1)无变量的盲目搜索状态空间、问题空间的盲目搜索深度优先、广度优先、代价优先、混合向前、向后、双向2)有变量的盲目搜索通代2、启发式搜索第三章搜索技术第二节启发式搜索一、启发式搜索把要求解的问题的具体领域的知识加进搜索算法中

5、，控制搜索过程，以提高算法效率的搜索方法，称为启发式搜索。注：1)这里，搜索的对象(常称状态)往往是边搜索边生成，因此在考虑这种搜索的复杂性时，必须将搜索对象的生成和评估的代价计算在内。第三章搜索技术第二节启发式搜索一、启发式搜索注：2)根据启发性信息(特定领域的知识信息)，在生成搜索树时可考虑种种可能的选择：a)下一步展开哪个节点？b)是部分展开还是全部展开？c)使用哪个规则(算子)？d)怎样决定舍弃还是保留新生成的节点？e)怎样决定舍弃还是保留一棵子树？f)怎样决定停止或继续搜索？g)如何定义启发函数(估值函数)？h)如何决定搜索方向

6、？第三章搜索技术第二节启发式搜索二、有序搜索算法1、基本思想a)对于每个在搜索过程中遇到的新状态，计算一个估计值，根据估计值的大小，确定下一步将从哪一个状态开始继续前进。b)一般以估计值小者作为较优的状态，以此实现最佳优先搜索。c)计算状态估计值的函数是确定的，但每个状态的估计值的大小与初始状态到该路径有关。第三章搜索技术第二节启发式搜索二、有序搜索算法2、算法1)建立一个空的状态序列SS2)建立一个空的状态库SB3)定义一个估值函数f4)若初始状态为S0,则定义初始状态S0(0,f(0))为当前新状态5)将当前新状态按估计值从小到大的顺

7、序插入到SS中，若新状态为目标状态，则将相应状态插入到具有相同估计值的状态的最前面；否则将相应状态插入到具有相同估计值的状态的最后面第三章搜索技术第二节启发式搜索二、有序搜索算法2、算法6)若在SS或SB中原有一个状态与当前新状态共一个状态，则删去原有状态7)若新状态在SS的最前面，则转11)8)若某种状态极限已达到，则搜索失败，算法运行结束，无解第三章搜索技术第二节启发式搜索二、有序搜索算法2、算法9)若任何规则均不能应用于状态序列SS中的第一个状态，或者虽能应用，但不能产生合适的新状态(在SS或SB中均没有者，称为新)，或虽能产生合适

8、的新状态S(path2,f(path2)),但不是改进型的(若SS和SB中已有状态S(path1,f(path1)),它与新状态共一个状态S，且f(path2)f(path1),则称新状态不