状态空间法word版本.ppt

《状态空间法word版本.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、状态空间法LT逻辑理论家ILP归纳逻辑程序设计2.1.1状态空间法1）问题描述状态：问题求解中每一步问题状况的数据结构状态描述：符号、字符串、向量、二维数组、树、表等数据结构表示的问题状态例2-1八数码难题初始状态目标状态图2-1八数码难题X1X2X3X4X5X6X7X8X1X2X3X4X5X6X7X8状态：棋盘布局每一步的状态状态描述：图表、二维矩阵算符：把问题从一种状态描述转变为另一种状态描述的运算算符集合：问题求解中所有算符的集合八数码算符：EL--空格左移ER--空格右移EU--空格上移ED--空格下移约束：E1，4，6--禁止E

2、LE1，2，3--禁止EUE3，5，8--禁止ERE6，7，8--禁止ED例2-2代数式简化问题。(AB+CD)/BCA/C+D/B状态描述：二元树法非终端：节点算术运算符号+、-、*、/终端节点：变量、常量树图：ABCDBCACDB图2-2代数简化树图算符：代数规则：分配律、结合律、。。。字符串法：ABCDBCACDB前缀（只作用于两个运算数）目标状态单一目标状态多目标状态：某一条件下产生的子状态集合。例如，象棋、围棋的终局八数码难题目标状态：最上面一行不存在编号大于5的棋子最优化问题：寻找遵循某种规则的最

3、优路径例如，八数码难题求解中使用的算符最少，走步最少（最优解搜索问题）状态描述三原则：（1）状态描述方式选择，尤其是初始状态（2）算符集合及其对状态描述的作用（3）目标状态描述特性2）图示法（问题求解的抽象描述）（1）图论的几个概念图：节点的集合，包括有限节点或无限节点。有向图：节点之间用有向弧线联结的图。节点：nj祖先后裔算符状态ini状态j图2-3节点定义路径：存在某个节点序列N[n]=（ni1,ni2,…,nij,…,nik）,令j=2,3,……,k，对每一个nij-1,如果都存在后裔nij，则称序列N[n]为长度为k的路径可达节点：

4、如果两节点之间存在路径，则后裔是祖先的可达节点弧线费用：弧线表示的算符计算的费用c(ni,nj)路径费用：路径上所有弧线费用之和优化问题：寻求图中最小费用路径路径：k=10，k=6可达节点：j=2，3，。。。，k路径费用：ni1ni2ni3nikC(ni4,ni5)优化问题：寻求图中最小费用路径(2)问题求解的图描述初始节点S与目标节点集合{ti}中任一节点之间的路径。初始节点集合{si}中任一节点与目标节点T之间的路径。初始节点集合{si}中任一节点与目标节点集合{ti}中任一节点之间的路径。(3)图分类显式图：各节点及其费用的弧线可以用

5、图表或表格的形式明确给出隐式图：已知无限集合{si}及后裔算符L，则{si}和L规定的图3）状态空间求解举例例2-3推销员旅行问题。一个推销员计划作一次旅行，必须访问图2-4所示的每个城市。从城市A出发，访问每一个城市一次，且最多一次，并返回城市A，求最短距离路线。状态描述：目前为止访问过的城市列表（A…）初始状态:（A）目标状态:（A……A）ABCDE776105691013图2–4推销员旅行问题地图算符：下一步走向的城市(a)(b)(c)(d)(e)约束：每个城市只能走过一次，A除外(AE)(A)(AB)(AC)(AD)(ACD)(AC

6、DE)(ACDEB)(ACDEBA)目标节点初始节点图2-5推销员旅行问题搜索树76101356107例2-2．猴子和香蕉问题acb猴子香蕉箱子图2-8猴子和香蕉问题状态描述模式：用变量描述状态集合的表达式猴子状态：水平走动w上下箱子x[0,1]，(1=箱上，0=箱下)摘取香蕉z[0,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

7、,V,0)climbbox(V,1,V,0)④grasp(c,1,c,0)grasp(c,1,c,1)(a,0,c,0)初始状态goto(U)(U,0,b,0)goto(U)(b,1,b,0)U=b,climbboxU=b,pushbox(V)(V,0,V,0)pushbox(V)climbbox(V,1,V,0)V=c,grasp(c,1,c,1)目标状态goto(U)(U,0,V,0)goto(U)图2-9猴子和香蕉状态空间图人工智能经典问题：1设有三个传教士和三个野人来到河边，打算乘一只船从河右岸渡到河左岸去。该船的最大负荷能力为两人

8、。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？2把八个皇后摆在一个标准的国际象棋棋盘上，使得每行、每列以及每个对角