人工智能一般搜索原理94

12019/8/1搜索技术问题提出：有了知识表示方法之后，就需要有解决问题的方法，也就是搜索技术。所谓搜索，就是寻找一条从初始问题到问题解的路径本章内容：搜索技术有许多种，本章介绍一些早期的、比较简单的搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术关键问题：如何利用知识，尽可能有效地找到问题的解(最佳解)。第三章一般搜索原理22019/8/1一般搜索原理搜索策略可分为三大类不可撤回方式、回朔方式、图搜索方式不可撤回方式：每一次搜索时，利用局部知识根据最优评价，选出下一状态，选定后不能撤回，只能继续回朔方式：在搜索过程中，有时会发现所选的路径不适合找到目标，这时允许退回去另选一条路径。图搜索方式：如果把问题求解过程用图来表示。节点代表问题的状态，弧代表状态变化的方向，则搜索就变成对图进行从初始节点开始，到目标节点路径的搜索。第三章一般搜索原理3.1盲目搜索32019/8/1回溯搜索策略例：皇后问题QQQQ第三章一般搜索原理3.1盲目搜索42019/8/1()皇后问题搜索过程（一）第三章一般搜索原理3.1盲目搜索52019/8/1Q()((1,1))皇后问题搜索过程（二）第三章一般搜索原理3.1盲目搜索62019/8/1QQ()((1,1))((1,1)(2,3))皇后问题搜索过程（三）第三章一般搜索原理3.1盲目搜索72019/8/1Q()((1,1))((1,1)(2,3))皇后问题搜索过程（四）第三章一般搜索原理3.1盲目搜索82019/8/1QQ()((1,1))((1,1)(2,3))((1,1)(2,4))皇后问题搜索过程（五）第三章一般搜索原理3.1盲目搜索92019/8/1QQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章一般搜索原理3.1盲目搜索皇后问题搜索过程（六）102019/8/1QQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章一般搜索原理3.1盲目搜索皇后问题搜索过程（七）112019/8/1Q()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章一般搜索原理3.1盲目搜索皇后问题搜索过程（八）122019/8/1()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章一般搜索原理3.1盲目搜索皇后问题搜索过程（九）132019/8/1Q()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))第三章一般搜索原理3.1盲目搜索皇后问题搜索过程（十）142019/8/1QQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))第三章一般搜索原理3.1盲目搜索皇后问题搜索过程（十一）152019/8/1QQQ()((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))第三章一般搜索原理3.1盲目搜索皇后问题搜索过程（十二）162019/8/1QQQQ()((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.1盲目搜索皇后问题搜索过程（十三）172019/8/1递归的思想从前有座山……从前有座山……从前有座山……第三章一般搜索原理3.1盲目搜索182019/8/1一个递归的例子intListLenght(LIST*pList){if(pList==NULL)return0;elsereturnListLength(pList-next)+1;}第三章一般搜索原理3.1盲目搜索192019/8/1回溯搜索算法说明BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章一般搜索原理3.1盲目搜索202019/8/1回溯搜索算法（一）递归过程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:=APPRULES(DATA);第三章一般搜索原理3.1盲目搜索TERM:找目标DEADEND:状态不合法,无法继续搜索APPRULES:取可应用规则集212019/8/1回溯搜索算法（二）4,LOOP:IFNULL(RULES)RETURNFAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAILGOLOOP;10,RETURNCONS(R,PATH);第三章一般搜索原理3.1盲目搜索TAIL:删除头条规则GEN:调用规则作用于当前状态CONS:获取解路径规则表222019/8/1存在问题及解决办法问题：深度问题:如果深度太深死循环问题:如果状态出现重复解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径第三章一般搜索原理3.1盲目搜索232019/8/1增加约束后的回溯搜索算法BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章一般搜索原理3.1盲目搜索242019/8/1增加约束后的回溯搜索算法(一)1,DATA:=FIRST(DATALIST)2,IFMENBER(DATA,TAIL(DATALIST))RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)BOUNDRETURNFAIL;第三章一般搜索原理3.1盲目搜索252019/8/1增加约束后的回溯搜索算法(二)6,RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);第三章一般搜索原理3.1盲目搜索262019/8/1增加约束后的回溯搜索算法(三)10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAILGOLOOP;14,RETURNCONS(R,PATH);第三章一般搜索原理3.1盲目搜索272019/8/1一些深入的问题失败原因分析、多步回溯QQ第三章一般搜索原理3.1盲目搜索282019/8/1一些深入问题（续）回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。QQQQ4334第三章一般搜索原理3.1盲目搜索292019/8/1模式导向搜索这个算法是将递归搜索应用到谓词演算的通用搜索算法要判断一个谓词表达式是某个断言集合的逻辑结论首先谓词表达式作为目标，使用合一来选择能与其后件匹配的蕴涵式并把得到的置换运用于该蕴涵式的前件这个前件成了新的目标—称其为子目标应用递归搜索解这个子目标如果与事实相匹配，则搜索结实第三章一般搜索原理3.1盲目搜索302019/8/1模式导向搜索算法描述一Functionpattern_search(current_goal)beginifcurrent_goalisinclosedthenreturnFAILelseputcurrent_goalintoclosedwhileeveryruleandfactsdobegincasecurrent_goal与事实合一returnSUCCESS第三章一般搜索原理3.1盲目搜索312019/8/1模式导向搜索算法描述二current_goal是合取式beginforevery合取项itemdoret=pattern_search(item)ifret==FAILthenreturnFAILendcurrent_goal与规则的后件合一begin对前件q应用对应的合一置换ret=pattern_search(q)ifret==FAILthenreturnFAILelseSUCCESSendendreturnFAILend第三章一般搜索原理3.1盲目搜索322019/8/1图搜索策略图搜索策略就是在图中寻找从起始点到目标点的路径的方法图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展的过程就是搜索的过程扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的路径不同。第三章一般搜索原理3.1盲目搜索332019/8/1图搜索策略图示S0Sg第三章一般搜索原理3.1盲目搜索342019/8/1节点扩展扩展一个节点生成出该节点的所有后继节点，并给出它们之间的代价值。这一过程称为“扩展一个节点”。第三章一般搜索原理3.1盲目搜索352019/8/1路径路径设一节点序列为(n0,n1,…,nk)，对于i=1…k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的代价值一条路径的代价值等于连接这条路径各节点间所有代价值的总和。用C(ni,nj)表示从ni到nj的路径的代价值。第三章一般搜索原理3.1盲目搜索362019/8/1节点深度节点深度：根节点深度=0其它节点深度=父节点深度+10123第三章一般搜索原理3.1盲目搜索372019/8/1图搜索的一般过程第三章一般搜索原理3.1盲目搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向把S放入OPEN表重排OPEN表是否否OPEN为空？n为目标节点？失败开始382019/8/1图搜索过程说明我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构OPEN表中的节点都是搜索树的端节点，即至今尚未被选作为扩展的节点CLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点重排OPEN表，实际上就是在选择搜索顺序，也就是扩展的节点的顺序。第三章一般搜索原理3.1盲目搜索392019/8/1节点类型说明…...mj…...mk…...…...…...ml第三章一般搜索原理3.1盲目搜索扩展的节点OPEN表没有的部分扩展的节点在已在close表中的部分扩展的节点已在OPEN表中的部分选定的扩展节点402019/8/1第三章一般搜索原理3.1盲目搜索图搜索过程的图示（一）现要扩展它412019/8/1第三章一般搜索原理3.1盲目搜索图搜索过程的图示（二）修改父子关系现要扩展它422019/8/1第三章一般搜索原理3.1盲目搜索图搜索过程的图示（三）修改父子关系修改父子关系432019/8/1盲目搜索概述盲目搜索也叫无信息搜索盲目搜索实际上是对解空间的遍历盲目搜索包括有：宽度优先搜索：搜索以接近起始节点的程度依次扩展节点，在对下一层搜索前，必须搜索完本层的所有节点。深度优先搜索：搜索首先扩展最新产生的节点。等代价搜索：搜索沿最小代价节点进行扩展。第三章一般搜索原理3.1盲目搜索442019/8/1宽度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？是否有任何后继节点为