人工智能 第三章.ppt
42页
第三章 搜索策略,3.1 控制策略分类 控制策略分为两类：不可撤回的方式和试探方式 不可撤回的方式：选择一条适用的规则并应用它时，不必为以后重新考虑做准备 试探方式：选择一条适用的规则执行，但需为以后应用另一条规则做准备 试探方式也可分为两种：回溯式和图搜索式 回溯式：在选择一条规则时要建立一个回溯点，当计算遇到困难，不能得到一个解时，使状态返回原来的回溯点上，从那里改选另一条可应用规则 图搜索：同时记住几个规则序列及其产生的结果3.2 不可撤回方式 这种方式是利用问题给出的局部知识来决定如何选取规则，不必考虑撤回已用的规则这种控制策略的优点是控制简单 3.2.1爬山法 爬山法就是利用高度随位置变化的函数引导爬山 爬山法只有在登单峰的山时才有效，如遇到多峰、山脊或平顶时，并不总是有效我们以八数码游戏为例加以说明 在3×3的棋盘上，有八个将牌和一个空格，每一个将牌都标有1—8中的某一个数码，空格周围的将牌可向空格移动，求解的问题是：有一个初始布局和一个目标布局，问如何移动将牌，从初始布局达到目标 综合数据库：我们用二维数组来表示3×3的棋盘初始状态 目标状态,规则集合：可用四条产生式规则代表四种走法： 空格左移、空格上移、空格右移、空格下移 设用Bij表示表中第i行第j列的数码，u、v表示空格所在的行列数，空格用0表示，则空格左移的规则定义如下： IF ｖ－１≧１ THEN Buv︰=Bu(v-1)∧Bu(v-1)=0 搜索策略： 不在位将牌个数：当前状态与目标状态对应位置逐一比较后有差异的将牌个数。
我们定义一个描述状态的函数-W(n)，其中，n表示任一状态，W(n)的值为不在位将牌个数初始状态的函数值为-4，目标状态的函数值为0爬山法选取规则的原则：选取使用规则后生成的新状态的函数值有最大增长的规则，如没有使函数值增长的规则，则选取使函数值不减少的规则，若这种规则也没有，则过程停止 使用爬山法过程如下：2 8 31 6 47 5 2 8 31 47 6 5,,,,,,2 3 2 8 3 8 1 31 8 4 1 4 2 47 6 5 7 6 5 7 6 52 3 8 3 1 31 8 4 2 1 4 8 2 47 6 5 7 6 5 7 6 51 2 3 8 3 1 38 4 2 1 4 8 2 47 6 5 7 6 5 7 6 51 2 3 8 1 3 1 2 38 4 2 4 8 47 6 5 7 6 5 7 6 5,,,,,,,,,,,,,,,,,,,,,,,,,从上述过程可知，用不可撤回方式（爬山策略）可找到通往目标的路径，控制简单是其优点，缺点是对任何状态不是总能选得最优解，并且具有一定的局限性，例如：初始状态 目标状态图3.4 八数码题的爬山局部极大值初始状态处于局部极大值，无法搜索。
3.2.2可交换的产生式系统 可交换产生式系统应满足的性质： （1） 可应用于D的规则集合，对用了其中任意一条规则之后所生成的任何数据库，这个规则集合还适用； （2） 满足目标条件的某个数据库D，当应用任何一个可应用于数据库D的规则之后所生成的任何数据库，仍然满足目标条件； （3） 若对D应用某一规则序列之后得到一个数据库D（设有一对应于DD 的一条解路），则当改变D 的可应用规则集合中的规则次序后，仍然可求得解，即求得D与使用满足D的可应用规则集合中的规则次序无关3.3回溯策略 回溯策略是试探性的控制方式，需要记住一条路径，可用递归过程BACKTRACK加以描述用DATA表示综合数据库，既是当前需处理的状态，当算法成功返回时，返回一张规则表 递归过程BACKTRACK(DATA) IF TERM(DATA), RETURN NIL; TERM取真即找到目标，则过程返回空表NIL IF DEADEND(DATA), RETURN FAIL; DEADEND取真，即该状态不合法，则过程返回FAIL，必须回溯 RULES:=APPRULES(DATA); APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。
LOOP:IF NULL(RULES), RETURN FAIL; NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯 R:=FIRST(RULES); 取头条可应用规则 RULES:=TAIL(RULES);删去头条规则，减少可应用规则表的长度 RDATA:=GEN(R, DATA);调用规则R作用于当前状态，生成新状态 PATH:=BACKTRACK(RDATA);对新状态递归调用本过程 IF PATH=FAIL, GO LOOP;当PATH=FAIL时，递归调用失败，则转移调用另一规则进行测试 RETURN CONS(R, PATH); 过程返回解路径规则表（或局部解路径子表）例:皇后问题 综合数据库是一个最多为四个元素的表DATA，每个元素为一个两位的数字，其中十位表示棋子所在的行，个位表示棋子所在的列 规则集：{ Rij1i4，1j4} Rij：if 1 i 4 and Length (DATA) =i1Then APPEND (DATA , (ij))(a) (b),若按固定排序进行搜索，回溯22次，其过程如图3.7所示。
)(11) (12)(21) (22) (23) (24) (21) (22) (23) (24)(31) (32) (33) (34) (31) (32) (33) (34) (31)(41) (42) (43) (44) (41) (42) (43) 图3.7 四皇后问题固定排序搜索,,,,,,,,,,,,,,,,,,,,,,,,,,,利用与问题有关的启发信息,定义对角线函数d (i ,j)，对规则动态排序进行搜索，只回溯2次,其过程如图3.8 )(12)(21) (24)(31)(42) (43)图3.8 四皇后问题动态排序搜索 对于像八数码这种类型的问题设置深度界限另外，为防止出现重复状态引起的死循环需作检查3.4 图搜索策略 图搜索策略就是要记住应用规则后产生的所有路径. 节点深度：根节点的深度为0，其他节点的深度规定为父节点深度加1，即 dn+1 =d n+1 路径：设一节点序列为(n0,n1,…,ni,…nk)，对i=1,2,…,k,若节点ni-1都具有一个后继节点ni,则该节点序列称为从节点n0到节点nk长度为k的一条路径。
路径耗散值：令C(ni, nj)为节点 ni到 nj这段路径（或弧线）的耗散值，一条路径的耗散值等于连接这条路径各节点间所有弧线耗散值的总和路径耗散值可按如下递归公式计算：C(ni, t)=C(ni, nj)+C(nj, t) C(ni, t)为 ni t这条路径的耗散值 扩展一个节点：后继节点操作符（相当于可应用规则）作用到节点（对应于某一状态描述）上，生成出其所有后继节点（新状态），并给出连接弧线的耗散值（相当于使用规则的代价），这个过程叫做扩展一个节点一般图搜索算法 1. G:=G0 (G0=s)，OPEN:=(s)；G表示图，s为初始节点，设置OPEN 表，最初只含初始节点. 2. CLOSED:=( )；设置CLOSED表,起始设置为空表. 3. LOOP: IF OPEN=( )，THEN EXIT(FAIL); 4. n:=FIRST(OPEN)，REMOVE(n, OPEN)，ADD(n, CLOSED);称n为当前节点 5. IF GOAL(n)，THEN EXIT(SUCCESS)；由n返回到s的路径上的指针,可给出解路径6. EXPAND(n) (m), G:=ADD(mi, G)；子节点集(mi)中不包含n的先辈节点，其中(mi)=(mj) (mk) (ml)。
7. 标记和修改指针ADD(mj，OPEN), 并标记mj连接到n的指针;mj为OPEN和CLOSED中未出现过的子节点 计算是否要修改mk、ml到n的指针； mk为已出现在 OPEN中的子节点，ml为在CLOSED中的子节点 计算是否要修改ml到其后继节点的指针； 8．对OPEN中的节点按某种原则重新排序； 9．GO LOOP；,S 1 6 2 3 4 5 （a）,S 1 6 2 3 4 5 （b）,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,3.5 盲目图搜索 深度优先(DEPTH-FIRST-SEARCH): 1.G:=G0(G0=s)，OPEN:=(s)，CLOSED:=( ); 2.LOOP: IF OPEN=( ) THEN EXIT (FAIL); 3.n:=FIRST(OPEN); 4.IF GOAL(n) THEN EXIT(SUCCESS); 5.REMOVE(n，OPEN)，ADD(n，CLOSED); 6.EXPAND(n) {mi}, G:=ADD(mi, G); 7.ADD(mj，OPEN), 并标记mj到n的指针；把不在OPEN或CLOSED中的节点放到OPEN表的最前面，是深度大的节点可优先扩展。
8.GO LOOP;,说明： 1） 扩充节点与图搜索一致，不包括n 的祖先节点 2） 深度优先一般应对搜索深度加以限制 3） 广度优先，在单位耗散的条件下，可找到最短路径 4） 无信息的回溯与不保存多条路径的深度优先的控制是相同的 5） 深度与广度的区别是扩展结点放在前与后 3.6 启发式图搜索利用所处理问题的启发信息引导搜索，被成为启发式搜索，利用启发信息定义一个评价函数f对待扩展的节点计算，用来对OPEN表排序3.6.1 分支界限法 K(ni，nj)：表示任意两个节点nI与nj之间最小耗散值路径的实际耗散值（当nI到nj无通路时，K(ni，nj)无意义） 为说明从起始节点s到任意节点n的最小耗散值路径的实际耗散值，我们定义： g*(n)=K(s，n) 假设n0 (即s)，n1 ，n2 ，…，nk是最小耗散值路径上的节点序列，则有 g*(nk)=K(s，nk)= K(ni，ni+1) 且g*(s)=0 我们设g(n)是到目前为止，从s到n的一条最小耗散值路径的耗散值，为g*(n)的估计值，即g*(n) g(n)，g(n)可计算出来 分支界限法是优先扩展当前具有最小耗散值分支路径的端节点n，其评价函数为f(n)=g(n)。
