第一章人工智能蔡自兴.ppt

第一章 搜索问题 内容： 状态空间的搜索问题。 搜索方式： 盲目搜索 启发式搜索 关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。 搜索问题（续1） 搜索问题（续2） 讨论的问题： 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。 1.1 回溯策略 例：皇后问题 回溯策略 回溯策略属于盲目搜索的一种。 回溯策略是这样一种策略： 首先将规则给出一个固定排序，在搜索时，对当前状态依次检查每条规则，在当前状态未使用过的规则中找到第一条可应用规则应用于当前状态，得到的新状态设置为当前状态，并重复以上搜索。 如果当前状态无规则可用，或者所有规则已经用过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前的状态。重复以上搜索，直到找到问题的解。 递归的思想 回溯有多种实现方法,其中递归是一种最直接的实现方法. 回溯搜索算法 递归过程：BACKTRACK（DATA） DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。 回溯搜索算法 递归过程BACKTRACK(DATA) 1, IF TERM(DATA) RETURN NIL; //满足结束条件时返回 2, IF DEADEND(DATA) RETURN FAIL; //不合法状态的回溯点 3, RULES:=APPRULES(DATA);//可应用规则集 4, LOOP: IF NULL(RULES) RETURN FAIL; //全部规则均失败的回溯点 5, R:=FIRST(RULES); 6, RULES:=TAIL(RULES); //删去第一条规则，减少可应用规则表的长度 7, RDATA:=GEN(R, DATA); //调用规则R作用于当前状态，生成新状态 8, PATH:=BACKTRACK(RDATA);//对新状态递归调用 9, IF PATH=FAIL GO LOOP; 10, RETURN CONS(R, PATH); //返回解路径规则表 递归的思想（续） 存在问题及解决办法 解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径 一些深入问题 在回溯策略中，也可以引入一些与问题有关的信息来加快搜索解的速度。 基本思想(以皇后问题为例)： 尽可能选取划去对角线上位置数最少的。 回溯搜索算法1 BACKTRACK1（DATALIST） DATALIST：从初始到当前的状态表（逆向） 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。 回溯搜索算法1 1, DATA:=FIRST(DATALIST) //设置DATA为当前状态 2, IF MENBER(DATA, TAIL(DATALIST)) RETURN FAIL; //TAIL取尾操作，取DATALIST中除第一个以外的所有元素，如果DATA在TAIL(DATALIST）中存在，则说明有回路，返回FAIL，必须回溯. 3, IF TERM(DATA) RETURN NIL; //找到目标，结束 4, IF DEADEND(DATA) RETURN FAIL;//状态不合法，返回FAIL，必须回溯. 5, IF LENGTH(DATALIST)BOUND RETURN FAIL; //LENGTH计算DATALIST的长度，即搜索深度，当搜索深度大于BOUND值时，搜索失败，返回FAIL，必须回溯. 6, RULES:=APPRULES(DATA); //APPRULES计算DATA的可应用规则集，依某种原则（任意排列或启发式排列）排列后附给RULES. 7, LOOP: IF NULL(RULES) RETURN FAIL; //规则用完没找到目标，返回FAIL,必须回溯。 回溯搜索算法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, IF PATH=FAIL GO LOOP; //递归调用失败，转移调用另一规则进行测试 14, RETURN CONS(R, PATH); //返回解