人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习.pdf》由会员分享,可在线阅读,更多相关《人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习.pdf(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、山东大学 期末考试知识点复习第五章第五章状态空间搜索策略状态空间搜索策略搜索是人工智能的一个基本问题,是推理不可分割的一部分.搜索是求解问题的一种方法,是根据问题的实际情况,按照一定的策略或规则,从知识库中寻找可利用的知识,从而构造出一条使问题获得解决的推理路线的过程。搜索包含两层含义:一层含义是要找到从初始事实到问题最终答案的一条推理路线;另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线.搜索可分为盲目搜索和启发式搜索两种。1 11 1盲目搜索策略盲目搜索策略 1状态空间图的搜索策略为了利用搜索的方法求解问题,首先必须将被求解的问题用某种形式表示出来。一般情况下,不同的知识表示对应
2、着不同的求解方法.状态空间表示法是一种用“状态”和“算符 表示问题的方法。状态空间可由一个三元组表示(S0,F,Sg)。利用搜索方法求解问题的基本思想是:首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态,选择一适当的算符作用于当前状态,生成一组后继状态(或称后继节点),然后检查这组后继状态中有没有目标状态。如果有,则说明搜索成功,从初始状态到目标状态的一系列算符即是问题的解;若没有,则按照某种控制策略从已生成的状态中再选一个状态作为当前状态,重复上述过程,直到目标状态出现或不再有可供操作的状态及算符时为止.算法 51状态空间图的一般搜索算法建立一个只含有初始节点 S0的搜索图 G,
3、把 S0放入 OPEN 表中。建立 CLOSED 表,且置为空表.判断 OPEN 表是否为空表,若为空,则问题无解,退出。选择 OPEN 表中的第一个节点,把它从 OPEN 表移出,并放入 CLOSED 表中,山东大学 期末考试知识点复习将此节点记为节点 n。考察节点 n 是否为目标节点,若是,则问题有解,并成功退出。问题的解即可从图 G 中沿着指针从 n 到 S0的这条路径得到.扩展节点 n 生成一组不是 n 的祖先的后继节点,并将它们记作集合 M,将 M中的这些节点作为 n 的后继节点加入图 G 中.对那些未曾在 G 中出现过的(即未曾在 OPEN 表上或 CLOSED 表上出现过的)M
4、中的节点,设置一个指向父节点(即节点 n)的指针,并把这些节点加入 OPEN表中;对于已在 G 中出现过的 M 中的那些节点,确定是否需要修改指向父节点(n节点)的指针;对于那些先前已在 G 中出现并且已在 COLSED 表中的 M 中的节点,确定是否需要修改通向它们后继节点的指针。按某一任意方式或按某种策略重排 OPEN 表中节点的顺序.转第步.2宽度优先搜索策略宽度优先搜索是一种盲目搜索策略。其基本思想是,从初始节点开始,逐层对节点进行依次扩展,并考察它是否为目标节点,在对下层节点进行扩展(或搜索)之前,必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中,未扩展节点表 OPEN 中的
5、节点排序准则是:先进入的节点排在前面,后进入的节点排在后面(即将扩展得到的后继节点放于 OPEN 表的末端).宽度优先搜索的盲目性较大,搜索效率低,这是它的缺点.但宽度优先搜索策略是完备的,即只要问题有解,用宽度优先搜索总可以找到它的解。3深度优先搜索深度优先搜索也是一种盲目搜索策略,其基本思想是:首先扩展最新产生的(即最深的)节点,即从初始节点 S0开始,在其后继节点中选择一个节点,对其进行考察,若它不是目标节点,则对该节点进行扩展,并再从它的后继节点中选择山东大学 期末考试知识点复习一个节点进行考察。依此类推,一直搜索下去,当到达某个既非目标节点又无法继续扩展的节点时,才选择其兄弟节点进行
6、考察。深度优先搜索与宽度优先搜索的区别就在于:在对节点 n 进行扩展时,其后继节点在OPEN表中的存放位置。宽度优先搜索是将后继节点放入OPEN表的末端,而深度优先搜索则是将后继节点放入 OPEN 表的前端.4有界深度优先搜索对于许多问题,其状态空间搜索树的深度可能为无限深。为了避免搜索过程沿着无穷的路径搜索下去,往往对一个节点扩展的最大深度进行限制。任何节点如果达到了深度界限,就把它作为没有后继节点进行处理,即对另一个分支进行搜索。在有界深度优先搜索算法中,深度界限的选择很重要。选择过大,可能会影响搜索的效率;选择的过小,有可能求不到解.有界深度优先搜索策略是不完备的。5代价树的宽度优先搜索
7、前面的搜索算法没有考虑搜索的代价问题,即假设状态空间图中各节点之间的有向边的代价是相同的。在实际问题求解中,往往是将一个状态变换成另一个状态时所付出的操作代价(或费用)是不一样的,即状态空间图中各有向边的代价是不一样的。把有向边上标有代价的搜索树称为代价搜索树,简称代价树。代价树宽度优先搜索的基本思想是:每次从 OPEN 表中选择一个代价最小的节点,移入 COLSED 表.因此,每当对一节点扩展之后,就要计算它的所有后继节点的代价,并将它们与 OPEN 表中已有的待扩展的节点按代价的大小从小到大依次排序。而从OPEN 表选择被扩展节点时即选择排在最前面的节点(代价最小)。代价树的宽度优先搜索算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五章状态空间搜索策略 人工智能 第五 状态 空间 搜索 策略 山东大学 期末 考试 知识点 复习
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内