人工智能-一般搜索原理

1,2019/4/18,搜索技术,问题提出：有了知识表示方法之后，就需要有解决问题的方法，也就是搜索技术。所谓搜索，就是寻找一条从初始问题到问题解的路径 本章内容：搜索技术有许多种，本章介绍一些早期的、比较简单的搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术 关键问题： 如何利用知识，尽可能有效地找到问题的解(最佳解)。,第三章 一般搜索原理,2,2019/4/18,一般搜索原理,搜索策略可分为三大类 不可撤回方式、回朔方式、图搜索方式 不可撤回方式：每一次搜索时，利用局部知识根据最优评价，选出下一状态，选定后不能撤回，只能继续 回朔方式：在搜索过程中，有时会发现所选的路径不适合找到目标，这时允许退回去另选一条路径。 图搜索方式：如果把问题求解过程用图来表示。节点代表问题的状态，弧代表状态变化的方向，则搜索就变成对图进行从初始节点开始，到目标节点路径的搜索。,第三章 一般搜索原理 3.1盲目搜索,3,2019/4/18,回溯搜索策略,例：皇后问题,第三章 一般搜索原理 3.1盲目搜索,4,2019/4/18,( ),皇后问题搜索过程（一）,第三章 一般搜索原理 3.1盲目搜索,5,2019/4/18,Q,皇后问题搜索过程（二）,第三章 一般搜索原理 3.1盲目搜索,6,2019/4/18,皇后问题搜索过程（三）,第三章 一般搜索原理 3.1盲目搜索,7,2019/4/18,Q,皇后问题搜索过程（四）,第三章 一般搜索原理 3.1盲目搜索,8,2019/4/18,皇后问题搜索过程（五）,第三章 一般搜索原理 3.1盲目搜索,9,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（六）,10,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（七）,11,2019/4/18,Q,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（八）,12,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（九）,13,2019/4/18,Q,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（十）,14,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（十一）,15,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（十二）,16,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（十三）,17,2019/4/18,递归的思想,第三章 一般搜索原理 3.1盲目搜索,18,2019/4/18,一个递归的例子,int ListLenght(LIST *pList) if (pList = NULL) return 0; else return ListLength(pList-next)+1; ,第三章 一般搜索原理 3.1盲目搜索,19,2019/4/18,回溯搜索算法说明,BACKTRACK（DATA） DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,第三章 一般搜索原理 3.1盲目搜索,20,2019/4/18,回溯搜索算法（一）,递归过程BACKTRACK(DATA) 1, IF TERM(DATA) RETURN NIL; 2, IF DEADEND(DATA) RETURN FAIL; 3, RULES:=APPRULES(DATA);,第三章 一般搜索原理 3.1盲目搜索,TERM: 找目标 DEADEND: 状态不合法,无法继续搜索 APPRULES: 取可应用规则集,21,2019/4/18,回溯搜索算法（二）,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: 获取解路径规则表,22,2019/4/18,存在问题及解决办法,问题： 深度问题:如果深度太深 死循环问题: 如果状态出现重复 解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径,第三章 一般搜索原理 3.1盲目搜索,23,2019/4/18,增加约束后的回溯搜索算法,BACKTRACK1（DATALIST） DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,第三章 一般搜索原理 3.1盲目搜索,24,2019/4/18,增加约束后的回溯搜索算法(一),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)BOUND RETURN FAIL;,第三章 一般搜索原理 3.1盲目搜索,25,2019/4/18,增加约束后的回溯搜索算法(二),6, RULES:=APPRULES(DATA); 7, LOOP: IF NULL(RULES) RETURN FAIL; 8, R:=FIRST(RULES); 9, RULES:=TAIL(RULES);,第三章 一般搜索原理 3.1盲目搜索,26,2019/4/18,增加约束后的回溯搜索算法(三),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盲目搜索,27,2019/4/18,一些深入的问题,失败原因分析、多步回溯,第三章 一般搜索原理 3.1盲目搜索,28,2019/4/18,一些深入问题（续）,回溯搜索中知识的利用 基本思想： 尽可能选取划去对角线上位置数最少的。,第三章 一般搜索原理 3.1盲目搜索,29,2019/4/18,模式导向搜索,这个算法是将递归搜索应用到谓词演算的通用搜索算法 要判断一个谓词表达式是某个断言集合的逻辑结论 首先谓词表达式作为目标，使用合一来选择能与其后件匹配的蕴涵式 并把得到的置换运用于该蕴涵式的前件 这个前件成了新的目标称其为子目标 应用递归搜索解这个子目标 如果与事实相匹配，则搜索结实,第三章 一般搜索原理 3.1盲目搜索,30,2019/4/18,模式导向搜索算法描述一,Function pattern_search(current_goal) begin if current_goal is in closed then return FAIL else put current_goal into closed while every rule and facts do begin case current_goal 与事实合一 return SUCCESS,第三章 一般搜索原理 3.1盲目搜索,31,2019/4/18,模式导向搜索算法描述二,current_goal 是合取式 begin for every合取项item do ret = pattern_search(item) if ret = FAIL then return FAIL end current_goal 与规则的后件合一 begin 对前件q应用对应的合一置换 ret = pattern_search(q) if ret = FAIL then return FAIL else SUCCESS end end return FAIL end,第三章 一般搜索原理 3.1盲目搜索,32,2019/4/18,图搜索策略,图搜索策略就是在图中寻找从起始点到目标点的路径的方法 图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展的过程就是搜索的过程 扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的路径不同。,第三章 一般搜索原理 3.1盲目搜索,33,2019/4/18,图搜索策略图示,S0,Sg,第三章 一般搜索原理 3.1盲目搜索,34,2019/4/18,节点扩展,扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的代价值。这一过程称为“扩展一个节点”。,第三章 一般搜索原理 3.1盲目搜索,35,2019/4/18,路径,路径 设一节点序列为(n0, n1,nk)，对于i = 1k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。 路径的代价值 一条路径的代价值等于连接这条路径各节点间所有代价值的总和。用C(ni, nj)表示从ni到nj的路径的代价值。,第三章 一般搜索原理 3.1盲目搜索,36,2019/4/18,节点深度,节点深度： 根节点深度=0 其它节点深度=父节点深度+1,0,1,2,3,第三章 一般搜索原理 3.1盲目搜索,37,2019/4/18,图搜索的一般过程,第三章 一般搜索原理 3.1盲目搜索,38,2019/4/18,图搜索过程说明,我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构 OPEN表中的节点都是搜索树的端节点，即至今尚未被选作为扩展的节点 CLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点 重排OPEN表，实际上就是在选择搜索顺序，也就是扩展的节点的顺序。,第三章 一般搜索原理 3.1盲目搜索,39,2019/4/18,节点类型说明,.,mj,第三章 一般搜索原理 3.1盲目搜索,扩展的节点OPEN表没有的部分,扩展的节点在已在close表中的部分,扩展的节点已在OPEN表中的部分,选定的扩展节点,40,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示（一）,现要扩展它,41,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示（二）,修改父子关系,现要扩展它,42,2019/4/18,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示（三）,修改父子关系,修改父子关系,43,2019/4/18,盲目搜索概述,盲目搜索也叫无信息搜索 盲目搜索实际上是对解空间的遍历 盲目搜索包括有： 宽度优先搜索：搜索以接近起始节点