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

《知识的状态空间表示法及搜索问题讨论.ppt》由会员分享，可在线阅读，更多相关《知识的状态空间表示法及搜索问题讨论.ppt（117页珍藏版）》请在三一办公上搜索。

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

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

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

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

5、 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斤，另有一个大油桶，里面有足够的油。我们可以任意从油桶中取出油灌满某

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）且 E 0（0，S）f4：6斤油瓶不空时倒空（E，S）且 S 0（E，0）f5：8斤油瓶内油全部装入6斤油瓶内（E，S）E 0

7、 且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 且E+S 8（8，E+S-8）f8：用8斤油瓶内油去灌满6斤油瓶（E，S）且 S 6 且E+S 6（E+S-6，6）,3.2 搜索问题讨论,（1）求任一解路的搜索策略 回溯法（Backtracking）爬山法（Hill Climbing）宽度优先法（Breadth-first）深度优先法（Depth-first）限定范围搜索法（Beam Search）好的优先法（Best-first）,（2）求最佳解路的搜索策略 大英博物馆法（B

8、ritish Museum）分枝界限法（Branch and Bound）动态规划法（Dynamic Programming）最佳图搜索法（A）,（3）求与或关系解图的搜索法一般与或图搜索法（AO）极小极大法（Minimax）剪枝法（Alpha-beta Pruning）启发式剪枝法（Heuristic Pruning）,3.3 图搜索,用计算机进行状态空间问题求解的基本思路：首先把问题的初始状态（即初结点）作为当前状态，选择合适的算符对其进行操作，生成一组子状态，然后检查目标状态是否在其中出现。若出现，则搜索成功，若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态，重复上述过

9、程，直到目标状态出现，或者不在有可供操作的状态为止。,一、显示图与隐式图1显式图（显式存储）把与问题有关的全部状态空间以及相应的有关知识（叙述性知识、过程性知识、控制性知识)都直接存入知识库，称为显式图，或“显式存贮”。2隐式图（隐式存贮）只存贮与问题有关的部分知识，存贮的状态由初始状态开始运用相应的知识，逐步生成所需的部分状态空间，通过搜索推理，逐渐转移到要求的目标状态，只需在知识库中存贮局部的状态空间，称为“隐式图”或“隐式存贮”。通常采用隐式图进行解题（搜索推理）。,3.3 图搜索（续）,二、“隐式图”求解问题的一般过程open表：用于存放刚生成的结点closed表：用于存放将要扩展或者

10、已扩展的结点,3.3 图搜索（续）,open表,closed 表,搜索过程如下：1：把初始结点s0放入open表中。2：检查open表是否为空，若空，问题无解，退出。3：把open表中的第一个结点取出放入closed表中，并证实该结点为n结点。4：考察结点n为是否为目标结点，若是，退出。5：扩展结点n,生成一组子结点，把其中不是先辈的那些结点加入open表的尾部，并配以指向父结点的指针。6：按某种搜索策略对open表中的结点进行排序7：转入第2步。,3.3 图搜索（续）,一般的图搜索算法,1、G=G0(G0=s)，OPEN:=(s);2、CLOSED:=();3、LOOP:IF OPEN=()

11、THEN EXIT(FAIL);4、n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED),5、IF GOAL(n)THEN EXIT(SUCCESS);6、EXPAND(n)mi,G:=ADDmi,G;,一般的图搜索算法(续),7、标记和修改指针:ADD(mi,OPEN),并标记mi到n的指针;计算是否要修改mk、ml到n的指针；计算是否修改ml到其后续节点的指针；8、对OPEN中的节点按某种原则重新排序；9、GO LOOP；,一些基本概念,节点深度根节点深度=0其它节点深度=父节点深度+1路径设一节点序列为（n0，n1，nk）,对于i=1,k，若节点ni-1

12、具有一个后续节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。扩展一个节点生成该节点的所有后续节点,并给出它们之间的耗散值.这一过程称为“扩展一个节点”.,三、广度优先搜索流程图 广度优先搜索的含义：在对第n层结点没有搜索考察完之前，不对第n+1层结点进行搜索，但在隐式图优先搜索中是讲：从初始结点s0开始，按生成规则逐步生成下一级各子结点，在检查同级子结点同时，生成下级子结点并放在open表的末尾，而后再检查下一个同级结点，如不是目标结点，则按规则生成下级子结点，并放在open表末

13、尾，如此下去，直到找到目标为止。,3.3 图搜索（续）,广度优先搜索算法流程,G:=G0（G0=s）,OPEN:=(s),CLOSED:=（）；LOOP：IF OPEN（）THEN EXIT（FAIL）；n:FIRST（OPEN）；IF GOAL（n）THEN EXIT（SUCCESS）；REMOVE（n，OPEN），ADD（n，CLOSED）；,3.3 图搜索（续）,EXPAND（n）mi，G:ADD（mi，G）；IF 目标在 mi 中，THEN EXIT（SUCCESS）；ADD（OPEN，mj），并标记 到n的指针；GO LOOP,3.3 图搜索（续）,宽度优先搜索示例,8数码问题的宽度

14、优先搜索树,广度优先搜索的性质,当问题有解时,一定能找到解当问题为单位耗散值时,且问题有解时,一定能找到最优解方法与问题无关,具有通用性效率较低属于图搜索方法,3.3 图搜索（续）,四、深度优先搜索流程 从初始结点s0开始，按生成规则逐步生成下一级各子结点，在检查同级子结点同时，生成下级子结点并放在open表的首部，而后再检查下一个同级结点，如不是目标结点，则按规则生成下级子结点，并放在open表首部，如此下去，直到找到目标为止。,3.3 图搜索（续）,深度优先搜索,1、G=G0(G0=s)，OPEN:=(s);，CLOSED:=();2、LOOP:IF OPEN=()THEN EXIT(FA

15、IL);3、n:=FIRST(OPEN),4、IF GOAL(n)THEN EXIT(SUCCESS);5、REMOVE(n,OPEN),ADD(n,CLOSED),6、IF DEPTH(n)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;,目标,深度优先搜索性质,一般不能保证找到最优解当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制最坏情况时,搜索空间等于穷举与回溯法的差别:图搜索是一个通

16、用的与问题无关的方法,3.4 回溯策略,所谓回溯策略，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探用过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。,一个递归的例子,Int abc(int n)abc(m);,递归的思想,从前有座山,从前有座山

17、,从前有座山,从前有座山,八数码游戏回溯控制方式,新生成的状态在通向初始状态的路径上已出现过；从初始状态开始，应用的规则数目达到所规定的数目之后还未找到目标状态（这一组规则的数目实际上就是搜索对当前状态，再没有可应用的规则。,回溯搜索算法（）,BACKTRACK（DATA）功能：如果从当前状态DATA到目标状态有路径存在，则返回以规则序列表示的从DATA到目标状态的路径（以规则表的形式表示）；如果从当前状态DATA到目标状态没有路径存在，则返回FAIL。,回溯搜索算法（）,递归过程BACKTRACK（DATA）IF TERM（DATA），RETURN NIL；TERM取真即找到目标，则过程返回

18、空表NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND取真，即该状态不合法，则过程返回FAIL，必须回溯。RULES：APPRULES（DATA）；APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。LOOP：IF NULL（RULES），RETURN FAIL；NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯。R：FIRST（RULES）；取头条可应用规则。,回溯搜索算法（）,RULES：TAIL（RULES）；删去头条规则，减少可应用规则表的长度。RDATA：GEN（R，DATA）；调用规则R作用

19、于当前状态，生成新状态。PATH：BACKTRACK（RDATA）；对新状态递归调用本过程。IF PATHFAIL，GO LOOP；当PATHFAIL时，递归调用失败，则转移调用另一规则进行测试。RETURN CONS（R，PATH）；过程返回解路径规则表（或局部解路径子表）。,回溯搜索算法（）,BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：同前面的算法一样，是以规则序列表示的路径表（当求解成功时），或者是FAIL（当求解失败时）。,回溯搜索算法（续）,DATA：FIRST（DATALIST）；设置DATA为当前状态IF MEMBER（DATA，

20、TAIL（DATALIST)，RETURN FAIL；TAIL是取尾操作，表示取表DATALIST中除了第一个元素以外的所有元素。如果DATA在TAIL（DATALIST）中存在，则表示有环路出现，过程返回FAIL，必须回溯。IF TERM（DATA），RETURN NIL；TERM取真即找到目标，则过程返回空表NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND取真，即该状态不合法，则过程返回FAIL，必须回溯。,回溯搜索算法（续）,IF LENGTH（DATALIST）BOUND，RETURN FAIL；LENGTH计算DATALIST的长度，即搜索的深度，当搜

21、索深度大于给定值BOUND时，则过程返回FAIL，必须回溯。RULES：APPRULES（DATA）；APPRULES计算DATA的可应用规则集，依某种原则（任意排列或按启发式准则排列）排列后赋给RULES。LOOP：IF NULL（RULES），RETURN FAIL；NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯。R：FIRST（RULES）；取头条可应用规则。RULES：TAIL（RULES）；删去头条规则，减少可应用规则表的长度。,回溯搜索算法（续）,RDATA：GEN（R，DATA）；调用规则R作用于当前状态，生成新状态。RDATALIST:CONS(RDATA，DA

22、TALIST)；将新状态加入到表DATALIST中。PATH：BACKTRACK1（RDATALIST）；递归调用本过程。IF PATHFAIL，GO LO0P；当PATHFAIL时，递归调用失败，则转移调用另一规则进行测试。RETURN CONS（R，PATH）；过程返回解路径规则表（或局部解路径子表）。,2.1 回溯策略（Backtracking Strategies）,例：四皇后问题,存在问题及解决办法：,问题：深度问题死循环问题解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径,一些深入的问题,失败原因分析、多步回溯,一些深入的问题（续）,回溯搜索中知识的利用 基本思想（以皇后

23、问题为例）：尽可能选取划去对角线上位置数最少的,3.5 状态空间的与/或树表示法,1、分解（与树）把一个复杂的问题变成简单的子问题，各子问题又可以化成更为简单的子问题，重复此过程，直到不能分解为止。然后对各子问题求解，最后把各子问题复合起来就是问题的解。,2、等价变换（或树）通过同结构的等价变换或同态的等价变换把问题分解成比较容易解的子问题，P1，P2，P3任何一个子问题有解，则问题P就可解，称P1，P2，P3之间存在“或”的关系，节点P成为“或”节点，由P1，P2，P3，P之间构成的树为“或”树。,3.5 状态空间的与/或树表示法（续）,几个概念（1）父问题、子问题：问题空间是由一个个问题组

24、成的空间，在问题求解中，用一个节点代表一个问题，若节点A有一边通向B，则表示A的解决有赖于B的解决。A称为父问题，B称为子问题。（2）本原问题：不能再分解或变换，而且直接可解的子问题。（3）端节点与终止节点：没有子节点的节点，本原问题对应的节点是终止节点。注意，终止节点一定是端节点，但端节点不一定是终止节点。,3.5 状态空间的与/或树表示法（续）,与或图的搜索:,基本概念：,与或图是一个超图，节点间通过连接符连接。K-连接符：,可解节点：,终节点是可解节点；若非终节点有“或”子节点时，当且仅当其子节点至少有一能解，该非终节点才可解；若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节

25、点才可解。,不可解节点,没有后裔的非终节点是不可解节点；若非终节点有“或”子节点时，当且仅当所有子节点均不能解时，该非终节点才不可解；若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不可解。,“与/或”树的搜索过程,1.把初始节点S0放入OPEN表；2.移出OPEN表的第一个节点N放入CLOSED表，并冠以序号n；3.若节点N可扩展，则做下列工作：(1)扩展N,将其子节点配上指向父节点的指针后放入OPEN表；(2)考察这些子节点中是否有终止节点。(3)删去OPEN表中那些具有可解先辈的节点（因为其先辈节点已经可解，故已无再考察该节点的必要），转步骤2；,4.若N不可扩展，则做

26、下列工作：(1)标记N为不可解节点，然后由它的不可解返回推断其先辈节点的可解性，并对其中的不可解节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，退出。(2)删去OPEN表中那些具有不可解先辈的节点（因为其先辈节点已不可解，故已无再考察这些节点的必要），转步骤2；与状态图搜索一样，搜索成功后，解树已经记录在CLOSED表中。这时需按指向父节点的指针找出整个解树。,例 3.9 三阶梵塔问题设有A，B，C三个金片（盘）以及三个钢针，盘按自上而下从小到大的顺序穿在1号钢针上，要求将它们全部移到3号钢针上。规则：一次只能搬移一个金片，任何时刻都不能把大的金片压在小的金片上，2号钢针作为过

27、渡使用。,解法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）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

28、，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）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）

29、把A，B金片移到3号针问题，双片移动问题。用“=”表示状态变换，则由,博弈树的搜索,博弈问题:双人一人一步双方信息完备零和,分钱币问题:,中国象棋问题:,每个势态有40种不同的走法，如果一盘棋双方平均走50步，则搜索的位置有(402)50=10160，即深度达100层，总节点数约为10161个。假设一毫微秒走一步,约需10145年。结论：不可能穷举。,极小极大过程：,一字棋,在九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。设程序方MAX的棋子用（）表示，对手MIN的棋子用（）表示，MAX先走。,静态估计函数f（p）规定如下：若p对任何一方来说都不是获

30、胜的格局，则f（p）（所有空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角）的总（所有空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角）的总数）若p是MAX获胜的格局，则f（p）；若p是MIN获胜的格局，则f（p）。,一字棋第一阶段搜索树,一字棋第二阶段搜索树,一字棋第三阶段搜索树,-搜索过程,MAX节点的值为当前子节点的最大倒推值MIN节点的值为当前子节点的最小倒推值剪枝的条件：任何MAX节点n 的值它先辈节点的值，则n以下的分值可以停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝；任何MIN节点n 的值它先辈节点的值，则n以下的分值可以停止搜索，并令节点n的倒推值为，这

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

32、路径的耗散值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.扩展结点n，生成出不是n祖先的后继结点集mi,计算f(n,mi):=g(n,mi)+h(mi)；6.若mi没有在OPEN表和CLOSED表中出现过，则ADD(mi,OPEN)；7

33、.若mi在OPEN表中有重复结点k，且g(mi)g(k)，则REMOVE(k,OPEN)，ADD(mi,OPEN);,A算法(续),8.若mi在CLOSED表中有重复结点k，且g(mi)g(k)，则(1)CLOSED表的结点k改为结点mi；(2)按后继元表，修改结点k的所有在OPEN表和CLOSED表中的后裔的g、f值；9.OPEN中的节点按f值从小到大排序；10.GO LOOP,一个A算法的例子,定义评价函数:f(n)=g(n)+h(n)g(n)为初始节点到当前节点的耗散值 h(n)为当前节点”不在位”的将牌数,h计算举例,h(n)=4,2.最佳图搜索算法A*(A*算法),在A算法中如果满足

34、条件 h(n)h*(n)则A算法称为A*算法,A*条件举例,8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和,h1(n)=4 h2(n)=5,A*算法的性质,A*算法的假设 设ni,nj是任意两个节点,有:C(ni,nj)其中为大于0的常数几个等式 f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始节点,t是目标节点,n是s到t的最佳路径上的节点,A*算法的性质(续1),定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。引理2.1 对无限图,若有从初始节点S到目标节点t的路径,则A*不结束时,在OPEN表中即使最小的一

35、个f值也将增到任意大,或有f(n)f*(s),A*算法的性质(续3),引理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)=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

36、)的节点n,最终将被A*选作扩展节点 由定理2,知A*一定结束,由A*的结束条件,OPEN表中f(t)最小时才结束,而 f(t)f*(t)=f*(s)所以f(n)f*(s)的n均被扩展.得证,A*算法的性质(续5),定理3(可采纳性定理):若存在从初始节点s到目标节点t有路径,则A*必能找到最佳解结束,可采纳性的证明,由定理1、2知A*一定找到一条路径结束设找到的路径st不是最佳的(t为目标)则:f(t)=g(t)f*(s)由引理2.2知结束前OPEN中存在f(n)f*(s)的节点n,所以 f(n)f*(s)f(t)因此A*应选择n扩展,而不是t.而假设A*选择t结束矛盾.得证.注意:A*的结

37、束条件,A*算法的性质(续6),推论3.1 A*选择扩展的任一节点n,有f(n)f*(s)由引理2.2知在A*结束前,OPEN中存在节点n,f(n)f*(s).设此时A*选择n扩展.如果n=n,则f(n)f*(s),得证.如果nn,由于A*选择n扩展,而不是n所以有 f(n)f(n)f*(s),得证.,A*算法的性质(续7),定理4:设对同一问题定义了两个A*算法A1和A2,若A2比A1有较多的启发信息,即对所有非目标节点有h2(n)h1(n),则在一条从s到t的路径的隐含图上,搜索结束时,由A2所扩展的每一个节点,也必定由A1所扩展,即A1所扩展的节点数至少和A2一样多.简写:如果h2(n)

38、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)

39、，即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效果越

40、好实验表明，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表的可能，因此一

41、个节点有可能被反复扩展多次。因此单纯用扩展的节点数并不能客观地来评判搜索算法的好坏。因为即便是扩展的节点数比较少，但如果很多节点被多次重复扩展的话，搜索效率同样是很低的。,出现多次扩展节点的原因,主要就是因为在扩展一个节点时，A*并不能保证此时就已经找到了从初始节点s到当前节点n的最短路径，使得算法在第六步，有可能将其重新放回到OPEN表中，而放入OPEN表以后，该节点就有可能被再次扩展。,解决的途径：,对启发函数h进一步加上限制使得A*算法在扩展一个节点n时，就已经找到了从初始节点s到当前节点n的最短路径 对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展,改进的条件：,可采纳性不变

42、不多扩展节点不增加算法的复杂度,对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

43、)+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为“不在位的将牌数”h(t)=0;C(ni,nj)=1 满足单调条件。,对算法加以改进：,一些结论：OPEN表中任意满足f(n)f*(s)的节点都会被扩展。A*选作扩展的任意节点都满足f(n)f*(s)。,算法改进的基本思路,我们仍像A*算法那样，按照节点的f值从小到大排序OPEN表中的节点，我们以f*(s)为界将OPEN表划分为两部分，一部分由那些f值小于f*(s)的节点组成，我们称其为NEST，其他的节点属于另一个部分。OPEN=|,f*(s),ff*(s)的节点,f f*(s)的节点,其它的一些搜索算法：,爬山法（局部搜索算法）随机搜索算法动态规划算法,