搜索技术l问题提出：有了知识表示方法之后，就需要有解决 问题的方法，也就是搜索技术。所谓搜索，就是寻 找一条从初始问题到问题解的路径l本章内容：搜索技术有许多种，本章介绍一些早期 的、比较简单的搜索原理：1，盲目搜索；2，启发 式搜索；3，消解原理；4，通用问题求解技术l关键问题： 如何利用知识，尽可能有效地找到问题的解(最佳解) 。第三章 一般搜索原理 Date1一般搜索原理l搜索策略可分为三大类不可撤回方式、回朔方式、图搜索方式l不可撤回方式：每一次搜索时，利用局部知识根据 最优评价，选出下一状态，选定后不能撤回，只能 继续l回朔方式：在搜索过程中，有时会发现所选的路径 不适合找到目标，这时允许退回去另选一条路径。l图搜索方式：如果把问题求解过程用图来表示。节 点代表问题的状态，弧代表状态变化的方向，则搜 索就变成对图进行从初始节点开始，到目标节点路 径的搜索。第三章 一般搜索原理 3.1盲目搜索Date2回溯搜索策略l例：皇后问题第三章 一般搜索原理 3.1盲目搜索Date3( )皇后问题搜索过程（一）第三章 一般搜索原理 3.1盲目搜索Date4Q( )(1,1)皇后问题搜索过程（二）第三章 一般搜索原理 3.1盲目搜索Date5QQ( )(1,1)(1,1) (2,3)皇后问题搜索过程（三）第三章 一般搜索原理 3.1盲目搜索Date6Q( )(1,1)(1,1) (2,3)皇后问题搜索过程（四）第三章 一般搜索原理 3.1盲目搜索Date7QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)皇后问题搜索过程（五）第三章 一般搜索原理 3.1盲目搜索Date8QQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)第三章 一般搜索原理 3.1盲目搜索 皇后问题搜索过程（六）Date9QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)第三章 一般搜索原理 3.1盲目搜索 皇后问题搜索过程（七）Date10Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)第三章 一般搜索原理 3.1盲目搜索 皇后问题搜索过程（八）Date11( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)第三章 一般搜索原理 3.1盲目搜索 皇后问题搜索过程（九）Date12Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)第三章 一般搜索原理 3.1盲目搜索 皇后问题搜索过程（十）Date13QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)第三章 一般搜索原理 3.1盲目搜索 皇后问题搜索过程（十一）Date14QQQ( )(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盲目搜索 皇后问题搜索过程（十二）Date15QQQQ( )(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盲目搜索 皇后问题搜索过程（十三）Date16递归的思想从前有座山从前有座山从前有座山第三章 一般搜索原理 3.1盲目搜索Date17一个递归的例子int ListLenght(LIST *pList) if (pList = NULL) return 0; else return ListLength(pList-next)+1; 第三章 一般搜索原理 3.1盲目搜索Date18回溯搜索算法说明BACKTRACK（DATA）DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。第三章 一般搜索原理 3.1盲目搜索Date19回溯搜索算法（一）递归过程BACKTRACK(DATA) 1, IF TERM(DATA) RETURN NIL; 2, IF DEADEND(DATA) RETURN FAIL; 3, RULES:=APPRULES(DATA);第三章 一般搜索原理 3.1盲目搜索TERM: 找目标DEADEND: 状态不合法,无法继续搜索APPRULES: 取可应用规则集Date20回溯搜索算法（二）4, LOOP: IF NULL(RULES) RETURN FAIL; 5, R:=FIRST(RULES); 6, RULES:=TAIL(RULES); 7, RDATA:=GEN(R, DATA); 8, PATH:=BACKTRACK(RDATA); 9, IF PATH=FAIL GO LOOP; 10, RETURN CONS(R, PATH);第三章 一般搜索原理 3.1盲目搜索TAIL: 删除头条规则GEN: 调用规则作用于当前状态CONS: 获取解路径规则表Date21存在问题及解决办法l问题：深度问题:如果深度太深死循环问题: 如果状态出现重复l解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径第三章 一般搜索原理 3.1盲目搜索Date22增加约束后的回溯搜索算法BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆 向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。第三章 一般搜索原理 3.1盲目搜索Date23增加约束后的回溯搜索算法(一)1, DATA:=FIRST(DATALIST) 2, IF MENBER(DATA, TAIL(DATALIST)RETURN FAIL; 3, IF TERM(DATA) RETURN NIL; 4, IF DEADEND(DATA) RETURN FAIL; 5, IF LENGTH(DATALIST)BOUNDRETURN FAIL;第三章 一般搜索原理 3.1盲目搜索Date24增加约束后的回溯搜索算法(二)6, RULES:=APPRULES(DATA); 7, LOOP: IF NULL(RULES) RETURN FAIL; 8,R:=FIRST(RULES); 9,RULES:=TAIL(RULES);第三章 一般搜索原理 3.1盲目搜索Date25增加约束后的回溯搜索算法(三)10, RDATA:=GEN(R, DATA); 11, RDATALIST:=CONS(RDATA, DATALIST); 12, PATH:=BACKTRCK1(RDATALIST) 13, IF PATH=FAIL GO LOOP; 14, RETURN CONS(R, PATH);第三章 一般搜索原理 3.1盲目搜索Date26一些深入的问题l失败原因分析、多步回溯QQ第三章 一般搜索原理 3.1盲目搜索Date27一些深入问题（续）l回溯搜索中知识的利用 基本思想： 尽可能选取划去对角线上位置数最少的。QQQQ4 3 3 4第三章 一般搜索原理 3.1盲目搜索Date28模式导向搜索l这个算法是将递归搜索应用到谓词演算的通 用搜索算法l要判断一个谓词表达式是某个断言集合的逻 辑结论l首先谓词表达式作为目标，使用合一来选择 能与其后件匹配的蕴涵式l并把得到的置换运用于该蕴涵式的前件 l这个前件成了新的目标称其为子目标l应用递归搜索解这个子目标l如果与事实相匹配，则搜索结实第三章 一般搜索原理 3.1盲目搜索Date29模式导向搜索算法描述一Function pattern_search(current_goal) beginif current_goal is in closed then return FAILelse put current_goal into closedwhile every rule and facts dobegincasecurrent_goal 与事实合一 return SUCCESS第三章 一般搜索原理 3.1盲目搜索Date30模式导向搜索算法描述二current_goal 是合取式beginfor every合取项item do ret = pattern_search(item)if ret = FAIL then return FAILendcurrent_goal 与规则的后件合一begin对前件q应用对应的合一置换ret = pattern_search(q)if ret = FAIL then return FAIL else SUCCESSendendreturn FAILend第三章 一般搜索原理 3.1盲目搜索Date31图搜索策略l图搜索策略就是在图中寻找从起始点到 目标点的路径的方法l图搜索的一般过程是构造搜索图的过程 。令搜索图开始时只有起始点S0，然后 逐步扩展节点，直到将目标点扩展到搜 索图里为止。扩展的过程就是搜索的过 程l扩展节点的方法不同，就意味着搜索的 方法不同，也就是搜索的路径不同。第三章 一般搜索原理 3.1盲目搜索Date32图搜索策略图示 S0Sg第三章 一般搜索原理 3.1盲目搜索Date33节点扩展l扩展一个节点 生成出该节点的所有后继节点，并给出它 们之间的代价值。这一过程称为“扩展一个 节点”。第三章 一般搜索原理 3.1盲目搜索Date34路径l路径 设一节点序列为(n0, n1,nk)，对于i = 1k ，若节点ni-1具有一个后继节点ni，则该序 列称为从n0到nk的路径。l路径的代价值 一