第一章 搜索问题ppt课件.ppt

《第一章 搜索问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章搜索问题人类思维过程：搜索问题答案搜索过程1一个简单的例子设有三枚钱币，其排列处在“正，正，反”状态，现允许每次可翻动其中任意一个钱币，问只允许操作三次的情况下，如何翻动钱币使其变成“正，正，正”或“反，反，反”状态。2若“正面”用“1”表示，“反面”用“0”表示，则问题化成求解从初始状态（1,1,0）到目标状态（1，1，1）或(0,0,0)的路径问题，且该路径的长度为3。即：（1，1，0）--------->（1，1，1）或（1，1，0）--------->（0，0，0）一个简单的例子3状态图4状态空间图人工智能科学中，把这种描述问题的有向图称为状态空间图，简称状态图

2、(statediagram)。状态图中的一个结点(node)代表问题中的一种格局或状态。边表示两个结点之间的某种联系（某种操作、规则、变换、算子、通道或关系）。在状态图中，从初始结点到目标结点的一条路径或者所找到的目标结点就是相应的一个解。5总结：问题的求解状态空间的搜索。6搜索问题S0Sg问题的全状态空间搜索空间解路径7搜索问题内容：状态空间的搜索问题。搜索策略：确定如何选取规则。盲目搜索(无信息引导的搜索策略)不考虑给定问题的特定知识，按固定的规则排序，依次调用规则或随机调用规则。启发式搜索(有信息引导的搜索策略)考虑给定问题的特定知识，动态确定规则的排序，优先调用较合

3、适的规则。8搜索问题盲目搜索算法：回溯法、深度优先法、宽度优先法启发式搜索算法：爬山法最佳图搜索法(A*)、分支界限法、动态规划法一般与或图搜索法(AO*)、α-β剪支法、极大极小值法等9搜索问题讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。10状态图11当前状态目标状态gr1r2ri-1ri1.1回溯策略子状态12递归法每个状态及其子状态执行同样的操作递归调用同一过程13递归法递归过程BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。

4、RULES：当前状态可用规则集序列表R：当前调用的规则14递归法RDATA：新生成的子状态。PATH：当前解路径表(当前状态到目标状态)NIL：空表FAIL：回溯点标记LOOP：循环标号15记忆测试DATARULESR当前状态。当前状态可用规则集序列表当前调用的规则16记忆测试新生成的子状态。当前解路径表(当前状态到目标状态)空表回溯点标记RDATAPATHNILFAILLOOP循环标号17递归过程BACKTRACK(DATA)IFTERM(DATA)RETURNNIL;如果当前状态即为目标状态，则返回空表IFDEADEND(DATA)RETURNFAIL;如果当前状态不合法

5、，则返回FAIL，必须回溯RULES:=APPRULES(DATA);计算当前状态可用的规则集并排序，赋给RULESLOOP:IFNULL(RULES)RETURNFAIL;如果规则用完，则返回FAIL，必须回溯18递归过程BACKTRACK(DATA)R:=FIRST(RULES);取第一条可用规则RULES:=TAIL(RULES);从规则集中删除第一条规则RDATA:=GEN(R,DATA);对当前状态调用规则R，生成新状态19递归过程BACKTRACK(DATA)8PATH:=BACKTRACK(RDATA);对新状态递归调用本过程，将新状态到目标状态的路径赋给PAT

6、HIFPATH=FAILGOLOOP;如果递归调用失败，即当前规则失败，则转移调用另一规则。RETURNCONS(R,PATH);如果递归调用成功，将当前规则加到新状态解路径规则表前面并返回解路径规则表20递归过程BACKTRACK设置两个回溯点:（1）当前状态非法（2）当前状态的所有子状态均无解自变量：当前状态返回值：当前状态到目标状态的解路径规则表或FAIL21四皇后问题要求:每行、每列及对角线只能有一个棋子22QQL=((1,1)(2,3))当前状态DATA(1,1)(2,3)棋局状态的表示23四皇后问题DATA=L(表)1、综合数据库：L元素个数----最多为4L--

7、-当前棋局中各棋子的位置表。L的元素---当前棋局中每个棋子的位置(ij)1≤i,j≤424四皇后问题2、规则集：按行摆棋子:If1≤i≤4且Lenth(DATA)=i-1thenAPPEND(DATA(ij))(1≤j≤4)当前棋盘中已经有i-1个棋子在第i行第j列摆一个棋子，即在(ij)位置摆一个棋子25四皇后问题规则集：从第一行开始逐行摆棋子，每行摆1个棋子,每行逐列试探摆棋子。4行4列，共16个摆放规则Rij26i=1时没有棋子Lenth(DATA)=0=i-1Q在第1行摆1个棋子四皇后问题27