清华大学《人工智能导论》课程电子教案(一)课件

《清华大学《人工智能导论》课程电子教案(一)课件》由会员分享，可在线阅读，更多相关《清华大学《人工智能导论》课程电子教案(一)课件（143页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,,*,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,第一章 产生式系统,,1943,年,Post,首先在一种计算形式体系中提出,,60,年代开始，成为专家系统的最基本的结构,,形式上很简单，但在一定意义上模仿了人类思考的过程,,,,,1,,1.1,产生式系统的基本组成,,组成三要素：,,,一个综合数据库,——,存放信息,,一组产生式规则,——,知识,,一个控制系统,——,规则的解释或执行程序 （控制策略） （推理引擎）,,2,,规则的一般形式,,

2、IF <,前提,> THEN <,结论,>,,IF <,条件,> THEN <,行动,>,,或者简写为：,,,<,前提,>,－,> <,结论,>,,<,条件,>,－,> <,行动,>,,3,,1.2,产生式系统的基本过程,,过程,PRODUCTION,,1,，,DATA←,初始数据库,,2，,until DATA,满足结束条件，,do,,3,，,{,,4,，,在规则集中选择一条可应用于,DATA,的规则,R,,5,，,DATA ←R,应用到,DATA,得到的结果,,6,，,},,4,,一个简单的例子,,问题：设字符转换规则,,,A∧B→C,,A∧C→D,,B∧C→G,,B∧E→

3、F,,D→E,,,已知：,A,，,B,,,求：,F,,5,,一个简单的例子（续,1,）,,一、综合数据库,,,{x},，,其中,x,为字符,,二、规则集,,,,1，IF A∧B THEN C,,2，IF A∧C THEN D,,3，IF B∧C THEN G,,4，IF B∧E THEN F,,5，IF D THEN E,,6,,一个简单的例子（续,2,）,,三、控制策略,,顺序排队,,四、初始条件,,,{A,，,B},,五、结束条件,,,F∈{x},,7,,求解过程,数据库 可触发规则 被触发规则,A，B,（1）,（1）,A，B，C,（,2,）

4、（,3,）,（2）,A，B，C，D,（,3,）（,5,）,（3）,A，B，C，D，G,（5）,（5）,A，B，C，D，G，E,（4）,（4）,A，B，C，D，G，E，F,1，IF A∧B THEN C 2，IF A∧C THEN D,,3，IF B∧C THEN G 4，IF B∧E THEN F,,5，IF D THEN E,,8,,1 .3,问题表示举例,,例,1,：传教士与野人问题（,M-C,问题）,,问题,：,N,个传教士，,N,个野人，一条船，可同时乘坐,k,个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。,,问：

5、如何过河。,,,以,N=3,，,k=2,为例求解。,,,9,,M-C,问题（续,1,）,,,,初始 目标,,,L R L R,,m 3 0 m 0 3,,c 3 0 c 0 3,,B 1 0 B 0

6、 1,,10,,M-C,问题（续,2,）,,1,，综合数据库,,（,m, c, b),，,,,其中：,0≤m, c≤3, b ∈{0, 1},,2,，,初始状态,,（,3,，,3,，,1,）,,3,，目标状态（结束状态）,,（,0,，,0,，,0,）,,,11,,M-C,问题（续,3,）,,4,，规则集,,,,IF (m, c, 1) THEN (m-1, c, 0),,IF (m, c, 1) THEN (m, c-1, 0),,IF (m, c, 1) THEN (m-1, c-1, 0),,IF (m, c, 1) THEN (m-2, c, 0),,IF (m, c, 1)

7、THEN (m, c-2, 0),,12,,M-C,问题（续,4,）,,,,IF (m, c, 0) THEN (m+1, c, 1),,IF (m, c, 0) THEN (m, c+1, 1),,IF (m, c, 0) THEN (m+1, c+1, 1),,IF (m, c, 0) THEN (m+2, c, 1),,IF (m, c, 0) THEN (m, c+2, 1),,,5,，,控制策略：（略）,,13,,M-C,问题（第二种方法）,,4,，规则集：,,,,IF (m, c, 1) AND 1 ≤i+j≤2 THEN (m-i, c-j, 0),,IF (m, c, 0) A

8、ND 1 ≤i+j≤2 THEN (m+i, c+j, 1),,,14,,猴子摘香蕉问题,,,,,,,,c a b,,15,,猴子摘香蕉问题（续,1,）,,1,，综合数据库,,（,M, B, Box, On, H,）,,,M,：,猴子的位置,,,B,：,香蕉的位置,,,Box,：,箱子的位置,,,On=0,：,猴子在地板上,,,On=1,：,猴子在箱子上,,,H=0,：,猴子没有抓到香蕉,,,H=1,：,猴子抓到了香蕉,,16,,猴子摘香蕉问题（续,2,）,,2,，初始状态,,（,c, a, b, 0, 0,）,,,3,，,结束状态,,（,x,1

9、,, x,2,, x,3,, x,4,, 1,）,,,其中,x,1,～,x,4,为变量。,,17,,猴子摘香蕉问题（续,3,）,,4,，规则集,,r1: IF (x, y, z, 0, 0) THEN (w, y, z, 0, 0),,r2: IF (x, y, x, 0, 0) THEN (z, y, z, 0, 0),,r3: IF (x, y, x, 0, 0) THEN (x, y, x, 1, 0),,r4: IF (x, y, x, 1, 0) THEN (x, y, x, 0, 0),,r5: IF (x, x, x, 1, 0) THEN (x,

10、x, x, 1, 1),,,其中,x, y, z, w,为变量,,18,,1.4,产生式系统的特点,,数据驱动,,知识的无序性,,控制系统与问题无关,,数据、知识和控制相互独立,,,19,,1.5,产生式系统的类型,,正向、逆向、双向产生式系统,,可交换的产生式系统,,可分解的产生式系统,,,20,,第二章 产生式系统的搜索策略,,内容：,,状态空间的搜索问题。,,搜索方式：,,盲目搜索,,启发式搜索,,关键问题：,,如何利用知识，尽可能有效地找到问题的解（最佳解）。,,21,,产生式系统的搜索策略（续,1,）,,S,0,S,g,,22,,产生式系统的搜索策略（续,2,）,,讨论的问题：,,,

11、有哪些常用的搜索算法。,,问题有解时能否找到解。,,找到的解是最佳的吗？,,什么情况下可以找到最佳解？,,求解的效率如何。,,23,,2.1,回溯策略,,例：皇后问题,,,24,,( ),,25,,( ),Q,((1,1)),,26,,( ),Q,Q,((1,1)),((1,1) (2,3)),,27,,( ),Q,((1,1)),((1,1) (2,3)),,28,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),,29,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),Q,((1,1) (2,4) (3.2))

12、,,30,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),((1,1) (2,4) (3.2)),,31,,( ),Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),((1,1) (2,4) (3.2)),,32,,( ),((1,1)),((1,1) (2,3)),((1,1) (2,4)),((1,1) (2,4) (3.2)),,33,,( ),((1,1)),((1,1) (2,3)),((1,1) (2,4)),((1,1) (2,4) (3.2)),Q,((1,2)),,34,,( ),((1,1)),((1,1)

13、 (2,3)),((1,1) (2,4)),((1,1) (2,4) (3.2)),Q,((1,2)),Q,((1,2) (2,4)),,35,,( ),((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)),,36,,( ),((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,

14、2) (2,4) (3,1) (4,3)),,37,,递归的思想,,,当前状态,目标状态,g,,38,,一个递归的例子,,int,,ListLenght(LIST,*,pList,),,{,,if (,pList,== NULL) return 0;,,else return,ListLength(pList,->next)+1;,,},NULL,pLIST,1,2,3,,39,,回溯搜索算法,,,BACKTRACK,（,DATA,）,,,,,DATA,：,当前状态。,,返回值：从当前状态到目标状态的路径,,（以规则表的形式表示）,,或,FAIL,。,,40,,回溯搜索算法,递归过程,BACK

15、TRACK(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);

16、,,41,,存在问题及解决办法,,解决办法：,,对搜索深度加以限制,,记录从初始状态到当前状态的路径,,当前状态,问题：,,深度问题,,死循环问题,,42,,回溯搜索算法,1,,BACKTRACK1,（,DATALIST,）,,,,,DATALIST,：,从初始到当前的状态表（逆向）,,返回值：从当前状态到目标状态的路径,,（以规则表的形式表示）,,或,FAIL,。,,,43,,回溯搜索算法,1,,1, DATA:=FIRST(DATALIST),,2, IF MENBER(DATA, TAIL(DATALIST)),,RETURN FAIL;,,,3, IF TERM(DATA) RE

17、TURN 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);,,,44,,回溯搜索算法,1,（续）,,9, RULES:=TAIL(RULES);,,10, RDATA:=GEN(R, DATA);,,11, RDATALIST:=CONS(RDATA, DATALIST);,,12, PATH:=

18、BACKTRCK1(RDATALIST),,13, IF PATH=FAIL GO LOOP;,,14, RETURN CONS(R, PATH);,,45,,一些深入的问题,,失败原因分析、多步回溯,,Q,Q,,46,,一些深入问题（续）,,回溯搜索中知识的利用,,基本思想,(,以皇后问题为例,),：,,尽可能选取划去对角线上位置数最少的。,Q,,Q,Q,,Q,3 2 2 3,,47,,2.2,图搜索策略,,问题的引出,,,回溯搜索：只保留

19、从初始状态到当前状态的一条路径。,,图搜索：保留所有已经搜索过的路径。,,,,48,,一些基本概念,,节点深度：,,根节点深度,=0,,,其它节点深度,=,父节点深度,+1,0,1,2,3,,49,,一些基本概念（续,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,的路径的耗散值。,,50,,一些基本概念（续

20、,1,）,,扩展一个节点,,生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为,“,扩展一个节点,”,。,,51,,一般的图搜索算法,,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);,,,52,,一般的图搜

21、索算法（续）,,7,,标记和修改指针：,,,ADD(m,j,, OPEN),,并标记,m,j,到,n,的指针；,,计算是否要修改,m,k,、,m,l,到,n,的指针；,,计算是否要修改,m,l,到其后继节点的指针；,,8,,,对,OPEN,中的节点按,某种原则,重新排序；,,9, GO LOOP,；,,53,,节点类型说明,,,…...,…...,…...,…...,…...,m,j,m,k,m,l,,54,,修改指针举例,1,2,3,4,5,6,s,,55,,修改指针举例（续,1,）,1,2,3,4,5,6,s,,56,,1,2,3,4,5,6,修改指针举例（续,2,）,s,,57,,1,2

22、,3,4,5,6,修改指针举例（续,3,）,s,,58,,2.3,无信息图搜索过程,,深度优先搜索,,宽度优先搜索,,,59,,深度优先搜索,,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,},

23、G:=ADD(m,i,, G);,,8, IF,目标在,{m,i,},中,THEN EXIT(SUCCESS);,,9,,ADD(m,j,, OPEN),,并标记,m,j,到,n,的指针,;,,10, GO LOOP;,,60,,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

24、 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,,

25、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,目标,,61,,深度优先搜索的性质,,一般不能保证找到最优解,,当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制,,最坏情况时，搜索空间等同于穷举,,与回溯法的差别：图搜索,,是一个通用的与问题无

26、关的方法,,,62,,宽度优先搜索,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

27、,到,n,的指针,;,,9, GO LOOP;,,63,,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

28、 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,,64,,宽度优先搜索的性质,,当问题有解时，一定能找到解,,当问题为单位耗散值，且问题有解时，一定能找到最优解,

29、,方法与问题无关，具有通用性,,效率较低,,属于图搜索方法,,,65,,渐进式深度优先搜索方法,,目的,,解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。,,思想,,首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。,,66,,2.4,启发式图搜索,,利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。,,启发信息的强度,,强：降低搜索工作量，但可能导致找不到最 优解,,弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解,,67,,希望：,,,引入启发知识，在保证找到最佳解的情况下，尽可能

30、减少搜索范围，提高搜索效率。,,,68,,基本思想,,定义一个评价函数,f,，,对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,,,69,,1,，启发式搜索算法,A,（,A,算法）,,评价函数的格式：,,,,f(n) = g(n) + h(n),,,f(n),：,评价函数,,,h(n),：,启发函数,,70,,符号的意义,,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

31、),、,f*(n),的估计值,,,71,,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,);,,,,72,,A,算法（续）,,,ADD(m,j,, OPEN),,标记,m,j,到,n,的指针；,,

32、,IF f(n,,m,k,)<,f(m,k,) THEN,f(m,k,):=f(n,,m,k,),,,,标记,m,k,到,n,的指针；,,,IF f(n, m,l,)

33、) = g(n) + h(n),,g(n),为从初始节点到当前节点的耗散值,,,h(n),为当前节点,“,不在位,”,的将牌数,,,2 8 3,,1 6 4,,7 5,,1 2 3,,8 4,,7 6 5,,,76,,h,计算举例,,h(n) =4,2,,8,3,,1,,6,4,,7 5,1 2 3,4,,5,7 6,,8,,77,,2 8 3,,1 6 4,,7 5,2 8 3,,1 4,,7 6 5,2 8

34、 3,,1 6 4,,7 5,2 8 3,,1 6 4,,7 5,2 3,,1 8 4,,7 6 5,2 8 3,,1 4,,7 6 5,2 8 3,,1 4,,7 6 5,2 8 3,,7 1 4,,6 5,,8 3,,2 1 4,,7 6 5,,2 3,,1 8 4,,7 6 5,2 3,,1 8 4,,7 6 5,1 2 3,,8 4,,7 6 5,1 2 3,,8

35、 4,,7 6 5,1 2 3,,7 8 4,,6 5,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,6,,78,,2,，最佳图搜索算法,A*,（,A*,算法）,,在,A,算法中，如果满足条件：,,,h(n)≤h*(n),,,则,A,算法称为,A*,算法。,,,,79,,A*,条件举例,,8,数码问题,,h1(n) =,“,不在位,”,的将牌数,,h2(n) =,将牌,“,不在位,”,的距离和,2,,8,3,,1,,6,4,,7

36、 5,1 2 3,4,,5,7 6,,8,将牌,1,：,1,,将牌,2,：,1,,将牌,6,：,1,,将牌,8,：,2,,80,,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,的最佳路径上的节点。,,81,,A*,算法的性质（续,1,）,,定理,1,：,,对有限图，如果从初始节点,s,到目标节点,t,有路

37、径存在，则算法,A,一定成功结束。,,,,82,,A*,算法的性质（续,2,）,,引理,2.1,：,,对无限图，若有从初始节点,s,到目标节点,t,的路径，则,A*,不结束时，在,OPEN,表中即使最小的一个,f,值也将增到任意大，或有,f(n)>f*(s),。,,83,,A*,算法的性质（续,3,）,,引理,2.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),,84,,A*,算法的性质（续

38、,3,）,,定理,2,：,,对无限图，若从初始节点,s,到目标节点,t,有路径存在，则,A*,一定成功结束。,引理,2.1,：,A*,如果不结束，则,OPEN,中所有的,n,有,f(n) > f*(s),,引理,2.2,：在,A*,结束前，必存在节点,n,，,使得,f(n) ≤ f*(s),,所以，如果,A*,不结束，将导致矛盾。,,85,,A*,算法的性质（续,4,）,,推论,2.1,：,,,OPEN,表上任一具有,f(n)

39、,,f(t) ≥,f*(t),＝,f*(s),,,所以,f(n) f*(s),,由引理,2.2,知结束前,OPEN,中存在,f(n)≤f*(s),的,节点,n,，,所以,,,f(n) ≤ f*(s) < f(t),,因此,A*,

40、应选择,n,扩展，而不是,t,。,与假设,A*,选择,t,结束矛盾。得证。,,注意,：,A*,的结束条件,,88,,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),，,得证。,,如果,n≠ n’,，,由于,A*,选择,n,扩展，而不是,n’,，,所以有,f(n) ≤ f(n’)≤f*(s),。,得证。,,89,,A*,算法的性质（续,7,）,,定理,4

41、,：设对同一个问题定义了两个,A*,算法,A,1,和,A,2,，若,A,2,比,A,1,有较多的启发信息，即对所有非目标节点有,h,2,(n) > h,1,(n),，,则在具有一条从,s,到,t,的路径的隐含图上，搜索结束时，由,A,2,所扩展的每一个节点，也必定由,A,1,所扩展，即,A,1,扩展的节点数至少和,A,2,一样多。,,简写：如果,h,2,(n),>,h,1,(n) (,目标节点除外,),，则,A,1,扩展的节点数,≥,A,2,扩展的节点数,,90,,A*,算法的性质（续,7,）,,注意：,,,在定理,4,中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只

42、计算一次。,,91,,定理,4,的证明,,使用数学归纳法，对节点的深度进行归纳,,（,1,）当,d(n),＝,0,时，即只有一个节点，显然定理成立。,,（,2,）设,d(n)≤k,时定理成立。（归纳假设）,,（,3,）当,d(n)=k+1,时，用反证法。,,设存在一个深度为,k,＋,1,的节点,n,，被,A,2,扩展，但没有被,A,1,扩展。而由假设，,A,1,扩展了,n,的父节点，即,n,已经被生成了。因此当,A,1,结束时，,n,将被保留在,OPEN,中。,,92,,定理,4,的证明（续,1,）,,所以有：,f,1,(n) ≥ f*(s),,,即：,g,1,(n)+h,1,(n) ≥ f*

43、(s),,所以：,h,1,(n) ≥ f*(s) - g,1,(n),,另一方面，由于,A,2,扩展了,n,，有,f2(n) ≤ f*(s),,即：,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),，与,定理条

44、件矛盾。故定理得证。,,93,,对,h,的评价方法,,平均分叉树,,设共扩展了,d,层节点，共搜索了,N,个节点，则,:,,,,,其中，,b*,称为平均分叉树。,,b*,越小，说明,h,效果越好。,,实验表明，,b*,是一个比较稳定的常数，同一问题基本不随问题规模变化。,,94,,对,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,

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

46、(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),,98,,出现多次扩展节点的原因,,在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点,A,。,,s(10),A(1),B(5),C(8),G,目标,6,3,1,1,1,8,,99,,解决的途径,,对,h,加以

47、限制,,能否对,h,增加适当的限制，使得第一次扩展一个节点时，就找到了从,s,到该节点的最短路径。,,对算法加以改进,,能否对算法加以改进，避免或减少节点的多次扩展。,,100,,改进的条件,,可采纳性不变,,不多扩展节点,,不增加算法的复杂性,,,101,,对,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,是单

48、调的。,h(n,i,),n,i,n,j,h(n,j,),c(n,i,,n,j,),,102,,h,单调的性质,,定理,5,：,,若,h(n),是单调的，则,A*,扩展了节点,n,之后，就已经找到了到达节点,n,的最佳路径。,,即：当,A*,选,n,扩展时，有,g(n)=g*(n),。,,103,,定理,5,的证明,,设,n,是,A*,扩展的任一节点。,当,n,＝,s,时，定理显然成立。下面考察,n ≠s,的情况。,,设,P,＝,(n,0,=s, n,1,, n,2,, …,,n,k,=n),是,s,到,n,的最佳路径,,P,中一定有节点在,CLOSED,中，设,P,中最后一个出现在,CLOSE

49、D,中的节点为,n,j,，则,n,j+1,在,OPEN,中,。,,104,,定理,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,),,从

50、,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,中,),,105,,定理,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)

51、,。,得证。,,106,,h,单调的性质（续）,,定理,6,：,,若,h(n),是单调的，则由,A*,所扩展的节点序列其,f,值是非递减的。即,f(n,i,) ≤,f(n,j,),。,,,,107,,定理,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(

52、n,i,),+C(n,i,,,n,j,),≤,C(n,i,,,n,j,),,,f(n,i,) -,f(n,j,),,≤ 0,，,得证。,,,108,,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,,,,满足单调的条件。,,,109,,对算法加以改进,,一些结论：,,OPEN,表上任以具有,f(n) < f*(s),的节点定会被扩展。,,A*,选作扩展的任一节点，定有,f(n)≤f*(s),。,,

53、,110,,改进的出发点,,OPEN = ( … … … … ),f*(s),f,值小于,f*(s),的节点,,f,值大于等于,f*(s),的节点,,f,m,：,到目前为止已扩展节点的最大,f,值，,用,f,m,代替,f*(s),,111,,修正过程,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,)

54、,,,f,m,:=f(n);,,4, …, 8:,同过程,A,。,,112,,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),,113,,h,的单调化方法,,如果令：,,,f(n) = max(f(n,的父节点,), g(n)+h(n)),

55、,,则容易证明，这样处理后的,h,是单调的。,,114,,IDA*,算法(,Iterative Deepening A*),,基本思想：回溯与,A*,的结合,,算法简介（非严格地）,,,1,，设初始值,f0,；,,,2,，,集合,S,＝,NULL,；,,,3,，,用回溯法求解问题，如果节点,n,的,f,值大于,f0,，,则将该节点放入集合,S,中，并回溯；,,,4,，如果在,3,中找到了解，则结束；,,,5,，如果,3,以失败结束，则,f0,＝,S,中节点的最小,f,值；,,,6,，返回到,2,。,,115,,知识的灵活应用,,例：如何转动，使得每个扇区数字和为,12,。,1,3,5,5,1,

56、4,4,1,3,3,2,5,2,3,1,2,3,1,2,2,5,5,2,3,4,2,5,4,3,4,3,3,分析：,,阴影部分数字和：,48,,,直径部分数字和：,24,,,转,45°,改变阴影部分,,转,90°,改变直径部分,,但不改变阴影部分,,转,180°,改变扇区部分,,但不改变阴影部分,,也不改变直径部分,,,,116,,4,，其他的搜索算法,,爬山法（局部搜索算法）,,,117,,其他的搜索算法（续,1,）,,随机搜索算法,,动态规划算法,,如果对于任何,n,，当,h(n)=0,时，,A*,算法就成为了动态规划算法。,,118,,动态规划,,,S,0,t,S,1,S,2,S,3,S

57、,n,……,……,……,W,0,W,1,1,W,1,2,W,2,1,W,2,2,W,2,3,W,3,3,W,3,2,W,3,1,W,n,1,W,n,2,W,n,3,W,n+1,,119,,,其中：,Q(W,ij,),表示到点,W,ij,的最佳路径值,,,D(W,i-1,j,,,W,i,k,),表示,W,i-1,j,到,W,i,k,的距离,,120,,5,，搜索算法实用举例,,汉字识别后处理,,一个例子,,我钱线载哦栽哉裁劣绥,,优仍们仿伦奶砧犯扔妨,,要耍密穷安壁驻努窑垂,,扳报叔嵌奴振技寂叙蔽,,奋夯杏蚕香脊秀吞吝番,,精猜指洁括治捐活冶桔,,种神衬祥科钟拌样拎补,,,,121,,汉字识别后

58、处理,,,二元语法时：,为常量,用识别信度代替,问题变为求,最大,,122,,第三章 与或图的搜索,,,目标,目标,初始节点,s,a,,b,,c,,,123,,3.1,基本概念,,与或图是一个超图，节点间通过连接符连接。,,K-,连接符：,,…...,K,个,,124,,耗散值的计算,,,k(n, N) = C,n,+k(n,1,, N)+…+,k(n,i,, N),,其中：,N,为终节点集,,,C,n,为连接符的耗散值,…...,i,个,n,n,1,n,2,n,i,,125,,目标,目标,初始节点,解图：,,126,,能解节点,,终节点是能解节点,,若非终节点有,“,或,”,子节点时，当且仅

59、当其子节点至少有一能解时，该非终节点才能解。,,若非终节点有,“,与,”,子节点时，当且仅当其子节点均能解时，该非终节点才能解。,,127,,不能解节点,,没有后裔的非终节点是不能解节点。,,若非终节点有,“,或,”,子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。,,若非终节点有,“,与,”,子节点时，当至少有一个子节点不能解时，该非终节点才不能解。,,128,,普通图的情况,,,f(n) = g(n) + h(n),,,对,n,的评价实际是对从,s,到,n,这条路径的评价,n,s,,129,,与或图,:,对局部图的评价,,,目标,目标,初始节点,a,b,c,,130,,两个过程,

60、,图生成过程，即扩展节点,,从最优的局部途中选择一个节点扩展,,计算耗散值的过程,,对当前的局部图新计算耗散值,,131,,AO*,算法举例,,,其中：,,,h(n,0,)=3,,h(n,1,)=2,,h(n,2,)=4,,h(n,3,)=4,,h(n,4,)=1,,h(n,5,)=1,,h(n,6,)=2,,h(n,7,)=0,,h(n,8,)=0,,,设：,K,连接符,,的耗散值为,K,,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,132,,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始

61、节点,n,0,n,1,(2),n,4,(1),n,5,(1),红色：,4,,黄色：,3,,133,,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始节点,n,0,,n,4,(1),n,5,(1),红色：,4,,黄色：,6,n,1,n,2,(4),n,3,(4),5,,134,,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,红色：,5,,黄色：,6,初始节点,n,0,,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),2,,1

62、35,,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,红色：,5,,黄色：,6,初始节点,n,0,,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),2,1,,136,,3.3,博弈树搜索,,博弈问题,,双人,,一人一步,,双方信息完备,,零和,,137,,分钱币问题,,,（7）,（6,1）,（5,2）,（4,3）,（5,1,1）,（4,2,1）,（3,2,2）,（3,3,1）,（4,1,1,1）,（3,2,1,1）,（2,2,2,1）,（3,1,1,1,1）,（2,2,1

63、,1,1）,（2,1,1,1,1,1）,对方先走,我方必胜,,138,,中国象棋,,一盘棋平均走,50,步，总状态数约为,10,的,161,次方。,,假设,1,毫微秒走一步，约需,10,的,145,次方年。,,结论：不可能穷举。,,,139,,1,，极小极大过程,,,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,9,-3,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,极大,极小,a,b,,140,,,-,剪枝,极大节点的下界为,。,,极小节点的上界为。,,剪枝的条件：,,后辈节点的值≤祖先节点的值时， 剪枝,,后辈节点的 值≥祖先节点的值时， 剪枝,,简记为：,,极小≤极大，剪枝,,极大≥极小，剪枝,,141,,,-,剪枝（续）,,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,9,-3,0,0,-3,0,3,3,0,5,4,1,1,-3,1,6,6,1,a,b,c,d,e,f,g,h,i,j,k,m,n,,142,,,-,剪枝的其他应用,故障诊断,,,,,A B C D,,,风险投资,,,143,,