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

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状态空间（转换）图状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作。二、状态

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

5、（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.2 分油问题。 有两只空油瓶，容量分别为8斤和6斤，另有一个大油桶，里面有足够的油。我们可以任意从油桶中取出油灌满某一油瓶，也可以把某瓶中的油全部倒回油桶，两个油瓶之间可以相互灌。问如何在8斤油瓶中精确的得到4斤油。问题的求解明显用2维数组或状态空间描述比较合适，第一位

6、表示8斤油瓶油量，其次位表示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 < 6（E，6） f3：8斤油瓶不空时倒空（E，S）且 E > 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斤油瓶内油全部装入

7、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）求最佳解路的搜寻策略 大英博物馆法（British Museu

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

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

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

11、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具有一个后续节点ni，则该序列称为从n0到nk的路径。路径

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

13、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）；EXPAND（n）mi，G:ADD（ mi ，G）； IF 目标在 mi 中，THEN EXIT（SUCCESS）； ADD（OPEN， mj ），并标记 到n的指针；GO LOOP 宽度优先搜寻示例8数码问题的宽度优先搜寻树广度优先搜寻的性质当问题有解时,肯定能找到解当问题为单位耗散值时,且问题有解时,肯定能找到最优解方法与问题

14、无关,具有通用性效率较低属于图搜寻方法四、深度优先搜寻流程 从初始结点s0开头，按生成规章逐步生成下一级各子结点，在检查同级子结点同时，生成下级子结点并放在open表的首部，而后再检查下一个同级结点，如不是目标结点，则按规章生成下级子结点，并放在open表首部，如此下去，直到找到目标为止。深度优先搜寻1、G=G0(G0=s)，OPEN:= (s);，CLOSED:=( );2、LOOP:IF OPEN=( ) THEN EXIT(FAIL);3、n:=FIRST(OPEN),4、IF GOAL(n) THEN EXIT(SUCCESS);5、REMOVE(n,OPEN), ADD (n,CLO

15、SED),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;深度优先搜寻性质一般不能保证找到最优解当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制最坏状况时, 搜寻空间等于穷举与回溯法的差别:图搜寻是一个通用的与问题无关的方法3.4 回溯策略所谓回溯策略，简洁地说是这样一种策略：首先将规章给出一个固定的排序，在搜寻时，对当前状态（搜寻开头时，当前状态是初始状

16、态）依次检测每一条规章，在当前状态未使用过的规章中找到第一条可触发规章，被应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜寻。假如当前状态无规章可用，或者全部规章已经被摸索用过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜寻，直到找到问题的解，或者摸索了全部可能后仍找不到问题的解为止。一个递归的例子Int abc(int n) abc(m); 八数码玩耍回溯把握方式新生成的状态在通向初始状态的路径上已消灭过；从初始状态开头，应用的规章数目达到所规定的数目之后还未找到目标状态（这一组规章的数目实际上就是搜寻对当前状态，再没有可应用的规章

17、。回溯搜寻算法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的可应用规章集，依某种原则（任意排列或按启

18、发式准则）排列后赋给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，PATH）；过程返回解路径规章表（或局部解路

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

20、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），RETURN FAIL；NULL取真，即规

21、章用完未找到目标，过程返回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）；过程返回解路径规章表（或局部解路径子表）。 2

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

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

24、一个超图，节点间通过连接符连接。K-连接符： 可解节点：终节点是可解节点；若非终节点有“或”子节点时，当且仅当其子节点至少有一能解，该非终节点才可解；若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终节点才可解。不行解节点没有后裔的非终节点是不行解节点；若非终节点有“或”子节点时，当且仅当全部子节点均不能解时，该非终节点才不行解；若非终节点有“与”子节点时，当至少有一子节点不能解时，该非终节点才不行解。“与/或”树的搜寻过程1. 把初始节点S0放入OPEN表；2. 移出OPEN表的第一个节点N放入CLOSED表，并冠以序号n；3. 若节点N可扩展，则做下列工作： (1)扩展N,将其子节

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

26、 例 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） S7=（1，3，2） S8=（1，3，3）

27、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） A（2，1）.A（3，1） A（3，2）

28、 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层，总节点数约为10161个。假设一毫微秒走一步,约需1

29、0145年。结论：不行能穷举。微小极大过程： 一字棋在九宫格棋盘上，两位选手轮番在棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜。设程序方MAX的棋子用（×）表示，对手MIN的棋子用（）表示，MAX先走。静态估量函数f（p）规定如下：若p对任何一方来说都不是获胜的格局，则f（p）（全部空格都放上MAX的棋子之后，MAX的三子成线（行、列、对角）的总（全部空格都放上MIN的棋子之后，MIN的三子成线（行、列、对角）的总数）若p是MAX获胜的格局，则f（p）；若p是MIN获胜的格局，则f（p）。 -搜寻过程 极大节点的下界为微小节点的上界为剪枝的条件：（后继层）（先辈层），

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

31、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(n) mi,计算f(

32、n,mi):=g(n,mi)+h(mi) ADD (mi,OPEN),标记mi到n的指针 若mi在open表或closed表中有重复，依据耗散值确定取舍。7.OPEN中的节点按f值从小到大排序8.GO LOOP一个A算法的例子 h计算举例21823318604477 655h(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,nj是任意两个节点,

33、有: 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) =

34、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)的节点n,最终将被A*选作扩展节点 由定理2,知A*肯定结束,由A*的结束条件,OPEN表中f(t)最小时才结束,而 f(t) f*(t)=f*(s) 所以f(n)f*(s) 的n均被扩展.得证定理3(可接受性定理): 若存在从初始节点s到目标节点t有路径,则A*必能找到最佳

35、解结束可接受性的证明由定理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*的结束条件推论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),得证.

36、定理4: 设对同一问题定义了两个A*算法A1和A2,若A2比A1有较多的启发信息,即对全部非目标节点有h2(n)>h1(n),则在一条从s到t的路径的隐含图上,搜寻结束时,由A2所扩展的每一个节点,也必定由A1所扩展,即A1所扩展的节点数至少和A2一样多. 简写:假如h2(n)>h1(n)(目标节点除外), 则A1扩展的节点数 A2扩展的节点数.留意: 在定理4中,评价指标是”扩展的节点数”也就是说,同一个节点无论被扩展多少次,都只计算一次.定理4的证明使用数学归纳法,对节点的深度进行归纳. (1)当 d(n)=0时,即只有一个节点,明显定理成立. (2)设d(n)k时,定理成立.

37、(归纳假设) (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) （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*是一个比较稳定的常数，同一问题基本不随问题规模变化对h的评价举例：例：数码问题，随机产生若干初始状态使用h1：d=14,N=53