知识的状态空间表示法及搜索问题讨论

知识的状态空间表示法,计算机科学技术学院陈峰,1课前思考：人类的思维过程，可以看作是一个搜索的过程。某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。2学习目标：掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法，对典型问题，掌握启发式函数的定义方法。,3学习指南：了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下，程序实现每一个算法，求解一些典型的问题。4难重点：回溯搜索算法、算法及其性质、改进的算法。,5知识点：,本章所要的讨论的问题如下：,有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。,3.1状态空间表示知识,一、状态空间表示知识要点1状态状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成：Q=q1，q2，qn当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。,2操作（规则或算符）操作（Operator）是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某个可用操作时，它将引起该状态中某一些分量发生变化，从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。通常可表示为：F=f1,f2,fm,3.1状态空间表示知识（续）,3状态空间状态空间（StateSpace）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间。用三元组表示为：（Qs，F，Qg）Qs：初始状态，Qg：目标状态，F：操作（或规则）。4状态空间（转换）图状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作。,3.1状态空间表示知识（续）,二、状态图搜索1.搜索方式用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。2.搜索策略大体可分为盲目搜索和启发式（heuristic）搜索两大类。,3.1状态空间表示知识（续）,搜索空间示意图,例3.1钱币翻转问题设有三枚硬币，其初始状态为（反，正，反），允许每次翻转一个硬币（只翻一个硬币，必须翻一个硬币）。必须连翻三次。问是否可以达到目标状态（正，正，正）或（反，反，反）。问题求解过程如下：用数组表示的话，显然每一硬币需占一维空间，则用三维数组状态变量表示这个知识：Q=（q1,q2,q3）取q=0表示钱币的正面q=1表示钱币的反面,3.1状态空间表示知识（续）,构成的问题状态空间显然为：Q0=（0，0，0），Q1=（0，0，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.1状态空间表示知识（续）,3.1状态空间表示知识（续）,例3.2分油问题。有两只空油瓶，容量分别为8斤和6斤，另有一个大油桶，里面有足够的油。我们可以任意从油桶中取出油灌满某一油瓶，也可以把某瓶中的油全部倒回油桶，两个油瓶之间可以互相灌。问如何在8斤油瓶中精确的得到4斤油。,3.1状态空间表示知识（续）,问题的求解显然用2维数组或状态空间描述比较合适，第一位表示8斤油瓶油量，第二位表示6斤油瓶油量，构成整数序列偶（E，S）E：=0，1，2，3，4，5，6，7，8。表示8斤油瓶中含有的油量。S：=0，1，2，3，4，5，6。表示6斤油瓶中含有的油量。总结出如下分油操作规则：,3.1状态空间表示知识（续）,f1：8斤油瓶不满时装满（E，S）且E0（0，S）f4：6斤油瓶不空时倒空（E，S）且S0（E，0）f5：8斤油瓶内油全部装入6斤油瓶内（E，S）E0且E+S6（0，E+S）f6：6斤油瓶内油全部装入8斤油瓶内（E，S）S0且E+S8（E+S，0）f7：用6斤油瓶内油去灌满8斤油瓶（E，S）且E”表示状态变换，则由,博弈树的搜索,博弈问题:双人一人一步双方信息完备零和,分钱币问题:,中国象棋问题:,每个势态有40种不同的走法，如果一盘棋双方平均走50步，则搜索的位置有(402)50=10160，即深度达100层，总节点数约为10161个。假设一毫微秒走一步,约需10145年。结论：不可能穷举。,极小极大过程：,一字棋,在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。设程序方MAX的棋子用（）表示，对手MIN的棋子用（）表示，MAX先走。,静态估计函数f（p）规定如下：若p对任何一方来说都不是获胜的格局，则f（p）（所有空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角）的总（所有空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角）的总数）若p是MAX获胜的格局，则f（p）；若p是MIN获胜的格局，则f（p）。,一字棋第一阶段搜索树,一字棋第二阶段搜索树,一字棋第三阶段搜索树,-搜索过程,MAX节点的值为当前子节点的最大倒推值MIN节点的值为当前子节点的最小倒推值剪枝的条件：任何MAX节点n的值它先辈节点的值，则n以下的分值可以停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝；任何MIN节点n的值它先辈节点的值，则n以下的分值可以停止搜索，并令节点n的倒推值为，这种剪枝称为剪枝。,一字棋第一阶段-剪枝方法,-搜索过程的博弈树,3.7启发式搜索,启发式图搜索,利用知识来引导搜索,以达到减少搜索范围,降低问题复杂度的目的启发信息的强度强：降低搜索工作量,但可能导致找不到最优解弱：一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解,希望：,引入启发知识,在保证找到最佳解的情况下,尽可能减少搜索范围,提高搜索效率基本思想：定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展,启发式搜索算法A(A算法),评价函数的格式：f(n)=g(n)+h(n)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:IFOPEN=()THENEXIT(FAIL);3.n:=FIRST(OPEN);4.IFGOAL(n)THENEXIT(SUCCESS);5.扩展结点n，生成出不是n祖先的后继结点集mi,计算f(n,mi):=g(n,mi)+h(mi)；6.若mi没有在OPEN表和CLOSED表中出现过，则ADD(mi,OPEN)；7.若mi在OPEN表中有重复结点k，且g(mi)f*(s),A*算法的性质(续3),引理2.2A*结束前,OPEN表中必存在一个节点n,n在最佳路径上且满足f(n)f*(s)f(n)=g(n)+h(n)=g*(n)+h(n)g*(n)+h*(n)=f*(n)=f*(s),A*算法的性质(续3),定理2对无限图,若从初始节点s到目标节点t有路径存在,则A*一定成功结束证明：引理2.1:A*如果不结束,则OPEN中所有的n有f(n)f*(s)引理2.2:在A结束前,必存在节点n,使得f(n)f*(s)所以,如果A*不结束,将导致矛盾,A*算法的性质(续4),推论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扩展的节点数A2扩展的节点数.,A*算法的性质(续7),注意:在定理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中。,定理4的证明（续）,n没有被A1选择扩展，有f1(n)f*(s)，即g1(n)+h1(n)f*(s)所以h1(n)f*(s)g1(n)（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的假设不成立。证毕,对h的评价方法：,平均分叉数：设共扩展了d层节点，共搜索了N个节点，则：其中b*称为平均分叉数b*越好，说明h效果越好实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化,对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.27,A*的复杂性：,一般说来，*的算法复杂性是指数型的,可以证明当且仅当以下条件成立时：abs(h(n)-h*(n)O(log(h*(n)*的算法复杂性才是非指数型的，但是通常情况下，h和h*的差别至少是和离目标的距离成正比的,A*算法的改进,在A算法的第六步，对于ml类节点，存在重新放回到OPEN表的可能，因此一个节点有可能被反复扩展多次。因此单纯用扩展的节点数并不能客观地来评判搜索算法的好坏。因为即便是扩展的节点数比较少，但如果很多节点被多次重复扩展的话，搜索效率同样是很低的。,出现多次扩展节点的原因,主要就是因为在扩展一个节点时，A*并不能保证此时就已经找到了从初始节点s到当前节点n的最短路径，使得算法在第六步，有可能将其重新放回到OPEN表中，而放入OPEN表以后，该节点就有可能被再次扩展。,解决的途径：,对启发函数h进一步加上限制使得A*算法在扩展一个节点n时，就已经找到了从初始节点s到当前节点n的最短路径对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展,改进的条件：,可采纳性不变不多扩展节点不增加算法的复杂度,对h加以限制,定义：一个启发函数h，如果对所有节点ni和nj（nj是ni的子节点），都有h(ni)-h(nj)C(ni，nj)或h(ni)C(ni，nj)h(nj)且h(t)0，则称该h函数满足单调限制条件。,h单调的性质：,定理5：若h(n)满足单调限制条件，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即若A*选n来扩展，在单调限制条件下有g(n)=g*(n)。,定理5的证明：,由单调限制条件，对P中任意结点ni有h(ni)C(ni，ni+1)+h(ni+1)g*(ni)+h(ni)g*(ni)+C(ni，ni+1)+h(ni+1)g*(ni+1)+h(ni+1)g*(n)+h(n)而在于f(n)=g(n)+h(n)f(ni+1)所以：g(n)g*(n)（最小）只能是：g(n)=g*(n),h单调的性质（续）：,定理6：若h(n)满足单调限制，则由A*所扩展的节点序列，其f值是非递减的，即f(ni)f(nj)。证明：由单调限制条件：h(ni)-h(nj)C(ni,nj)即f(ni)-g(ni)-f(nj)+g(nj)C(ni,nj)f(ni)-g(ni)-f(nj)+g(ni)C(ni,nj)C(ni,nj)f(ni)-f(nj)0。证毕,h单调的例子：,8数码：h为“不在位的将