《华中科技大学人工智能第三章一般搜索原理1讲述》由会员分享,可在线阅读,更多相关《华中科技大学人工智能第三章一般搜索原理1讲述(104页珍藏版)》请在金锄头文库上搜索。
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