状态空间法2009.ppt_第1页
状态空间法2009.ppt_第2页
状态空间法2009.ppt_第3页
状态空间法2009.ppt_第4页
状态空间法2009.ppt_第5页
已阅读5页,还剩51页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第二章自动智能的基本方法、2.1象征符方法物理象征符系统(象征符操作系统)有限合理性原理探索computerscienceempiricalinquiry:symbolsandsearch,herbertalexandersimon (1916-2001 ) 1975年第一届图灵奖获得者,LT发明者之一,1978年诺贝尔经济学奖获奖者,Allen Newell (1927-1992 ) 1975年第一届图灵奖获奖者LT逻辑理论家ILP归纳逻辑计程仪编程2.1.1状态空间法1 ) 问题描述状态:问题解决中各步骤的问题状况的数据结构状态描述:符号、字符串、矢量、二次元排列、树、表等数据结构所表示的

2、问题状态例2-1八数字问题,初始状态目标状态图2-1状态:盘版结构的各步骤的状态描述:格拉夫, 二次元矩阵运算符:将问题从一个状态描述转换为另一个状态描述的一组运算符:正在解决问题的所有运算符的集合,八数字运算符: EL-左空格,ER-右空格,EU-右空格,ed-。 (AB CD)/BC A/C D/B状态描述:二元树法:非终端:结节点算术计算符号,-,*,/终端结节点:变量,常数树图:图2-2代数简化树图,选择修正运算。 的双曲馀弦值。 字符串方法: ABCDBC ACDB前缀(仅作用于两个命令)目标状态单目标状态多目标状态:在某些条件下生成的子状态集合。 例如围棋的残局,八数字难题目标状态

3、:最上面一行不存在编号大于5的棋子,最优化问题:寻找遵循某规则的最佳路径,例如,用于解决八数字难题的算子最少,步行最少(最佳解搜索问题)状态描述的三原则: (1)状态描述方式选择有向图节点:路径:存在某节点系列Nn=(ni1,ni2,nij,nik ),设j=2,3,k,每个nij-1,如果存在子孙nij )路径费用:求路径上所有电弧费用的和最优化问题:图中的最小费用路径,路径: k=10 的双曲馀弦值。 的双曲馀弦值。k路径费用:、ni1、ni2、ni3、nik、C(ni4、ni5 )、最优化问题:图中求初始节点集合si的任一节点与营销对象节点t间的路径。 初始节点集合si的任一节点与营销对

4、象节点集合ti的任一节点之间的路径。 (3)格拉夫分类、明示格拉夫:各节点及其费用的弧形以格拉夫和表的形式,能够明确地给予隐含格拉夫:如果知道无限集合si和子孙运算符l,则si和l规定的图3 )状态空间解决例23的推销员旅行问题。 一位推销员正在修订旅行,必须访问图24所示的各城市。 从城市a开始每个城市访问一次,并且最多访问一次,返回城市a求出最短距离路径。状态记述:到目前为止访问的城市列表(a )初始状态:(A )目标状态:(A ),13,图2 4推销员旅行问题地图,运算符:接下来的城市(a)(b)(c )状态记述模式:用变量记述状态集合的表现式猴子状态:水平行走w上下箱x 0,1,(1=

5、箱上,上) 箱状态:水平移动y的四个状态: (w,x,y,z )运算符集合: goto(U) (a,0,b,0) goto(U) (U,0,b 0) grasp (c,1,c,0) grasp (c,1,c,1 )、自动智能经典问题: 1中有三个无论何时,只要野人的数量超过宣教师的数量,野人就吃宣教师。 他们怎样才能使所有人安全渡河呢?把28位皇后放在标准棋盘上,使每行、每列及每对折角线只包括一位以下的皇后。 画一部分状态空间图,写出运算符规则。图2 - 10过河问题、图2- 11八皇后问题、4 )状态空间搜索策略搜索过程要点:图论法:起点节点-运算符扩展后续节点(子节点) -指针- -检查后

6、续节点是否为目标节点-是,结束搜索。 上述路径是问题的解决。 不,继续扩展。 搜索控制:宽度优先搜索深度优先搜索,启发式文明棍搜索,图2-12宽度优先搜索,图2-13深度优先搜索,盲目的搜索,宽度优先搜索,深度优先搜索,启发式文明棍搜索:利用启发式文明棍信息进行搜索的过程启发式文明棍信息:用于加速搜索的特别信息, 图2-12如何喀呖声自动智能系统修正费用,如何选择下一个节点,如何决定在选择下一个节点的过程中生成的节点数,如何决定在检索树中废弃或修剪的节点? 评估函数(启发信息):估计节点可以扩展“希望”的程度的函数、节点1扩展前(b )节点1扩展后修剪:节点1扩展前后的搜索树, 已扩展节点未扩

7、展节点、启发式文明棍搜索算法:有序状态空间搜索定义: S -问题初始状态T -问题搜索格拉夫的数据结构在CLOSED表-节点扩展后,搜索格拉夫的数据结构中,s输入OPEN表示f(S )、失败、结束、f(ni )、i=1, 2 .修正minf (ni各后续节点f(nij ),nij,加上OPEN,加上从nj到节点nij的指针。 对f(nij )进行校正,将f(nij-1 )指针变更为j,f(nij ),而不是f(n )小-大排序,n,n,f(nij-1 )指针评估函数: f(n)=d(n) w(n) d(n)-搜索树节点n的深度w(n)-节点n弄错了棋子数,分别为283167、283167、28

8、3167、2345、23345、2831645、83145、2376 数字难题解析图之一,f(S)=d(n) w(n ), A*算法是h*(n)=k (n ) :从源节点s到目的地节点n的最小路径费用f(n)=g(n) h(n) : f*(n )的估计f*(S)=h*(S) :从源节点到目的地节点的最佳A*的可接受性:对于任何格拉夫g, 如果存在从s到t的路径,则搜索算法总是在从s到t的最佳路径上终止,而(1)每个到达一个营销对象节点时,该搜索算法证明算法就终止。 结论1 :对于A*有限图总是结束的结论1 :对于A*无限图也是结束的证明:反证法,假设A*不结束的d * (n ) :基于A*的搜

9、索树中从s到任意节点n的搜索默示图中最短路径长度e :图中所有弧的最小长度g (n ) g * (n ) d * (n ) eh 证明:在A*结束之前,OPEN表总是有一个节点,其中f(n)f*(s )是S=n0,n1,nt是s到t的最佳路径A*结束之前,n是OPEN表的这个序列的节点。 因此,在无穷大的格拉夫情况下,A*必须终止,因为g(n)=g*(n) f(n)=g*(n) h(n )和h(n)h*(n)f(n)g*(n )是无穷大的。 结论1 :只要存在从s到营销对象节点的路径,A*就必须终止。 推论1:OPEN表中具有任何f(n)f*(S )的结节点n最终由A*选择作为扩展结节点。 的双曲馀弦值。 a. A*必须找到关营销对象节点并退出。 如果存在从s到营销对象节点t的路径,则OP

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论