搜索推理技术之搜索技术ppt课件.ppt

《搜索推理技术之搜索技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chap3-1搜索推理技术之搜索技术1主要内容概述图搜索策略盲目搜索策略启发式搜索策略2概述搜索是人工智能的一个基本策略，是推理不可分割的一部分；搜索是求解问题的一种方法；为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来3例如:Romania在Romania度暑假;目前在Arad市.有张明天从Bucharest离开Romania的机票目标状态的形式化描述:到达Bucharest问题的形式化描述:状态:所有城市行动:从一个城市到另一个城市求解:找到一个城市序列，e.g.,Arad,Si

2、biu,Fagaras,Bucharest4例如:Romania5问题的形式描述问题形式化定义的4部分：问题的初始状态：e.g.,“atArad”动作/操作描述：常见形式是一个后继函数。e.g.,S(Arad)={,…}目标测试：确定给定状态是否是目标状态显式测试：e.g.,x="atBucharest"隐式测试：e.g.,Checkmate(x)路径耗散函数：给每条路径分配一个数值化的耗散值。问题的解：引导智能体从初始状态到达目标状态的行动/操作序列6例如：8数

3、码难题状态?：操作/动作?目标测试?路径耗散?数字的位置空格的移动:上、下、左、右目标状态(问题给出)空格移动一次，耗散费用值加17搜索技术的分类盲目搜索(无信息搜索)：在搜索过程中，只按照预定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。特点：搜索带有盲目性，效率不高，如果遇到比较复杂的问题，其求解的效率可能就相当低。用途：用于解决比较简单的问题。8搜索技术的分类启发式搜索（有信息搜索）：在搜索求解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索

4、朝着最有希望的方向前进，加速问题的求解，并找到最优解。启发式搜索优点：利用了问题本身的特性存在的困难：并不是对所有的问题都能方便地抽取问题的有关特性和信息9图搜索策略什么是状态空间图？使用图示的方式用状态空间图对一个问题进行描述的方法。状态空间图是一个有向图。求解问题就相当于在有向图上寻找一条从某一节点（初始状态节点）到另一节点（目标节点）的路径。10图搜索策略问题1如何保存问题的状态空间？保存所有状态空间？保存部分状态空间？问题2如何来生成并存储与问题有关的部分状态空间？缺点：需要太多的存储空间11图

5、搜索策略求解的基本思想将问题的初始状态（状态空间图中的初始节点）当作当前节点，选择一适当的算符作用于当前状态，生成一组后继状态（或后继节点）检查这组后继状态中有没有目标状态，如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解。若没有，则按照某种控制策略从已生成的状态中再选择一个状态作为当前状态。重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。12图搜索策略状态空间图:由节点和分支构成的集合。有限节点图：节点数目有限的状态空间图有向分支：有方向的分支无向分支：没有方向的

6、分支父节点：当存在从节点N1到节点N2的路径时，节点N1被称为节点N2的父节点；子节点：点N2被称为节点N1的。闭路：如果从N1到N2的路径只有一条的时候，而且两端的节点相同，则这种路径称为。13图搜索策略14图搜索策略已扩展节点和未扩展节点用适合的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求后继节点的过程。已扩展的节点:对状态空间图中，已求出了其的后继节点的节点。未扩展节点，尚未求出其的后继节点的节点未扩展OPEN表扩展CLOSED表15图搜索策略图搜索算法流程：建立一个只含有初始节点

7、S的搜索图G,把S放入OPEN表中。建立CLOSED表，且置为空表。LOOP:若OPEN表是空表，则失败退出。选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n。若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的。扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。对那些未曾在G中出现过的，M成员设置一个通向n的指针，把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每

8、一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。按某一任意方式或按某个试探值，重排OPEN表。GOLOOP16图搜索策略算法流程开始节点n是否为目标节点失败退出YN根据后入先出或先入先出的原则从Open表中选择一个节点，并置为n将n的子节点中未包含在Closed表中的节点加入Open表中Open表是否空成功退出YN将初始节点加入Open表Closed表置