人工智能-第一章课件.ppt

《人工智能-第一章课件.ppt》由会员分享，可在线阅读，更多相关《人工智能-第一章课件.ppt（117页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章、搜索问题有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)许多实际问题（如最优路径规划、人力排班、装箱问题、机器人行动规划等）都都可可以以归归结结为为在在某某一一状状态态空空间间中中搜搜索索目目标标或路径的问题。或路径的问题。1 12 23 34 45 5问题：如何解决这类问题？这类问题不能用简单的数学公式/数学方程来描述，属于非结构化问题。难以获得求解所需的全部信息；更没有现成的算法可供求解使用属于组合爆炸问题，稍大规模的问题就超出了人类的认知负荷解决方法：利用计算机的超人计算能力，通过不断试探搜索找到问题的（最优）解。优点建模简单6 6具体方法：状态空间法状态：是

2、指问题状态的的向量表示（x,y,z,.)。问题有初始状态，有目标状态有些状态可能是非法的，问题不可能发展到那种状态问题表示为向量，向量就是在Euclidean空间，因此问题的初始状态和目标状态都是此空间中的点。此类问题的特征是找出从初始状态到目标状态的路径，方法是通过一个状态向另一个状态的转换实现的。7 7问题状态的表示方法（一）8 8问题状态的表示方法（二）9 9问题状态的变迁1010问题状态的表示方法1111问题状态的变迁1212搜索问题-主要内容内容：状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解），寻找过程就是搜索。1313状态

3、空间法状态空间法1.状态空间表示方法状态空间表示方法状态状态(State)：求解过程中每一步问题状况的表示：求解过程中每一步问题状况的表示Sk=Sk0,Sk1)当对每一个分量都给以确定的值时，就得到了一个具体的当对每一个分量都给以确定的值时，就得到了一个具体的状态。状态。操作操作(Operator):也称为算符，它是把问题从一种状态变也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。个运算，一条规则或一个过程。状态空间状态空间(State space):用来描述一个问题的全部状态用来描述

4、一个问题的全部状态以及这些状态之间的相互关系。常用表示为以及这些状态之间的相互关系。常用表示为(S,F,G)其中，其中，S为问题的所有初始状态的集合；为问题的所有初始状态的集合；F为操作的集合；为操作的集合；G为目标状态的集合。为目标状态的集合。状态空间也可用一个赋值的有向图来表示，称为状态空状态空间也可用一个赋值的有向图来表示，称为状态空间图间图,其中节点表示问题的状态，有向边表示操作。其中节点表示问题的状态，有向边表示操作。1414状态空间法求解问题的基本过程：状态空间法求解问题的基本过程：1.1.首先为问题选择适当的首先为问题选择适当的“状态状态”及及“操作操作”的的形式化描述方法；形式

5、化描述方法；2.2.然后从某个初始状态出发，每次使用一个然后从某个初始状态出发，每次使用一个“操操作作”，递增地建立起操作序列，直到达到目标，递增地建立起操作序列，直到达到目标状态为止；状态为止；此时，由初始状态到目标状态所使用的算符序此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。列就是该问题的一个解。状态空间法状态空间法2.状态空间问题求解状态空间问题求解1515 修道士修道士(Missionaries)和野人和野人(Cannibals)问题问题(简称简称M-C问问题题)。设在河的一岸有三个野人、三个修道士和一条船，修道士想设在河的一岸有三个野人、三个修道士和一条船，修道士想

6、用这条船把所有的人运到河对岸，但受以下条件的约束：用这条船把所有的人运到河对岸，但受以下条件的约束：1.修道士和野人都会划船，但每次船上至多可载两个人；修道士和野人都会划船，但每次船上至多可载两个人；2.在河的任一岸，如果野人数目超过修道士数，修道士会被在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计和野人都能过河，且没有修道士被野人吃掉的安全过河计划。划。状态空间法状态空间法3.状态空间的例子状态空间的例子1616 解

7、：首先选取描述问题状态的方法。在这个问题中，需要解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态右岸。从而可用一个三元组来表示状态 S=(m,c,b)其中，其中，m表示左岸的修道士人数，表示左岸的修道士人数，c表示左岸的野人数，表示左岸的野人数，b表示表示左岸的船数。左岸的船数。右岸的状态可由下式确定：右岸的状态可由下式确定：右岸修道士数右岸修道士数 m=3-m 右岸野人数右岸野人数 c=3-c 右岸船数右岸船数 b=1-b 在这种表示方式下，在这种表

8、示方式下，m和和c都可取都可取0、1、2、3中之一，中之一，b可取可取0和和1中之一。因此，共有中之一。因此，共有442=32种状态。种状态。状态空间法状态空间法3.状态空间的例子状态空间的例子1717 这这32种状态并非全有意义，除去不合法状态和修道士被野人吃种状态并非全有意义，除去不合法状态和修道士被野人吃掉的状态，有意义的状态只有掉的状态，有意义的状态只有16种：种：S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S

9、11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)有了这些状态，还需要考虑可进行的操作。有了这些状态，还需要考虑可进行的操作。操作是指用船把修道士或野人从河的左岸运到右岸，或从河的操作是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。右岸运到左岸。每个操作都应当满足如下条件：每个操作都应当满足如下条件：一是船至少有一个人（一是船至少有一个人（m或或c）操作，离开岸边的操作，离开岸边的m和和c的减少数的减少数目应该等于到达岸边的目应该等于到达岸边的m和和c的增加数目；的增加数目；二是每次操作船上人数不得超过二是每次操作船上人

10、数不得超过2个；个；三是操作应保证不产生非法状态。三是操作应保证不产生非法状态。因此，操作应由条件部分和动作部分：因此，操作应由条件部分和动作部分：条件条件：只有当其条件具备时才能使用只有当其条件具备时才能使用 动作：刻划了应用此操作所产生的结果。动作：刻划了应用此操作所产生的结果。1818操作的表示：操作的表示：用符号用符号Pij表示从左岸到右岸的运人操作表示从左岸到右岸的运人操作 用符号用符号Qij表示从右岸到左岸的操作表示从右岸到左岸的操作其中：其中：i表示船上的修道士人数表示船上的修道士人数 j表示船上的野人数表示船上的野人数操作集操作集 本问题有本问题有10种操作可供选择：种操作可供

11、选择：F=P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20 下面以下面以P01和和Q01为例来说明这些操作的条件和动作。为例来说明这些操作的条件和动作。操作符号操作符号 条件条件 动作动作 P01 b=1,m=0或或m=3，c1 b=0,c=c-1 Q01 b=0,m=0或或m=3，c2 b=1,c=c+1 1919搜索问题S0Sg2020如何实现搜索？讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。21211.1 回溯策略例：皇后问题2222()2323()Q(1,1)2424()QQ(1,1

12、)(1,1)(2,3)2525()Q(1,1)(1,1)(2,3)2626()QQ(1,1)(1,1)(2,3)(1,1)(2,4)2727()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)2828()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)2929()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)3030()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)3131()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.

13、2)Q(1,2)3232()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)3333()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)3434()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)Q(1,2)(2,4)(3,1)(4,3)3535递归的思想（续）当前状态目标状态g3636一个递归的例子int ListLenght(LIS

14、T*pList)if(pList=NULL)return 0;else return ListLength(pList-next)+1;NULLpLIST1233737回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。3838回溯搜索算法递归过程BACKTRACK(DATA)1,IF TERM(DATA)RETURN NIL;2,IF DEADEND(DATA)RETURN FAIL;3,RULES:=APPRULES(DATA);4,LOOP:IF NULL(RULES)RETURN FAIL;5,R:=FIRS

15、T(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);3939存在问题及解决办法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态l问题：深度问题死循环问题4040回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。4141回溯搜索算法11,DATA:=FIRST(DATALI

16、ST)2,IF MENBER(DATA,TAIL(DATALIST)RETURN FAIL;3,IF TERM(DATA)RETURN NIL;4,IF DEADEND(DATA)RETURN FAIL;5,IF LENGTH(DATALIST)BOUND RETURN FAIL;6,RULES:=APPRULES(DATA);7,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);4242回溯搜索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DA

17、TALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);4343一些深入的问题失败原因分析、多步回溯QQ4444一些深入问题（续）回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ3 2 2 345451.2 图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。4646一些基本概念节点深度：根节点深度=0其它节点深度=父节点深度+101234747一些基本概念（续1）路径设一节点序列为(n0,

18、n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。4848一些基本概念（续1）扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。4949一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IF OPEN=()THEN EXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,I

19、F GOAL(n)THEN EXIT(SUCCESS);6,EXPAND(n)mi,G:=ADD(mi,G);5050一般的图搜索算法（续）7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GO LOOP；5151节点类型说明.mjmkml5252修改指针举例123456s5353修改指针举例（续1）123456s5454123456修改指针举例（续2）s5555123456修改指针举例（续3）s56561.3 无信息图搜索过程深度优先搜索宽度优先搜索575

20、7深度优先搜索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,CLOSED);6,IF DEPTH(n)Dm GO LOOP;7,EXPAND(n)mi,G:=ADD(mi,G);8,IF 目标在mi中 THEN EXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GO LOOP;58581 2 38 47 6 52 31 8 47

21、6 559592 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abc

22、d1 2 3 8 47 6 5目标6060深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举图搜索是一个通用的与问题无关的方法6161宽度优先搜索宽度优先搜索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,CLOSED);6,EXPAND(n)mi,G:=ADD(mi,G);7,IF 目标

23、在mi中 THEN EXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GO LOOP;62622 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标82 3 41 8 7

24、6 546363宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法64641.4 启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解*6565希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。*6666基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。*67671，启发式搜索算法A（A算法）评

25、价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数h(n)：启发函数*6868符号的意义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)的估计值*6969A算法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,C

26、LOSED);6,EXPAND(n)mi,计算f(n,mi):=g(n,mi)+h(mi);7070A算法（续）ADD(mj,OPEN),标记mj到n的指针；IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),标记mk到n的指针；IF f(n,ml)t的最短路径,对某一中间结点I,只要考虑s 到I的最短路径分支,其余路径不考虑,A算法就成为了动态规划算法。79792，最佳图搜索算法A*（A*算法）在A算法中，如果满足条件：h(n)h*(n)则A算法称为A*算法。*8080A*条件举例8数码问题h1(n)=“不在位”的将牌数h2(n)=将牌“不在位”的距离和2 8 31 6 4

27、7 51 2 3457 6 8将牌1：1将牌2：1将牌6：1将牌8：2*8181A*算法的性质A*算法的假设算法的假设 设ni、nj是任意两个节点，有：C(ni,nj)其中为大于0的常数几个等式几个等式 f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。*8282A*算法的性质（续1）定理1.1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。*8383A*算法的性质（续2）引理1.1：对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f

28、(n)f*(s)。*8484A*算法的性质（续3）引理1.2：A*结束前，OPEN表中必存在f(n)f*(s)。存在一个节点n，n在最佳路径上。f(n)=g(n)+h(n)=g*(n)+h(n)g*(n)+h*(n)=f*(n)=f*(s)*8585A*算法的性质（续3）定理1.2：对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。引理1.1：A*如果不结束，则OPEN中所有的n有f(n)f*(s)引理1.2：在A*结束前，必存在节点n，使得 f(n)f*(s)所以，如果A*不结束，将导致矛盾。*8686A*算法的性质（续4）推论1.1：OPEN表上任一具有f(n)f*(s)

29、的节点n，最终都将被A*选作扩展的节点。由定理1.2，知A*一定结束，由A*的结束条件，OPEN表中f(t)最小时才结束。而 f(t)f*(t)f*(s)所以f(n)f*(s)由引理1.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扩展的节点数*9191A*算法的性质（续7）注意：注意：在定理1.4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论

30、被扩展多少次，都只计算一次。*9292定理1.4的证明使用数学归纳法，对节点的深度进行归纳（1）当d(n)0时，即只有一个节点，显然定理成立。（2）设d(n)k时定理成立。（归纳假设）（3）当d(n)=k+1时，用反证法。设存在一个深度为k1的节点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父节点，即n已经被生成了。因此当A1结束时，n将被保留在OPEN中。9393定理1.4的证明（续1）所以有：f1(n)f*(s)即：g1(n)+h1(n)f*(s)所以：h1(n)f*(s)-g1(n)另一方面，由于A2扩展了n，有f2(n)f*(s)(引理1.2)即：h2(n)f*(s)g2

31、(n)(A)由于d(n)=k时，A2扩展的节点A1一定扩展，有 g1(n)g2(n)(因为A2的路A1均走到了)所以：h1(n)f*(s)-g1(n)f*(s)g2(n)(B)比较A、B两式，有 h1(n)h2(n)，与定理条件矛盾。故定理得证。9494对h的评价方法平均分叉树设共扩展了d层节点，共搜索了N个节点，则:其中，b*称为平均分叉树。b*越小，说明h效果越好。实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化。9595对h的评价举例例：8数码问题，随机产生若干初始状态。使用h1：d=14,N=539,b*=1.44;d=20,N=7276，b*=1.47；使用h2：d=

32、14,N=113,b*=1.23;d=20,N=676,b*=1.279696A*的复杂性一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时：abs(h(n)-h*(n)O(log(h*(n)A*的算法复杂性才是非指数型的，但是通常情况下，h与h*的差别至少是和离目标的距离成正比的。*97973，A*算法的改进问题的提出：因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。*9898s(10)A(1)B(5)C(8)G 目标631118一个例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A

33、(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)*9999出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。s(10)A(1)B(5)C(8)G 目标631118*100100解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。*10

34、1101改进的条件可采纳性不变不多扩展节点不增加算法的复杂性*102102对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足h(ni)-h(nj)c(ni,nj)h(t)=0或 h(ni)c(ni,nj)+h(nj)h(t)=0 则称h是单调的。h(ni)ninjh(nj)c(ni,nj)*103103h单调的性质定理1.5：若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有g(n)=g*(n)。*104104定理1.5的证明设n是A*扩展的任一节点。当ns时，定理显然成立。下面考察n s的情况。设P(n

35、0=s,n1,n2,nk=n)是s到n的最佳路径P中一定有节点在CLOSED中，设P中最后一个出现在CLOSED中的节点为nj，则nj+1在OPEN中。105105定理1.5的证明（续1）由单调限制条件，对P中任意节点ni有：h(ni)C(ni,ni+1)+h(ni+1)g*(ni)+h(ni)g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最佳路径上，所以：g*(ni+1)=g*(ni)+C(ni,ni+1)带入上式有：g*(ni)+h(ni)g*(ni+1)+h(ni+1)从i=j到i=k-1应用上不等式，有：g*(nj+1)+h(nj+1)g*(nk)+h(nk)即

36、：f(nj+1)g*(n)+h(n)注意：(nj在CLOSED中，nj+1在OPEN中)106106定理1.5的证明（续2）重写上式：f(nj+1)g*(n)+h(n)另一方面，A*选n扩展，必有：f(n)=g(n)+h(n)f(nj+1)比较两式，有：g(n)g*(n)但已知g*(n)是最佳路径的耗散值，所以只有：g(n)=g*(n)。得证。107107h单调的性质（续）定理1.6：若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(ni)f(nj)。*108108定理1.6的证明由单调限制条件，有：h(ni)h(nj)C(ni,nj)=f(ni)-g(ni)=f(nj)-g

37、(nj)f(ni)-g(ni)-f(nj)+g(nj)C(ni,nj)=g(ni)+C(ni,nj)f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)C(ni,nj)f(ni)-f(nj)0，得证。*109109h单调的例子8数码问题：h为“不在位”的将牌数 1h(ni)-h(nj)=0(nj为ni的后继节点)-1 h(t)=0c(ni,nj)=1 满足单调的条件。*110110对算法加以改进一些结论：OPEN表上任以具有f(n)f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)f*(s)。*111111改进的出发点OPEN=()f*(s)f值小于f*(s)的节点f

38、值大于等于f*(s)的节点fm：到目前为止已扩展节点的最大f值，用fm代替f*(s)h(n)=0 for nodes in NEST*112112修正过程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,NEST:=ni|f(ni)fmIF NEST ()THEN n:=NEST中g最小的节点 ELSE n:=FIRST(OPEN),fm:=f(n);4,8:同过程A。*113113s(10)A(1)B(5)C(8)G 目标631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10

39、A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)*114114h的单调化方法如果令：f(n)=max(f(n的父节点),g(n)+h(n)则容易证明，这样处理后的h是单调的。*115115搜索算法的讨论1.弱方法盲目搜索算法产生组合爆炸启发搜索算法属于弱方法,不能保证找到解2.算法分析数学分析统计分析程序分析分析指标:时间和空间*116116作业1.28数码问题.Figure 1.17h1(n)=“不在位”的将牌数Draw out the searching tree using A*117117