状态空间法word版本

状态空间法

LT逻辑理论家

ILP归纳逻辑程序设计2.1.1状态空间法1）问题描述

状态：问题求解中每一步问题状况的数据结构状态描述：符号、字符串、向量、二维数组、树、表等数据结构表示的问题状态

例2-1八数码难题初始状态目标状态图2-1八数码难题

X1X2X3X4X5X6X7X8X1X2X3X4X5X6X7X8状态：棋盘布局每一步的状态状态描述：图表、二维矩阵算符：把问题从一种状态描述转变为另一种状态描述的运算算符集合：问题求解中所有算符的集合

八数码算符：EL--空格左移ER--空格右移EU--空格上移ED--空格下移约束：E1，4，6--禁止ELE1，2，3--禁止EUE3，5，8--禁止ERE6，7，8--禁止ED例2-2代数式简化问题。(AB+CD)/BCA/C+D/B状态描述：二元树法非终端：节点算术运算符号+、-、*、/终端节点：变量、常量树图：

ABCDBCACDB图2-2代数简化树图

算符：代数规则：分配律、结合律、。。。字符串法：ABCDBCACDB前缀（只作用于两个运算数）目标状态单一目标状态多目标状态：某一条件下产生的子状态集合。例如，象棋、围棋的终局八数码难题目标状态：最上面一行不存在编号大于5的棋子

最优化问题：寻找遵循某种规则的最优路径例如，八数码难题求解中使用的算符最少，走步最少（最优解搜索问题）

状态描述三原则：（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的路径可达节点：如果两节点之间存在路径，则后裔是祖先的可达节点

弧线费用：弧线表示的算符计算的费用c(ni,nj)路径费用：路径上所有弧线费用之和优化问题：寻求图中最小费用路径路径：k=10，k=6可达节点：j=2，3，。。。，k路径费用：ni1ni2ni3nikC(ni4,ni5)优化问题：寻求图中最小费用路径(2)

问题求解的图描述初始节点S与目标节点集合{ti}中任一节点之间的路径。初始节点集合{si}中任一节点与目标节点T之间的路径。初始节点集合{si}中任一节点与目标节点集合{ti}中任一节点之间的路径。

(3)图分类

显式图：各节点及其费用的弧线可以用图表或表格的形式明确给出隐式图：已知无限集合{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)(ACDE)(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,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设有三个传教士和三个野人来到河边，打算乘一只船从河右岸渡到河左岸去。该船的最大负荷能力为两人。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？2把八个皇后摆在一个标准的国际象棋棋盘上，使得每行、每列以及每个对角线上都只包含不多于一个皇后。画出部分状态空间图，写出算符规则。图2-10过河问题？图2-11八皇后问题？？？？？4）状态空间搜索策略搜索过程要点：图论法：起始节点-〉算符Γ扩展后继节点（子节点）-〉加指针-〉…-〉检查后继节点是否为目标节点-〉是，终止搜索。上述路径为问题的解。否，继续扩展。搜索控制：宽度优先搜索

深度优先搜索

启发式搜索

图2-12宽度优先搜索图2-13深度优先搜索盲目搜索:宽度优先搜索,深度优先搜索启发式搜索：利用启发式信息进行搜索的过程启发式信息：用来加速搜索的特别信息

计算费用信息量完整信息规则应用费用控制策略费用系统总费用图2-12人工智能系统计算费用……....如何选择下一节点？….如何决定选定下一个节点的过程中生成的节点数？如何决定搜索树中抛弃或修剪的节点？估价函数（启发信息）：估计节点可扩展“希望”程度的函数S123456S123456（a）节点1扩展前（b）节点1扩展后

修剪：节点1扩展前后的搜索树已扩展节点未扩展节点启发式搜索算法：有序状态空间搜索定义：S

---问题初始状态T---问题目标状态ni---i时刻的问题状态

f(n)---估价函数，单调减OPEN表---节点未扩展时，搜索图的数据结构CLOSED表---节点扩展后，搜索图数据结构

S入OPEN标出f(S)OPEN空？失败，退出计算f(ni)，i=1,2..MIN[f(ni)入CLOSEDYNni=T？YN扩展ni,生成全部后继节点。计算每个后继节点f(nij)nij=T？nij在CLOSED？nij,加入OPEN，从nj加一指向节点nij的指针。计算f(nij),按f(n)小-〉大排序NNf(nij)<f’(nij-1)？f(nij)取代f’(nij-1)指针改指jf(nij)<f’(nij-1)？f(nij)取代f’(nij-1)nij移回OPEN成功，退出启发式有序搜索算法

YYNnij在OPEN？YYNYN例八数码难题。估价函数：f(n)=d(n)+w(n)d(n)----搜索树节点n的深度w(n)----节点n错放棋子数2831647512384765初始状态S目标状态T28316475283164752831476528316475

46

4628314765523184765

5283147656

8321476528371465672318476523184765

57712384765

51238476523184765

57八数码难题解图之一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):从起始节点到目标节点的最佳路径.SnTf*(n)=g*(n)+h*(n)A*的可纳性可纳性：对于任意图G，如果存在从S到T的路径，那么，搜索算法总能终止在一条从S到T的最佳路径上，则此搜索算法可纳证明：（1）每当一个目标节点可达时，算法终止。结论1：A*对有限图总是终止的

结论1：A*对无限图也是终止的证明：反证法，假设A*不终止

OPENCLOSED终止：找到目标用完OPEN节点设：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)相矛盾，所以，算法终止。

d*(n)=3g*(n)3ef*(n)=g*(n)+h*(n)nSe

证明：A*终止之前，OPEN表上总有一个节点使得f(n)f*(s)设：S=[n0,n1,…，nt]是S到T的一条最佳路径A*终止前，令n’是OPEN表上这个序列的一个节点

存在：f(n’)=g(n’)+h(n’)

∵

n’在最佳路径上，

∴

g(n’)=g*(n’)

f(n’)=g*(n’)+h(n’)又∵h(n’)h*(n’)∴f(n’)

g*(n’)+h*(n’)=f*(n’)n0n1n2n3nk…….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，总会有一个节点在OPEN表上，且是最佳路径上。b.A*只能找到一条最佳路径而终止。假定A*未找到一条最佳路径而在目标节点t终止，则：f(t)=g(t)>f*(S)，根据结论1，终止前OPEN表上存在一个节点n’，且满足：f(n’)<f*(S)<f(t)因此，这一步A*将选取n’而不是t进行扩展，与假设A*已终止矛盾。

得证。

结论2：A*算法可纳

A*算法的最优性

h(n)=0（无启发信息）是h*(n)的下界设两种A*算法A1,A2有下式：

f1(n)=g1(n)+h1(n)f2(n)=g2(n)+h2(n)

设：n≠

T

，h2(n)>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扩展

A2d=knA1d=k+1

根据假设，A2搜索树中n的任一父辈节点都可由A1扩展。因此，节点n也在搜索树A1中存在：

g1(n)g2(n)(1)

反证：A1不能扩展由A2扩展的节点n

A1终止的地方，节点n必须在OPEN表上。因为A1已扩展了n的一个父辈节点。由于A1没有扩展节点n而在最小路径上终止。所以：

f1(n)=g1(n)+h1(n)f*(S)(2)g2(n)+h1(n)g1(n)+h1(n)f*(S)(3)h1(n)f*(S)–g2(n)(4)

由A*选来扩展的任一节点n，满足：f(n)f*(S)由于A2已经扩展了节点n，所以：

f2(n)=g2(n)+h2(n)f*(S)(5)h2(n)f*(S)–g2(n)(6)比较（4），（6）两式得：

h2(n)f*(S)–g2(n)h1(n)至少在节点n，h1(n)=h2(n)，与A2比A1有更多信息的假设矛盾。

结论4：若A1和A2是A*的两种搜索形式，且A2比A1有更多的信息。则在从S到T的路径搜索终止处，由A2所扩展的每一个节点，也可以由A1扩展。因此，A1扩展的节点数至少和A2一样多。

h的单调限制

为避免生成的后继节点在OPEN或CLOSED表中，给h一个合理的限制

单调限制：如果对所有节点ni及其后继节点nj，使得当h(t)=0时下式成立：

0h(ni)–h(nj)c(ni,nj）

则h满足单调

结论5：如果h满足单调限制，若A*选n扩展，则g(n)=g*(n)

证明：设n为A*要扩展的节点a.若n=S,则A*已找到一条最佳路径b.若nS,设序列{S=n0,n1,……,nk=n}是S到n的一条最佳路径。令nl是这个序列的最后一个节点。

A*扩展时nl在CLOSED表上，nk，nl+1在OPEN表上∵h单调：h(ni)c(ni,ni+1)+h(ni+1)

g*(ni)+h(ni)g*(ni)+h(ni+1)+c(ni,ni+1)又∵ni和ni+1在最佳路径上g*(ni+1)=g*(ni)+c(ni,ni+1)g*(ni)+h(ni)g*(ni+1)+h(ni+1)

∴g*(nl+1)+h(nl+1)g*(nk)+h(nk)

f(nl+1)g*(n)+h(n)=f(n)

当A*选择节点n而不是节点nl+1时，g(n)g*(n)必须成立，否则，f(n)可能大于f(nl+1)。但是，由定义,对搜索树中所有节点m存在：

g(m)g*(m)∴必有

g(n)=g*(n)证毕结论6：如果满足单调限制，那么由A*所扩展的节点序列的f值非递减。

证明：a.设扩展n1时，n2在OPEN表上f(n1)f(n2)b.设扩展n1时，n2不在OPEN表上，则

f(n2)=g(n2)+h(n2)=g*(n2)+h(n2)=g*(n1)+c(n1,n2)+h(n2)=g(n1)+c(n1,n2)+h(n2)

∵c(n1,n2)+h(n2)h(n1)

∴f(n2)g(n1)+h(n1)=f(n1)证毕h的启发能力例：八数码难题的较好估计：h(n)=P(n)+3S(n)P(n):每个棋子离家距离的总和。S(n):棋子排列顺序的计分值。依次检验非中心方格的棋子，如果某棋子后跟的棋子和目标顺序不同，则该棋子得2分，一致得0分，所有棋子得分综合为S(n)。影响启发能力的因素路径费用寻找路径时所扩展的节点数目h的计算量美卫星首次实现在轨自动补给燃料2007年4月5日美国宇航局太空网报道ASTRO卫星(左)与NextSat卫星(右)ASTRO卫星的太阳能帆板

美国“轨道快车计划”(OrbitalExpress)

发起单位：美国国防预先研究计划局（DARPA）美国首创技术：卫星修复、自主机器人、在轨燃料加注

任务：发送低成本航天器对更昂贵的故障卫星进行修复和燃料燃料补给平台：航天器（3亿美元）ASTRO：主动航天器，模拟自主空间转移及机器人轨道器

NextSat：扮演补给站，又扮演被修复的客户卫星的角色

航天器制造：波音幻影工作室和鲍尔宇航公司建造实验过程：2007年3月8日从卡纳维拉尔角空军基地发射。两颗卫星绕距地球300英里（483公里）高的轨道飞行。系列实验包括：利用机器臂进行多次交会、捕获与转移操作

“情景0”试验：

ASTRO推进剂箱中的肼燃料泵入到NextSat中，

ASTRO携带约重300磅（136千克）的推进剂，用于燃料加注试验和之后的交会操作

燃料输送试验：尝试以不同的流动速率，利用泵式加注和压力加注两种方法进行试验机械臂目标捕获试验：机器臂将从ASTRO抓取替换单元（一节电池、传感器处理计算机）备用电池，并插入到NextSat上。（机器臂数次将电池在ASTRO和NextSat之间进行来回转移，但在不进行转移时，电池将会留在NextSat上提供外部动力。依照设计程序，在任务后期加入传感器处理计算机，将其从ASTRO移走后再放置回去，以试验传感器处理计算机的接口界面）

情景1（Scenario1）：重达156磅的机器臂抓住NextSat，把它推离ASTRO，预计持续11天。试验中，NextSat未固定，以便丢弃连接两颗卫星的结合环。此后，ASTRO还将再次抓取NextSat进行燃料补给试验，转移备用轨道替换单元。NextSat可通过对接或利用ASTRO上的机器臂被抓取

在情景2（Scenarios2）—情景5：设计了一系列渐进的步骤，将使ASTRO与NextSat分离，在3周内逐渐增大它们之间的距离

情景6（Scenarios6）—情景8：为进行远距离交会验证试验，ASTRO将上升至距离NextSat7千米的高度上