清华大学人工智能导论课程电子教案省公共课一等奖全国赛课获奖课件.pptx

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