第一章人工智能蔡自兴

1第一章搜索问题•内容：状态空间的搜索问题。•搜索方式：–盲目搜索–启发式搜索•关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。2搜索问题（续1）S0Sg问题全状态空间搜索空间解路径3搜索问题（续2）•讨论的问题：–有哪些常用的搜索算法。–问题有解时能否找到解。–找到的解是最佳的吗？–什么情况下可以找到最佳解？–求解的效率如何。41.1回溯策略•例：皇后问题QQQQ5()6()Q((1,1))7()QQ((1,1))((1,1)(2,3))8()Q((1,1))((1,1)(2,3))9()QQ((1,1))((1,1)(2,3))((1,1)(2,4))10()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))11()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))14()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))15()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))16()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))17()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))18•回溯策略属于盲目搜索的一种。•回溯策略是这样一种策略：首先将规则给出一个固定排序，在搜索时，对当前状态依次检查每条规则，在当前状态未使用过的规则中找到第一条可应用规则应用于当前状态，得到的新状态设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经用过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前的状态。重复以上搜索，直到找到问题的解。回溯策略19递归的思想回溯有多种实现方法,其中递归是一种最直接的实现方法.从前有座山……从前有座山……从前有座山……20回溯搜索算法递归过程：BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。21回溯搜索算法递归过程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;//满足结束条件时返回2,IFDEADEND(DATA)RETURNFAIL;//不合法状态的回溯点3,RULES:=APPRULES(DATA);//可应用规则集4,LOOP:IFNULL(RULES)RETURNFAIL;//全部规则均失败的回溯点5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);//删去第一条规则，减少可应用规则表的长度7,RDATA:=GEN(R,DATA);//调用规则R作用于当前状态，生成新状态8,PATH:=BACKTRACK(RDATA);//对新状态递归调用9,IFPATH=FAILGOLOOP;10,RETURNCONS(R,PATH);//返回解路径规则表22递归的思想（续）当前状态n目标状态tr1r2ri-1rim1m2mi-1mi23存在问题及解决办法•解决办法：–对搜索深度加以限制–记录从初始状态到当前状态的路径当前状态问题：–深度问题–死循环问题24一些深入问题•在回溯策略中，也可以引入一些与问题有关的信息来加快搜索解的速度。基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ322325回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。26回溯搜索算法11,DATA:=FIRST(DATALIST)//设置DATA为当前状态2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;//TAIL取尾操作，取DATALIST中除第一个以外的所有元素，如果DATA在TAIL(DATALIST）中存在，则说明有回路，返回FAIL，必须回溯.3,IFTERM(DATA)RETURNNIL;//找到目标，结束4,IFDEADEND(DATA)RETURNFAIL;//状态不合法，返回FAIL，必须回溯.5,IFLENGTH(DATALIST)BOUNDRETURNFAIL;//LENGTH计算DATALIST的长度，即搜索深度，当搜索深度大于BOUND值时，搜索失败，返回FAIL，必须回溯.6,RULES:=APPRULES(DATA);//APPRULES计算DATA的可应用规则集，依某种原则（任意排列或启发式排列）排列后附给RULES.7,LOOP:IFNULL(RULES)RETURNFAIL;//规则用完没找到目标，返回FAIL,必须回溯。27回溯搜索算法1（续）8,R:=FIRST(RULES);//取第一条规则9,RULES:=TAIL(RULES);//删去第一条规则，减少可应用规则表的长度10,RDATA:=GEN(R,DATA);//调用规则R作用于当前状态，生成新状态11,RDATALIST:=CONS(RDATA,DATALIST);//将新状态加入到表DATALIST中12,PATH:=BACKTRCK1(RDATALIST)//递归调用本过程13,IFPATH=FAILGOLOOP;//递归调用失败，转移调用另一规则进行测试14,RETURNCONS(R,PATH);//返回解路径规则表28分析•这个算法与BACKRACK的差别是递归过程自变量是状态的链表。•在过程BACKRACK1中，形参DATALIST是从初始状态到当前状态的逆序表，即初始状态排在表的最后，当前状态排在表的最前面。•在第2、5步增设了两个回溯点以检验是否重新访问已出现过的状态和限定搜索深度范围。291.2图搜索策略•问题的引出–回溯搜索：只保留从初始状态到当前状态的一条路径。–图搜索：保留所有已经搜索过的路径。30一些基本概念•节点深度：根节点深度=0其它节点深度=父节点深度+1012331一些基本概念（续1）•路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若任一节点ni-1都具有一个后继节点ni，则该节点序列称为从n0到nk的长度为k的一条路径。•路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值.路径耗散值可按如下递推公式计算：C(ni,t)=C(ni,nj)+C(nj,t)32一些基本概念（续1）•扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。33一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);//设置open表,最初只含有初始点s2,CLOSED:=();//设置closed表,初始为空表3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);//n为当前节点5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);//子节点集{mi}中不包含n的父辈节点34一般的图搜索算法（续）7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；//mj为open表和closed表中未出现过的子结点计算是否要修改mk、ml到n的指针；//mk为已出现在open表中的子结点，ml为已出现在closed表中的子结点，{mj}={mj}∪{mk}∪{ml}计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；35说明•这里给出的是一个图搜索的一般框架，不是一个具体的算法，关键是算法的第8步，按不同的原则对OPEN表进行排序，将得到不同的图搜索算法。•算法中有两个表：OPEN表和CLOSED表。其中OPEN表记录的是已经被生成出来，但还没有被扩展的节点；CLOSED表记录的是已经被扩展过的节点。36几类节点的图例说明如上图所示，假设n是当前被扩展的节点。在n被扩展之前，节点mk和ml已经被生成出来了，其中mk还没有被扩展，他们在OPEN表中，而ml已经被扩展了，他们在CLOSED表中。当n被扩展时，它生成了节点mi，mi由mj、mk和ml三部分组成，其中mj是新出现的节点。37算法解释•图搜索算法，简单地说就是，每次从OPEN表中取出第一个节点进行扩展，生成的新节点放到OPEN表中，然后按照某种原则对OPEN表进行排序。不同的排序原则构成了不同的图搜索算法。•值得注意的是算法成功结束的判断方法，是当从OPEN表中取出一个节点后，再判断该节点是否是目标节点，而不是在扩展节点，生成新节点时判断。这一点一定要注意，在后面将可以看到，这是构成某些最优算法的关键所在。38算法解释•这个过程是在第8步要对OPEN表上的节点进行排序，以便在第4步能选出一个“最好”的节点优先扩展。不同的排序方法便可构成形式多样的专门搜索算法，这在后面还要进一步讨论。•如果选出待扩展的节点是目标节点，则算法在第5步成功结束，并可根据回溯到s的指针给出解路径。如果某个循环中，搜索树不再剩有待选的节点，即OPEN表变空时，则过程失败结束，问题找不到解。39算法解释现在说明一下第7步中标记和修改指针的问题。•如果要搜索的隐含图是一棵树，则可肯定第6步生成的后继节点不可能是以前生成过的，这时搜索图就是搜索树，不存在mk、ml这种类型的子节点，因此不必进行修改指针的操作。•如果要搜索的隐含图不是一棵树，则有可能出现这样的子节点，就是说这时又发现了到达的新通路，这样就要比较不同路径的耗散值，把指针修改到具有较小耗散值的路径上。40例如，下图所示的两个搜索图中，实心圆点在CLOSED表中（已扩展过的节点），空心圆点则在OPEN表中（待扩展点）。•先设下一步轮到要扩展节点6，并设生成的两个子节点，其中有一个4已在OPEN中，那么原先路径（s→3→2→4）耗散值为5（设每段路径均为单位耗散），新路径（s→6→4）的耗散值为4，所以4的指针应由指向2修正到指向6，如图2.5（a）所示。•接着设下一循环要扩展节点1，若节点1只生成一个子节点2（它已在CLOSED上），显然这时节点2原先指向节点3的指针，要修改到指向节点1，由此又引起子节点3的指针又修改为指向2，如图2.5（b）所示。411.3无信息图搜索过程无信息图搜索属于盲目搜索，这里给两种常用的无信息图搜索方法：•深度优先搜索•宽度优先搜索42•所谓深度优先搜索，就是在每次扩展一个节点时，选择到目前为止深度最深的节点优先扩展。•第7步中的ADD（mj，OPEN）表示将被扩展节点n的所有新子节点mj加到OPEN表的前面。开始时，OPEN表中只有一个初始节点s，s被扩展，其子节点被放入OPEN表中。•在算法的第3步，OPEN表的第一个元素(设为n)被取出扩展，这时节点n的深度在OPEN表中是最大的，OPEN表中的其他节点的深度都不会超过n的深度。n的子节点被放到OPEN表的最前面。由于子节点的深度要大于父节点的深度，实际上OPEN表是按照节点的深度进行排序的，深度深的节点被排在了前面，而深度浅的节点被放在了后面。这样当下一个循环再次取出OPEN表的第一个元素