人工智能-第一章课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第1章、搜索问题,有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等),许多实际问题（如最优路径规划、人力排班、装箱问题、机器人行动规划等）,都可以归结为在某一状态空间中搜索目标或路径的问题。,1,第1章、搜索问题有许多智力问题(如梵塔问题、旅行商问题、八皇,2,2,3,3,4,4,5,5,问题 ： 如何解决这类问题？,这类问题不能用简单的数学公式/数学方程来描述，属于非结构化问题。,难以获得求解所需的全部信息；更没有现成的算法可供求解使用,属于组合爆炸问题，稍大规模的问题就超出了人类的认知负荷,解决方法：利用计算机的超人计算能力，通过不断试探搜索找到问题的（最优）解。优点建模简单,6,问题 ： 如何解决这类问题？这类问题不能用简单的数学公式/数,具体方法： 状态空间法,状态：是指问题状态的的向量表示（x,y,z,.)。,问题有初始状态，有目标状态,有些状态可能是非法的，问题不可能发展到那种状态,问题表示为向量，向量就是在Euclidean空间，因此问题的初始状态和目标状态都是此空间中的点。,此类问题的特征是找出从初始状态到目标状态的路径，方法是通过一个状态向另一个状态的转换实现的。,7,具体方法： 状态空间法状态：是指问题状态的的向量表示（x,y,问题状态的表示方法（一）,8,问题状态的表示方法（一）8,问题状态的表示方法（二）,9,问题状态的表示方法（二）9,问题状态的变迁,10,问题状态的变迁10,问题状态的表示方法,11,问题状态的表示方法11,问题状态的变迁,12,问题状态的变迁12,搜索问题-主要内容,内容：,状态空间的搜索问题。,搜索方式：,盲目搜索,启发式搜索,关键问题：,如何利用知识，尽可能有效地找到问题的解（最佳解），寻找过程就是搜索。,13,搜索问题-主要内容内容：13,状态空间法,1. 状态空间表示方法,状态(State)：求解过程中每一步问题状况的表示,S,k,=S,k0, S,k1,),当对每一个分量都给以确定的值时，就得到了一个具体的状态。,操作(Operator): 也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。,状态空间(State space): 用来描述一个问题的全部状态以及这些状态之间的相互关系。常用表示为(S, F, G),其中，S为问题的所有初始状态的集合；F为操作的集合；G为目标状态的集合。,状态空间也可用一个赋值的有向图来表示，称为状态空间图,其中节点表示问题的状态，有向边表示操作。,14,状态空间法1. 状态空间表示方法状态(State)：求解过程,状态空间法求解问题的基本过程：,首先为问题选择适当的“状态”及“操作”的形式化描述方法；,然后从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止；,此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。,状态空间法,2. 状态空间问题求解,15,状态空间法求解问题的基本过程：状态空间法15,修道士(Missionaries)和野人(Cannibals)问题(简称M-C问题)。,设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：,修道士和野人都会划船，但每次船上至多可载两个人；,在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。,如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。,状态空间法,3. 状态空间的例子,16,修道士(Missionaries)和野人(Cann,解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态,S=(m, c, b),其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数。,右岸的状态可由下式确定：,右岸修道士数 m=3-m,右岸野人数 c=3-c,右岸船数 b=1-b,在这种表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有442=32种状态。,状态空间法,3. 状态空间的例子,17,解：首先选取描述问题状态的方法。在这个问题中，需,这32种状态并非全有意义，除去不合法状态和修道士被野人吃掉的状态，有意义的状态只有16种：,S,0,=(3, 3, 1) S,1,=(3, 2, 1) S,2,=(3, 1, 1) S,3,=(2, 2, 1),S,4,=(1, 1, 1) S,5,=(0, 3, 1) S,6,=(0, 2, 1) S,7,=(0, 1, 1),S,8,=(3, 2, 0) S,9,=(3, 1, 0) S,10,=(3, 0, 0) S,11,=(2, 2, 0),S,12,=(1, 1,0) S,13,=(0, 2, 0) S,14,=(0, 1, 0) S,15,=(0, 0, 0),有了这些状态，还需要考虑可进行的操作。,操作是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。,每个操作都应当满足如下条件：,一是船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；,二是每次操作船上人数不得超过2个；,三是操作应保证不产生非法状态。,因此，操作应由条件部分和动作部分：,条件：只有当其条件具备时才能使用,动作：刻划了应用此操作所产生的结果。,18,这32种状态并非全有意义，除去不合法状态和修道士,操作的表示：,用符号P,ij,表示从左岸到右岸的运人操作,用符号Q,ij,表示从右岸到左岸的操作,其中：,i表示船上的修道士人数,j表示船上的野人数,操作集,本问题有10种操作可供选择：,F=P,01, P,10, P,11, P,02, P,20,Q,01, Q,10, Q,11, Q,02, Q,20,下面以P,01,和Q,01,为例来说明这些操作的条件和动作。,操作符号 条件 动作,P,01,b=1, m=0或m=3， c1 b=0, c=c-1,Q,01,b=0, m=0,或,m=3，c2 b=1, c=c+1,19,操作的表示： 19,搜索问题,S,0,S,g,20,搜索问题S0Sg20,如何实现搜索？,讨论的问题：,有哪些常用的搜索算法。,问题有解时能否找到解。,找到的解是最佳的吗？,什么情况下可以找到最佳解？,求解的效率如何。,21,如何实现搜索？讨论的问题：21,1.1 回溯策略,例：皇后问题,22,1.1 回溯策略例：皇后问题22,( ),23,( )23,( ),Q,(1,1),24,( )Q(1,1)24,( ),Q,Q,(1,1),(1,1) (2,3),25,( )QQ(1,1)(1,1) (2,3)25,( ),Q,(1,1),(1,1) (2,3),26,( )Q(1,1)(1,1) (2,3)26,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),27,( )QQ(1,1)(1,1) (2,3)(1,1,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),Q,(1,1) (2,4) (3.2),28,( )QQ(1,1)(1,1) (2,3)(1,1,( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),29,( )QQ(1,1)(1,1) (2,3)(1,1,( ),Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),30,( )Q(1,1)(1,1) (2,3)(1,1),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),31,( )(1,1)(1,1) (2,3)(1,1),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),32,( )(1,1)(1,1) (2,3)(1,1),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),33,( )(1,1)(1,1) (2,3)(1,1),( ),(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),34,( )(1,1)(1,1) (2,3)(1,1),( ),(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),35,( )(1,1)(1,1) (2,3)(1,1),递归的思想（续）,当前状态,目标状态g,36,递归的思想（续）当前状态目标状态g36,一个递归的例子,int ListLenght(LIST *pList),if (pList = NULL) return 0;,else return ListLength(pList-next)+1;,NULL,pLIST,1,2,3,37,一个递归的例子int ListLenght(LIST *pL,回溯搜索算法,BACKTRACK（DATA）,DATA：当前状态。,返回值：从当前状态到目标状态的路径,（以规则表的形式表示）,或FAIL。,38,回溯搜索算法BACKTRACK（DATA）38,回溯搜索算法,递归过程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:=FIRST(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);,39,回溯搜索算法递归过程BACKTRACK(DATA)39,存在问题及解决办法,解决办法：,对搜索深度加以限制,记录从初始状态到当前状态的路径,当前状态,问题：,深度问题,死循环问题,40,存在问题及解决办法解决办法：当前状态问题：40,回溯搜索算法1,BACKTRACK1（DATALIST）,DATALIST：从初始到当前的状态表（逆向）,返回值：从当前状态到目标状态的路径,（以规则表的形式表示）,或FAIL。,41,回溯搜索算法1BACKTRACK1（DATALIST）41,回溯搜索算法1,1, DATA:=FIRST(DATALIST),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);,42,回溯搜索算法11, DATA:=FIRST(DATALIS,回溯搜索算法1（续）,9,RULES:=TAIL(RULES);,10,RDATA:=GEN(R, DATA);,11,RDATALIST:=CONS(RDATA, DATALIST);,12,PATH:=BACKTRCK1(RDATALIST),13,IF PATH=FAIL GO LOOP;,14,RETURN CONS(R, PATH);,43,回溯搜索算法1（续）9,RULES:=TAIL(RULE,一些深入的问题,失败原因分析、多步回溯,Q,Q,44,一些深入的问题失败原因分析、多步回溯QQ44,一些深入问题（续）,回溯搜索中知识的利用,基本思想(以皇后问题为例)：,尽可能选取划去对角线上位置数最少的。,Q,Q,Q,Q,3 2 2 3,45,一些深入问题（续）回溯搜索中知识的利用QQQQ3,1.2 图搜索策略,问题的引出,回溯搜索：只保留从初始状态到当前状态的一条路径。,图搜索：保留所有已经搜索过的路径。,46,1.2 图搜索策略问题的引出46,一些基本概念,节点深度：,根节点深度=0,其它节点深度=父节点深度+1,0,1,2,3,47,一些基本概念节点深度：012347,一些基本概念（续1）,路径,设一节点序列为(n,0, n,1,n,k,)，对于i=1,k，若节点n,i-1,具有一个后继节点n,i,，则该序列称为从n,0,到n,k,的路径。,路径的耗散值,一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(n,i, n,j,),表示从n,i,到n,j,的路径的耗散值。,48,一些基本概念（续1）路径48,一些基本概念（续1）,扩展一个节点,生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,49,一些基本概念（续1）扩展一个节点49,一般的图搜索算法,1, G=G,0,(G,0,=s), OPEN:=(s);,2, CLOSED:=( );,3, LOOP: IF OPEN=( ) THEN EXIT(FAIL);,4, n:=FIRST(OPEN), REMOVE(n, OPEN),ADD(n, CLOSED);,5, IF GOAL(n) THEN EXIT(SUCCESS);,6, EXPAND(n)m,i, G:=ADD(m,i, G);,50,一般的图搜索算法1, G=G0 (G0=s), OPEN:=,一般的图搜索算法（续）,7, 标记和修改指针：,ADD(m,j, OPEN),并标记m,j,到n的指针；,计算是否要修改m,k,、m,l,到n的指针；,计算是否要修改m,l,到其后继节点的指针；,8, 对OPEN中的节点按,某种原则,重新排序；,9, GO LOOP；,51,一般的图搜索算法（续）7, 标记和修改指针：51,节点类型说明,.,.,.,.,.,m,j,m,k,m,l,52,节点类型说明.mjmk,修改指针举例,1,2,3,4,5,6,s,53,修改指针举例123456s53,修改指针举例（续1）,1,2,3,4,5,6,s,54,修改指针举例（续1）123456s54,1,2,3,4,5,6,修改指针举例（续2）,s,55,123456修改指针举例（续2）s55,1,2,3,4,5,6,修改指针举例（续3）,s,56,123456修改指针举例（续3）s56,1.3 无信息图搜索过程,深度优先搜索,宽度优先搜索,57,1.3 无信息图搜索过程深度优先搜索57,深度优先搜索,1, G:=G,0,(G,0,=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) m,i, G:=ADD(m,i, G);,8, IF 目标在m,i,中 THEN EXIT(SUCCESS);,9, ADD(m,j, OPEN), 并标记m,j,到n的指针;,10, GO LOOP;,58,深度优先搜索1, G:=G0(G0=s), OPEN:=(s,1 2 3,8 4,7 6 5,2 3,1 8 4,7 6 5,59,1 2 32 359,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1 7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,5,6,7,8,9,a,b,c,d,1 2 3,8 4,7 6 5,目标,60,2 3 2 32 8 32,深度优先搜索的性质,一般不能保证找到最优解,当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制,最坏情况时，搜索空间等同于穷举,图搜索是一个通用的与问题无关的方法,61,深度优先搜索的性质一般不能保证找到最优解61,宽度优先搜索,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) m,i, G:=ADD(m,i, G);,7, IF 目标在m,i,中 THEN EXIT(SUCCESS);,8,ADD(OPEN, m,j,),并标记m,j,到n的指针;,9, GO LOOP;,62,宽度优先搜索1, G:=G0(G0=s), OPEN:=(s,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,5,6,7,3,1 2 3,8 4,7 6 5,目标,8,2 3 4,1 8,7 6 5,4,63,2 3 2 32 8 32,宽度优先搜索的性质,当问题有解时，一定能找到解,当问题为单位耗散值，且问题有解时，一定能找到最优解,方法与问题无关，具有通用性,效率较低,属于图搜索方法,64,宽度优先搜索的性质当问题有解时，一定能找到解64,1.4 启发式图搜索,利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。,启发信息的强度,强：降低搜索工作量，但可能导致找不到最 优解,弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解,*,65,1.4 启发式图搜索利用知识来引导搜索，达到减少搜索范围，降,希望：,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,*,66,希望：*66,基本思想,定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,*,67,基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一,1，启发式搜索算法A（A算法）,评价函数的格式：,f(n) = g(n) + h(n),f(n)：评价函数,h(n)：启发函数,*,68,1，启发式搜索算法A（A算法）评价函数的格式：*68,符号的意义,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)的估计值,*,69,符号的意义g*(n)：从s到n的最短路径的耗散值*69,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),m,i,计算f(n, m,i,):=g(n, m,i,)+h(m,i,);,70,A算法1, OPEN:=(s), f(s):=g(s)+h(,A算法（续）,ADD(m,j, OPEN), 标记m,j,到n的指针；,IF f(n, m,k,)f(m,k,) THEN f(m,k,):=f(n, m,k,),标记m,k,到n的指针；,IF f(n, m,l,)t的最短路径,对某一中间结点I, 只要考虑s 到I的最短路径分支,其余路径不考虑, A算法就成为了动态规划算法。,79,动态规划算法79,2，最佳图搜索算法A*（A*算法）,在A算法中，如果满足条件：,h(n)h*(n),则A算法称为A*算法。,*,80,2，最佳图搜索算法A*（A*算法）在A算法中，如果满足条件：,A*条件举例,8数码问题,h1(n) = “不在位”的将牌数,h2(n) =,将牌“不在位”的距离和,2,8,3,1,6,4,7 5,1 2 3,4,5,7 6,8,将牌1：1,将牌2：1,将牌6：1,将牌8：2,*,81,A*条件举例8数码问题2 8 31 2,A*算法的性质,A*算法的假设,设n,i,、n,j,是任意两个节点，有：,C(n,i, n,j,) ,其中为大于0的常数,几个等式,f*(s) = f*(t) = h*(s) = g*(t) = f*(n),其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。,*,82,A*算法的性质A*算法的假设几个等式*82,A*算法的性质（续1）,定理1.1：,对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。,*,83,A*算法的性质（续1）定理1.1：*83,A*算法的性质（续2）,引理1.1 ：,对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)f*(s)。,*,84,A*算法的性质（续2）引理1.1 ：*84,A*算法的性质（续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),*,85,A*算法的性质（续3）引理1.2：存在一个节点n，n在*,A*算法的性质（续3）,定理1.2：,对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。,引理1.1：A*如果不结束，则OPEN中所有的n有f(n) f*(s),引理1.2：在A*结束前，必存在节点n，使得 f(n) f*(s),所以，如果A*不结束，将导致矛盾。,*,86,A*算法的性质（续3）定理1.2：引理1.1：A*如果不结束,A*算法的性质（续4）,推论1.1：,OPEN表上任一具有f(n)f*(s)的节点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) h,1,(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A,2,所扩展的每一个节点，也必定由A,1,所扩展，即A,1,扩展的节点数至少和A,2,一样多。,简写：如果h,2,(n),h,1,(n) (目标节点除外)，则A,1,扩展的节点数,A,2,扩展的节点数,*,91,A*算法的性质（续7）定理1.4：设对同一个问题定义了两个A,A*算法的性质（续7）,注意：,在定理1.4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。,*,92,A*算法的性质（续7）注意：*92,定理1.4的证明,使用数学归纳法，对节点的深度进行归纳,（1）当d(n)0时，即只有一个节点，显然定理成立。,（2）设d(n)k时定理成立。（归纳假设）,（3）当d(n)=k+1时，用反证法。,设存在一个深度为k1的节点n，被A,2,扩展，但没有被A,1,扩展。而由假设，A,1,扩展了n的父节点，即n已经被生成了。因此当A,1,结束时，n将被保留在OPEN中。,93,定理1.4的证明使用数学归纳法，对节点的深度进行归纳93,定理1.4的证明（续1）,所以有：f,1,(n) f*(s),即：g,1,(n)+h,1,(n) f*(s),所以： h,1,(n) f*(s) - g,1,(n),另一方面，由于A,2,扩展了n，有f2(n) f*(s) (引理1.2),即： h,2,(n) f*(s) g,2,(n) (A),由于d(n)=k时，A,2,扩展的节点A,1,一定扩展，有,g,1,(n) g,2,(n) (因为A,2,的路A,1,均走到了),所以： h,1,(n) f*(s) - g,1,(n) f*(s) g,2,(n) (B),比较A、B两式，有 h,1,(n) h,2,(n) ，与定理条件矛盾。故定理得证。,94,定理1.4的证明（续1）所以有：f1(n) f*(s),对h的评价方法,平均分叉树,设共扩展了d层节点，共搜索了N个节点，则:,其中，b*称为平均分叉树。,b*越小，说明h效果越好。,实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化。,95,对h的评价方法平均分叉树95,对h的评价举例,例：8数码问题，随机产生若干初始状态。,使用h,1,：,d=14, N=539,b*=1.44;,d=20, N=7276， b*=1.47；,使用h,2,：,d=14, N=113, b*=1.23;,d=20, N=676,b*=1.27,96,对h的评价举例例：8数码问题，随机产生若干初始状态。96,A*的复杂性,一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时：,abs(h(n)-h*(n) O(log(h*(n),A*的算法复杂性才是非指数型的，但是通常情况下， h与h*的差别至少是和离目标的距离成正比的。,*,97,A*的复杂性一般来说，A*的算法复杂性是指数型的，可以证明，,3，A*算法的改进,问题的提出：,因A算法第6步对m,l,类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。,*,98,3，A*算法的改进问题的提出：*98,s(10),A(1),B(5),C(8),G 目标,6,3,1,1,1,8,一个例子：,OPEN表,CLOSED表,s(10),s(10),A(7),B(8) C(9),A(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),*,99,s(10)A(1)B(5)C(8)G 目标631118一个例,出现多次扩展节点的原因,在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。,s(10),A(1),B(5),C(8),G 目标,6,3,1,1,1,8,*,100,出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到,解决的途径,对h加以限制,能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。,对算法加以改进,能否对算法加以改进，避免或减少节点的多次扩展。,*,101,解决的途径对h加以限制*101,改进的条件,可采纳性不变,不多扩展节点,不增加算法的复杂性,*,102,改进的条件可采纳性不变*102,对h加以限制,定义：一个启发函数h，如果对所有节点n,i,和n,j,，其中n,j,是n,i,的子节点，满足,h(n,i,) - h(n,j,) c(n,i, n,j,),h(t) = 0,或,h(n,i,) c(n,i, n,j,) + h(n,j,),h(t) = 0,则称h是单调的。,h(n,i,),n,i,n,j,h(n,j,),c(n,i,n,j,),*,103,对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，,h单调的性质,定理1.5：,若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。,即：当A*选n扩展时，有g(n)=g*(n)。,*,104,h单调的性质定理1.5：*104,定理1.5的证明,设n是A*扩展的任一节点。当ns时，定理显然成立。下面考察n s的情况。,设P(n,0,=s, n,1, n,2, , n,k,=n)是s到n的最佳路径,P中一定有节点在CLOSED中，设P中最后一个出现在CLOSED中的节点为n,j,，则n,j+1,在OPEN中。,105,定理1.5的证明设n是A*扩展的任一节点。当ns时，定理显,定理1.5的证明（续1）,由单调限制条件，对P中任意节点n,i,有：,h(n,i,) C(n,i, n,i+1,)+h(n,i+1,),g*(n,i,),+h(n,i,) ,g*(n,i,),+C(n,i, n,i+1,)+h(n,i+1,),由于n,i,、n,i+1,在最佳路径上，所以：,g*(n,i+1,) = g*(n,i,)+C(n,i, n,i+1,),带入上式有：,g*(n,i,)+h(n,i,) g*(n,i+1,)+h(n,i+1,),从i=j到i=k-1应用上不等式，有：,g*(n,j+1,)+h(n,j+1,) g*(n,k,)+h(n,k,),即：f(n,j+1,) g*(n)+h(n),注意：(n,j,在CLOSED中，n,j+1,在OPEN中),106,定理1.5的证明（续1）由单调限制条件，对P中任意节点ni有,定理1.5的证明（续2）,重写上式：f(n,j+1,) g*(n)+h(n),另一方面，A*选n扩展，必有：,f(n) = g(n)+h(n) f(n,j+1,),比较两式，有：,g(n) g*(n),但已知g*(n)是最佳路径的耗散值，所以只有：g(n) = g*(n)。得证。,107,定理1.5的证明（续2）重写上式：f(nj+1) g*(,h单调的性质（续）,定理1.6：,若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(n,i,) f(n,j,)。,*,108,h单调的性质（续）定理1.6：*108,定理1.6的证明,由单调限制条件，有：,h(n,i,) h(n,j,) C(n,i, n,j,),=,f(n,i,)-g(n,i,),=,f(n,j,)-g(n,j,),f(n,i,)-g(n,i,) - f(n,j,)+g(n,j,) C(n,i, n,j,),=,g(n,i,)+C(n,i, n,j,),f(n,i,)-g(n,i,) - f(n,j,)+ g(n,i,)+C(n,i, n,j,) C(n,i, n,j,),f(n,i,) - f(n,j,) 0，得证。,*,109,定理1.6的证明由单调限制条件，有：= f(ni)-g(ni,h单调的例子,8数码问题：,h为“不在位”的将牌数,1,h(n,i,) - h(n,j,) = 0(n,j,为n,i,的后继节点),-1,h(t) = 0,c(n,i, n,j,) = 1,满足单调的条件。,*,110,h单调的例子8数码问题：*110,对算法加以改进,一些结论：,OPEN表上任以具有f(n) f*(s)的节点定会被扩展。,A*选作扩展的任一节点，定有f(n)f*(s)。,*,111,对算法加以改进一些结论：*111,改进的出发点,OPEN = ( ),f*(s),f值小于f*(s)的节点,f值大于等于f*(s)的节点,f,m,：,到目前为止已扩展节点的最大f值，用f,m,代替f*(s),h(n)=0 for nodes in NEST,*,112,改进的出发点OPEN = ( )f*(,修正过程A,1, OPEN:=(s), f(s)=g(s)+h(s), f,m,:=0;,2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);,3, NEST:=n,i,|f(n,i,)f,m,IF NEST ( ) THEN n:=NEST中g最小的节点,ELSE n:=FIRST(OPEN),f,m,:=f(n);,4, , 8:,同过程A。,*,113,修正过程A1, OPEN:=(s), f(s)=g(s)+h,s(10),A(1),B(5),C(8),G 目标,6,3,1,1,1,8,前面的例子：,OPEN表,CLOSED表,f,m,s(0+10),s(0+10),10,A(6+1) B(3+5) C(1+8),s(0+10) C(1+8),10,A(6+1) B(2+5),s(0+10) C(1+8) B(2+5),10,A(3+1),s(0+10)C(1+8)B(2+5)A(3+1),10,G(11+0),*,114,s(10)A(1)B(5)C(8)G 目标631118前面的,h的单调化方法,如果令：,f(n) = max(f(n的父节点), g(n)+h(n),则容易证明，这样处理后的h是单调的。,*,115,h的单调化方法如果令：*115,搜索算法的讨论,1.弱方法,盲目搜索算法产生组合爆炸,启发搜索算法属于弱方法,不能保证找到解,2. 算法分析,数学分析,统计分析,程序分析,分析指标: 时间和空间,*,116,搜索算法的讨论1.弱方法*116,作业,1.2,8数码问题. Figure 1.17,h1(n) = “不在位”的将牌数,Draw out the searching tree using A,*,117,作业1.28数码问题. Figure 1.17*117,