华中科技大学人工智能及其应用第三章一般搜索原理1

第三章 一般搜索原理

第三章 一般搜索原理

2011-9-10

第三章 一般搜索原理

3.1概述

搜索技术搜索是人工智能中进行问题求解的一大类方法 搜索 根据是否使用启发式信息可分为 ： 盲目搜索； 2,启发式搜索； 根据问题的表示方式分为： 状态空间搜索； 2,与/或树搜索。 例如： 例如 1, 1,

用状态空间法来求解问题时，采用的是状态空间搜索； 用问题归约方法来求解问题时，采用的是与/或树搜 索。2011-9-10 2

第三章 一般搜索原理

3.1概述

搜索的特点和通常的搜索空间不同，人工智能中大多数问题的状 态空间在问题求解之前不是全部知道的。 所以，人工智能中的搜索可以分成两个阶段：状态空 间的生成阶段和在该状态空间中对所求解问题状态的 搜索。 由于一个问题的整个空间可能会非常的大，在搜索之 前生成整个空间会占用太大的存储空间。为此，状态 空间一般是逐渐扩展的 “目标”状态是在每次扩展的时候进行搜索的。2011-9-10 3

第三章 一般搜索原理

3.2 盲目搜索

3.2 盲目搜索

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

盲目搜索 盲目搜索是按预定的控制策赂进行搜索， 盲目搜索 没有任何关于问题本身的信息，在搜索 过程中获得的中间信息并不改变控制策 略。由于搜索总是按预先规定的路线进 行，没有考虑到问题本身的特性，因此 这种搜索具有盲目性，效率不高，不便 于复杂问题的求解。2011-9-10 5

第三章 一般搜索原理

3.2 盲目搜索

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

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

图搜索方式与回溯方式的不同回溯方式不记忆那些试探失败的操作和 它们产生的状态描述，只

记忆当前正在 搜索的路径。 图搜索方式则保存所有试探过的路径， 因而可以在任何一条路径上继续搜索

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

不可撤回搜索策略不可撤回方式的控制策略是，选择一条可应用的 操作作用于当前状态，不论后果如何都接着做下 去。这个方法类似于高等数学中求函数极值的爬 山法。 在爬山法中，我们从任一点出发，在该点的最大 梯度方向前进一步，得到一个新的点，再在新点 的最大梯度方向上前进一步，一直到梯度为0为止， 这个点就是函数的极大值点。如果函数只有一个 极大值点.则这个点就是该函数的最大值点。 。

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

不可撤回搜索的实现不可撤回搜索的实现是将状态描述定义成一 个实数值的爬山函数。 控制策略就利用这个爬山函数来选择一个可 应用的操作，施行该操作的结果应使爬山函 数的值得到最大限度的增加。

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

不可撤回搜索举例(一 不可撤回搜索举例 一)选择八数码问题 我们选取“不在位”的数字个数的负值作为爬山函数 八数码游戏的操作可描述为下面的4条产生式规则 (1) if空格不在最上一行then空格上移 (2) if空格不在最下一行then生格下移 (3) if空格不在最左一列then空格左移 (4) if空格不在最右一列then空格有移初始状态2011-9-10

2 8 3 1 6 4 7 5

1 2 3 8 4 7 6 5

目标状态10

第三章 一般搜索原理

3.2 盲目搜索

不可撤回搜索举例(二 不可撤回搜索举例 二)从初始状态出发，应用第一条规则，空格上移可 获得爬山函数的最大增加、因此控 制策略选择 第一条规则作为当前的操作。 在没有操作能够增加爬山函数的值时.可任选一 个不减小函数值的操作，如果不存在这样的操作， 则过程停止。-42 8 3 1 6 4 7 5

-32 8 3 1 4 7 6 5

-32 3 1 8 4 7 6 5

-22 3 1 8 4 7 6 5

-11 2 3 8 4 7 6 5

01 2 3 8 4 7 6 5

爬山函 数值2011-9-10

目标状态11

第三章 一般搜索原理

3.2 盲目搜索

不可撤回搜索举例(三 不可撤回搜索举例 三)对于上例，采用不可撤回策略可以很快得到问题 的解。 但一般来讲，如果爬山函数有多个局部极大值存 在，该策略可能会引导到局部极大值点，而达不 到目标状态。 例如当八数码问题的初始状态和目标状态分别如 下时，任意一个可应用的操作都会降低爬山函数 的值，因此，得不到目标：初始状态1 2 3 7 4 8 6 5 1 2 5 7 4 8 6 3

目标12

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

回溯搜索策略回溯策略是一种试探性方式。在选择一个 操作时要建立一个回溯点。 在搜索过程中，如果遇到了困难，则要返

回到最近的一个回溯点，换一个操作继续 进行搜索。

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

回溯搜索策略举例例：皇后问题Q Q Q Q

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

皇后问题搜索过程( 皇后问题搜索过程(一)()

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

皇后问题搜索过程( 皇后问题搜索过程(二)() ((1,1)) Q

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

皇后问题搜索过程( 皇后问题搜索过程(三)() ((1,1)) Q Q

((1,1) (2,3))

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

皇后问题搜索过程( 皇后问题搜索过程(四)() ((1,1)) Q

((1,1) (2,3))

2011-9-10

第三章 一般搜索原理

3.2 盲目搜索

皇后问题搜索过程( 皇后问题搜索过程(五)() ((1,1)) Q Q

((1,1) (2,3))

((1,1) (2,4))

2011-9-10

本文来源：https://www.bwwdw.com/article/o2bi.html