《状态空间法2009》由会员分享，可在线阅读，更多相关《状态空间法2009（56页珍藏版）》请在金锄头文库上搜索。
1、第二章 人工智能的基本方法,2.1 符号方法 物理符号系统（符号操作系统） 假设 有限合理性原理 搜索 Computer Science Empirical Inquiry：Symbols and Search,Allen Newell （1927-1992 ） 1975年第一届图灵奖获得者，LT发明者之一，美国人工智能学会AAAI的发起人之一,LT 逻辑理论家 ILP 归纳逻辑程序设计2.1.1 状态空间法1）问题描述状 态：问题求解中每一步问题状况的数据结构状态描述：符号、字符串、向量、二维数组、树、表等数据结构表示的问题状态 例 2-1 八数码难题,初始状态 目标状态 图 2-1 八数码
2、难题,状 态：棋盘布局每一步的状态 状态描述：图表、二维矩阵 算 符：把问题从一种状态描述转变为另一种状态描述的运算 算符集合：问题求解中所有算符的集合,八数码算符：EL- 空格左移ER-空格右移EU-空格上移ED-空格下移约 束：E1，4，6 - 禁止ELE1，2，3 - 禁止EUE3，5，8 - 禁止ERE6，7，8 - 禁止ED,例2-2 代数式简化问题。(AB+CD)/BC A/C+D/B状态描述：二元树法：非 终 端：节点算术运算符号+、-、*、/终端节点：变量、常量树图：,图2-2 代数简化树图,算符：代数规则： 分配律、结合律、。 字符串法： ABCDBC ACDB前缀（只作用于
3、两个运算数） 目标状态 单一目标状态 多目标状态：某一条件下产生的子状态集合。例如，象棋、围棋的终局,八数码难题目标状态：最上面一行不存在编号大于5的棋子,最优化问题：寻找遵循某种规则的最优路径例如，八数码难题求解中使用的算符最少，走步最少（最优解搜索问题） 状态描述三原则： （1）状态描述方式选择，尤其是初始状态 （2）算符集合及其对状态描述的作用 （3）目标状态描述特性2）图示法（问题求解的抽象描述） （1）图论的几个概念,图：节点的集合，包括有限节点或无限节点。 有向图：节点之间用有向弧线联结的图。 节点：,路径：存在某个节点序列Nn=（ni1, ni2, nij ,nik）, 令j=2
4、,3, ,k，对每一个nij-1,如果都存在后裔nij，则称序列Nn为长度为k的路径 可达节点：如果两节点之间存在路径，则后裔是祖先的可达节点 弧线费用：弧线表示的算符计算的费用c(ni, nj) 路径费用：路径上所有弧线费用之和 优化问题：寻求图中最小费用路径,路径：k=10 ，k=6 可达节点：j=2，3，。，k路径费用：,ni1,ni2,ni3,nik,C(ni4, ni5),优化问题：寻求图中最小费用路径 (2) 问题求解的图描述 初始节点S与目标节点集合ti中任一节点之间的路径。 初始节点集合si中任一节点与目标节点T之间的路径。 初始节点集合si中任一节点与目标节点集合ti中任一节
5、点之间的路径。 (3) 图分类,显式图：各节点及其费用的弧线可以用图表或表格的形式明确给出 隐式图：已知无限集合si 及后裔算符L，则si和L规定的图 3）状态空间求解举例例 2-3 推销员旅行问题。一个推销员计划作一次旅行，必须访问图2-4所示的每个城市。从城市A出发，访问每一个城市一次，且最多一次，并返回城市A，求最短距离路线。,状态描述：目前为止访问过的城市列表（A）初始状态:（A）目标状态: （A A）,13,图2 4 推销员旅行问题地图,算符：下一步走向的城市 (a)(b)(c)(d)(e) 约束：每个城市只能走过一次，A除外,(AE),例2-2猴子和香蕉问题,图 2-8 猴子和香蕉
6、问题,状态描述模式：用变量描述状态集合的表达式 猴子状态：水平走动 w上下箱子 x0,1，( 1=箱上，0 =箱下)摘取香蕉 z0,1，(1= 拿到,0 = 未拿到）。 箱子状态：水平移动Y 四种状态：（W, x, Y, z） 算符集合： goto(U) (a,0,b,0) goto(U) (U,0,b,0) pushbox(V) (b,0,b,0) pushbox(V) (V,0,V,0) climbbox (V,0,V,0) climbbox (V,1,V,0) grasp (c,1,c,0) grasp (c,1,c,1),人工智能经典问题： 1 设有三个传教士和三个野人来到河边，打算乘
7、一只船从河右岸渡到河左岸去。该船的最大负荷能力为两人。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？ 2 把八个皇后摆在一个标准的国际象棋棋盘上，使得每行、每列以及每个对角线上都只包含不多于一个皇后。画出部分状态空间图，写出算符规则。,图2 - 10 过河问题,图 2- 11 八皇后问题,4）状态空间搜索策略 搜索过程要点： 图论法：起始节点 -算符扩展后继节点（子节点）-加指针 - -检查后继节点是否为目标节点 -是，终止搜索。上述路径为问题的解。否，继续扩展。 搜索控制：宽度优先搜索深度优先搜索启发式搜索,图2-12 宽度优先搜
8、索 图2-13 深度优先搜索 盲目搜索: 宽度优先搜索,深度优先搜索 启发式搜索：利用启发式信息进行搜索的过程启发式信息：用来加速搜索的特别信息,图 2 - 12 人工智能系统计算费用,如何选择下一节点？,如何决定选定下一个节点的过程中生成的节点数？,如何决定搜索树中抛弃或修剪的节点？,估价函数（启发信息）：估计节点可扩展“希望”程度的 函数,S,1,2,3,4,5,6,S,1,2,3,4,5,6,（a）节点1扩展前 （b）节点1扩展后,修剪：节点1扩展前后的搜索树,已扩展节点 未扩展节点,启发式搜索算法：有序状态空间搜索 定义：S - 问题初始状态T - 问题目标状态ni - i时刻的问题状
9、态f(n) - 估价函数，单调减OPEN表-节点未扩展时，搜索图的数据结构CLOSED表-节点扩展后，搜索图数据结构,S入OPEN 标出f(S),失败，退出,计算f(ni)，i=1,2 MINf(ni)入CLOSED,Y,N,Y,N,扩展ni,生成全部后继节点。计算每个后继节点f(nij),nij,加入OPEN，从nj加一指向节点nij的指针。计算f(nij),按 f(n)小-大排序,N,N,f(nij)取代 f(nij-1) 指针改指j,f(nij)取代 f(nij-1) nij移回OPEN,成功，退出,启发式有序搜索算法,Y,Y,N,Y,Y,N,Y,N,例 八数码难题。 估价函数：f(n)
10、=d(n)+w(n) d(n)-搜索树节点n的深度w(n)-节点n错放棋子数,2 8 3 1 6 4 7 5,1 2 3 8 4 7 6 5,初始状态S 目标状态T,2 8 3 1 6 4 7 5,2 8 3 1 6 47 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,2 8 31 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,8 3 2 1 4 7 6 5,2 8 3 7 1 46 5,2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2 38 4 7 6 5,1 2 3 8 4 7 6 5,2 31 8 47 6 5
11、,八数码难题解图之一,f(S)=d(n)+w(n),A*算法 证明h*(n)= k (n,T) ：从节点n到目标节点最小路径费用g*(n) = k (S,n)：从起始节点S到节点n最小路径费用f(n) = g(n) + h(n) ： f*(n)的一个估计f*(S) = h*(S) :从起始节点到目标节点的最佳路径 .,S,n,T,f*(n)=g*(n)+h*(n),A*的可纳性可纳性：对于任意图G，如果存在从S到T的路径，那么，搜索算法总能终止在一条从S到T的最佳路径上，则此搜索算法可纳证明： （1）每当一个目标节点可达时，算法终止。结论1：A*对有限图总是终止的 结论1：A*对无限图也是终止
12、的证明：反证法 ，假设A*不终止,设：d*(n) ： A*产生的搜索树中从S到任一节点n的搜索隐含图中最短路经长度e ：图中所有弧的最小长度g(n) g*(n) d*(n) e h(n) 0 f(n) g(n) d*(n) e 说明：即使A*扩展的节点n的f(n)最小，但仍具有任意大的d*(n)，如果A*不终止，节点就具有任意大的f(n)，这与节点扩展最小f(n)相矛盾，所以，算法终止。,证明： A*终止之前，OPEN表上总有一个节点使得f(n)f*(s)设：S=n0,n1,，nt 是S到T的一条最佳路径A*终止前，令n是OPEN表上这个序列的一个节点存在： f(n) = g(n) + h(n
13、) n在最佳路径上， g(n) = g*(n)f(n) = g*(n) + h(n)又 h(n) h*(n) f(n) g*(n) + h*(n)=f*(n),在最佳路径上的任一节点费用 f(n) f*(S) 说明即使在A*还没有终止的OPEN表上，节点的最小f值也不会变为无界。因此，对于无限图来说，A*必须终止。结论1：只要存在一条从S到某个目标节点的路径，则A*必须终止。推论1：OPEN表上任一具有f(n)f*(S)的节点n，最终都将被A*选为扩展节点。,可纳性证明： a. A*一定会找到一个目标节点而终止。如果存在一条从S到目标节点T的路径，终止之前OPEN表不会空。因为结论1，总会有一
14、个节点在OPEN表上，且是最佳路径上。 b. A*只能找到一条最佳路径而终止。假定A*未找到一条最佳路径而在目标节点t终止，则：f(t)=g(t)f*(S)，,根据结论1，终止前OPEN表上存在一个节点n，且满足：f(n)f*(S)h1(n)，且存在一条从S到T的最佳路径, A1, A2都中止在最佳路径上。,证明：在终止的地方，如果图G的节点n能够用A2来扩展，那么，也必定能用A1来扩展。因此， A1扩展的节点数至少与用A2扩展的节点数一样多。 n = S，若S=T，两种算法都不必扩展节点 b. 若ST，两种算法都要扩展S归纳法假设：A1扩展了A2搜索树中深度 k 的所有节点证明：A2搜索树中由A2扩展的深度k+1的任意节点n也可由A1扩展,
