第三章 知识的状态空间表示法.docx

1、第三章 知识的状态空间表示法1 课前思考：人类的思维过程，可以看作是一个搜索的过程。某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。 2 学习目标：掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法，对典型问题，掌握启发式函数的定义方法。 3 学习指南：了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下，程序实现每一个算法，求解一些典型的问题。 4 难重点：回溯搜索算法、 算法及其性质、改进的算法。5 知识点： 本章所要的讨论的问题如下： 有哪些

2、常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。 3.1 状态空间表示知识一、状态空间表示知识要点1状态状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成：Q=q1，q2，qn当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。2操作（规则或算符）操作（Operator）是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某个可用操作时，它将引起该状态

3、中某一些分量发生变化，从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。通常可表示为：F= f1 , f2, fm3状态空间状态空间（State Space）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间。用三元组表示为：（Qs，F，Qg）Qs：初始状态，Qg：目标状态，F：操作（或规则）。4状态空间（转换）图状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作。二、状态图搜索1

4、.搜索方式用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。 2.搜索策略大体可分为盲目搜索和启发式（heuristic）搜索两大类。搜索空间示意图 例3.1 钱币翻转问题设有三枚硬币，其初始状态为（反，正，反），允许每次翻转一个硬币（只翻一个硬币，必须翻一个硬币）。必须连翻三次。问是否可以达到目标状态（正，正，正）或（反，反，反）。问题求解过程如下： 用数组表示的话，显然每一硬币需占一维空间，则用三维数组状态变量表示这个知识： Q=（q1 , q2 , q3） 取q=0 表示钱币的正面 q=1 表示钱币的反面构成的问题状态空间显然为： Q0=（0，0，0）， Q1=（0，0

5、，1）， Q2=（0，1，0） ， Q3=（0，1，1） Q4=（1，0，0） ，Q5=（1，0，1） ，Q6=（1，1，0）， Q7=（1，1，1）引入操作：f1：把q1翻一面。 f2：把q2翻一面。f3：把q3翻一面。 显然：F=f1，f2，f3 目标状态：（找到的答案） Qg=（0，0，0）或（1，1，1） 例3.2 分油问题。 有两只空油瓶，容量分别为8斤和6斤，另有一个大油桶，里面有足够的油。我们可以任意从油桶中取出油灌满某一油瓶，也可以把某瓶中的油全部倒回油桶，两个油瓶之间可以互相灌。问如何在8斤油瓶中精确的得到4斤油。问题的求解显然用2维数组或状态空间描述比较合适，第一位表示8斤

6、油瓶油量，第二位表示6斤油瓶油量，构成整数序列偶（E，S）E：=0，1，2，3，4，5，6，7，8 。表示8斤油瓶中含有的油量。S：=0，1，2，3，4，5，6。表示6斤油瓶中含有的油量。总结出如下分油操作规则：f1：8斤油瓶不满时装满（E，S）且 E 8（8，S）f2：6斤油瓶不满时装满（E，S）且 S 0（0，S） f4：6斤油瓶不空时倒空（E，S）且 S 0（E，0） f5：8斤油瓶内油全部装入6斤油瓶内 （E，S）E 0 且E+S 6（0，E+S）f6：6斤油瓶内油全部装入8斤油瓶内 （E，S）S 0 且 E+S 8（E+S，0）f7：用6斤油瓶内油去灌满8斤油瓶 （E，S）且 E 8

7、 且E+S 8（8，E+S-8）f8：用8斤油瓶内油去灌满6斤油瓶 （E，S）且 S Dm GO LOOP;7、EXPAND(n) mi,G:=ADDmi,G;8、IF 目标在mi中 THEN EXIT(SUCCESS);9、ADD(mi,OPEN),并标记mj到n指针;10、将mi重排序到open表头部。11、GO LOOP;深度优先搜索性质一般不能保证找到最优解当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制最坏情况时, 搜索空间等于穷举与回溯法的差别:图搜索是一个通用的与问题无关的方法3.4 回溯策略所谓回溯策略，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时

8、，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探用过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。一个递归的例子Int abc(int n) abc(m); 八数码游戏回溯控制方式新生成的状态在通向初始状态的路径上已出现过；从初始状态开始，应用的规则数目达到所规定的数目之后还未找到目标状态（这一组规则的数目实

9、际上就是搜索对当前状态，再没有可应用的规则。回溯搜索算法BACKTRACK（DATA）功能：如果从当前状态DATA到目标状态有路径存在，则返回以规则序列表示的从DATA到目标状态的路径（以规则表的形式表示）；如果从当前状态DATA到目标状态没有路径存在，则返回FAIL。 递归过程BACKTRACK（DATA）IF TERM（DATA），RETURN NIL；TERM取真即找到目标，则过程返回空表NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND取真，即该状态不合法，则过程返回FAIL，必须回溯。RULES：APPRULES（DATA）；APPRULES计算DATA

10、的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。LOOP：IF NULL（RULES），RETURN FAIL；NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯。R：FIRST（RULES）；取头条可应用规则。RULES：TAIL（RULES）；删去头条规则，减少可应用规则表的长度。RDATA：GEN（R，DATA）；调用规则R作用于当前状态，生成新状态。PATH：BACKTRACK（RDATA）；对新状态递归调用本过程。IF PATHFAIL，GO LOOP；当PATHFAIL时，递归调用失败，则转移调用另一规则进行测试。RETURN CONS（R，P

11、ATH）；过程返回解路径规则表（或局部解路径子表）。回溯搜索算法（）BACKTRACK1（DATALIST） DATALIST：从初始到当前的状态表（逆向）返回值：同前面的算法一样，是以规则序列表示的路径表（当求解成功时），或者是FAIL（当求解失败时）。 回溯搜索算法（续）DATA：FIRST（DATALIST）；设置DATA为当前状态IF MEMBER（DATA，TAIL（DATALIST) )，RETURN FAIL；TAIL是取尾操作，表示取表DATALIST中除了第一个元素以外的所有元素。如果DATA在TAIL（DATALIST）中存在，则表示有环路出现，过程返回FAIL，必须回溯。

12、IF TERM（DATA），RETURN NIL；TERM取真即找到目标，则过程返回空表NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND取真，即该状态不合法，则过程返回FAIL，必须回溯。IF LENGTH（DATALIST）BOUND，RETURN FAIL；LENGTH计算DATALIST的长度，即搜索的深度，当搜索深度大于给定值BOUND时，则过程返回FAIL，必须回溯。RULES：APPRULES（DATA）；APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则排列）排列后赋给RULES。LOOP：IF NULL（RULES），

13、RETURN FAIL；NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯。R：FIRST（RULES）；取头条可应用规则。RULES：TAIL（RULES）；删去头条规则，减少可应用规则表的长度。RDATA：GEN（R，DATA）；调用规则R作用于当前状态，生成新状态。RDATALIST:CONS(RDATA，DATALIST)；将新状态加入到表DATALIST中。PATH：BACKTRACK1（RDATALIST）；递归调用本过程。IF PATHFAIL，GO LO0P；当PATHFAIL时，递归调用失败，则转移调用另一规则进行测试。RETURN CONS（R，PATH）；过程

14、返回解路径规则表（或局部解路径子表）。 2.1 回溯策略（Backtracking Strategies） 例：四皇后问题 QQQQ存在问题及解决办法：问题：深度问题死循环问题解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径一些深入的问题失败原因分析、多步回溯QQ一些深入的问题（续）回溯搜索中知识的利用 基本思想（以皇后问题为例）： 尽可能选取划去对角线上位置数最少的QQQQ3.5 状态空间的与/或树表示法1、 分解（与树）把一个复杂的问题变成简单的子问题，各子问题又可以化成更为简单的子问题，重复此过程，直到不能分解为止。然后对各子问题求解，最后把各子问题复合起来就是问题的解。2、

15、等价变换（或树）通过同结构的等价变换或同态的等价变换把问题分解成比较容易解的子问题，P1，P2，P3任何一个子问题有解，则问题P就可解，称P1，P2，P3之间存在“或”的关系，节点P成为“或”节点，由P1，P2，P3，P之间构成的树为“或”树。几个概念（1）父问题、子问题：问题空间是由一个个问题组成的空间，在问题求解中，用一个节点代表一个问题，若节点A有一边通向B，则表示A的解决有赖于B的解决。A称为父问题，B称为子问题。（2）本原问题：不能再分解或变换，而且直接可解的子问题。（3）端节点与终止节点：没有子节点的节点，本原问题对应的节点是终止节点。注意，终止节点一定是端节点，但端节点不一定是终

16、止节点。与或图的搜索: 基本概念：与或图是一个超图，节点间通过连接符连接。K-连接符： 可解节点：终节点是可解节点；若非终节点有“或”子节点时，当且仅当其子节点至少有一能解，该非终节点才可解；若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节点才可解。不可解节点没有后裔的非终节点是不可解节点；若非终节点有“或”子节点时，当且仅当所有子节点均不能解时，该非终节点才不可解；若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不可解。“与/或”树的搜索过程1. 把初始节点S0放入OPEN表；2. 移出OPEN表的第一个节点N放入CLOSED表，并冠以序号n；3. 若节点N可扩

17、展，则做下列工作： (1)扩展N,将其子节点配上指向父节点的指针后放入OPEN表； (2)考察这些子节点中是否有终止节点。 (3) 删去OPEN表中那些具有可解先辈的节点（因为其先辈节点已经可解，故已无再考察该节点的必要），转步骤2； 4. 若N不可扩展，则做下列工作： (1)标记N为不可解节点，然后由它的不可解返回推断其先辈节点的可解性，并对其中的不可解节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，退出。 (2)删去OPEN表中那些具有不可解先辈的节点（因为其先辈节点已不可解，故已无再考察这些节点的必要），转步骤2；与状态图搜索一样，搜索成功后，解树已经记录在CLOSED表

18、中。这时需按指向父节点的指针找出整个解树。 例 3.9 三阶梵塔问题设有A，B，C三个金片（盘）以及三个钢针，盘按自上而下从小到大的顺序穿在1号钢针上，要求将它们全部移到3号钢针上。规则：一次只能搬移一个金片，任何时刻都不能把大的金片压在小的金片上，2号钢针作为过渡使用。 解法1：用状态转换图法。用三维状态空间来表示知识或过程。（i，j，k）i表示C片所钢针号，j表示B片所在钢针号，k表示A中所在钢针号。显然，组成的状态空间有27个（3*3*3）S0=（1，1，1） S1=（1，1，2） S2=（1，1，3）S3=（1，2，1） S4=（1，2，2） S5=（1，2，3）S6=（1，3，1）

19、S7=（1，3，2） S8=（1，3，3）S9=（2，1，1） S10=（2，1，2） S11=（2，1，3）S12=（2，2，1） S13=（2，2，2） S14=（2，2，3）S15=（2，3，1） S16=（2，3，2） S17=（2，3，3）S18=（3，1，1） S19=（3，1，2） S20=（3，1，3）S21=（3，2，1） S22=（3，2，2） S23=（3，2，3）S24=（3，3，1） S25=（3，3，2） S26=（3，3，3）依题意规则可用18个状态空间表示算子，A（），B（），C（）A（1，2）表示从1号针移到2号针，以下类推：A盘共有6种搬移规则。A（1，3）

20、 A（2，1）.A（3，1） A（3，2） B（1，2） B（1，3） B（3，1） B（3，2）C（1，2） C（1，3）C（3，1） C（3，2） 解法2：用“与/或”树解题为把3个金片移到3号针可分解成如下步骤：1）把A，B金片移到2号针问题，双片移动问题。2）把C片移到3号针问题，终止节点，单片移动。3）把A，B金片移到3号针问题，双片移动问题。用“=”表示状态变换，则由 博弈树的搜索 博弈问题:双人一人一步双方信息完备零和分钱币问题: 中国象棋问题:每个势态有40种不同的走法，如果一盘棋双方平均走50步，则搜索的位置有(402)50=10160 ，即深度达100层，总节点数约为101

21、61个。假设一毫微秒走一步,约需10145年。结论：不可能穷举。极小极大过程： 一字棋在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。设程序方MAX的棋子用（）表示，对手MIN的棋子用（）表示，MAX先走。静态估计函数f（p）规定如下：若p对任何一方来说都不是获胜的格局，则f（p）（所有空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角）的总（所有空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角）的总数）若p是MAX获胜的格局，则f（p）；若p是MIN获胜的格局，则f（p）。 -搜索过程 极大节点的下界为极小节点的上界为剪枝的条件：

22、（后继层）（先辈层）， 剪枝；（后继层）（先辈层）， 剪枝。简记为：极小极大， 剪枝；极大极小， 剪枝；一字棋第一阶段-剪枝方法 -搜索过程的博弈树 3.7 启发式搜索 启发式图搜索利用知识来引导搜索,以达到减少搜索范围,降低问题复杂度的目的启发信息的强度强：降低搜索工作量,但可能导致找不到最优解弱：一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解希望：引入启发知识,在保证找到最佳解的情况下,尽可能减少搜索范围,提高搜索效率基本思想：定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展启发式搜索算法A(A算法)评价函数的格式： f(n)=g(n)+h(n)

23、 f(n)：评价函数 h(n)：启发函数 符号的意义g*(n):从s到n的最短路径的耗散值h*(n):从n到g的最短路径的耗散值f*(n)= g*(n)+ h*(n):从s经过n到g的最短路径的耗散值g(n)、 h(n)、f(n) 分别是g*(n)、 h*(n)f*(n)的估计值A 算 法1.OPEN:= (s), f(s)=g(s)+h(s);2.LOOP:IF OPEN=( ) THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n) THEN EXIT(SUCCESS);5.REMOVE(n,OPEN), ADD (n,CLOSED);6. EXPAND

24、(n) mi,计算f(n,mi):=g(n,mi)+h(mi) ADD (mi,OPEN),标记mi到n的指针 若mi在open表或closed表中有重复，根据耗散值确定取舍。7.OPEN中的节点按f值从小到大排序8.GO LOOP一个A算法的例子 h计算举例21823318604477655h(n)=4 2.最佳图搜索算法A*(A*算法)在A算法中如果满足条件 h(n)h*(n) 则A算法称为A*算法89A*条件举例8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和21823318604477 655h1(n)=4 h2(n)=5A*算法的性质A*算法的假设 设ni,

25、nj是任意两个节点,有: C(ni,nj) 其中为大于0的常数几个等式 f*(s)=f*(t)=h*(s)=g*(t)=f*(n) 其中s是初始节点,t是目标节点,n是s到t的最佳路径上的节点定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。引理2.1 对无限图,若有从初始节点S到目标节点t的路径,则A*不结束时,在OPEN表中即使最小的一个f值也将增到任意大,或有f(n)f*(s)引理2.2 A*结束前,OPEN表中必存在一个节点n, n在最佳路径上且满足f(n)f*(s)f(n)=g(n)+h(n) =g*(n)+h(n) g*(n)+h*(n) =f*(n)

26、 =f*(s)定理2 对无限图,若从初始节点s到目标节点t有路径存在,则A*一定成功结束证明：引理2.1: A*如果不结束,则OPEN中所有的n有f(n)f*(s)引理2.2: 在A结束前,必存在节点n,使得f(n)f*(s)所以,如果A*不结束,将导致矛盾推论2.1: OPEN表上任意一具有f(n)f*(s)由引理2.2知结束前OPEN中存在f(n)f*(s)的节点n, 所以 f(n)f*(s)h1(n),则在一条从s到t的路径的隐含图上,搜索结束时,由A2所扩展的每一个节点,也必定由A1所扩展,即A1所扩展的节点数至少和A2一样多. 简写:如果h2(n)h1(n)(目标节点除外), 则A1

27、扩展的节点数 A2扩展的节点数.注意: 在定理4中,评价指标是”扩展的节点数”也就是说,同一个节点无论被扩展多少次,都只计算一次.定理4的证明使用数学归纳法,对节点的深度进行归纳. (1)当 d(n)=0时,即只有一个节点,显然定理成立. (2)设d(n)k时,定理成立.(归纳假设) (3)当d(n)=k+1时,用反证法.设存在一个深度为k+1的节点n,被A2扩展, 但没有被A1扩展.而由假设,A1扩展了n的父节点，即n已经被生成了。因此当A1结束时，n将被保留在OPEN中。n没有被A1选择扩展，有f1(n)f*(s)，即g1(n)+h1(n)f*(s)所以 h1(n)f*(s) g1(n)

28、（1）另一方面A2扩展了n，有f2(n)f*(s)，即g2(n)+h2(n)f*(s)所以 h2(n)f*(s)g2(n) （2）由于d=k时，A2扩展的节点，A1也一定扩展，故有g1(n)g2(n)（因A1扩展的节点数可能较多）所以 h1(n)f*(s) g1(n)f*(s) g2(n) （3）比较式（2）、（3）可得：至少在节点n上有h1(n)h2(n)，这与定理的前提条件矛盾，因此存在节点n的假设不成立。证毕102对h的评价方法：平均分叉数：设共扩展了d层节点，共搜索了N个节点，则： 其中b*称为平均分叉数b*越好，说明h效果越好实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规

29、模变化对h的评价举例：例：数码问题，随机产生若干初始状态使用h1：d=14,N=539,b*=1.44d=20,N=7276,b*=1.47使用h2：d=14,N=113,b*=1.23d=20,N=676,b*=1.27A*的复杂性：一般说来，*的算法复杂性是指数型的,可以证明当且仅当以下条件成立时：abs(h(n)-h*(n)O(log(h*(n)*的算法复杂性才是非指数型的，但是通常情况下，h和h*的差别至少是和离目标的距离成正比的A*算法的改进在A算法的第六步，对于ml类节点，存在重新放回到OPEN表的可能，因此一个节点有可能被反复扩展多次。因此单纯用扩展的节点数并不能客观地来评判搜索算法的好坏。因为即