华中科技大学人工智能第三章一般搜索原理剖析

《华中科技大学人工智能第三章一般搜索原理剖析》由会员分享，可在线阅读，更多相关《华中科技大学人工智能第三章一般搜索原理剖析（100页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

6、 if空格不在最下一行then生格下移 l (3) if空格不在最左一列then空格左移 l (4) if空格不在最右一列then空格有移 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 目标状态 初始状态 第三章 一般搜索原理 3.2 盲目搜索 Date 10 不可撤回搜索举例(二) l从初始状态出发，应用第一条规则，空格上移可 获得爬山函数的最大增加、因此控 制策略选择 第一条规则作为当前的操作。 l在没有操作能够增加爬山函数的值时可任选一 个不减小函数值的操作，如果不存在这样的操作 ，则过程停止。 2 8 3 1 6 4 7 5 2 3 1 8 4 7 6 5 2 8 3

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

8、态 第三章 一般搜索原理 3.2 盲目搜索 Date 12 回溯搜索策略 l回溯策略是一种试探性方式。在选择一个 操作时要建立一个回溯点。 l在搜索过程中，如果遇到了困难，则要返 回到最近的一个回溯点，换一个操作继续 进行搜索。 第三章 一般搜索原理 3.2 盲目搜索 Date 13 回溯搜索策略举例 l例：皇后问题 第三章 一般搜索原理 3.2 盲目搜索 Date 14 ( ) 皇后问题搜索过程（一） 第三章 一般搜索原理 3.2 盲目搜索 Date 15 Q ( ) (1,1) 皇后问题搜索过程（二） 第三章 一般搜索原理 3.2 盲目搜索 Date 16 Q Q ( ) (1,1) (1

9、,1) (2,3) 皇后问题搜索过程（三） 第三章 一般搜索原理 3.2 盲目搜索 Date 17 Q ( ) (1,1) (1,1) (2,3) 皇后问题搜索过程（四） 第三章 一般搜索原理 3.2 盲目搜索 Date 18 Q Q ( ) (1,1) (1,1) (2,3) (1,1) (2,4) 皇后问题搜索过程（五） 第三章 一般搜索原理 3.2 盲目搜索 Date 19 Q Q Q ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) 皇后问题搜索过程（六） 第三章 一般搜索原理 3.2 盲目搜索 Date 20 Q Q ( ) (1

10、,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) 皇后问题搜索过程（七） 第三章 一般搜索原理 3.2 盲目搜索 Date 21 Q( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) 皇后问题搜索过程（八） 第三章 一般搜索原理 3.2 盲目搜索 Date 22 ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) 皇后问题搜索过程（九） 第三章 一般搜索原理 3.2 盲目搜索 Date 23 Q ( ) (1,1) (1,1) (2,3) (1,1)

11、 (2,4) (1,1) (2,4) (3.2) (1,2) 皇后问题搜索过程（十） 第三章 一般搜索原理 3.2 盲目搜索 Date 24 Q Q ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) (1,2) (2,4) 皇后问题搜索过程（十一） 第三章 一般搜索原理 3.2 盲目搜索 Date 25 Q Q Q ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) (1,2) (2,4) (1,2) (2,4) (3,1) 皇后问题搜索过程（十二） 第三章 一般搜

12、索原理 3.2 盲目搜索 Date 26 Q Q Q Q ( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) (1,2) (2,4) (1,2) (2,4) (3,1) (1,2) (2,4) (3,1) (4,3) 皇后问题搜索过程（十三） 第三章 一般搜索原理 3.2 盲目搜索 Date 27 回溯搜索算法 l回溯搜索可以用递归的方法来实现 l下面的算法是一个用递归实现的算法： BACKTRACK（DATA） DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。 第三章 一般搜索原理

13、3.2 盲目搜索 Date 28 回溯搜索算法（一） BACKTRACK(DATA) 1, IF TERM(DATA) RETURN NIL; 2, IF DEADEND(DATA) RETURN FAIL; 3, RULES:=APPRULES(DATA); TERM: 找目标 DEADEND: 状态不合法,无法继续搜索 APPRULES: 取可应用规则集 第三章 一般搜索原理 3.2 盲目搜索 Date 29 回溯搜索算法（二） 4, LOOP: IF NULL(RULES) RETURN FAIL; 5, R:=FIRST(RULES); 6, RULES:=TAIL(RULES); 7

14、, RDATA:=GEN(R, DATA); 8, PATH:=BACKTRACK(RDATA); 9, IF PATH=FAIL GO LOOP; 10, RETURN CONS(R, PATH); TAIL: 删除头条规则 GEN: 调用规则作用于当前状态 CONS: 获取解路径规则表 第三章 一般搜索原理 3.2 盲目搜索 Date 30 存在问题及解决办法 l问题： 深度问题:如果深度太深 死循环问题: 如果状态出现重复 l解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径 第三章 一般搜索原理 3.2 盲目搜索 Date 31 增加约束后的回溯搜索算法 BACKTRACK1（DATALIST） DATALIST：从初始到当前的状态表（逆向 ） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。 第三章 一般搜索原理 3.2 盲目搜索 Date 32 增加约束后的回溯搜索算法(一) 1, DATA:=FIRST(DATALIST) 2, IF MENBER(DATA, TAIL(DATALIST) RETURN FAI