人工智能3第三章一般搜索原理ppt课件.ppt

《人工智能3第三章一般搜索原理ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章一般搜索原理第三章一般搜索原理2021/7/291搜索技术搜索是人工智能中进行问题求解的一大类方法根据是否使用启发式信息可分为：1，盲目搜索；2，启发式搜索；根据问题的表示方式分为：1，状态空间搜索；2，与／或树搜索。例如：用状态空间法来求解问题时，采用的是状态空间搜索；用问题归约方法来求解问题时，采用的是与／或树搜索。第三章一般搜索原理3.1概述2021/7/292搜索的特点和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。所以，人工智能中的搜索可以分成两个阶段：状态空间的生成阶段和在该状态空间中对所求解问题状态的搜索。由于一个问题的整个空间可能会非常的

2、大，在搜索之前生成整个空间会占用太大的存储空间。为此，状态空间一般是逐渐扩展的“目标”状态是在每次扩展的时候进行搜索的。第三章一般搜索原理3.1概述2021/7/2933.2盲目搜索第三章一般搜索原理3.2盲目搜索2021/7/294盲目搜索盲目搜索是按预定的控制策赂进行搜索，没有任何关于问题本身的信息，在搜索过程中获得的中间信息并不改变控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，因此这种搜索具有盲目性，效率不高，不便于复杂问题的求解。第三章一般搜索原理3.2盲目搜索2021/7/295盲目搜索分类搜索策略可分为三大类不可撤回方式、回朔方式、图搜索方式不可撤回方式：每

3、一次搜索时，利用局部知识根据最优评价，选出下一状态，选定后不能撤回，只能继续回朔方式：在搜索过程中，有时会发现所选的路径不适合找到目标，这时允许退回去另选一条路径。图搜索方式：将所有应用过的操作和它们产生的状态描述都以图的形式记录下来。由于当前可继续往下搜索的状态不只一个，因此可以从其中任一个状态往下搜索。图搜索方式与回溯方式的不同之处在于，回溯方式不记亿那些试探失败的操作和它们产生的状态描述，只记忆当前正在搜索的路径。图搜索方式则保存所有试探过的路径，因而可以在任何一条路径上继续搜索第三章一般搜索原理3.2盲目搜索2021/7/296图搜索方式与回溯方式的不同回溯方式不记忆那些试探失败的操作

4、和它们产生的状态描述，只记忆当前正在搜索的路径。图搜索方式则保存所有试探过的路径，因而可以在任何一条路径上继续搜索第三章一般搜索原理3.2盲目搜索2021/7/297不可撤回搜索策略不可撤回方式的控制策略是，选择一条可应用的操作作用于当前状态，不论后果如何都接着做下去。这个方法类似于高等数学中求函数极值的爬山法。在爬山法中，我们从任一点出发，在该点的最大梯度方向前进一步，得到一个新的点，再在新点的最大梯度方向上前进一步，一直到梯度为0为止，这个点就是函数的极大值点。如果函数只有一个极大值点．则这个点就是该函数的最大值点。第三章一般搜索原理3.2盲目搜索2021/7/298不可撤回搜索的实现不可

5、撤回搜索的实现是将状态描述定义成一个实数值的爬山函数。控制策略就利用这个爬山函数来选择一个可应用的操作，施行该操作的结果应使爬山函数的值得到最大限度的增加。第三章一般搜索原理3.2盲目搜索2021/7/299不可撤回搜索举例(一)选择八数码问题我们选取“不在位”的数字个数的负值作为爬山函数八数码游戏的操作可描述为下面的4条产生式规则(1)if空格不在最上一行then空格上移(2)if空格不在最下一行then生格下移(3)if空格不在最左一列then空格左移(4)if空格不在最右一列then空格有移2831647512384765目标状态初始状态第三章一般搜索原理3.2盲目搜索2021/7/29

6、10不可撤回搜索举例(二)从初始状态出发，应用第一条规则，空格上移可获得爬山函数的最大增加、因此控制策略选择第一条规则作为当前的操作。在没有操作能够增加爬山函数的值时．可任选一个不减小函数值的操作，如果不存在这样的操作，则过程停止。2831647523184765283147651238476523184765-3-3-4-2-1012384765目标状态爬山函数值第三章一般搜索原理3.2盲目搜索2021/7/2911不可撤回搜索举例(三)对于上例，采用不可撤回策略可以很快得到问题的解。但一般来讲，如果爬山函数有多个局部极大值存在，该策略可能会引导到局部极大值点，而达不到目标状态。例如当八数码

7、问题的初始状态和目标状态分别如下时，任意一个可应用的操作都会降低爬山函数的值，因此，得不到目标：1237486512574863目标初始状态第三章一般搜索原理3.2盲目搜索2021/7/2912回溯搜索策略回溯策略是一种试探性方式。在选择一个操作时要建立一个回溯点。在搜索过程中，如果遇到了困难，则要返回到最近的一个回溯点，换一个操作继续进行搜索。第三章一般搜索原理3.2盲目搜索2021/7/291