《清华大学人工智能导论课堂PPT》由会员分享，可在线阅读，更多相关《清华大学人工智能导论课堂PPT（143页珍藏版）》请在金锄头文库上搜索。
1、第一章 产生式系统l1943年Post首先在一种计算形式体系中提出l60年代开始，成为专家系统的最基本的结构l形式上很简单，但在一定意义上模仿了人类思考的过程11.1 产生式系统的基本组成l组成三要素：一个综合数据库存放信息一组产生式规则知识一个控制系统规则的解释或执行程序 （控制策略） （推理引擎）2规则的一般形式lIF THEN lIF THEN l或者简写为： 31.2 产生式系统的基本过程过程PRODUCTION1，DATA初始数据库2，until DATA满足结束条件，do3，4， 在规则集中选择一条可应用于DATA 的规则R5， DATA R应用到DATA得到的结果6，4一个简单的
2、例子l问题：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F5一个简单的例子（续1）一、综合数据库x，其中x为字符二、规则集1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E6一个简单的例子（续2）三、控制策略顺序排队四、初始条件A，B五、结束条件Fx7求解过程数据库可触发规则被触发规则A，B（1）（1）A，B，C（2）（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，F1，IF AB THEN C 2，IF AC
3、 THEN D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN E81 .3 问题表示举例例1：传教士与野人问题（M-C问题）问题：N个传教士，N个野人，一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。问：如何过河。以N=3，k=2为例求解。9M-C问题（续1） 初始 目标 L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 110M-C问题（续2）1，综合数据库 （m, c, b)，其中：0m, c3, b 0, 12，初始状态 （3，3，1）3，目标状态（结束状态） （0，0，0）11M-C
4、问题（续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) THEN (m, c-2, 0)12M-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,
5、 0) THEN (m, c+2, 1)5，控制策略：（略）13M-C问题（第二种方法）4，规则集：IF (m, c, 1) AND 1 i+j2 THEN (m-i, c-j, 0)IF (m, c, 0) AND 1 i+j2 THEN (m+i, c+j, 1)14猴子摘香蕉问题 c a b15猴子摘香蕉问题（续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，结束状态（x1,
6、x2, x3, x4, 1）其中x1x4为变量。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, x, x, 1, 1)其中x, y, z, w为变量181.4 产生式系统的特点l数据驱动l知识的无序性l控
7、制系统与问题无关l数据、知识和控制相互独立191.5 产生式系统的类型l正向、逆向、双向产生式系统l可交换的产生式系统l可分解的产生式系统20第二章 产生式系统的搜索策略l内容：状态空间的搜索问题。l搜索方式：盲目搜索启发式搜索l关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。21产生式系统的搜索策略（续1）S0Sg22产生式系统的搜索策略（续2）l讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。232.1 回溯策略l例：皇后问题24( )25( )Q(1,1)26( )QQ(1,1)(1,1) (2,3)27(
8、 )Q(1,1)(1,1) (2,3)28( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)29( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)30( )QQ(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) (
9、3.2)Q(1,2)34( )(1,1)(1,1) (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,2) (2,4) (3,1) (4,3)37递归的思想当前状态目标状态g38一个递归的例子int
10、ListLenght(LIST *pList)if (pList = NULL) return 0;else return ListLength(pList-next)+1;NULLpLIST12339回溯搜索算法BACKTRACK（DATA） DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。40回溯搜索算法递归过程BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);4, LOOP: IF NULL(RULE
11、S) 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);41存在问题及解决办法l解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态l问题：深度问题死循环问题42回溯搜索算法1BACKTRACK1（DATALIST） DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。43回溯搜索
12、算法11, 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);44回溯搜索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R
13、, DATA);11,RDATALIST:=CONS(RDATA, DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);45一些深入的问题l失败原因分析、多步回溯QQ46一些深入问题（续）l回溯搜索中知识的利用基本思想(以皇后问题为例)：尽可能选取划去对角线上位置数最少的。QQQQ3 2 2 3472.2 图搜索策略l问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。 48一些基本概念l节点深度：根节点深度=0其它节点深度=父节点深
14、度+1012349一些基本概念（续1）l路径设一节点序列为(n0, n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。l路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。50一些基本概念（续1）l扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。51一般的图搜索算法1, G=G0 (G0=s), OPEN:=(s);2, CLOSED:=( );3, LOOP: IF OPEN=( ) THEN EXIT(FAIL);4, n:=F
15、IRST(OPEN), REMOVE(n, OPEN),ADD(n, CLOSED);5, IF GOAL(n) THEN EXIT(SUCCESS);6, EXPAND(n)mi, G:=ADD(mi, G);52一般的图搜索算法（续）7, 标记和修改指针：ADD(mj, OPEN), 并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8, 对OPEN中的节点按某种原则重新排序；9, GO LOOP；53节点类型说明.mjmkml54修改指针举例123456s55修改指针举例（续1）123456s56123456修改指针举例（续2）s571234
16、56修改指针举例（续3）s582.3 无信息图搜索过程l深度优先搜索l宽度优先搜索59深度优先搜索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)
17、;9, ADD(mj, OPEN), 并标记mj到n的指针;10, GO LOOP;602 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
18、 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目标61深度优先搜索的性质l一般不能保证找到最优解l当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制l最坏情况时，搜索空间等同于穷举l与回溯法的差别：图搜索l是一个通用的与问题无关的方法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,
19、 OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, G:=ADD(mi, G);7, IF 目标在mi中 THEN EXIT(SUCCESS);8, ADD(OPEN, mj), 并标记mj到n的指针;9, GO LOOP;632 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
20、 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标82 3 41 8 7 6 5464宽度优先搜索的性质l当问题有解时，一定能找到解l当问题为单位耗散值，且问题有解时，一定能找到最优解l方法与问题无关，具有通用性l效率较低l属于图搜索方法65渐进式深度优先搜索方法l目的解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。l思想首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。662.4 启发式图搜索l利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。l启发信息的强度强：降低搜索工作量，但可
21、能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解67希望：l引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。68基本思想l定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。691，启发式搜索算法A（A算法）l评价函数的格式：f(n) = g(n) + h(n)f(n)：评价函数h(n)：启发函数70符号的意义lg*(n)：从s到n的最短路径的耗散值lh*(n)：从n到g的最短路径的耗散值lf*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值lg(n)、h(n)、f(n)分别是g*(n)
22、、h*(n)、f*(n)的估计值71A算法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(n, mi):=g(n, mi)+h(mi); 72A算法（续）ADD(mj, OPEN), 标记mj到n的指针；IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 标记mk到n的指针
23、；IF f(n, ml) 其中为大于0的常数l几个等式 f*(s) = f*(t) = h*(s) = g*(t) = f*(n) 其中s是初始节点，t是目标节点，n是s到t的最佳路径上的节点。81A*算法的性质（续1）定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。82A*算法的性质（续2）引理2.1 ：对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)f*(s)。83A*算法的性质（续3）引理2.2：A*结束前，OPEN表中必存在f(n)f*(s)。存在一个节点n，n在最佳路径上。f(n
24、) = g(n) + h(n) = g*(n)+h(n) g*(n)+h*(n) = f*(n) = f*(s)84A*算法的性质（续3）定理2：对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。引理2.1：A*如果不结束，则OPEN中所有的n有f(n) f*(s)引理2.2：在A*结束前，必存在节点n，使得 f(n) f*(s)所以，如果A*不结束，将导致矛盾。85A*算法的性质（续4）推论2.1：OPEN表上任一具有f(n)f*(s)的节点n，最终都将被A*选作扩展的节点。 由定理2，知A*一定结束，由A*的结束条件，OPEN表中f(t)最小时才结束。而 f(t) f*(
25、t) f*(s) 所以f(n) f*(s)l由引理2.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扩展的节点数90A*算法的性质（续7）l注意： 在定理4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。91定理4的证明l使用数学归纳法，对节点的深度进行归纳l（1）当d(n)0时，即只有一个节点，显然定理成立。
26、l（2）设d(n)k时定理成立。（归纳假设）l（3）当d(n)=k+1时，用反证法。l设存在一个深度为k1的节点n，被A2扩展，但没有被A1扩展。而由假设，A1扩展了n的父节点，即n已经被生成了。因此当A1结束时，n将被保留在OPEN中。92定理4的证明（续1）l所以有：f1(n) f*(s) l 即：g1(n)+h1(n) f*(s) l所以： h1(n) f*(s) - g1(n)l另一方面，由于A2扩展了n，有f2(n) f*(s)l即： h2(n) f*(s) g2(n) (A)l由于d(n)=k时，A2扩展的节点A1一定扩展，有 g1(n) g2(n) (因为A2的路A1均走到了)l
27、所以： h1(n) f*(s) - g1(n) f*(s) g2(n) (B)l比较A、B两式，有 h1(n) h2(n) ，与定理条件矛盾。故定理得证。93对h的评价方法l平均分叉树设共扩展了d层节点，共搜索了N个节点，则:其中，b*称为平均分叉树。lb*越小，说明h效果越好。l实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化。94对h的评价举例例：8数码问题，随机产生若干初始状态。l使用h1：d=14, N=539,b*=1.44; d=20, N=7276， b*=1.47；l使用h2：d=14, N=113, b*=1.23;d=20, N=676,b*=1.2795A
28、*的复杂性l一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时：abs(h(n)-h*(n) O(log(h*(n)A*的算法复杂性才是非指数型的，但是通常情况下， h与h*的差别至少是和离目标的距离成正比的。963，A*算法的改进l问题的提出：因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。97s(10)A(1)B(5)C(8)G 目标631118一个例子：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
29、(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出现多次扩展节点的原因l在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。s(10)A(1)B(5)C(8)G 目标63111899解决的途径l对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。l对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。100改进的条件l可采纳性不变l不多扩展节点l不增加算法的复
30、杂性101对h加以限制l定义：一个启发函数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)102h单调的性质l定理5：若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有g(n)=g*(n)。103定理5的证明l设n是A*扩展的任一节点。当ns时，定理显然成立。下面考察n s的情况。l设P(n0=s, n1, n2, , nk=n)是s到n的最佳
31、路径lP中一定有节点在CLOSED中，设P中最后一个出现在CLOSED中的节点为nj，则nj+1在OPEN中。104定理5的证明（续1）l由单调限制条件，对P中任意节点ni有： h(ni) C(ni, ni+1)+h(ni+1) g*(ni)+h(ni) g*(ni)+C(ni, ni+1)+h(ni+1)l由于ni 、ni+1在最佳路径上，所以： g*(ni+1) = g*(ni)+C(ni, ni+1)l带入上式有： g*(ni)+h(ni) g*(ni+1)+h(ni+1)l从i=j到i=k-1应用上不等式，有： g*(nj+1)+h(nj+1) g*(nk)+h(nk)l即：f(nj+
32、1) g*(n)+h(n) 注意：(nj在CLOSED中，nj+1在OPEN中)105定理5的证明（续2）l重写上式：f(nj+1) g*(n)+h(n)l另一方面，A*选n扩展，必有： f(n) = g(n)+h(n) f(nj+1) l比较两式，有： g(n) g*(n)l但已知g*(n)是最佳路径的耗散值，所以只有：g(n) = g*(n)。得证。106h单调的性质（续）l定理6：若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。即f(ni) f(nj)。 107定理6的证明l由单调限制条件，有： h(ni) h(nj) C(ni, nj) = f(ni)-g(ni)= f(
33、nj)-g(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，得证。108h单调的例子l8数码问题：h为“不在位”的将牌数 1h(ni) - h(nj) = 0(nj为ni的后继节点) -1 h(t) = 0c(ni, nj) = 1 满足单调的条件。109对算法加以改进l一些结论：OPEN表上任以具有f(n) f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)f*(s)。110改进的出发点O
34、PEN = ( )f*(s)f值小于f*(s)的节点f值大于等于f*(s)的节点fm：到目前为止已扩展节点的最大f值，用fm代替f*(s)111修正过程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。112s(10)A(1)B(5)C(8)G 目标631118前面的例子：OPEN表CLOSED表fms(0+10
35、)s(0+10)10A(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) 113h的单调化方法l如果令：f(n) = max(f(n的父节点), g(n)+h(n)则容易证明，这样处理后的h是单调的。114IDA*算法(Iterative Deepening A*)l基本思想：回溯与A*的结合l算法简介（非严格地）1，设初始值f0；2，集合SNULL；3，用回溯法求解问题，如果节点n的f值大于f0，则将该节点放入集合S中，
36、并回溯；4，如果在3中找到了解，则结束；5，如果3以失败结束，则f0S中节点的最小f值；6，返回到2。115知识的灵活应用例：如何转动，使得每个扇区数字和为12。13551441332523123122552342543433分析： 阴影部分数字和：48 直径部分数字和：24 转45改变阴影部分 转90改变直径部分 但不改变阴影部分 转180改变扇区部分 但不改变阴影部分 也不改变直径部分1164，其他的搜索算法l爬山法（局部搜索算法）117其他的搜索算法（续1）l随机搜索算法l动态规划算法如果对于任何n，当h(n)=0时，A*算法就成为了动态规划算法。118动态规划S0tS1S2S3SnW0
37、W1,1W1,2W2,1W2,2W2,3W3,3W3,2W3,1Wn,1Wn,2Wn,3Wn+1119其中：Q(Wij)表示到点Wij的最佳路径值 D(Wi-1,j, Wi,k)表示Wi-1,j到Wi,k的距离1205，搜索算法实用举例l汉字识别后处理l一个例子我钱线载哦栽哉裁劣绥优仍们仿伦奶砧犯扔妨要耍密穷安壁驻努窑垂扳报叔嵌奴振技寂叙蔽奋夯杏蚕香脊秀吞吝番精猜指洁括治捐活冶桔种神衬祥科钟拌样拎补 121汉字识别后处理二元语法时：为常量用识别信度代替问题变为求最大122第三章 与或图的搜索目标目标初始节点sabc1233.1 基本概念l与或图是一个超图，节点间通过连接符连接。lK-连接符：.
38、K个124耗散值的计算k(n, N) = Cn+k(n1, N)+k(ni, N)其中：N为终节点集 Cn为连接符的耗散值.i个nn1n2ni125目标目标初始节点 解图：126能解节点l终节点是能解节点l若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。l若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。127不能解节点l没有后裔的非终节点是不能解节点。l若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。l若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。128普通图的情况f(n) = g(
39、n) + h(n)对n的评价实际是对从s到n这条路径的评价ns129与或图: 对局部图的评价目标目标初始节点abc130两个过程l图生成过程，即扩展节点从最优的局部途中选择一个节点扩展l计算耗散值的过程对当前的局部图新计算耗散值131AO*算法举例其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n8132目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：3133目标
40、目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)5134目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2135目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)211363.3 博弈树搜索l博弈问题双人一人一步双方信息完备零和137分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,
41、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,1,1）（2,1,1,1,1,1）对方先走我方必胜138中国象棋l一盘棋平均走50步，总状态数约为10的161次方。l假设1毫微秒走一步，约需10的145次方年。l结论：不可能穷举。1391，极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小ab140-剪枝l极大节点的下界为。l极小节点的上界为。l剪枝的条件：后辈节点的值祖先节点的值时， 剪枝后辈节点的 值祖先节点的值时， 剪枝l简记为：极小极大，剪枝极大极小，剪枝141-剪枝（续）05-333-3022-30-23541-30689-300-303305411-31661abcdefghijkmn142-剪枝的其他应用l故障诊断 A B C Dl风险投资143
