人工智能导论东南大学优秀课件

《人工智能导论东南大学优秀课件》由会员分享，可在线阅读，更多相关《人工智能导论东南大学优秀课件（249页珍藏版）》请在金锄头文库上搜索。

1、东南大学远程教育人人人人 工工工工 智智智智 能能能能第第01讲讲主讲教师：翟玉庆主讲教师：翟玉庆1计算机科学技术的发展趋向1、基于网络(普适计算)2、并行化3、智能化（以知识为中心）4、人性化2参考资料：1、人工智能（上、下册），陆汝钤 科学出版社2、高级人工智能，史忠植 科学出版社3、智能主体及其应用，史忠植 科学出版社4、 Artificial Intelligence A New Synthesis, N.J.Nilsson,机械工业出版社 Morgan Kaufmann3第一章 引言第一节 基本概念一、智能智能是个体有目的的行为、合理的思维，以及有效地适应环境的综合能力。通俗地讲，智

2、能是个体认识客观事物、客观世界和运用知识解决问题的能力。人类个体的智能是一种综合性能力。具体地讲，可包括：1）感知与认识事物、客观世界与自我的能力；2）通过学习取得经验、积累知识的能力；4第一章 引言第一节 基本概念一、智能人类个体的智能是一种综合性能力。具体地讲，可包括：3）理解知识、运用知识和运用经验分析问题和解决问题的能力；4）联想、推理、判断、决策的能力；5）运用语言进行抽象、概括的能力；6）发现、发明、创造、创新的能力；5第一章 引言第一节 基本概念一、智能人类个体的智能是一种综合性能力。具体地讲，可包括：7）实时地、迅速地、合理地应付复杂环境的能力；8）预测、洞察事物发展变化的能力

3、；等。注：智能是相对的、发展的。离开特定时间说智能是困难的、没有意义的。6东南大学远程教育人人人人 工工工工 智智智智 能能能能第第02讲讲主讲教师：翟玉庆主讲教师：翟玉庆7第一章 引言第一节 基本概念二、人工智能人工智能是相对人的自然智能而言，即用人工的方法和技术，研制智能机器或智能系统来模仿、延伸和扩展人的智能，实现智能行为和“机器思维”解决需要人类专家才能处理的问题。人工智能是人工制品(artifact)中所涉及的智能行为。其中，智能行为包括：感知(perception)、推理(Reasoning)、学习(learning)、通信(communicating)和复杂环境下的动作行为(ac

4、ting)。8第一章 引言第一节 基本概念三、人工智能目标人工智能目标是实现智能行为和“机器思维”，解决需要人类专家才能处理的问题。 1、研究像人一样工作的机器，甚至比人做得更好 2、能够理解机器、人或动物的智能行为 9第一章 引言第一节 基本概念四、智能革命智能革命是指人的自然智能通过人工智能的模仿和扩展，实现社会生产的自动化和智能化，促进知识密集型经济的发展。10第一章 引言第二节 人工智能的发展概况一、萌芽阶段1、Aristotle(公元前384-322)在工具论中提出形式逻辑（三段论）2、Bacon(1561-1626)在新工具中提出归纳法，提出“知识就是力量”3、Leibnitz(1

5、646-1716)研制四则计算器，提出“通用符号”和“推理计算”概念，使形式逻辑符号化，从而能对人的思维进行运算和推理，奠定了数理逻辑的基础11第一章 引言第二节 人工智能的发展概况一、萌芽阶段4、Boole(1815-1864)创立布尔代数，在思维法则中首次用符号语言描述思维活动的基本推理规则5、Godel(1906-1978)提出不完备性定理，指出人的思维形式化和机械化的某些极限6、Turing(1912-1954)提出理想计算模型图灵机，创立自动机理论，提出“图灵试验”，用以判断“Can a machine think?”12第一章 引言第二节 人工智能的发展概况一、萌芽阶段7、Mauc

6、hly和Eckert等研制成功ENIAC电子数字计算机，为人工智能研究奠定物质基础8、Von Neumann提出冯诺依曼计算机模型9、McCulloch和Pitts建立神经网络数学模型，通过模拟人脑实现智能，开创人工神经网络研究。Kleene将其抽象为有限自动机理论10、Wiener创立控制论，Shannon创立信息论13第一章 引言第二节 人工智能的发展概况二、人工智能的诞生1、导因现实世界中相当多的问题求解是复杂的，常无算法可循，即使有计算方法，也是NP问题。为此，人们可采用启发式知识进行问题求解，把复杂的问题大大简化，可在浩瀚的搜索空间中迅速找到解答。这是运用专门领域的经验知识。经常会取

7、得有关问题的满意解，而非数学上的最优解。这就是启发式搜索。14第一章 引言第二节 人工智能的发展概况二、人工智能的诞生2、提出1956年，由McCarthy、Minskey、Shannon、Newell等提出。15东南大学远程教育人人人人 工工工工 智智智智 能能能能第第03讲讲主讲教师：翟玉庆主讲教师：翟玉庆16第一章 引言第二节 人工智能的发展概况三、人工智能的发展1、50年代以博弈、游戏为对象进行研究1）Samuel研制成功具有自学能力的启发式博弈程序2）Newell研制了启发式程序Logic Theorist。对数学原理中38条定理进行了证明，开创了利用计算机研究思维活动规律的工作3）

8、Chomsky提出语言文法，开创了形式语言研究17第一章 引言第二节 人工智能的发展概况三、人工智能的发展1、50年代4）McCarthy建立LISP，不仅可以处理数值，而且可更方便地处理符号，为人工智能研究提供了重要工具18第一章 引言第二节 人工智能的发展概况三、人工智能的发展2、60年代前期以搜索问题、通用问题求解研究为主1）Newell发表问题求解程序，使启发式程序有更大的普遍性2）Feigenbaum研制成功DENDRAL化学专家系统，使人工智能研究从着重算法转向知识表示的研究，也是人工智能研究走向实用化的标志19第一章 引言第二节 人工智能的发展概况三、人工智能的发展2、60年代3

9、）Robinson提出归结原理4）Quilian提出语义网络的知识表示法5）IJCAI成立20第一章 引言第二节 人工智能的发展概况三、人工智能的发展3、70年代前期以自然语言理解、知识表示研究为主1）Winograd发表自然语言理解系统SHRDLU2）Colmerauer创建PROLOG语言3）Schank提出概念从属理论4）Minskey提出框架知识表示法5）Feigenbaum提出知识工程21第一章 引言第二节 人工智能的发展概况三、人工智能的发展4、80年代专家系统广泛应用，出现了专家系统开发工具，开始兴起人工智能产业1）日本提出五代机计划2）中国提出863计划-863-30622第一

10、章 引言第二节 人工智能的发展概况三、人工智能的发展5、90年代-现在1）人工神经网络的复兴2）基于知识的系统 CYC3）Deep Blue 1997.5.11 4）分布式人工智能与多Agent系统 robots, Softbot,集成自治系统5）知识科学23东南大学远程教育人人人人 工工工工 智智智智 能能能能第第04讲讲主讲教师：翟玉庆主讲教师：翟玉庆24第一章 引言第三节 人工智能的研究方法人工智能经过发展，形成了许多学派。不同学派的研究方法、学术观点、研究重点有所不同。这里主要介绍认知学派、逻辑学派、行为主义学派和连接主义学派。一、认知学派(以Simon,Minskey和Newell等

11、为代表)1、基本思想从人的思维活动出发，利用计算机进行宏观功能模拟。基于物理符号系统假设，将任何信息加工系统看成是一个具体的物理系统。25第一章 引言第三节 人工智能的研究方法一、认知学派2、基本观点物理系统表现智能行为的充要条件是该系统是一个物理符号系统。3、主要工作1）Newell的Logic Theorist，模拟人证明数学定理的思维过程2）GPS，模拟人的解题过程(拟定初步解题计划利用公理、定理和规则，按规则实施解题过程不断进行“目的手段“分析，修订解题计划。26第一章 引言第三节 人工智能的研究方法一、认知学派3、主要工作3）物理符号系统假设符号是模式。物理符号系统的基本任务和功能是

12、辨认相同的符号和区别不同的符号。27第一章 引言第三节 人工智能的研究方法二、逻辑学派 （以McCarthy和Nilsson等为代表)1、基本思想用逻辑来研究人工智能，用形式化的方法（统一的逻辑框架）描述客观世界。2、基本观点1）智能机器必须有关于自身环境的知识2）通用智能机器要能陈述性地表达关于自身环境的大部分知识3）通用智能机器表示陈述性知识的语言至少要有一阶逻辑的能力28第一章 引言第三节 人工智能的研究方法二、逻辑学派3、主要工作1）概念化知识表示2）模型论语义29东南大学远程教育人人人人 工工工工 智智智智 能能能能第第05讲讲主讲教师：翟玉庆主讲教师：翟玉庆30第一章 引言第三节

13、人工智能的研究方法二、逻辑学派3、主要工作1）概念化知识表示2）模型论语义3）演绎推理4）非单调逻辑用于常识推理31第一章 引言第三节 人工智能的研究方法三、行为主义学派 (以Brooks为代表)1、基本思想以复杂的现实世界为背景，让人工智能理论先经受解决实际问题的考验，并在这种考验中成长。智能只是在与环境的交互作用中表现出来。2、基本观点1）到现场去2）物理实现3）初级智能 4）行为产生智能32第一章 引言第三节 人工智能的研究方法三、行为主义学派3、主要工作1）无需知识表示的智能2）无需推理的智能3）机器虫33第一章 引言第三节 人工智能的研究方法四、连接主义学派1、基本思想从脑的神经系统

14、结构出发来研究脑的功能，研究大量简单的神经元的集团信息处理能力及其动态行为，模拟和实现人的认识过程中的感知觉过程、形象思维、分布式记忆和自学习自组织过程。2、基本观点1）神经网络以分布式方式存储信息2）神经网络以并行方式处理信息3）神经网络具有自组织、自学习能力34第一章 引言第三节 人工智能的研究方法四、连接主义学派3、主要工作人工神经网络35东南大学远程教育人人人人 工工工工 智智智智 能能能能第第06讲讲主讲教师：翟玉庆主讲教师：翟玉庆36第一章 引言第四节 人工智能的主要研究内容一、博弈跳棋、国际象棋、五子棋二、机器定理证明Logic Theorist王浩：利用一阶谓词逻辑吴文俊：吴方

15、法三、自动程序设计四、通用问题求解GPS37东南大学远程教育人人人人 工工工工 智智智智 能能能能第第07讲讲主讲教师：翟玉庆主讲教师：翟玉庆38第一章 引言第四节 人工智能的主要研究内容五、感知1、视觉2、语音六、自然语言理解与生成计算语言学七、自动推理1、推理从一个或几个已知的判断（前提）逻辑地推论出一个新的判断（结论）的思维形式。39第一章 引言第四节 人工智能的主要研究内容七、自动推理1、推理注：利用以往的知识通过推理可得到新的结论。2、主要工作1）机器定理证明2）归结原理：推理规则简单。在逻辑上是完备的，是PROLOG的计算模型3）非单调推理：闭世假说（CWA）、默认推理、限定推理4

16、0第一章 引言第四节 人工智能的主要研究内容七、自动推理2、主要工作4）定性推理：把物理系统或物理过程细分为子系统或子过程，对于每个子系统或子过程及它们之间的相互作用或影响均建立起结构描述，通过局部因果性的传播和行为合成，获得实际物理系统的行为描述和功能描述41东南大学远程教育人人人人 工工工工 智智智智 能能能能第第08讲讲主讲教师：翟玉庆主讲教师：翟玉庆42第一章 引言第四节 人工智能的主要研究内容七、自动推理2、主要工作5）不确定性推理：不确定性来自人类的主观认识与客观实际之间存在的差异。事物发生的随机性，人类知识的不完全、不可靠、不精确和不一致，自然语言中存在的模糊性和歧义性均反映了这

17、种差异，均会带来不确定性。有代表性的不确定性理论和推理方法有：概率论，Bayes理论，证据理论(Dempster和Shafer)，模糊集理论等。43第一章 引言第四节 人工智能的主要研究内容八、机器学习知识、知识表示及运用知识的推理算法是人工智能的核心，而机器学习则是关键问题。1、学习学习是获取知识、积累经验、改进性能、发现规律、适应环境的过程。其基本机制是设法将在一种情形下成功的表现行为转移到另一类似的新情形中去。2、学习种类1）无知识的学习：神经元模拟和基于决策论方法的自适应和自组织系统。44第一章 引言第四节 人工智能的主要研究内容八、机器学习2、学习种类2）归纳学习：AQ算法、ID3算

18、法等。3）分析学习（实例学习）：基于解释的学习、知识块（Chunking）学习。4）类比学习5）发现学习：根据实验数据或模型重新发现定律的方法。45第一章 引言第四节 人工智能的主要研究内容八、机器学习2、学习种类6）遗传学习：自然选择、变异。7）连接学习：神经网络学习。8）数据库知识发现：主要发现分类规则、特征规划、关联规则、差异规则、演化规则、异常规则等。其方法有统计方法、机器学习、神经网络、数据仓库等。46东南大学远程教育人人人人 工工工工 智智智智 能能能能第第09讲讲主讲教师：翟玉庆主讲教师：翟玉庆47第一章 引言第四节 人工智能的主要研究内容九、分布式人工智能（Distribute

19、d AI）第一届DAI会议是在1980年。1、基本概念DAI是研究在逻辑上或物理上分散的智能动作者如何协调其智能行为（知识、技能和规划），求解单目标和多目标问题，为设计和建立大型复杂的智能系统或计算机支持协同工作(CSCW)提供有效途径。48第一章 引言第四节 人工智能的主要研究内容九、分布式人工智能（Distributed AI）第一届DAI会议是在1980年。2、主要内容1）分布式问题求解(DPS)2）多Agent系统(MAS)Agent是自主的，可能是预先存在的，并且是异构的，是一开放的系统。49第一章 引言第四节 人工智能的主要研究内容十、人工思维模型 真实世界 柔性信息处理 集体智能

20、 开放式自主系统50第一章 引言第四节 人工智能的主要研究内容十一、知识系统知识工程已成为人工智能应用最显著的特点。知识系统主要研究内容：1、专家系统知识库+推理机2、知识库系统将知识以一定的结构存入，进行知识管理，实现知识共享3、智能决策系统4、知识科学51第一章 引言讨论题：1、你相信人是机器吗？请说出理由。2、如果你是图灵测试的测试者，你会如何设计题目？52东南大学远程教育人人人人 工工工工 智智智智 能能能能第第10讲讲主讲教师：翟玉庆主讲教师：翟玉庆53第二章 知识与知识表示第一节 引言一、知识知识是信息经过加工整理、解释、挑选和改造而成的。二、知识类型1、事实性知识一般采用直接表示

21、形式。注：1）若事实性知识是批量的、有规律的，则往往以表格、图册，甚至数据库等形式出现；2）某些事实性知识表现为规则的形式（尽管有时事实和规则分开处理）54第二章 知识与知识表示第一节 引言二、知识类型2、过程性知识描述做某事的过程，使人或计算机照此去做。3、行为性知识不直接给出事实本身，只给出它在某方面的行为。注：从某种意义上说，行为性知识是描述事物的内涵，而非外延。4、实例性知识只给出一些实例，关于事物的知识就隐藏在这些实例中。55第二章 知识与知识表示第一节 引言二、知识类型4、实例性知识注：实例性知识和事实性知识的主要区别是：人们感兴趣的一般不是这些实例本身，而是在大批实例后面隐藏的规

22、律性知识。5、类比性知识既不给出外延，也不给出内涵，只给出它与其它事物的某些相似之处。56第二章 知识与知识表示第一节 引言二、知识类型5、类比性知识注：类比性知识一般不能完整地刻划事物，有时会以偏概全，但它可以启发人们在不同领域的知识间架起桥梁，利用一个领域的知识去解决另一个领域的问题。6、元知识关于知识的知识。注：元知识经常以控制知识的形式出现。57东南大学远程教育人人人人 工工工工 智智智智 能能能能第第11讲讲主讲教师：翟玉庆主讲教师：翟玉庆58第二章 知识与知识表示第一节 引言三、知识表示原则1、表示知识的范围是否广泛？注：逻辑是一种广谱的知识表示工具。2、是否适合于推理？注：人工智

23、能主要对适合推理的知识表示感兴趣。3、是否适合于计算机处理？4、是否有高效的算法？5、能否表示不精确知识？注：自然界的信息具有先天的模糊性和不精确性。59第二章 知识与知识表示第一节 引言三、知识表示原则6、能否模块化，以便于知识分层？7、知识和元知识能否用统一的形式表示？8、是否适合于加入启发式信息？控制知识（元知识）信息启发式信息9、过程性表示还是说明性表示？说明性表示：只给出事物本身的属性及事物之间的相互关系，对问题的解答就隐含在这些知识之中。60第二章 知识与知识表示第一节 引言三、知识表示原则9、过程性表示还是说明性表示？过程性表示：给出解决一个问题的具体过程。注：说明性表示涉及细节

24、少，抽象程度高，可靠性较好，修改方便，但执行效率较低。10、表示方式是否自然？61第二章 知识与知识表示第一节 引言四、常见的知识表示形式1、演绎系统2、产生式系统3、框架结构4、语义网络5、过程性知识表示6、面向对象知识表示62第二章 知识与知识表示第二节 演绎系统一、谓词演算1、命题 陈述2、谓词 带有参数的命题注：1）谓词比命题有更强的表达能力，可将知识单元细分；2）谓词可代表变化着的情况，谓词的真假值可因参数而异；3）可利用谓词在不同的知识之间建立联系，使用同名参数。63第二章 知识与知识表示第二节 演绎系统一、谓词演算3、谓词解释 人为地指派给谓词的含义注：1）由于解释的不同，谓词的

25、真假值也就不同；2）对于复杂的谓词公式，研究其不同的解释具有更大的重要性；3）对一个谓词公式可给出多种甚至无穷多种不同的解释。64第二章 知识与知识表示第二节 演绎系统一、谓词演算3、谓词解释 人为地指派给谓词的含义注：4）每种解释由下列基本部分组成：A）一组基本域Di,i=1nB）每个常量均是某个Di中的一个元素C）每个变量均在某个Di中取值D）每个m目函数均是一个映射Di1Di2 . DimDim+1（对于jk,可以有Dij=Dik)65第二章 知识与知识表示第二节 演绎系统一、谓词演算3、谓词解释 人为地指派给谓词的含义注：4）每种解释由下列基本部分组成：E）每个m目谓词均是一个映射Di

26、1Di2 . Dim（T，F）（T代表真，F代表假)5）若一个谓词公式在所有解释下均为真，则称此公式为永真公式。66第二章 知识与知识表示第二节 演绎系统一、谓词演算3、谓词解释 人为地指派给谓词的含义注：5）利用谓词演算进行逻辑推理的核心任务就是判断一个谓词公式是否永真。但判断一个谓词公式的永真性比较困难，甚至有人证明，根本不存在这样的算法。67东南大学远程教育人人人人 工工工工 智智智智 能能能能第第12讲讲主讲教师：翟玉庆主讲教师：翟玉庆68第二章 知识与知识表示第二节 演绎系统一、谓词演算4、谓词演算 谓词及谓词之间关系的研究1）符号集 真值常量：T、F 联结符号：、 运算符：= 量词

27、：、 常量：函数常量、谓词常量 变量：函数变量、谓词变量注：对于变量，可使用量词。69第二章 知识与知识表示第二节 演绎系统一、谓词演算4、谓词演算 谓词及谓词之间关系的研究2）项 A）常量和变量是项 B）若t1,t2,.,tn是项，则fn(t1,t2,tn)和Fn(t1,t2,tn)也是项。3）原子公式和合式公式 P1670第二章 知识与知识表示第二节 演绎系统一、谓词演算5、主要的谓词演算命题演算一阶谓词演算二阶谓词演算其中，最重要的是一阶谓词演算。71第二章 知识与知识表示第二节 演绎系统二、自然演绎系统给定一个有限的或递归的公理集，及一个有限推理规则集，构成一个自然演绎系统。注：1）若

28、在某个确定的范围内，任何永真公式均可由一个演绎系统推导出，则称此演绎系统对于该范围来说是完备的。2）对于一阶谓词演算，存在着完备的演绎系统，对于二阶谓词演算，不存在着完备的演绎系统。72第二章 知识与知识表示第二节 演绎系统二、自然演绎系统注：3）在实际应用中，仅推演永真式是不够的，任何有意义的知识推理系统均需处理非永真公式，它的谓词被指派以某种解释，即语义。我们应该使用含有语义的演绎系统。73第二章 知识与知识表示第二节 演绎系统三、与或句演绎系统1、与或句只有与符号()、或符号()、谓词(也称原子)和前有非符号的谓词(也称负原子，正负原子统称句节)以及看不见的全称量词的合式公式称为与或句。

29、2、与或句的生成步骤1）化成前束范式，使所有量词均在合式公式的最前面，且每个量词的辖域均是整个公式。2）消去存在量词，只剩下全称量词。74第二章 知识与知识表示第二节 演绎系统三、与或句演绎系统3、置换规则左部只能有一个句节，右部可以是任意的与或句。注：与或句演绎系统可以用于求证某个目标推理，也可以进行反向推理。当用作反向推理时，比较实用。75第二章 知识与知识表示第二节 演绎系统四、子句演绎系统1、子句只有或符号和非符号的合式谓词公式称为子句，用或符号连接多个句节而成。2、子句演绎方法消解法Robinson3、消解法基本思想把已知条件表示成一组子句，把求证目标先表示成子句，后在前面加非符号，

30、把加了非符号的目标子句和条件子句组合，若通过消解推出空子句，则目标得以证明。76第二章 知识与知识表示第三节 产生式系统一、基本概念1、产生式 在自然界的各种知识单元之间存在着大量的因果关系。这是前提和结论之间的关系，可用产生式（或称规则）来表示。 产生式（规则）：前提和结论之间的关系式。 表示形式：前提结论2、事实 无需前提条件的产生式，可用于表示已知的事实。 表示形式： 事实77第二章 知识与知识表示第三节 产生式系统一、基本概念3、产生式系统 将一组产生式放在一起，让它们互相配合、协调作用，一个产生式生成的结论可供另一个产生式作为前提使用。以这种方式求得问题的解决的系统，称为产生式系统。

31、78第二章 知识与知识表示第三节 产生式系统二、基本特征1、产生式系统构成a)一组规则(即产生式本身) 每个规则分为左部(LHS)和右部(RHS)。 一般说来，左部表示情形，即什么条件发生时此产生式应该被调用。右部表示动作，即此产生式被调用后所做的事情。 在核实左部情形时，通常采用匹配的方法，即查看当前数据基中是否存在规则左部所指示的情形。若存在，则认为匹配成功，否则认为匹配不成功。79第二章 知识与知识表示第三节 产生式系统二、基本特征1、产生式系统构成a)一组规则(即产生式本身) 匹配成功时，执行右部规定的动作。这种动作一般是对数据基中的数据作某种处理。80第二章 知识与知识表示第三节 产

32、生式系统二、基本特征1、产生式系统构成b)数据基 每个产生式系统均有一个数据基，其中存放的数据既是构成产生式的基本元素，又是产生式作用的对象。 注：数据基不同于数据库。数据基中的数据是广义的，可以是常量、变量、多元组、谓词、表结构、图象等等。其意义往往指一个事实或断言，可看成一个知识元。81第二章 知识与知识表示第三节 产生式系统二、基本特征1、产生式系统构成c)一个解释程序 负责整个产生式系统的运行，包括规则左部和数据基的匹配、从匹配成功的规则（可能不止一个）中选出一个加以执行、解释执行规则右部的动作，并掌握时机结束产生式系统的运行等等。注：其中每一步均可有不同的含义。82第二章 知识与知识

33、表示第三节 产生式系统二、基本特征2、产生式系统特点a)相对固定的格式 任何产生式均由LHS和RHS组成，左部匹配，右部动作。 匹配提供的信息只有两种：成功或失败。 匹配过程中不允许产生副作用。规则匹配失败时，对数据基无影响。 匹配一般无递归，无复杂的计算。右部的动作一般是最基本的，无复杂的控制。83第二章 知识与知识表示第三节 产生式系统二、基本特征2、产生式系统特点b)知识的模块化 在每个具体的产生式系统所适用的专门领域知识被分成许多知识元，存于数据基中。而每个规则指明了有关知识元之间的关系及其使用方法。 规则本身也可看成是知识元，这种知识元不同于通常数据基中存放的知识元，因为它是指示如何

34、使用数据基中存放的知识元，因此，也称为元知识，即关于知识的知识。由此可见，元知识也是模块化的。84第二章 知识与知识表示第三节 产生式系统二、基本特征2、产生式系统特点b)知识的模块化 此外，还有如何使用这些规则的知识，包括规则匹配的次序、匹配冲突的解决等解释系统中所包含的功能。这种有关元知识的知识称为高阶元知识。它们也可模块化并写成规则的形式。不过，只有少数系统能做到，而大部分系统是将高阶元知识不明确地写成规则的形式，不以任何明确的形式显示出来，规则使用方法隐含在系统本身的定义中。这是模块化不彻底的表现，可扩展性差。85第二章 知识与知识表示第三节 产生式系统二、基本特征2、产生式系统特点b

35、)知识的模块化 注：知识的模块化使得知识基（包括数据基和规则基）的补充和修改变得非常容易。但要注意任何修改和扩充必须保持知识基的无矛盾性和一致性。这种一致性检验最好由系统自动执行，至少检验到一定程度。因为从理论上，在某些情形下彻底的一致性检验是不现实的。86第二章 知识与知识表示第三节 产生式系统二、基本特征2、产生式系统特点c)相互影响的间接性 产生式系统一般是“数据驱动”，看不见控制流。 一个产生式的调用对其它产生式的影响不是直接传送过去，而是通过修改数据基来间接实现（当其它产生式的左部与数据基匹配时，发现数据基内容已变，从而，各产生式执行效果也就跟着发生变化）。87第二章 知识与知识表示

36、第三节 产生式系统二、基本特征2、产生式系统特点c)相互影响的间接性 注：这个特点有利于知识模块性，但使产生式系统的效率受到影响。88第二章 知识与知识表示第三节 产生式系统二、基本特征2、产生式系统特点d)机器可读性 包括机器识别产生式、语法检查和某种程度上的语义检查。 语法检查包括无矛盾性检验和冗余检查。 语义检查涉及知识的具体领域，如通常数据库中的一致性检验。 可读性的另一含义是对产生式作出解释，是对产生式系统为解决某一问题所给答案的解释，即，对推理过程作出解释。89第二章 知识与知识表示第三节 产生式系统二、基本特征2、产生式系统特点注：产生式系统对某些领域的应用是很有效的，如医疗诊断

37、，而对另一些领域不那么适用，如数学。其关键在于知识能否模块化。90东南大学远程教育人人人人 工工工工 智智智智 能能能能第第13讲讲主讲教师：翟玉庆主讲教师：翟玉庆91第二章 知识与知识表示第三节 产生式系统三、产生式的知识元形式1、常量字符串 是知识元的最简单形式。 匹配有精确匹配、不完全匹配(只要求LHS中的知识元是当前数据基中某个知识元的子串即可)。 匹配成功后，RHS的动作是把数据基内该知识元中所含的子串换成在RHS中出现的子串。 注：这种产生式系统称为置换系统。92第二章 知识与知识表示第三节 产生式系统三、产生式的知识元形式2、变量 若产生式的左部均只有一个符号，则这些符号也称为变

38、量。 注：引进变量的一个效果是把命题化为谓词，引进变量后，可构造由谓词构成的产生式系统，它的表达能力要强得多。93第二章 知识与知识表示第三节 产生式系统三、产生式的知识元形式3、元组 在许多专家系统中，经常以（对象,属性,值）的三元组形式作为产生式系统的知识元。4、树和图94第二章 知识与知识表示第三节 产生式系统三、产生式的知识元形式注：1)知识元可涉及复杂的计算，如exist(x,D) 2)一般地，变量的作用域仅限于它所在的产生式。若在匹配过程中，某规则中的一个变量被约束为某个值，则同一规则中所有同名变量必须约束为同一个值，但对其它规则中的同名变量无任何影响。同时，不论是规则匹配失败或成

39、功地结束，被约束的变量均要恢复原状，即只起一种形式参数的作用。但是也有例外，如在许多语法置换系统中，同一字符串中的几个同名变量可被置换为不同的子串。另一例外是作用域的放大。95第二章 知识与知识表示第三节 产生式系统四、推理方向1、最基本推理方式 a)向前推理：数据驱动推理。 b)向后推理：目标驱动推理。96第二章 知识与知识表示第三节 产生式系统四、推理方向2、向前推理基本原理 每个产生式的左部有一组条件，右部有一组动作。每当数据基的当前状态符合某一产生式左部的所有条件时，相应产生式被激发，并执行其右部的动作。这些动作一般要修改数据基的内容，动作执行完毕，数据基的状态可能已经发生改变。此时，

40、再找一个产生式，如此循环反复。S1S2S3执行产生式Pa执行产生式Pb.97第二章 知识与知识表示第三节 产生式系统四、推理方向2、向前推理基本原理 注：1)在大部分向前推理的产生式系统中，每个条件用一个谓词来表示，产生式的左部是一串谓词，产生式的右部也是一串谓词。产生式的左部与当前数据基匹配成功的含义是：对产生式左部所有谓词中出现的变量可以实行一种统一的置换，使得置换后的谓词均是当前数据基中某个谓词的样品。执行产生式右部动作的含义是：把左部匹配成功时实行的那个变量置换传播到右部来，使右部谓词中出现的变量按同一方式实行置换。 98第二章 知识与知识表示第三节 产生式系统四、推理方向2、向前推理

41、基本原理 注：2)向前推理可形成一片森林。 3)对于产生式的激发还应加一个条件：当执行一个产生式右部的动作不能改变数据基的状态时，即使产生式左部能与数据基匹配，也不应当激发该产生式。即，当产生式的右部不能为数据基增添新的谓词时，就不应激发此产生式，否则会产生许多无用的空转，可能使产生式系统的运行不能停止。99第二章 知识与知识表示第三节 产生式系统四、推理方向2、向前推理基本原理 注：4)在一般情况下，运行产生式系统应有一个目标。每执行一次向前推理，就要将当前数据基状态与目标状态比较一下，若已达到目标，则停止运行。 5)有时，无目标的向前推理也是需要的。这往往是为了推出所需要的全部结果。100

42、第二章 知识与知识表示第三节 产生式系统四、推理方向3、向后推理a)基本原理 设目标状态为S1,则首先查看数据基的当前状态是否已是S1。若是，则不必做任何工作，问题已解决，否则，查看有无这样的规则R1，可把状态S2转换为S1。若有，则查看当前数据基的状态是否是S2，若是，则只要执行R1，即可达到状态S1，问题也可解决。若当前数据基的状态不是S2，则进一步查看有无这样的规则R2，可把状态S3转换为S2，若有，则查看当前数据基的状态是否是S3,，如此反复，得到一条向后推理链。101第二章 知识与知识表示第三节 产生式系统四、推理方向3、向后推理a)基本原理 S1S3S2. 执行产生式R1 执行产生

43、式R2102东南大学远程教育人人人人 工工工工 智智智智 能能能能第第14讲讲主讲教师：翟玉庆主讲教师：翟玉庆103第二章 知识与知识表示第三节 产生式系统四、推理方向3、向后推理b)实现方式 对于这类产生式系统，推理目标也可取一个谓词的形态，称为目标谓词。 推理步骤是：以目标谓词为树根，首先查看当前数据基中是否有这样的谓词存在，它们与目标谓词存在最广通代。若有n个这样的谓词，则从树根生出n枝“或枝”，每枝或叉的终点是上述数据基谓词经过最广通代之后的一个样品；然后，再查看有无这样的规则，它们的右部谓词与目标谓词之间存在最广通代，若有m个这样的规则， 104第二章 知识与知识表示第三节 产生式系

44、统四、推理方向3、向后推理b)实现方式 (推理步骤)：则从树根再生出m枝“或叉”，每枝或叉的终点是上述规则的右部谓词经过最广通代之后的样品。若和某个右部谓词相对应的左部有k个谓词，则从相应或叉的终点又生出k枝“与叉”，每枝与叉的终点对应于一个左部谓词，其中的所有变元均已按照右部谓词所作的最广通代作了相应的置换。 在上述过程中，或叉的起点称为或结点，其终点称为与结点；与叉的起点称为与结点，其终点称为或结点。105第二章 知识与知识表示第三节 产生式系统四、推理方向3、向后推理b)实现方式 (推理步骤)：由上可知：或结点和与结点互为因果。按此办法不断进行下去，可使与叉和或叉，与结点和或结点循环轮回

45、，生成一棵树，称为与或树。它可以是有穷的，也可是无穷的。 若从一个或结点生出的所有或叉中，有一枝或叉的终点是当前数据基中某个谓词的一个样品，则称此或结点成功，它的子与结点(即上述谓词样品)自然也成功，并且是与或树的一个叶结点。若从一个或结点不能生出任何或叉，则称此或结点失败，它也与或树的一个叶结点。106第二章 知识与知识表示第三节 产生式系统四、推理方向3、向后推理b)实现方式 (推理步骤)：若一个或结点的所有子与结点皆失败，则该父或结点也失败。若一个与结点成功，则它的父或结点也成功。若一个父与结点的所有子或结点皆成功，则该父与结点也成功。 若由于某些叶结点的成功，使得根结点(它一定是或节点

46、)成功，则整个推理成功。若到某个时刻，由于某些叶结点的失败而使得推理不再能进行，则整个推理失败，否则，与或树有可能无穷地生长下去。107第二章 知识与知识表示第三节 产生式系统四、推理方向3、向后推理c)最广通代定义定义1通代 若有一组谓词W=1,2, n，又有一个代换，使 1=2=n，则称为谓词组W的通代。定义2广通代 若1和2均是谓词组W的通代，另有一个代换3，使得：W13=W2 ，则称通代1较通代2为广。定义3最广通代 设是谓词组W的一个通代,若对任意其它通代，均比广，则称为W的一个最广通代。注：最广通代可不唯一。108第二章 知识与知识表示第三节 产生式系统五、框架问题1、框架问题 一

47、般，每个谓词只有已知其真假和还未知道其真假的区别，不会原先是真的，后来变假了，或反过来，原先是假的，后来变真了。即，真的假不了，假的真不了。 但对于一些系统，谓词的真假值会在推理过程中发生变化，且数据基的状态每次只改变一些。而其余部分则没有变化。这就是框架问题。 注：具有框架问题的系统主要是用于描述客观世界中状态变迁的系统。109第二章 知识与知识表示第三节 产生式系统五、框架问题2、处理方法 a)直接指明法 在每个产生式中直接指明增加哪些谓词，删去哪些谓词。 b)引入状态参数法 在每个谓词中增加一个状态参数，以使得一个谓词在不同状态可取不同值。 注：具有不同状态参数的同一谓词是不同的谓词样品

48、，从而完全可有不同的值。 c)谓词函数化(高阶逻辑法) 所用的谓词全部写成函数的形式，这样谓词样品就是项。 110第二章 知识与知识表示第三节 产生式系统六、非确定性匹配 不要求产生式的左部能与数据基中的数据完全匹配，往往只需要部分的匹配(主要是由于已有的信息不是十完备)，就可推出某些结论性的信息。 注：可采用权、可信度来表示和确定事实与规则的匹配程序111第二章 知识与知识表示第三节 产生式系统七、匹配冲突的解决1、匹配冲突 在向前推理时，有n个产生式(n1)的左部均能与当前数据基中的数据匹配成功，或有m组不同数据(m1)均能和同一产生式的左部匹配成功，或两种情况的组合。 在向后推理时，有n

49、个产生式(n1)的右部均能和同一子目标匹配成功，或有m组不同数据(m1)均能和同一子目标匹配成功，或有l个子目标(l1)均能找到相应的数据或产生式右部并匹配成功，或三种情况的复合。 这就形成了匹配冲突。112第二章 知识与知识表示第三节 产生式系统七、匹配冲突的解决1、匹配冲突 注：产生式系统中的解释执行系统必须具有某种选择功能，以便排除上面列举的二义性。这是在设计产生式系统时应该考虑的一个策略问题，这就是解决匹配冲突的策略。2、解决冲突的策略a)按事先排好的固定顺序b)按通用性和针对性排序c)按数据的新鲜性排序d)按子目标的新鲜性排序e)按使用产生式和数据的公平性排序f)按匹配程度排序113

50、东南大学远程教育人人人人 工工工工 智智智智 能能能能第第15讲讲主讲教师：翟玉庆主讲教师：翟玉庆114第二章 知识与知识表示第四节 框架结构一、事物的属性1、属性 用于描述事物特性的项 注：1)掌握了事物的属性，就有关于事物的知识 2)属性一般具有属性名和相应值 3)属性是描述事物的最小元素2、属性表 将同一事物的各方面属性列成一张表，构成该事物的属性表 注：1)属性表是属性的集合，用于描述事物的整体特性 2)属性表中的属性之间可存在依赖关系115第二章 知识与知识表示第四节 框架结构一、事物的属性3、属性框架 对于具有同样一些属性的事物,可将这些属性确定为属性框架 注：1)只要在此框架内对

51、诸属性赋以不同的值,就可得到对同一类事物不同个体的描述 2)属性框架与数据库中关系表的定义非常相似，但属性框架中的某些属性可被看作事物而拥有自己的属性表，从而可形成层次式的嵌套结构 3)在对事物进行推理的过程中，事物的属性有时也要一起参加推理，推理可包含对有关属性的运算，运算结果组成推理结果的一部分 116第二章 知识与知识表示第四节 框架结构一、事物的属性3、属性框架 对于具有同样一些属性的事物,可将这些属性确定为属性框架 注：4)属性框架内的属性之间可存在横向关系和纵向关系，且纵向关系更能深刻地反映客观世界中各事物之间的关系 5)在事物子类的属性和事物母类的属性之间存在一种继承和发展的关系

52、。继承可以是直接继承，也可是经过计算以新的值继承；可以是全盘继承，也可是有选择的继承 6)将事物及其属性分类-分层加以描述的方法是框架理论的基础 117第二章 知识与知识表示第四节 框架结构二、框架1、概念 用于表示事物各方面的属性、事物之间的类属关系及事物的特征和变异等的概念2、基本思想 使用“套套”事物状态、属性、发展过程和相互关系的规律118第二章 知识与知识表示第四节 框架结构二、框架3、框架的主要特征a)有一个框架名（可带有参数）b)有一组属性，每个属性称为一个槽，里面可存放属性值c)每个属性对值有要求，不同属性的类型可不同d)有些属性值可为子框架调用（可带参数）e)有些属性值是预先

53、确定，有些属性值需在生成实例时代入f)有些属性值在代入时需满足一定条件，有时，在不同属性的属性值之间还有一些条件需要满足119第二章 知识与知识表示第四节 框架结构二、框架4、框架系统应具备的功能a)描述 通过工具建立和管理（查阅、修改、推理、）对某类客观事物的一个描述。 注：1)描述可由一组相互联系、互相支持的框架组成 2)在建立单个框架时，可根据需要设置一组槽，规定每个槽的性质，及槽之间的关系3)每个槽在框架中被认为无内部结构的，但当需要时，它本身又可扩充为一个有内部结构的框架120第二章 知识与知识表示第四节 框架结构二、框架4、框架系统应具备的功能b)子类 将复杂的事物分为子类,再将子

54、类分成更小的子类,定义更小的框架。c)实例 注：子类的最低层是实例,它已不是一个类,而只是一个个体的描述,它是框架体系树的树叶121第二章 知识与知识表示第四节 框架结构二、框架4、框架系统应具备的功能d)匹配注：1)框架匹配一般是部分匹配，完全匹配是特殊情形 2)框架不完全符合实际事物的可能性有：规定的属性不存在、规定的属性值不符、属性的缺省值和被匹配事物相应属性值不符、为某个属性的值规定的类型或条件不成立3)可通过规定必要条件、规定允许误差范围、规定计算偏差度、规定属性加权、设置一组判定产生式、既规定充分因子又规定必要因子、不局限于绝对成功的匹配来确定匹配成功条件122第二章 知识与知识表

55、示第四节 框架结构二、框架4、框架系统应具备的功能e)预测 根据框架对客观事物进行预测注：1)预测实际上是一种框架内部的推理 2)预测的用途有：指导进一步的观察、假定还未观察到的或难以观察到的事物123第二章 知识与知识表示第四节 框架结构二、框架4、框架系统应具备的功能f)继承注：继承除了子类继承，还可有如下情形的继承：有限制地继承和排斥属性、有限制地继承和排斥属性值、有限制地继承和排斥条件、给出属性值的映射函数、指明属性的分裂等124第二章 知识与知识表示第四节 框架结构二、框架4、框架系统应具备的功能g)变异 用于处理实际事物与框架很不一致的反常现象注：变异的概念使框架匹配的定义进一步精

56、确化。h)更新 注：在发生变异的情形下需更新i)修改 对老框架进行修改，以符合变异要求j)查找 注：查找时，可能需要回溯125东南大学远程教育人人人人 工工工工 智智智智 能能能能第第16讲讲主讲教师：翟玉庆主讲教师：翟玉庆126第二章 知识与知识表示第五节 语义网络一、基本思想1、用一个有向图表示概念和概念之间的关系，其中节点代表概念，节点之间的连接弧(也称联想弧)代表概念之间的关系2、寻找两个概念之间关系的方法是：从此两个概念出发，分别以广度优先的方法沿着连接弧向前搜索，这两个搜索圈逐渐扩大，若某个时刻两者碰上，即形成一条连接两个概念的通路，则认为是找到了两个概念之间的联系127第二章 知

57、识与知识表示第五节 语义网络二、 常见的语义网络形式1、命题语义网络2、数据语义网络 E-R图（实体-关系图）3、语言语义网络128第二章 知识与知识表示第五节 语义网络三、命题语义网络1、简单命题语义网络 a)基本思想 用节点表示命题，弧表示命题关系 例：她身穿大红袄，头戴一枝花人女人她头上身上与附有附有花大红袄戴着穿着动作事物个体子集部分部分地点地点对象方式方式对象个体个体个体个体状态129第二章 知识与知识表示第五节 语义网络三、命题语义网络1、简单命题语义网络 b)举例 例1：她身穿大红袄，头戴一枝花人女人她头上身上与附有附有花大红袄戴着穿着动作事物个体子集部分部分地点地点对象方式方式

58、对象个体个体个体个体状态130第二章 知识与知识表示第五节 语义网络三、命题语义网络1、简单命题语义网络 b)举例 例2：他用激光打印机打印了这份文件办公机器插座打印机激光打印机打印完成的动作动作他男人人文件办公资料资料个体子集电源子集个体工具动作主体动作对象个体子集131第二章 知识与知识表示第五节 语义网络三、命题语义网络2、一般谓词语义网络 a)基本思想 使用网络分块化技术：将复杂命题拆成许多子命题，每个子命题用一个小的语义网络表示，称为一个空间，复杂命题构成大空间，子命题构成子空间，它本身又可看作大空间中的一个节点，子空间可层层嵌套，也可用弧互相连接 132第二章 知识与知识表示第五节

59、 语义网络三、命题语义网络2、一般谓词语义网络 b)举例 例1： 每个学生都读过一本书 xy(学生(x)书(y) 读过(x,y)GS注：1)GS是全体命题的集合 2)F弧指示所代表的命题 gsrb学生读书个体个体个体个体动作主体动作对象F133第二章 知识与知识表示第五节 语义网络三、命题语义网络2、一般谓词语义网络 b)举例 例2：每个学生都读过所有的书 x y(学生(x)书(y) 读过(x,y)GS gsrb学生读书个体个体个体个体动作主体动作对象F134第二章 知识与知识表示第五节 语义网络三、命题语义网络2、一般谓词语义网络 b)举例 例3：每个学生都读过一本所有作家都喜欢的书 x (

60、学生(x)y(书(y) 读过(x,y) z(作家(z) 喜欢(z,y)135第二章 知识与知识表示第五节 语义网络三、命题语义网络2、一般谓词语义网络 b)举例 例3：每个学生都读过一本所有作家都喜欢的书学生g1GS作家sr读书bliken喜欢g2个体动作主体动作对象个体个体个体动作主体动作对象个体个体个体FF136第二章 知识与知识表示第五节 语义网络三、命题语义网络2、一般谓词语义网络 c)子空间(块)偏序排序规则 1)若从子空间S1内的某个节点有弧通向子空间S2中的某个节点(或S2完全包含S1)，则称S2在S1之上，或S1在S2之下。 2)若S2在S1之上，S3又在S2之上，则S3也在S

61、1之上（满足传递性） 注：1)这里，各子空间的节点之间不允许形成循环，它们形成一个偏序，一般说来还构成一个半格 2)在语义网络的推理和实现技术上，偏序有其特殊的意义，可将偏序解释为“可见”137第二章 知识与知识表示第五节 语义网络三、命题语义网络2、一般谓词语义网络 c)子空间(块)偏序排序规则 注：3)可见的定义为：若子空间S2在S1之上，则S1对于S1来说，是可见的。显然，可见关系具有自反和传递两种性质，但没有对称性。事实上，它是反对称的(因不允许循环) 4)子空间偏序相当于传统程序设计语言中的嵌套结构 5)利用“可见性”，能使系统提高系统的运行效率，因为在一个子空间中进行操作时，只需考

62、虑相关可见空间，这样可减少搜索和推理范围 138东南大学远程教育人人人人 工工工工 智智智智 能能能能第第17讲讲主讲教师：翟玉庆主讲教师：翟玉庆139第二章 知识与知识表示第五节 语义网络三、命题语义网络2、一般谓词语义网络 d)间接和嵌套命题的表示 例：李平说他想看红楼梦 三个命题： 1)李平说. 2)他想. 3)他看红楼梦140第二章 知识与知识表示第五节 语义网络三、命题语义网络2、一般谓词语义网络 d)间接和嵌套命题的表示 例：李平说他想看红楼梦李平人说g1GS个体动作主体动作对象个体st想g2看红楼梦同一同一动作主体动作主体动作对象动作对象FF书个体个体141第二章 知识与知识表示

63、第五节 语义网络四、数据语义网络1、基本概念 以数据为中心的语义网络。2、导因 利用数据时，需要数据的语义和数据间的关系，以向用户提供数据的有关知识，包括支持用户对数据实行推理的功能3、作用 用于知识型数据库的一种知识表示方法 142第二章 知识与知识表示第五节 语义网络四、数据语义网络4、主要形式 a)DBTG模型 系二级树 b)E-R模型学生选课课程学号姓名教室课程号课程名143第二章 知识与知识表示第五节 语义网络四、数据语义网络4、主要形式 c)Su-Lo语义联系模型 以实体之间的联系为中心,使用九种基本联系模型,以确切地表达各种数据之间的关系 1)成员联系 表示由属于同一概念的一组原

64、子元素或下层概念构成的一个集合,称作CC(概念类)节点CCCCCC学校院系部处144第二章 知识与知识表示第五节 语义网络四、数据语义网络4、主要形式 c)Su-Lo语义联系模型 2)特征联系 由一组特征构成某一实体的完整描述，有两类节点：DE(表示一组特征刻划了一个可独立存在的实体)、CE (表示一组特征刻划了一个不可独立存在的实体) 注：CE的存在依赖于由某个DE联系表达的独立存在的实体145第二章 知识与知识表示第五节 语义网络四、数据语义网络4、主要形式 c)Su-Lo语义联系模型 3)相互作用联系 用EI节点表示，用以描述两个实体之间的相互作用，其联系的实体中必须包含两个分量：AG(

65、动作主体)、DO(动作对象)。另外，可包含对相互作用加以修饰的成分(用MD表示) 注：AG,DO,MD标记在弧上146第二章 知识与知识表示第五节 语义网络四、数据语义网络4、主要形式 c)Su-Lo语义联系模型 4)集合关系联系 用SR节点表示 (1)子集关系 母集用ST弧联系，子集用SB弧连接 (2)互斥关系 均用SX弧连接 (3)相交关系 均用SI弧连接(4)对应关系 均用SE弧连接147第二章 知识与知识表示第五节 语义网络四、数据语义网络4、主要形式 c)Su-Lo语义联系模型 5)合成联系 用CP节点表示，分概念本身用COP弧连接 6)因果联系 用CF节点表示，用于建立原因(一般以

66、相互作用节点表示)与结果(相互作用节点或其它概念节点)之间的联系，用CA和EF分别标记连接原因和结果的弧148第二章 知识与知识表示第五节 语义网络四、数据语义网络4、主要形式 c)Su-Lo语义联系模型 7)活动方式联系 用AM节点表示，联系的一方是一个活动(用相互作用联系表示)，另一方是一些此活动的实体或联系。前者用AC弧连接,后者用MAC弧连接 8)活动目的联系 用AP节点表示，联系的一方是活动(可用EI或DE等节点表示)，另一方是活动的目的，也可用同类节点表示。前者用AC弧连接,后者用PR弧连接149第二章 知识与知识表示第五节 语义网络四、数据语义网络4、主要形式 c)Su-Lo语义

67、联系模型 9)蕴涵联系 用LRI节点表示，联系的一方是前提 (可用EI或DE等节点表示)，另一方是结论。前者用IF弧连接,后者用THEN弧连接 注：Su-Lo语义联系模型要用大量的附加一致性规则，即语义过程，去补充，从而使得语义过程不是网络的一个组成部分，使得由网络表示的知识很不完整，也不直观。150第二章 知识与知识表示第五节 语义网络五、语言语义网络1、基本思想 在分析语句时，以动词为中心，而将所有其它成分都看作是对动词(动作)的修饰。每一种修饰称为一个格，不同形式的格是对句子理解的重要支柱。其结构包括两个部分：一部分为纯语法性质，以为代表，另一部分是语义性质，称为格结构。一个格结构由许多

68、格变元组成，每个格变元从语法上讲是一个名词短语，从语义上讲分别属于五种格关系(动作主体、主题、地点、源泉、目标) 151第二章 知识与知识表示第五节 语义网络五、语言语义网络2、举例 例：猪八戒背媳妇背现在时说明式肯定式猪八戒媳妇语态格一格二地点主题152第二章 知识与知识表示第五节 语义网络六、几种特殊的语义网络1、结构网络 用于描述客观事物结构 注：结构网络常见于模式识别，机器学习等应用领域中2、分类网络 用于描述抽象的概念，对它们按层次进行分类，每个概念用一个节点代表，节点之间的关系只有两种：子集关系和个体关系。子集关系联接中间节点，个体关系联接叶节点。整个网络结构一般呈树形。注：1)分

69、类网络是理解客观事物的重要工具，常见于专家系统应用中153第二章 知识与知识表示第五节 语义网络六、几种特殊的语义网络2、分类网络注：2)若令分类网络为严格的树形结构，并且在每条弧上标出循这条弧往下走的条件，则分类网络就成了一种判定树，在专家系统中有广泛的应用，许多专家系统都是基于分类的专家系统154第二章 知识与知识表示第五节 语义网络六、几种特殊的语义网络3、推理网络 本质上是一种已规范化的命题网络，其基本节点是事实或概念，而节点间的关系则表示推理规则注：1)推理网络较适合于专家系统中的推理 2)有的推理网络将每个判断中的谓词部分和变元部分分开，以得到更深入的推理关系和更模块化的推理规则表

70、示 3)推理网络表示的推理可以是不精确的155第二章 知识与知识表示第五节 语义网络六、几种特殊的语义网络4、框架网络 是语义网络和框架的联合使用，其中，网络中的节点是框架，相当于基本事实或假设，利用节点之间的关系可由某些框架推论出另一些框架；或者，网络中的节点既可代表框架，也可代表框架中的槽，每条弧的一头连着某个框架的一个槽，另一头连着另一个框架，其意义是，后面的框架是前面的槽所代表的子框架，以此实现框架的任意深度的嵌套调用。156第二章 知识与知识表示第五节 语义网络七、语义网络上的推理1、推理种类 a)闭式推理 b)开式推理157第二章 知识与知识表示第五节 语义网络七、语义网络上的推理

71、2、闭式推理 a)作用 主要用于寻找几个概念之间的内在联系。 b)基本思想 1)将语义网络中的每个概念节点看成一个有限自动机。这个有限自动机从任何一个输入弧上接受信号后就开始工作，并将输出信息沿各个输出弧发送出去。所有这些自动机的工作都是独立进行的。 158第二章 知识与知识表示第五节 语义网络七、语义网络上的推理2、闭式推理 b)基本思想 2)若寻找两个概念C1与C2之间的联系，则启动相应节点n1与n2对应的自动机，使它们发出信息，启动邻近自动机，进一步启动其它自动机。继续这个过程，使产生的信息沿着以n1和n2为中心的波浪形的大圈向外扩散。若这两个大圈在某处会合，则会合点就是C1和C2两个概

72、念的共同点，从C1经过会合点到达C2的路径就是这两个概念相互联系的方式。159第二章 知识与知识表示第五节 语义网络七、语义网络上的推理3、开式推理 a)作用 针对语义网络中的某个或某些概念提出问题，并通过语义网上的推理来回答问题 b)工作原理 从被提问的概念出发，顺着网中的通路进行搜索，直到找到能回答这个问题的概念节点为止160第二章 知识与知识表示第五节 语义网络七、语义网络上的推理3、开式推理 c)实现方式 1)建立一套有关弧的推理体系 首先确定一组基本元素，然后给出它们的推理关系，此时可把每个基本元素看成一个谓词，并用产生规则来表达这种关系。 如：动作对象(x,y)个体(x,z) t(

73、个体(t,z) 动作对象(t,y)161第二章 知识与知识表示第五节 语义网络七、语义网络上的推理3、开式推理 c)实现方式 2)直接将推理规则编入语义网络中 注：这种类型的语义网络把语义的重点不放在弧上而放在节点中，这是因为几乎所有的弧表示同一含义，即前提和推论的连接162东南大学远程教育人人人人 工工工工 智智智智 能能能能第第18讲讲主讲教师：翟玉庆主讲教师：翟玉庆163第二章 知识与知识表示第六节 过程性知识表示一、知识的过程性含义1、把解决一个问题的过程描述出来，即，解题知识的过程性表示2、把客观事物的发展过程用某种方式表示出来，即，故事知识的过程性表示注：1)在某些情况下，这两种含

74、义很难绝然分开 2)第二种含义往往用于理解用自然语言写的故事，主要是故事知识的过程性表示 3)最典型的过程性知识表示当然是通常的计算机高级语言164第二章 知识与知识表示第六节 过程性知识表示二、常见的过程性知识表示法1、状态空间 所有可能状态的全体，构成状态空间。对问题的求解就是从初始状态到目标状态的遍历。 注：在状态空间中，求解路径不一定唯一，即使最短路径也不一定唯一2、时序框架 将框架中的各个槽赋以隐含的时间先后次序，或使框架语句的次序具有时序的意义 注：框架语句一般包括该框架的知识元(一般是故事中的一个情节)和元知识(用于协调各情节之间关系的控制性知识)165第二章 知识与知识表示第六

75、节 过程性知识表示二、常见的过程性知识表示法3、概念依赖理论 a)基本思想 1)将基本概念抽出来，成为一组原子概念 2)确定原子概念之间的相互依赖关系 3)将所有的故事情节都用这组原子概念及其依赖关系表示出来 注：1)由于人们的观点不同，考察问题的角度和表示事物的方法也不同，所以，抽象出来的原子概念也不尽一样。 2)对原子概念的要求是：无二义性、表示唯一性、正交性(表达范围不应重复)、原子性、概括性166第二章 知识与知识表示第六节 过程性知识表示二、常见的过程性知识表示法3、概念依赖理论 b)Schank的概念依赖理论 1)将概念分为七个范畴：PP(概念名词)、PA(对象属性)、ACT(动作

76、)、LOC(位置)、TIME、AA(动作属性)、VAL(各类属性的值) 2)用“概念体(conceptualization)” 表示概念之间的关系 167第二章 知识与知识表示第六节 过程性知识表示二、常见的过程性知识表示法4、脚本168东南大学远程教育人人人人 工工工工 智智智智 能能能能第第19讲讲主讲教师：翟玉庆主讲教师：翟玉庆169第二章 知识与知识表示第七节 常识性知识表示一、常识定义 常识是人类社会中经过长期验证使用，众所周知、不言自明的知识。 注：1)从人与自然的关系来说，常识应是那些经过人类社会千百年实践检验固定下来的，对于大多数情况而言正确地反映了对客观世界规律的认识 2)常

77、识有可能有例外，但在没有迹象表明当前情况属于例外时，按常识处理，一般应合理、正确。 3)从人与人的关系来说，常识应是一种公共性的、约定性的知识，一种由于其“众所周知”而无需在每次交往中显式说明的知识。因此，常识使人际交往更简便、经济。170第二章 知识与知识表示第七节 常识性知识表示一、常识定义 常识是人类社会中经过长期验证使用，众所周知、不言自明的知识。 注：4)为了使人与计算机的交互尽可能地像人际交往一样简便、经济，为了使计算机求解问题的知识环境更有利于问题的求解，必须考虑使计算机具有常识，包括常识内容和常识机制。5)常识对人类想要做的许多事情是足够的。随着人类对客观世界描述希望更精确时，

78、科学知识会渐渐地与常识相分离171第二章 知识与知识表示第七节 常识性知识表示二、常识表示的难点1、数量巨大 注：一个专家系统的专业知识一般可用几百条或几千条事实和规则来表示，但常识难以收集2、关联复杂 注：1)对常识，难以定义其边界。 2)对常识进行描述时，会涉及多个实体、函数和关系，从而会使描述非常复杂，产生混淆。3、对某些主题的常识难以用描述性知识表示方法来描述4、不确定性、近似性、模糊性、时变性 172第二章 知识与知识表示第七节 常识性知识表示三、常识的重要性1、具有常识的系统会有商业应用价值 如，家庭机器人2、具有常识处理功能的专家系统会更有用 a)识别何时需要外部的知识 b)扩展

79、专家系统的知识 如，采用类比、比喻方法扩展3、理解自然语言 173第二章 知识与知识表示第七节 常识性知识表示四、常识处理方法 1、非单调推理 2、CYC工程 将最起码的常识装进计算机并使之发挥作用五、常识表示 1、逻辑公式表示 2、自然语言六、常识推理 有关常识内容和常识机制的研究 注：1)常识内容和常识机制是一个统一体 2)常识推理不仅涉及规则的层次，也涉及控制的层次174东南大学远程教育人人人人 工工工工 智智智智 能能能能第第20讲讲主讲教师：翟玉庆主讲教师：翟玉庆175第三章 搜索技术第一节 引言一、搜索 对于无成熟方法可用的问题求解，必须一步步地摸索求解，这种问题求解过程就是搜索。

80、 注：搜索技术是人工智能的核心技术之一。二、研究和选用搜索算法的原则1、有限搜索还是无限搜索？ 若搜索空间有限，则任何一种穷举算法均能完成任务。176第三章 搜索技术第一节 引言二、研究和选用搜索算法的原则2、搜索空间是静态的还是动态生成的？ 在人工智能中，搜索的对象(常称状态)是在搜索过程中逐步生成的，需将搜索对象的生成和评估的代价计算在内。 对于一般搜索，搜索空间基本是静态的，或表或数组或数据库。3、已知目标还是未知目标？4、只要目标还是也要路径？ 路径是解题过程中应用的操作序列。177第三章 搜索技术第一节 引言二、研究和选用搜索算法的原则5、状态空间搜索还是问题空间搜索？ 在解题过程中

81、的每一时刻，所要解决的问题均处于一定的状态，搜索过程只是将一个状态变成另一个状态(如，一盘棋局变成另一盘棋局)，则称为状态空间搜索。 若搜索的对象是问题，搜索的原则是把一个复杂的问题化为一组比较简单的子问题(如把一个复杂的下棋策略分为几个子策略)，则称为问题空间搜索。注：问题空间搜索常常比状态空间搜索有效，但算法要复杂些。178第三章 搜索技术第一节 引言二、研究和选用搜索算法的原则6、有约束还是无约束？ 问题空间搜索时，若子问题间互相无约束关系，则求接比较简单，否则，一般需要回溯，即，放弃已解决的子问题，走回头路，寻找新的解法。7、数据驱动还是目标驱动？ 数据驱动是向前搜索，目标驱动是向后搜

82、索。8、单向搜索还是双向搜索？179第三章 搜索技术第一节 引言二、研究和选用搜索算法的原则9、盲目搜索还是启发式搜索？ 按照预定的控制策略实行搜索，在搜索过程中获取的中间信息不用来改进控制策略，称为盲目搜索，反之，称为启发式搜索。 注：关于“启发式”，可有两种看法：1)任何有助于找到问题的解，但不能保证找到解的方法均是启发式方法；2)有助于加速求解过程和找到较优解的方法是启发式方法。180第三章 搜索技术第一节 引言二、研究和选用搜索算法的原则10、有对手搜索还是无对手搜索？ 若有两个控制源均能改变同一状态空间，并且任何一方向目标前进时，另一方均试图将它从目标拉开，则称为有对手搜索，通常称为

83、博弈搜索。注：博弈搜索算法可以看成是一种特殊的问题空间搜索。181东南大学远程教育人人人人 工工工工 智智智智 能能能能第第21讲讲主讲教师：翟玉庆主讲教师：翟玉庆182第三章 搜索技术第一节 引言三、一般搜索方法分类1、盲目搜索 1)无变量的盲目搜索 状态空间、问题空间的盲目搜索 深度优先、广度优先、代价优先、混合 向前、向后、双向 2)有变量的盲目搜索 通代2、启发式搜索183东南大学远程教育人人人人 工工工工 智智智智 能能能能第第22讲讲主讲教师：翟玉庆主讲教师：翟玉庆184第三章 搜索技术第二节 启发式搜索一、启发式搜索 把要求解的问题的具体领域的知识加进搜索算法中，控制搜索过程，以

84、提高算法效率的搜索方法，称为启发式搜索。 注：1)这里，搜索的对象(常称状态)往往是边搜索边生成，因此在考虑这种搜索的复杂性时，必须将搜索对象的生成和评估的代价计算在内。185第三章 搜索技术第二节 启发式搜索一、启发式搜索注：2)根据启发性信息(特定领域的知识信息)，在生成搜索树时可考虑种种可能的选择： a)下一步展开哪个节点？ b)是部分展开还是全部展开？ c)使用哪个规则(算子)？ d)怎样决定舍弃还是保留新生成的节点？ e)怎样决定舍弃还是保留一棵子树？ f)怎样决定停止或继续搜索？ g)如何定义启发函数(估值函数)？ h)如何决定搜索方向？186第三章 搜索技术第二节 启发式搜索二、

85、有序搜索算法1、基本思想 a)对于每个在搜索过程中遇到的新状态，计算一个估计值，根据估计值的大小，确定下一步将从哪一个状态开始继续前进。 b)一般以估计值小者作为较优的状态，以此实现最佳优先搜索。 c)计算状态估计值的函数是确定的，但每个状态的估计值的大小与初始状态到该路径有关。187第三章 搜索技术第二节 启发式搜索二、有序搜索算法2、算法 1)建立一个空的状态序列SS 2)建立一个空的状态库SB 3)定义一个估值函数f 4)若初始状态为S0,则定义初始状态S0(0,f(0)为当前新状态 5)将当前新状态按估计值从小到大的顺序插入到SS中，若新状态为目标状态，则将相应状态插入到具有相同估计值

86、的状态的最前面；否则将相应状态插入到具有相同估计值的状态的最后面188第三章 搜索技术第二节 启发式搜索二、有序搜索算法2、算法 6)若在SS或SB中原有一个状态与当前新状态共一个状态，则删去原有状态 7)若新状态在SS的最前面，则转11) 8)若某种状态极限已达到，则搜索失败，算法运行结束，无解 189第三章 搜索技术第二节 启发式搜索二、有序搜索算法2、算法 9)若任何规则均不能应用于状态序列SS中的第一个状态，或者虽能应用，但不能产生合适的新状态(在SS或SB中均没有者，称为新)，或虽能产生合适的新状态S(path2,f(path2),但不是改进型的(若SS和SB中已有状态S(path1

87、,f(path1),它与新状态共一个状态S，且f(path2)f(path1),则称新状态不是改进型的)，则将此第一个状态从SS中除去，送入SB中，否则转12)190第三章 搜索技术第二节 启发式搜索二、有序搜索算法2、算法 10)若SS成为空序列，则搜索失败，算法运行结束，无解 11)若SS中第一个状态已是目标状态，则搜索成功，算法运行结束(若该状态形如S(path,f(path)，则解就是(path)；否则转9) 12)取一个可应用于SS的第一个状态S(path,f(path)，并产生改进型的合适新状态的规则Rn，产生新状态T(path,n,f(path)，定义它为当前新状态，转5) #算

88、法完191东南大学远程教育人人人人 工工工工 智智智智 能能能能第第23讲讲主讲教师：翟玉庆主讲教师：翟玉庆192第三章 搜索技术第二节 启发式搜索二、有序搜索算法2、算法 注：1)状态是带路径和估计值的状态，而状态只是一个状态 2)对当前生成的新状态是否是目标状态的判断需要两次 3)这里每次只生成一个后代 4)给定估计值函数f的意义，则有序搜索就可归结为已知的搜索，如令f为状态节点的深度，则有序搜索就成为广度优先搜索 193第三章 搜索技术第二节 启发式搜索二、有序搜索算法2、算法 注：5)有序搜索算法不一定找到解，即使有解 6)有序搜索算法的特点是使用启发式信息(表现在估计值函数f上)，可

89、是启发式信息也会骗人，会引人误入歧途 7)有序搜索即使能找到解，也未必一定是最优的194第三章 搜索技术第二节 启发式搜索二、有序搜索算法3、算法改进 1)用多个估计值函数来“层层设卡” 2)对估计值函数的形式加以限制，以保证它一定能找到解，甚至一定能找到最优解。195第三章 搜索技术第二节 启发式搜索三、估计值函数的改进 令S为初始节点，ti为一组目标节点， n,ni,nj为任意节点 k*(ni,nj)为从ni到nj的最小代价 g*(n)=k*(S,n)为从初始节点S到节点n的最小代价 h*(n)=min k*(n,ti)为从节点n到一个目标节点ti的最小代价 f*(n)=g*(n)+h*(

90、n)为从初始节点出发，经过节点n，到达一个目标节点的最小代价 ti196第三章 搜索技术第二节 启发式搜索三、估计值函数的改进 g(n)为对g*(n)的估计，g(n)0 h(n)为对h*(n)的估计，h(n)0 f(n)=g(n)+h(n)为每个节点n处的估计值函数197第三章 搜索技术第二节 启发式搜索四、H算法 使用上述改进的估计值函数f的有序搜索算法就是H算法。 注：1) g(n)是容易找到的，如将从初始节点到节点n实际上走过的路径的代价作为g(n)，且永远有g*(n)g(n)。g(n)不断改进，随着更多的搜索信息的获取，g(n)的值呈下降趋势。 2)h(n)的选取要与具体问题领域的启发

91、信息相关。 3)由于h(n)的选择仍有很大的随意性，因此，H算法并不能保证找到一个解，更不能保证找到最优解。从而需要改进。 198第三章 搜索技术第二节 启发式搜索五、H*算法 1. 在H算法中规定h(n)h*(n) 2. 推广k*(ni,nj)的定义：令k*(n1,n2,nm)为从n1出发，经过n2,到达nm的最小代价，规定存在一个正整数e0，使得对任意的ni,nj,nm(njnm)均有k*(ni,nj,nm)-k*(ni,nj)e 3.经过如此限制以后的H算法就是H*算法。注：1)可以证明：只要目标状态存在，并且从初始状态到目标状态有一条通路，则H*算法一定在有限步内终止，并找到一个最优解

92、(即代价为最低的解）。199第三章 搜索技术第二节 启发式搜索五、H*算法注：2)H*算法的搜索效率在很大程度上取决于函数h(n)的选择，它要求h(n)h*(n)，但若h(n)太小，则启发信息就很少。 3)若h(n)0，g(n)为搜索深度或代价，则H*算法将退化为广度优先搜索或代价优先搜索。 4)h(n)的值在满足小于或等于h*(n)的前提下越大越好，启发式信息多(即h值大)的H*算法展开的节点是启发式信息少(即h值小)的H *算法展开的节点的子集。 200第三章 搜索技术第二节 启发式搜索五、H*算法注：5)若估计值函数h(n)满足单调条件： h(ni)-h(nj) k*(ni,nj)（其中

93、k*(ni,nj)是从ni到nj的最小代价，nj是ni的后续节点），则H*算法是循着从初始状态通向该节点的最优路径到达该节点的。 6)在H*算法中，每次只生成一个后续节点。201东南大学远程教育人人人人 工工工工 智智智智 能能能能第第24讲讲主讲教师：翟玉庆主讲教师：翟玉庆202第三章 搜索技术第二节 启发式搜索六、完全展开的有序搜索算法 1)建立一个空的状态序列SS 2)建立一个空的状态库SB 3)定义一个估值函数f 4)若初始状态为S0,则定义初始状态S0(0,f(0)为当前新状态 5)将所有当前新状态按估计值从小到大的顺序插入到SS中203第三章 搜索技术第二节 启发式搜索六、完全展开

94、的有序搜索算法 6)若在SS或SB中原有一个状态与当前某个新状态共一个状态，则删去原有状态 7)若SS的第一项是一个新状态，则转11) 8)若某种状态极限已达到，则搜索失败，算法运行结束，无解204第三章 搜索技术第二节 启发式搜索六、完全展开的有序搜索算法 9)若任何规则均不能应用于状态序列SS中的第一个状态，或者虽能应用，但不能产生改进型的合适新状态，则将此第一个状态从SS中除去，送入SB中，否则转12) 10)若SS成为空序列，则搜索失败，算法运行结束，无解 11)若SS中第一个状态已是目标状态，则搜索成功，算法运行结束(若该状态形如S(path,f(path)，则解就是(path)；否

95、则转9) 205第三章 搜索技术第二节 启发式搜索六、完全展开的有序搜索算法 12)取所有可应用于SS的第一个状态S(path,f(path)，并产生各不相同的改进型的合适新状态的规则Ri(iI)，产生新状态集T(path,i,f(path)， 其中对属于同一状态的各个状态只取一个最优者，转5) #算法完 206第三章 搜索技术第二节 启发式搜索七、A算法 使用估计值函数f(n)=g(n)+h(n)的完全展开的有序搜索算法。207第三章 搜索技术第二节 启发式搜索八、A*算法 在A算法规定：h(n)h*(n), k*(ni,nj,nm)-k*(ni,nj)e,则A算法成为A*算法注：1)A*算

96、法与H*算法的主要区别有a)在H*算法中每次只生成一个后继节点，而在A*算法中每次生成一个节点的所有节点b)在H*算法中，每生成一个新节点，就询问它是否是目标节点，而在A*算法中，只询问栈顶节点是否是目标节点 2)在A*算法中，估计值函数f(n)=g(n)+h(n)的选择是一个关键208第三章 搜索技术第二节 启发式搜索八、A*算法注： 3)A*算法一定能保证找到最优解 4)若按展开的节点个数来估计它的效率，则当启发式函数h的值单调上升时，它的效率只会上升，不会下降，且有较合理的渐近性质 5)若不是考虑被展开的节点个数，而是考虑各节点被展开的次数，则A*算法在最坏情况下表示出很高的复杂性 6)

97、为了避免不正常的h值对解题路径的影响，Martelli提出了B算法，基本思想是h(n)可动态修改。209东南大学远程教育人人人人 工工工工 智智智智 能能能能第第25讲讲主讲教师：翟玉庆主讲教师：翟玉庆210第三章 搜索技术第二节 启发式搜索八、A*算法注： 7)在f(x)=g(x)+h(x)中，g(x)是“经验”项，起着稳定形势的作用，而h(x)是“冒险”项。九、双向启发式搜索十、几种特殊的启发式搜索 1、生成与测试方法 穷举？仍需要经验知识的指导 2、并行搜索法 3、爬山法 4、黄金分割法十一、与或树的启发式搜索 AO*算法211东南大学远程教育人人人人 工工工工 智智智智 能能能能第第2

98、6讲讲主讲教师：翟玉庆主讲教师：翟玉庆212第三章 搜索技术第三节 博弈树搜索一、博弈树 若参加搜索的不只有一个主体，而是对抗性的敌我双方，则搜索的进程不仅取决于一方，而且取决于对方应付的策略，由此产生的搜索树，称为博弈树。注：博弈树很象与或树213第三章 搜索技术第三节 博弈树搜索二、博弈树评价原则1、假定对手不会犯错误2、对手总是选择对他最有利的步子走3、在最坏的可能中选择最好的注：博弈树评价原则也称为极小极大原则，即在极小中取极大，因此，博弈树也称为极小极大树214第三章 搜索技术第三节 博弈树搜索三、极小极大算法1、以甲为博弈树的树根和或节点，并把甲送入待展开节点库TB2、若TB为空，

99、则对博弈树处理如下： 1)若某个或节点的所有子与节点的值均为已知，则此或节点的值定义为所有子与结点的值中之最大者（注：赢最大、平次之、输最小） 2)若某个与节点的所有子或节点的值均为已知，则此与节点的值定义为所有子或结点的值中之最小者 3)反复执行步骤1）、2），直至根节点被赋值，算法运行结束215第三章 搜索技术第三节 博弈树搜索三、极小极大算法3、若TB不为空，则从TB任取节点n，删去n，并 1)若n已直接表现出甲之赢、输或平，则对博弈树的n节点赋以相应的值(赢、输或平)，转2; 2)否则，若n为或节点，则生成n的所有子与节点，长在博弈树上，也送入TB之中，转2； 3)否则，若n为与节点，

100、则生成n的所有子或节点，长在博弈树上，也送入TB之中，转2； 算法完#216东南大学远程教育人人人人 工工工工 智智智智 能能能能第第27讲讲主讲教师：翟玉庆主讲教师：翟玉庆217第三章 搜索技术第三节 博弈树搜索三、极小极大算法注：1)博弈的结局可能不是简单的输赢，而是有几种可能的得分，但原理一样 2)该算法并不保证一定结束，事实上，若想穷尽博弈的所有可能性，则在许多情况下不会结束 3)博弈树中的每一分叉，必须有意义，该意义是根据具体领域情况而定 4)博弈树体积可能会达到计算机根本无法处理地步，穷举战术行不通 5)对博弈树的穷举搜索到一定深度就不再向下走218第三章 搜索技术第三节 博弈树搜

101、索三、极小极大算法注：6)不根据最后实际计算出的输赢来评分，而是根据在一定深度处的节点的估计值来评分，即用估计值代替实际的搜索 7)计算这种估计值的函数，称为静态估值函数f 8)对于表示输、赢、平的叶结点，其估计值可定义为：f(赢)=+、 f(输)=-、f(平)=0 9)一般情况下，f可定义为一个多项式，甚至线性函数，但若要取得较好的效果，则f往往定义为非线性的，此时，计算复杂性就增加了。10)除了确定静态估值函数外，还应尽量避免声称无用处的后代219第三章 搜索技术第三节 博弈树搜索三、博弈树优化1、优化方法 通过剪枝去除冗余现象2、冗余情形 a)极大值冗余 1 2 3 4 5 6 max

102、min min max f(4)=17 f(2)=19220第三章 搜索技术第三节 博弈树搜索三、博弈树优化2、冗余情形 b)极小值冗余 1 2 3 4 5 6 min max max min f(4)=25 f(2)=10221第三章 搜索技术第三节 博弈树搜索三、博弈树优化3、剪枝方法 a)-剪枝 将极大值冗余子树剪去的方法 b)-剪枝 将极大值冗余子树剪去的方法222东南大学远程教育人人人人 工工工工 智智智智 能能能能第第28讲讲主讲教师：翟玉庆主讲教师：翟玉庆223第三章 搜索技术第三节 博弈树搜索四、带剪枝的博弈树搜索算法使用静态估值函数以及-剪枝和-剪枝，形成带剪枝的博弈树搜索算

103、法1、建立一个空的棋局栈PSi,j, 其中，对每个i： PSi,1是棋局内容，PSi,2是“与”或“或” PSi,3是搜索深度，PSi,4是估计值 PSi,5是生成子节点数2、确定正整数depth为最大推理深度 224第三章 搜索技术第三节 博弈树搜索四、带剪枝的博弈树搜索算法3、建立已知结果的棋局库PB,PB的元素与PS的元素形式相同，并且每个元素的第一、第二和第四分量都已有确定的值；4、建立根节点： PS1,1=初始棋局 PS1,2=“或” PS1,3=0 PS1,4=- PS1,5=05、t=1 225第三章 搜索技术第三节 博弈树搜索四、带剪枝的博弈树搜索算法6、若PSt,1=X1,P

104、St,2=X2,且XPB,则 (1)PSt,4=X4 (2)转107、若PSt,3=depth，则 (1)PSt,4=f(PSt,1) (f是估值函数) (2)转108、若PSt,1不能生成新的后代，则 (1)若PSt,5=0，则PSt,4=f(PSt,1) (2)转10226第三章 搜索技术第三节 博弈树搜索四、带剪枝的博弈树搜索算法9、生成PSt,1的一个新后代： (1)PSt,5=PSt,5+1 (后代计数) (2)t=t+1 (3)PSt,1=新棋局 (4)PSt,2=if PSt-1,2=“或” then “与” else “或” (5)PSt,3=PSt-1,3+1 (6)PSt,

105、4=if PSt,2=“或” then - else + (7)PSt,5=0 (8)转610、若t=1则算法运行结束，最后的估计值已算出227第三章 搜索技术第三节 博弈树搜索四、带剪枝的博弈树搜索算法11、t=t-112、若PSt,2=“或”，则 (1)若PSt+1,4PSt,4,则PSt,4=PSt+1,4 (取极大值)，否则转8 (2)若t=1，则转8 (3)若PSt,4PSt-1,4,则t=t-1 (剪枝) (4)转8228东南大学远程教育人人人人 工工工工 智智智智 能能能能第第29讲讲主讲教师：翟玉庆主讲教师：翟玉庆229第三章 搜索技术第三节 博弈树搜索四、带剪枝的博弈树搜索算

106、法13、若PSt,2=“与”，则 (1)若PSt+1,4PSt,4,则PSt,4=PSt+1,4 (取极小值)，否则转8 (2)若t=1，则转8 (3)若PSt,4PSt-1,4,则t=t-1 (剪枝) (4)转8 #算法完230第三章 搜索技术第三节 博弈树搜索四、带剪枝的博弈树搜索算法注：1)该算法是从开局先行者的立场出发的，计算所得根节点的值是对先行者前途的预测 2)该算法只给出对先行者前途的估计值，以及第一步应该怎么走，而没有给出全局棋每一步的走法 3)该算法的缺陷就是需说明是从某人的立场出发，若换一个立场，则要做一个对称的改变231第三章 搜索技术第三节 博弈树搜索五、带剪枝的博弈树

107、搜索算法的改进1、采用负极大值原理 令父结点的估计值为各子节点的估计值的负数的极大值，即 PSi,4=max(-PSi+1,4) (i+1遍及i的所有子节点）2、B*算法 (1)尽早查出不合用的坏分枝，并把它剪掉(改进-剪枝) (2)合理地确定搜索的深度限制232东南大学远程教育人人人人 工工工工 智智智智 能能能能第第30讲讲主讲教师：翟玉庆主讲教师：翟玉庆233 人工智能及其应用一、人工智能的核心概念 知识、学习、推理、启发式搜索二、人工智能与应用的结合途径 1、基于知识的系统 专家系统、多专家系统 智能决策支持系统 知识科学 2、具有学习和推理功能的系统 自适应系统 3、协同合作系统 分

108、布式人工智能与多Agent系统 4、柔性处理系统 234 人工智能及其应用二、人工智能与应用的结合途径 5、智能控制系统 模糊控制 6、军事指挥系统 C4I Command Computer Control Communication Information 235东南大学远程教育人人人人 工工工工 智智智智 能能能能第第31讲讲主讲教师：翟玉庆主讲教师：翟玉庆236 复习一、复习和考试依据 课件和教材二、考试方式 闭卷考试，考试时间为2小时三、考试题型 1、概念题(40%) 八个 8*5 按照课件内容回答 2、简述题(30%) 三个 3*10 按照课件内容回答 3、论述题(30%) 两个 2

109、*15 根据自己的理解回答 237 复习四、主要知识点 1、人工智能的基本概念 2、人工智能的发展历史(萌芽、提出、发展) 3、人工智能的主要研究方法 4、人工智能的主要研究内容 5、知识及知识表示原则 6、演绎系统知识表示法的基本思想 7、产生式系统 8、向前推理、向后推理的基本思想 9、框架及语义网络知识表示法10、常识及其处理机制 238 复习四、主要知识点 11、搜索算法及其选择原则 12、动态搜索和启发式搜索的基本思想 13、有序搜索算法和完全展开的有序搜索算法的基本思想 14、启发式函数的改进思想 15、H*、A*算法的基本思想 16、博弈树及博弈树搜索算法的基本思想 17、极小极

110、大算法的基本思想 18、剪枝及带剪枝的博弈树搜索基本思想 19、人工智能及其应用239东南大学远程教育人人人人 工工工工 智智智智 能能能能第第32讲讲主讲教师：翟玉庆主讲教师：翟玉庆240 复习五、主要概念 智能、人工智能、智能革命、推理、定性推理、不确定性推理、学习、分布式人工智能(DAI)、Agent、知识、自然演绎系统、子句、产生式、产生式系统、框架、语义网络、常识、搜索、启发式搜索、博弈树。241 复习六、主要简述题 1、人的智能与人工智能 2、人工智能的导因 3、人工智能的主要研究方法及其基本思想和基本观点4、图灵测试的基本思想及作用5、常见的知识类型6、知识表示的基本原则7、Ro

111、binson子句消解法的基本思想8、产生式系统的构成及其基本特征9、向后推理的基本原理及实现方式的基本思想10、产生式系统中的匹配冲突及其解决方案242 复习六、主要简述题11、语义网络的基本思想12、概念依赖理论的基本思想13、常识表示的难点14、研究和选用搜索算法的原则15、有序搜索算法的基本思想16、可用的估计值函数的改进方法及其基本思想17、H*和A*算法的基本思想18、博弈树评价原则及极小极大算法的基本思想243 复习七、主要论述题1、人工智能及其应用2、基于知识的系统及其应用3、人脑、电脑与人工智能4、为什么说知识和推理是人工智能的核心，而学习是人工智能的关键？ 5、为什么说基于知

112、识的系统是人工智能的发展趋势之一？ 6、你认为人工智能的进一步发展趋势是什么？为什么？244 复习八、作业解答1、什么是智能和人工智能？2、智能革命的主要含义是什么？3、通过图灵测试，你认为机器能思考吗？为什么？4、为什么要提出人工智能研究？5、MaCarthy和Feigenbaum在人工智能发展历史中的各自地位是什么？6、为什么人工智能的发展趋势是建立基于知识的系统 245 复习八、作业解答7、人工智能的主要研究方法是什么？各自的基本思想和典型工作是什么？8、什么是推理、定性推理和不确定性推理？试举例说明。9、什么是学习？其基本机理是什么？10、什么是知识？常见的知识类型有哪些？11、知识表

113、示原则是什么？12、用演绎系统表示知识的基本思想是什么？ 246 复习八、作业解答13、什么是产生式系统？其基本组成有哪些？14、产生式系统的基本特征是什么？15、向前推理和向后推理的基本思想是什么？16、什么是匹配冲突？如何解决？17、框架知识表示法的基本思想是什么?18、语义网络知识表示法的基本思想是什么？ 247 复习八、作业解答19、如何使用语义网络表示复杂的知识？20、过程性知识表示的基本思想是什么？ 21、常见的过程性知识表示方法有哪些？22、什么是常识？为什么要研究常识知识表示问题？23、什么是动态搜索？24、如何选择搜索算法？248 复习八、作业解答25、无变量的盲目搜索的基本思想是什么？26、有序搜索算法的缺陷是什么？如何改进？27、估计函数的改进思想是什么？28、H*和A*算法的基本思想是什么？29、极大极小算法的基本思想是什么？30、人工智能及其应用领域249