欢迎大家学习人工智能导论

1、欢迎大家学习人工智能导论 计算机系 马少平自我介绍绍姓名：马马少平单位：智智能技术术与系统统国家重点点实验室室电话：62782266-8407E-mail：绪论论人工智能能（ArtificialIntelligence）简称AI起源于美美国1956年年的一次次夏季讨讨论会什么是AI？计算算计计图灵实验验AI的本本质问题题研究如何何制造出出人造的的智能机机器或系系统，来来模拟人人类智能能活动的的能力，以延伸伸人们智智能的科科学。AI的历历史回顾顾第一阶段段（40年代中中50年代末末）神神经元元网络时时代双层网络络M-P模模型、感知器器模型等等问题：XOR问问题不能能解决Minsky的的著作：Pe

2、rceptions（感感知器）AI的历历史回顾顾（续1）第二阶段段（50年代中中60年代中中）通通用方方法时代代物理符号号系统主要研究究的问题题：GPS、游游戏、翻翻译等对问题的的难度估估计不足足，陷入入困境AI的历历史回顾顾（续2）一个笑话话（英俄俄翻译）：Thespirit is willingbut thefleshisweek.（心有余余而力不不足）Thevodkaisstrong butmeat is rotten.（伏特加加酒虽然然很浓，但肉是是腐烂的的）AI的历历史回顾顾（续3）出现这样样的错误误的原因因：Spirit：1）精神神2）烈性性酒结论：必须理解解才能翻翻译，而而理解需

3、需要知识识AI的历历史回顾顾（续4）第三阶段段（60年代中中80年代初初）知知识工工程时代代专家系统统知识工程程知识工程程席卷全全球各国发展展计划：美国星球球大战计计划英国ALVEY计划法国UNIKA 计划划日本五代代机计划划中国“863”计划AI的历历史回顾顾（续5）第四阶段段（80年代中中90年代初初）新新的神神经元网网络时代代BP网（算法），解决决了多层层网的学学习问题题Hopfield网，成功功求解了了货郎担担问题存在问题题：理论依据据解决大规规模问题题的能力力新的动向向构构造化方方法螺旋线分分类问题题AI的历历史回顾顾（续6）第五阶段段（90年代初初现在在）数数据与网网络时代代网络给

4、AI带来来无限的的机会知识发现现与数据据挖掘AI走向向实用化化AI的研研究内容容搜索技术术知识表示示规划方法法机器学习习认知科学学AI的研研究内容容（续1）自然语言言理解与与机器翻翻译专家系统统与知识识工程定理证明明博弈机器人数据挖掘掘与知识识发现AI的研研究内容容（续2）多Agent系系统复杂系统统足球机器器人两个组织织：RoboCup和和FIRA模拟组与与机器人人组控制方式式：FIRA采采用集中中控制，而RoboCup采采用分布布式控制制人机交互互技术IBM的的“深蓝蓝”北京时间间1997年5月12日凌晨晨4点50分，美国纽纽约公平平大厦，当IBM公司司的“深深蓝”超超级电脑脑将棋盘盘上的

5、一一个兵走走到C4的位置置上时，国际象象棋世界界冠军卡卡斯帕罗罗夫对“深蓝”的人机机大战落落下帷幕幕，“深深蓝”以以3.5：2.5的的总比分分战胜卡卡斯帕罗罗夫。IBM的的“深蓝蓝”（续续1）96年2月第一一次比赛赛结果：“深蓝”：胜、负、平平、平、负、负负97年5月第二二次比赛赛结果：“深蓝”：负、胜、平平、平、平、胜胜IBM的的“深蓝蓝”（续续2）“深蓝”的技术术指标：32个CPU每个CPU有16个协协处理器器每个CPU有256M内存每个CPU的处处理速度度为200万步步/秒本课主要要学习的的内容产生式系系统搜索技术术盲目搜索索方法启发式搜搜索方法法与/或图图搜索方方法博弈树搜搜索方法法A

6、I中的的谓词演演算及应应用知识表示示简介AI中的的其它技技术介绍绍第一章产产生式式系统1943年Post首首先在一一种计算算形式体体系中提提出60年代代开始，成为专专家系统统的最基基本的结结构形式上很很简单，但在一一定意义义上模仿仿了人类类思考的的过程1.1产产生式式系统的的基本组组成组成三要要素：一个综合合数据库库存存放信息息一组产生生式规则则知知识一个控制制系统规则则的解释释或执行行程序（控控制策略略）（推理引引擎）1.2产产生式式系统的的基本过过程过程PRODUCTION1，DATA初始数据据库2，until DATA满满足结束束条件，do3，4，在在规则集集中选择择一条可可应用于于DA

7、TA的的规则R5，DATA R应用到到DATA得到到的结果果6，一个简单单的例子子问题：设设字符转转换规则则ABCACDBCGBEFDE已知：A，B求：F一个简单单的例子子（续1）一、综合合数据库库x，其中x为字符符二、规则则集1，IFABTHENC2，IFACTHEND3，IFBCTHENG4，IFBETHENF5，IFDTHENE一个简单单的例子子（续2）三、控制制策略顺序排队队四、初始始条件A，B五、结束束条件Fx求解过程程数据库可可触发规规则被被触发发规则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（

8、4）（4）A，B，C，D，G，E，F1，IFABTHENC2，IFACTHEND3，IFBCTHENG4，IFBETHENF5，IFDTHENE1 .3 问题题表示举举例例1：传传教士与与野人问问题（M-C问问题）问题：N个传教教士，N个野人人，一条条船，可可同时乘乘坐k个个人，要要求在任任何时刻刻，在河河的两岸岸，传教教士人数数不能少少于野人人的人数数。问：如何何过河。以N=3，k=2为例例求解。M-C问问题（续续1）左岸右右岸LRLRm30m03c30c03B10B01M-C问问题（续续2）1，综合合数据库库（m,c,b)，其中：0m, c3,b0, 12，初始始状态（3，3，1）3，目标

9、标状态（结束状状态）（0，0，0）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)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，控制制策略：（略）M-C问问题（第第二种方方法）4，规

10、则则集：IF(m,c,1)AND 1i+j2 THEN(m-i,c-j,0)IF(m,c,0)AND 1i+j2 THEN(m+i,c+j,0)猴子摘香香蕉问题题abc猴子摘香香蕉问题题（续1）1，综合合数据库库（M,B,Box,On,H）M：猴子子的位置置B：香蕉蕉的位置置Box：箱子的的位置On=0：猴子子在地板板上On=1：猴子子在箱子子上H=0：猴子没没有抓到到香蕉H=1：猴子抓抓到了香香蕉猴子摘香香蕉问题题（续2）2，初始始状态（c,a,b,0,0）3，结束束状态（x1, x2,x3,x4, 1）其中x1x4为变量量。猴子摘香香蕉问题题（续3）4，规则则集r1:IF(x,y,z,0,

11、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为变量1.4产产生式式系统的的特点数据驱动动知识的无无序性控制系统统与问题题无关1.5产产生式式系统的的类型正向、逆逆向、双双向产生生式系统统可交换的的产生式式系统可分解的的产生式式系统第二章产产生式式系统的的搜索策策略内容：状态空间间的搜索索问题。搜索

12、方式式：盲目搜索索启发式搜搜索关键问题题：如何利用用知识，尽可能能有效地地找到问问题的解解（最佳佳解）。产生式系系统的搜搜索策略略（续1）S0Sg产生式系系统的搜搜索策略略（续2）讨论的问问题：有哪些常常用的搜搜索算法法。问题有解解时能否否找到解解。找到的解解是最佳佳的吗？什么情况况下可以以找到最最佳解？求解的效效率如何何。2.1回回溯策策略例：皇后后问题( )( )Q(1,1)( )QQ(1,1)(1,1)(2,3)( )Q(1,1)(1,1)(2,3)( )QQ(1,1)(1,1)(2,3)(1,1)(2,4)( )QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4

13、)(3.2)( )QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)( )Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)( )(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,

14、2)(2,4)Q(1,2)(2,4)(3,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)递归的思思想从前有座山 从前有座山 从前有座山递归的思思想（续续）当前状态态目标状态态g一个递归归的例子子intListLenght(LIST *pList)if(pList=NULL)return 0;else returnListLength(pList-next)+1;回溯搜索索算法BACKTRACK（DATA）DATA：当前前状态。返回值：从当前前状

15、态到到目标状状态的路路径（以规则则表的形形式表示示）或FAIL。回溯搜索索算法递归过程程BACKTRACK(DATA)1,IFTERM(DATA)RETURNNIL;2,IFDEADEND(DATA)RETURNFAIL;3,RULES:=APPRULES(DATA);4,LOOP:IFNULL(RULES)RETURN FAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IFPATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);存在问

16、题题及解决决办法问题：深度问题题死循环问问题解决办法法：对搜索深深度加以以限制记录从初初始状态态到当前前状态的的路径回溯搜索索算法1BACKTRACK1（DATALIST）DATALIST：从从初始到到当前的的状态表表（逆向向）返回值：从当前前状态到到目标状状态的路路径（以规则则表的形形式表示示）或FAIL。回溯搜索索算法11,DATA:=FIRST(DATALIST)2,IFMENBER(DATA, TAIL(DATALIST)RETURNFAIL;3,IFTERM(DATA)RETURNNIL;4,IFDEADEND(DATA)RETURNFAIL;5,IFLENGTH(DATALIST)

17、BOUNDRETURNFAIL;6,RULES:=APPRULES(DATA);7,LOOP: IF NULL(RULES) RETURNFAIL;8,R:=FIRST(RULES);回溯搜索索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IFPATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);一些深入入的问题题失败原因因分析、多步回回溯QQ一些深入入问题（续）回溯搜索索中知识识的

18、利用用基本思想想：尽可能选选取划去去对角线线上位置置数最少少的。QQQQ4 3 3 42.2图图搜索索策略问题的引引出回溯搜索索：只保保留从初初始状态态到当前前状态的的一条路路径。图搜索：保留所所有已经经搜索过过的路径径。一些基本本概念节点深度度：根节点深深度=0其它节点点深度=父节点点深度+10123一些基本本概念（续1）路径设一节点点序列为为(n0, n1,nk)，对于于i=1,k，若若节点ni-1具有一个个后继节节点ni，则该序序列称为为从n0到nk的路径。路径的耗耗散值一条路径径的耗散散值等于于连接这这条路径径各节点点间所有有耗散值值的总和和。用C(ni, nj)表示从ni到nj的路径

19、的的耗散值值。一些基本本概念（续1）扩展一个个节点生成出该该节点的的所有后后继节点点，并给给出它们们之间的的耗散值值。这一一过程称称为“扩扩展一个个节点”。一般的图图搜索算算法1,G=G0 (G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THEN EXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n, OPEN),ADD(n,CLOSED);5,IFGOAL(n) THENEXIT(SUCCESS);6,EXPAND(n)mi,G:=ADD(mi,G);一般的图图搜索算算法（续续）7,标标记和修修改指针针：ADD(mj, OPEN

20、),并标记mj到n的指针针；计算是否否要修改改mk、ml到到n的指指针；计算是否否要修改改ml到到其后继继节点的的指针；8,对对OPEN中的的节点按按某种原则则重新排序序；9,GOLOOP；节点类型型说明.mjmkml2.3无无信息息图搜索索过程深度优先先搜索宽度优先先搜索深度优先先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n) THENEXIT(SUCCESS);5,REMOVE(n,OPEN), ADD(n,CLOSED);6,IFDEPTH(

21、n)DmGOLOOP;7,EXPAND(n)mi, G:=ADD(mi,G);8,IF目目标在mi中THEN EXIT(SUCCESS);9,ADD(mj, OPEN),并并标记mj到n的指指针;10,GOLOOP;23184765 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 4

22、7 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目标深度优先先搜索的的性质一般不能能保证找找到最优优解当深度限限制不合合理时，可能找找不到解解，可以以将算法法改为可可变深度度限制最坏情况况时，搜搜索空间间等同于于穷举与回溯法法的差别别：图搜搜索是一个通通用的与与问题无无关的方方法宽度优先先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THEN EXIT(FAIL)

23、;3,n:=FIRST(OPEN);4,IFGOAL(n) THENEXIT(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,GOLOOP;23184765 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

24、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 54回溯与宽宽度优先先方法的的结合目的解决宽度度优先方方法的空空间问题题和回溯溯方法不不能找到到最优解解的问题题。思想首先给回回溯法一一个比较较小的深深度限制制，然后后逐渐增增加深度度限制，知道找找到解或或找遍所所以分支支为止。宽度优先先搜索的的性质当问题有有解时，一定能能找到解解当问题为为单位耗耗散值，且问题题有解时时，一定定能找到到最优解解方法与问问题无关关，具有有通用性性效率较

25、低低属于图搜搜索方法法2.4启启发式式图搜索索利用知识识来引导导搜索，达到减减少搜索索范围，降低问问题复杂杂度的目目的。启发信息息的强度度强：降低低搜索工工作量，但可能能导致找找不到最最优优解解弱：一般般导致工工作量加加大，极极限情况况下变为为盲盲目搜索索，但可可能可以以找到最最优解希望：引入启发发知识，在保证证找到最最佳解的的情况下下，尽可可能减少少搜索范范围，提提高搜索索效率。基本思想想定义一个个评价函函数f，对当前前的搜索索状态进进行评估估，找出出一个最最有希望望的节点点来扩展展。1，启发发式搜索索算法A（A算算法）评价函数数的格式式：f(n) =g(n)+ h(n)f(n)：评价价函数

26、h(n)：启发发函数符号的意意义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)的估计计值A算法1,OPEN:=(s), f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n) THENEXIT(SUCCESS);5,REMOVE(n,OPEN), ADD(n,CLOSED);6,EXPAND(n)Mi,计算

27、f(n,mi):=g(n, mi)+h(mi);A算法（续）ADD(mj, OPEN),标标记mj到n的的指针；IFf(n, mk)f(mk)THEN f(mk):=f(n, mk),标记mk到n的的指针；IFf(n, ml)f*(s)。A*算法法的性质质（续2）引理2.2：A*结束前，OPEN表中中必存在在f(n)f*(s)。A*算法法的性质质（续3）定理2：对无限图图，若从从初始节节点s到到目标节节点t有有路径存存在，则则A*一一定成功功结束。A*算法法的性质质（续4）推论2.1：OPEN表上任任一具有有f(n) h1(n)，则在在具有一一条从s到t的的路径的的隐含图图上，搜搜索结束束时，

28、由由A2所所扩展的的每一个个节点，也必定定由A1所扩展展，即A1扩展展的节点点数至少少和A2一样多多。简写：如如果h2(n)h1(n),则则A1扩展的的节点数数A2扩展的节节点数对h的评评价方法法平均分叉叉树设共扩展展了d层层节点，共搜索索了N个个节点，则:N =(1-b*(d+1)/(1-b)其中，b*称为为平均分分叉树。b*越小小，说明明h效果果越好。实验表明明，b*是一个个稳定的的常数，基本不不随问题题规模变变化。对h的评评价举例例例：8数数码问题题，随机机产生若若干初始始状态。使用h1：d=14,N=539,b*=1.44;d=20,N=7276，b*=1.47；使用h2：d=14,N

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

30、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)出现多次次扩展节节点的原原因在前面的的扩展中中，并没没有找到到从初始始节点到到当前节节点的最最短路径径，如节节点A。解决的途途径对h加以以限制能否对h增加适适当的限限制，使使得第一一次扩展展一个节节点时，就找到到了从s到该节节点的最最短路径径。对算法加加以改进进能否对算算

31、法加以以改进，避免或或减少节节点的多多次扩展展。改进的条条件可采纳性性不变不多扩展展节点不增加算算法的复复杂性对h加以以限制定义：一一个启发发函数h，如果果对所有有节点ni和nj，其其中nj是ni的子节节点，满满足h(ni)- h(nj) c(ni,nj)h(t) =0则称h是是单调的的。h(ni)ninjh(nj)c(ni,nj)h单调的的性质定理5：若h(n)是单单调的，则A*扩展了了节点n之后，就已经经找到了了到达节节点n的的最佳路路径。即：当A*选n扩展时时，有g(n)=g*(n)。h单调的的性质（续）定理6：若h(n)是单单调的，则由A*所扩扩展的节节点序列列其f值值是非递递减的。h

32、单调的的例子8数码问问题：h为“不不在位”的将牌牌数1h(ni)- h(nj) =0(nj为ni的的后继节节点)-1h(t) =0c(ni,nj)=1满足单调调的条件件。对算法加加以改进进一些结论论：OPEN表上任任以具有有f(n) f*(s)的节点点定会被被扩展。A*选作作扩展的的任一节节点，定定有f(n)f*(s)。改进的出出发点OPEN =( )f*(s)f值小于于f*(s)的的节点f值大于于等于f*(s)的节节点fm：到目前为为止已扩扩展节点点的最大大f值，用fm代替f*(s)修正过程程A1,OPEN:=(s), f(s)=g(s)+h(s),fm:=0;2,LOOP:IFOPEN=(

33、)THEN EXIT(FAIL);3,NEST:=ni|f(ni)fmIFNEST () THENn:=NEST中g最小的的节点ELSE n:=FIRST(OPEN),fm:=f(n);4,8:同过程A。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)h的单调调化方法法如果令：f(n) =max(f

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

35、和：48直径部分分数字和和：24转45改变阴阴影部分分转90改变变直径部部分但不改变变阴影部部分转180 改改变扇区区部分但不改变变阴影部部分也不改变变直径部部分4，其他他的搜索索算法爬山法（局部搜搜索算法法）其他的搜搜索算法法（续1）随机搜索索算法动态规划划算法如果对于于任何n，当h(n)=0时时，A*算法就就成为了了动态规规划算法法。动态规划划st第一阶段段第二阶段段第三阶段段第四阶段段第五阶段段5，搜索索算法实实用举例例汉字识别别后处理理一个例子子我钱线载载哦栽哉哉裁劣绥绥优仍们仿仿伦奶砧砧犯扔妨妨要耍密穷穷安壁驻驻努窑垂垂扳报叔嵌嵌奴振技技寂叙蔽蔽奋夯杏蚕蚕香脊秀秀吞吝番番精猜指洁洁括

36、治捐捐活冶桔桔种神衬祥祥科钟拌拌样拎补补汉字识别别后处理理二元语法时：为常量用识别信度代替问题变为求最大第三章与与或图图的搜索索目标目标初始节点3.1基基本概概念与或图是是一个超超图，节节点间通通过连接接符连接接。K-连接接符：.K个耗散值的的计算k(n, N) =Cn+k(n1,N)+k(ni,N)其中：N为终节节点集Cn为连连接符的的耗散值值.i个nn1n2ni目标目标初始节点点解图：能解节点点终节点是是能解节节点若非终节节点有“或”子子节点时时，当且且仅当其其子节点点至少有有一能解解时，该该非终节节点才能能解。若非终节节点有“与”子子节点时时，当且且仅当其其子节点点均能解解时，该该非终节节点才能能解。不能解节节点没有后裔裔的非终终节点是是不能解解节点。若非终节节点有“或”子子节点，当且仅仅当所有有子节点点均不能能解时，该非终终节点才才不能解解。若非终节节点有“与”子子节点时时，当至至少有一一个子节节点不能能解时，该非