人工智能原理与方法.ppt

魏长华魏长华Department of Computer ScienceDepartment of Computer ScienceCCNUCCNUEmail:Email:CC人工智能原理与方法Artificial Intelligence2022/11/181WeiChanghua内 容第一章第一章 绪论绪论绪论绪论 什么是人工智能？什么是人工智能？人工智能研究的目标人工智能研究的目标 人工智能研究途径人工智能研究途径 人工智能研究的内容人工智能研究的内容 人工智能研究中的学派人工智能研究中的学派 人工智能研究的内容人工智能研究的内容 人工智能研究人工智能研究领领域域 2022/11/182WeiChanghua内 容第二章第二章第二章第二章 人工智能的数学基础人工智能的数学基础人工智能的数学基础人工智能的数学基础 命题逻辑和谓词逻辑命题逻辑和谓词逻辑命题逻辑和谓词逻辑命题逻辑和谓词逻辑 概率论概率论概率论概率论 模糊理模糊理模糊理模糊理论论论论 2022/11/183WeiChanghua内 容第三章第三章第三章第三章 知识表示知识表示知识表示知识表示 知识与知识表示知识与知识表示知识与知识表示知识与知识表示 对对对对知知知知识识识识表示的要求表示的要求表示的要求表示的要求 知知知知识识识识表示方法表示方法表示方法表示方法 一一一一阶谓词逻辑阶谓词逻辑阶谓词逻辑阶谓词逻辑 产产产产生式生式生式生式规则规则规则规则 语义语义语义语义网网网网络络络络 框架框架框架框架 状状状状态态态态空空空空间间间间 脚本脚本脚本脚本 Petri Petri Petri Petri网网网网 2022/11/184WeiChanghua内 容第四章第四章 基本的问题求解方法基本的问题求解方法基本的问题求解方法基本的问题求解方法 基本概念基本概念基本概念基本概念 状状状状态态态态空空空空间间间间搜索搜索搜索搜索 与与与与/或或或或树树树树搜索搜索搜索搜索 博弈博弈博弈博弈树树树树的启的启的启的启发发发发式搜索式搜索式搜索式搜索 2022/11/185WeiChanghua内 容第五章第五章第五章第五章 基本推理方法基本推理方法基本推理方法基本推理方法 推理的基本概念推理的基本概念 推理方式和分类推理方式和分类 推理控制策略推理控制策略 归结反演归结反演 基于规则的演绎系统基于规则的演绎系统 2022/11/186WeiChanghua内 容第六章第六章 不确定性推理不确定性推理不确定性推理不确定性推理 不确定性推理的基本概念不确定性推理的基本概念 确定因子法确定因子法 主观主观BayesBayes方法方法 证据理论证据理论 可能性理论可能性理论 2022/11/187WeiChanghua内 容第七章第七章 专家系统专家系统专家系统专家系统 专家系统的基本概念专家系统的基本概念 专家系统分类专家系统分类 专家系统的一般结构专家系统的一般结构 专家系统的建造与评价专家系统的建造与评价 专家系统开发工具专家系统开发工具 专家系统开发环境专家系统开发环境 新一代专家系统的研究新一代专家系统的研究 几个著名的专家系统几个著名的专家系统 2022/11/188WeiChanghua内 容第八章第八章 机器学习机器学习机器学习机器学习 机器学习的概念机器学习的概念 学习系统模型学习系统模型 机器学习分类机器学习分类 机器学习研究历史机器学习研究历史 机器学习的研究目标机器学习的研究目标 几个著名的学习系统几个著名的学习系统 2022/11/189WeiChanghua第一章 绪论绪论1什么是人工智能？人工智能是研究知识的一门科学，即如何表示知识，如何获取知识和如何利用知识的科学。2022/11/1810WeiChanghua第一章 绪论绪论2人工智能研究的目标近期目标：在近期，人工智能研究的任务是利用冯.偌依曼型计算机模拟人类智力行为，研制智能程序；远期目标：远期是研制全新的计算机，即智能计算机。2022/11/1811WeiChanghua第一章 绪论绪论33人工智能研究途径人工智能研究途径人工智能研究可以人工智能研究可以有三种途径有三种途径进行：进行：符符号号主主义义：（思思维维理理论论）符符号号主主义义认认为为人人类类认认知知的的基基本本元元素素是是符符号号，认认知知的的过过程程就就是是符符号号处处理理的的过过程程。（一一阶阶谓谓词词逻逻辑）辑）连连接接主主义义：（阈阈值值理理论论）连连接接主主义义认认为为人人类类认认知知的的基基本本元元素素是是神神经经元元本本身身。人人类类的的认认知知过过程程就就是是大大量量的的神神经经元元的的整整体体活动。（研究方法：人工神经网络）活动。（研究方法：人工神经网络）行行为为主主义义：（进进化化理理论论）由由美美国国麻麻省省理理工工学学院院的的教教授授提提出出的的。该该理理论论认认为为人人的的本本质质能能力力是是在在动动态态环环境境中中的的行行走走能能力力、对对外外界界事事物物的的感感知知能能力力、维维持持生生命命和和繁繁衍衍生生息息的的能能力力，正正是是这这些些能能力力对对智智能能的的发发展展提提供供了了基基础础，因因此此智智能能是是某某种种复复杂杂系统所浮现的性质。系统所浮现的性质。2022/11/1812WeiChanghua第一章 绪论绪论 44人工智能研究的内容人工智能研究的内容 （1 1）人工智能研究中的学派人工智能研究中的学派逻逻辑辑学学派派：以以麦麦卡卡锡锡和和尼尼尔尔逊逊为为代代表表的的研研究究基基于于逻逻辑辑的的知识表示和推理机制。知识表示和推理机制。认认知知学学派派：以以纽纽厄厄尔尔和和西西蒙蒙为为代代表表的的研研究究对对人人类类认认知知功功能的模拟，试图找出产生智能行为的原理。能的模拟，试图找出产生智能行为的原理。知知识识工工程程学学派派：以以费费根根鲍鲍姆姆为为代代表表的的研研究究知知识识在在人人类类智智能中的作用和地位，提出了知识工程概念。能中的作用和地位，提出了知识工程概念。连接学派：连接学派：以和以和J.D.RumelhartJ.D.Rumelhart为代表的研究神经网络。为代表的研究神经网络。分分布布式式学学派派：以以C.HewittC.Hewitt为为代代表表的的研研究究智智能能系系统统中中的的知知识识分布行为。分布行为。进化学派：进化学派：为代表为代表。2022/11/1813WeiChanghua第一章 绪论绪论（2 2）人工智能研究的内容）人工智能研究的内容 机机器器感感知知：所所谓谓的的机机器器感感知知就就是是使使机机器器具具有有类类似似于于人人的的感知能力，其中以机器视觉与机器听觉为主。感知能力，其中以机器视觉与机器听觉为主。机机器器思思维维：机机器器思思维维是是指指对对通通过过感感知知得得到到的的外外部部信信息息及机器内部的各种工作信息进行有目标的处理。及机器内部的各种工作信息进行有目标的处理。机机器器学学习习：研研究究使使机机器器具具有有获获取取新新知知识识、学学习习新新技技巧巧，并在实践中不断完善、改进的能力。并在实践中不断完善、改进的能力。机机器器行行为为：与与人人的的行行为为相相对对应应，机机器器行行为为主主要要是是指指计计算机的表达能力，即算机的表达能力，即“说说”、“写写”、“画画”等。等。2022/11/1814WeiChanghua第一章 绪论绪论5 5 人工智能研究领域人工智能研究领域 模式识别模式识别（PatternRecognitionPatternRecognition）自然语言理解自然语言理解（NaturallangrageUnderstandingNaturallangrageUnderstanding）专家系统专家系统（ExpertSystemExpertSystem）机器学习机器学习（MachineLearningMachineLearning）自动定理证明自动定理证明（AutomaticTheoremProvingAutomaticTheoremProving）自动程序设计自动程序设计（AutomaticProgrammingAutomaticProgramming）机器人学机器人学（RobotsRobots）博弈博弈（GameGame）智能决策支持系统智能决策支持系统（IntelligentDecisionSupportSystemIntelligentDecisionSupportSystem）人工神经网络人工神经网络（ArtificialnaturalnetworksArtificialnaturalnetworks）2022/11/1815WeiChanghua第一章 绪论绪论思考题思考题1 1、什么是人工智能？、什么是人工智能？2 2、人工智能研究的对象是什么？、人工智能研究的对象是什么？3 3、人工智能研究的途径有那些？、人工智能研究的途径有那些？4 4、人工智能研究的领域有那些？、人工智能研究的领域有那些？5 5、人工智能研究的近期目的和远期目的是什么？、人工智能研究的近期目的和远期目的是什么？6 6、简述图灵试验。、简述图灵试验。2022/11/1816WeiChanghua第二章第二章人工智能的数学基础人工智能的数学基础1 1命题逻辑和谓词逻辑命题逻辑和谓词逻辑命命题题：命命题题是具有真假意是具有真假意义义的的语语句。句。谓词谓词：一个一个谓词谓词由由谓词谓词名和个体两部分名和个体两部分组组成。成。谓词谓词公式：公式：连连接接词词、量、量词词。合合适适公公式式：原原子子是是合合适适公公式式；若若A A是是合合适适公公式式，则则 A A也也是是合合适适公公式式；若若A A、B B都都是是合合适适公公式式，则则A A B B ，A A B B ，A AB B ，也都是合适公式；也都是合适公式；若若A A是合适公式是合适公式则则，、也是合适公式。也是合适公式。谓词谓词公式的永真性公式的永真性、可、可满满足性和不可足性和不可满满足性足性 2022/11/1817WeiChanghua第二章第二章人工智能的数学基础人工智能的数学基础2 2 概率论概率论 条件概率条件概率：设：设A A，B B是两个事件，是两个事件，则称，则称为在为在A A事件已经发生的条件下事件已经发生的条件下B B事件发生的概率。事件发生的概率。全概率公式和全概率公式和BayesBayes公式的条件概率：设公式的条件概率：设 事件满事件满足：足：两两互不相容，即当两两互不相容，即当 时，有时，有 则对任何事件有下式成立：则对任何事件有下式成立：为全概率公式，它提供了一种计算的方法。为全概率公式，它提供了一种计算的方法。2022/11/1818WeiChanghua第二章第二章人工智能的数学基础人工智能的数学基础BayesBayes公式：称公式公式：称公式 为为BayesBayes公式。公式。2022/11/1819WeiChanghua第二章第二章人工智能的数学基础人工智能的数学基础3 3 模糊理论模糊理论 模糊集：模糊集：设设 是论域，是论域，是把任意是把任意 映射为映射为00，11上某个值的上某个值的函数，即函数，即 ，则称则称 由所构成的集合由所构成的集合A,A,称为称为U U上的一个模糊集。上的一个模糊集。隶属函数：隶属函数：称称 为为定定义义在在 U U上的一个隶属函数上的一个隶属函数。语语言言变变量：量：用自然用自然语语言表示言表示变变量的量的值值和描述和描述变变量之量之间间的内在的内在联联系系的一种的一种变变量。比如，年量。比如，年龄龄就是个就是个语语言言变变量，它可以取量，它可以取值为值为年年轻轻、很年很年轻轻、不很年、不很年轻轻、老、很老、不很老等。、老、很老、不很老等。语语言真言真值值 模糊推理模糊推理 2022/11/1820WeiChanghua第二章第二章人工智能的数学基础人工智能的数学基础思考题思考题 1 1、什么是合适公式？、什么是合适公式？2 2、试写出、试写出BayesBayes公式。公式。3 3、什么是语言变量？、什么是语言变量？4 4、试论述信息（知识）不确定性及其处、试论述信息（知识）不确定性及其处理的途径理的途径 2022/11/1821WeiChanghua第三章第三章 知识表示知识表示1 1 知识与知识表示知识与知识表示知知识识是是人人类类认认识识自自然然界界的的精精神神产产物物，是是人人类类进进行行智智能能活活动的基础。知识可以分为五类：动的基础。知识可以分为五类：描述性知描述性知识识 判断性知判断性知识识 过过程性知程性知识识 对对象象级级知知识识，或称，或称为领为领域相关的知域相关的知识识 元元级级知知识识 2022/11/1822WeiChanghua2 2 对知识表示的要求对知识表示的要求 表示能力表示能力 可理解性可理解性 可访问性可访问性 可扩展性可扩展性 3 3 知识表示方法知识表示方法 一阶谓词逻辑：它是一种描述性的表示方法，它的推理一阶谓词逻辑：它是一种描述性的表示方法，它的推理机制是归结原理。主要应用于定理证明。机制是归结原理。主要应用于定理证明。语义网络：是由语义网络：是由QuillianQuillian等人于等人于19681968年提出的，它在知识年提出的，它在知识表示中可以表示对象、概念及其相互间的关系。它广泛用于表示中可以表示对象、概念及其相互间的关系。它广泛用于基于知识的系统。基于知识的系统。产产生生式式规规则则：产产生生式式系系统统把把知知识识表表示示成成“模模式式动动作作”对对，表表示示方方式式自自然然、简简洁洁。它它的的推推理理机机制制以以演演绎绎为为基基础础。它它是专家系统的知识表示的主要方法。是专家系统的知识表示的主要方法。2022/11/1823WeiChanghua 框框架架：框框架架理理论论是是MinskyMinsky于于19741974年年提提出出的的，它它将将知知识识表表示示成成高高度度模模块块的的结结构构，它它是是把把关关于于一一个个概概念念或或对对象象的的所所有有信信息息和和知知识识都都存存储储在在一一起起的的数数据据结结构构。框框架架的的层层次次结结构构可可以以表表示示对对象象之之间间的的相相互互关关系系，用用框框架架表表示示知知识识的的系系统统称称为为框架的系统。框架的系统。状状态态空空间间：状状态态空空间间表表示示法法把把求求解解问问题题表表示示成成问问题题状状态态、操操作作、约约束束、初初始始状状态态和和目目标标状状态态。状状态态空空间间是是所所有有状态的集合。状态的集合。脚本：脚本也称为剧本。它是用来描述固定事件序列，脚本：脚本也称为剧本。它是用来描述固定事件序列，它的结构类似于框架。剧本更强调事件间的因果关系。它的结构类似于框架。剧本更强调事件间的因果关系。PetriPetri网：网：PetriPetri网是由德国计算机科学家网是由德国计算机科学家PetriPetri提出的，提出的，由于它很好的模拟异步操作，所以在并行处理和分布式计由于它很好的模拟异步操作，所以在并行处理和分布式计算机领域中应用很多。算机领域中应用很多。2022/11/1824WeiChanghua 一一阶阶谓谓词词逻逻辑辑表表示示法法：谓谓词词逻逻辑辑适适合合于于表表示示事事物物的的状状态态、属属性性、概概念念等等事事物物之之间间的的知知识识，也也可可以以用用来来表表示示事物之间的因果关系，谓词公式一般用合适公式表示。事物之间的因果关系，谓词公式一般用合适公式表示。谓词的选取谓词的选取 量词的选取（作用的范围）量词的选取（作用的范围）从自然语言翻译成谓词公式不能丢失信息从自然语言翻译成谓词公式不能丢失信息 易于理解易于理解 谓谓词词公公式式表表示示法法的的特特点点：自自然然性性、精精确确性性、严严密密性、容易实现。性、容易实现。2022/11/1825WeiChanghua产生式表示法：产生式表示法：产生式表示具有因果关系的知识，其基本形式产生式表示具有因果关系的知识，其基本形式是是 或者或者 其中其中P P是产生式前提，是产生式前提，Q Q是一组结论或操作。是一组结论或操作。产生式组成：规则库，综合数据库，控制系统。产生式组成：规则库，综合数据库，控制系统。产生式系统分类：可交换的产生式系统，可分解的产生式产生式系统分类：可交换的产生式系统，可分解的产生式系统，可恢复的产生式系统系统，可恢复的产生式系统 产生式表示法的特点：自然性，有效性，模块性，清晰性，产生式表示法的特点：自然性，有效性，模块性，清晰性，效率不高，不能表示具有结构性的知识效率不高，不能表示具有结构性的知识 2022/11/1826WeiChanghua框架：框架：框架是一种描述所论对象（一个事物、一个事件、一框架是一种描述所论对象（一个事物、一个事件、一个概念）属性的数据结构。个概念）属性的数据结构。框架的框架的结结构构：一个框架是由若干槽：一个框架是由若干槽组组成，每个槽又可成，每个槽又可以有若干个以有若干个侧侧面。槽用来描述所面。槽用来描述所论对论对象的某方面的属性，象的某方面的属性，侧侧面用来描述相面用来描述相应应属性的一个方面。槽和属性的一个方面。槽和侧侧面所具有的属面所具有的属性性值值分分别别称称为为槽槽值值和和侧侧面面值值。框架网框架网络络：框架中的槽：框架中的槽值值或或侧侧面面值值可以是另一个框架可以是另一个框架的名字，的名字，这这就在框架之就在框架之间间建立了建立了联联系，构成了框架网系，构成了框架网络络。通通过过框架网框架网络络可以找到另一个框架。可以找到另一个框架。继继承性承性是框架表示法的一个重要特征。它不是框架表示法的一个重要特征。它不仅仅可以在可以在两两层层框架之框架之间实现继间实现继承关系，而且可以通承关系，而且可以通过过两两的两两的继继承关承关系，从最底系，从最底层层追溯到最高追溯到最高层层，使最高，使最高层层的信息逐的信息逐层层向底向底层层传递传递。框架中槽的设置与组织框架中槽的设置与组织：2022/11/1827WeiChanghua 充分表达事物个有关方面的属性充分表达事物个有关方面的属性 充分表达相关事物间的各种关系充分表达相关事物间的各种关系 ISAISA槽槽 AKOAKO槽槽 SubclassSubclass槽槽 InstanceInstance槽槽 PartofPartof槽槽 InferInfer槽槽 Possible-ReasonPossible-Reason槽槽 有利于进行框架的推理有利于进行框架的推理2022/11/1828WeiChanghua框架表示法的特点框架表示法的特点 结构性结构性 继承性继承性 自然性自然性 语语义义网网络络表表示示法法：语语义义网网络络是是通通过过概概念念及及其其语语义义关关系系表表达达知识的一种网络图。最简单的语义网络是如下的三元组：知识的一种网络图。最简单的语义网络是如下的三元组：（节点（节点1 1，弧，节点，弧，节点2 2）知识的语义网络表示知识的语义网络表示 用用语语义义网网络络表表示示有有关关事事实实间间的的关关系系：分分类类关关系系；聚聚集集关系；推论关系；时间、位置关系；多元关系关系；推论关系；时间、位置关系；多元关系 用用语语义义网网络络表表示示比比较较复复杂杂的的知知识识：把把一一个个复复杂杂的的知知识识命命题题划划分分为为若若干干个个子子命命题题，每每个个子子命命题题用用一一个个较较简简单单的的语语义网络表示，称为子空间，多个子空间构成一个大空间。义网络表示，称为子空间，多个子空间构成一个大空间。2022/11/1829WeiChanghua 常用的语义联系常用的语义联系 A-Member-ofA-Member-ofComposed-ofComposed-ofHaveHaveBefore,After,AtBefore,After,AtLocated-on(-at,-under,-inside,-outside)Located-on(-at,-under,-inside,-outside)等等 Similar-to,Near-toSimilar-to,Near-to 语义网络系统中求解问题的基本过程语义网络系统中求解问题的基本过程 用用语语义义网网络络表表示示知知识识的的问问题题求求解解系系统统称称为为语语义义网网络络系统。系统。系系统统由由语语义义网网络络构构成成的的知知识识库库；问问题题求求解解的的解解释释程程序（语义网络推理机）组成。序（语义网络推理机）组成。问题求解一般是通过匹配实现的。问题求解一般是通过匹配实现的。2022/11/1830WeiChanghua 语义网络表示法的特点结构性联想性自然性2022/11/1831WeiChanghua 脚脚 本本 表表 示示 法法：脚脚 本本 的的 知知 识识 表表 示示 方方 法法 是是R.C.SchankR.C.Schank 根根据据他他的的概概念念依依赖赖理理论论提提出出的的一一种种知知识识表表示示方方法法。它它与与框框架架类类似似，由由一一组组槽槽组组成成，用用来表示特定领域内一些事件的发生序列。来表示特定领域内一些事件的发生序列。概概念念依依赖赖理理论论：把把人人类类生生活活中中的的各各类类故故事事情情节节的的基基本本概概念念抽抽取取出出来来，构构成成一一组组原原子子概概念念，确确定定这这些些原原子子概概念念之之间间的的相相互互依依赖赖关关系系，然然后后把把所所有有故故事事情情节节都都用用这这组组原原子子概概念念及及其其依依赖赖关关系系表表示示出出来。来。脚脚本本一一般般由由以以下下几几部部分分组组成成：进进入入条条件件；角角色；道具；场景；结局。色；道具；场景；结局。2022/11/1832WeiChanghua 过过程程表表示示法法：过过程程性性表表示示方方法法着着重重于于对对知知识识的的利利用用，它它把把问问题题有有关关的的知知识识以以及及如如何何应应用用这这些些知知识识求求解解问问题题的的控控制制策策略略都都表表述述为为一一个个或或多多个个求求解解问问题题的的过过程程。每每一一个个过过程程是是一一个个程程序序，用用于于完完成成对一个具体事件或情况的处理。对一个具体事件或情况的处理。用过程规则表示过程用过程规则表示过程 过程规则的一般结构：过程规则的一般结构：激发条件激发条件 演绎操作演绎操作 状态转换状态转换 返回返回 过过程程表表示示法法的的特特点点：效效率率较较高高；控控制制系系统统容容易设计易设计2022/11/1833WeiChanghua PetriPetri网网表表示示法法：对对于于不不同同的的应应用用PetriPetri网网的的构构成成及及构构成成元元素素的的意意义义均均不不相相同同，但但有有三三种种元元素素是是基基本本的的：位位置置、转转换、标记。换、标记。PetriPetri网的特点网的特点 便于描述系统状态的变化便于描述系统状态的变化 便于对系统特点进行分析便于对系统特点进行分析 可可以以在在不不同同层层次次上上变变换换描描述述，而而不不必必注注意意细细节节几几相应的物理表示。相应的物理表示。面面向向对对象象表表示示法法：对对象象、类类、封封装装、继继承承是是面面向向对对象象技术的基本概念。技术的基本概念。在在面面向向对对象象方方法法中中，类类、子子类类、具具体体对对象象构构成成了了一一个个层层次次结结构构，而而且且子子类类可可以以继继承承父父类类的的数数据据和和操操作作。这种层次结构及继承机制直接支持了分类知识的表示。这种层次结构及继承机制直接支持了分类知识的表示。2022/11/1834WeiChanghua第三章第三章 知识表示知识表示思考题思考题思考题思考题 1 1 知识可以分为哪五类？知识可以分为哪五类？2 2 知识表示主要有那些方法？知识表示主要有那些方法？3 3 用一阶谓词逻辑表示下列的句子用一阶谓词逻辑表示下列的句子 （1 1）一一个个充充分分大大的的偶偶数数（eveneven）可可以以表表示示为为两两个个素素数数（primeprime）之和。之和。（2 2）对对于于任任意意集集合合，存存在在有有一一个个集集合合，使使得得集集合合的的基基大大于于集合的基。集合的基。（3 3）A A computer computer system system is is intelligent intelligent if if it it can can perform perform a a task task which,if performed by a human,requires intelligence.which,if performed by a human,requires intelligence.（4 4）并非所有的有理数（并非所有的有理数（rational numberrational number）都是整数。都是整数。（5 5）计计算算机机系系20012001级级的的男男生生（man man studentstudent）除除了了看看电电影影的的人外，其余的都去听学术报告（人外，其余的都去听学术报告（academic reportacademic report）了。了。2022/11/1835WeiChanghua33用语义网络表示下列句子用语义网络表示下列句子 （1 1）树和草都是植物；）树和草都是植物；（2 2）树和草都是有根有叶的；）树和草都是有根有叶的；（3 3）水草是草，且长在水中；）水草是草，且长在水中；（4 4）果树是树，且会结果；苹果树是果树中的一种，它结苹果。）果树是树，且会结果；苹果树是果树中的一种，它结苹果。（5 5）典型的哺乳动物有毛发。）典型的哺乳动物有毛发。（6 6）狗是哺乳动物，且吃肉。）狗是哺乳动物，且吃肉。4 4一个求职框架系统包含以下框架：一个求职框架系统包含以下框架：(Frame Frame 求职类求职类-A (Frame A (Frame 经理经理(Isa Isa 求职类求职类)(Isa Isa 招聘类招聘类)(学位学位 ValueValue：硕士以上硕士以上)）(年龄年龄 ValueValue：Always 30Always 30以下以下)(Frame Frame 李明李明 (学位学位 ValueValue：AlwaysAlways学士以上学士以上)(Isa Isa 求职类求职类-A)(Frame A)(Frame 销售经理销售经理 (年龄年龄 ValueValue：4040岁岁)()(Isa Isa 经理经理)(公关能力公关能力 ValueValue：高高)）(公关能力公关能力 ValueValue：高高)）请问李明有资格申请销售经理的职位吗？为什么？请问李明有资格申请销售经理的职位吗？为什么？2022/11/1836WeiChanghua55试用框架结构表示一个大学的人事组织结构。试用框架结构表示一个大学的人事组织结构。6 6 产生式系统由那些部分组成？它们的作用是什么？产生式系统由那些部分组成？它们的作用是什么？7 7 为为什什么么说说框框架架系系统统和和语语义义网网络络都都是是结结构构化化的的知知识识表表示示方方法法？两两者的共同和不同之处是什么？者的共同和不同之处是什么？8 8 有有3 3个个积积木木块块（A A、B B、C C）放放在在桌桌子子上上，且且可可以以叠叠放放在在一一起起，要要求求在在任任意意初初始始状状态态，按按自自上上而而下下A A、B B、C C的的顺顺序序迭迭放放这这3 3个个积积木木块块。搬搬动积木块应遵循以下约束：动积木块应遵循以下约束：（1 1）每次只能搬一块每次只能搬一块 （2 2）只有顶空的积木块才能搬动只有顶空的积木块才能搬动 请请为为机机器器人人搬搬动动积积木木块块设设计计一一个个产产生生式式系系统统，包包括括综综合合数数据据库库、规则库和冲突消解算法。规则库和冲突消解算法。2022/11/1837WeiChanghua第四章 基本的问题求解方法基本的问题求解方法 1 1 基本概念基本概念 什么是搜索什么是搜索人人工工智智能能要要解解决决的的问问题题大大多多数数是是结结构构不不良良或或者者非非结结构构的的问问题题，对对这这样样的的问问题题一一般般不不存存在在成成熟熟的的求求解解算算法法，而而只只能能利利用用已已有有的的知知识识一一步步步步地地摸摸索索着着前前进进。在在这这个个过过程程中中，存存在在着着如如何何寻寻找找一一条条推推理理路路线线，使使得得付付出出的的代代价价尽尽可可能能地地少少，而而问问题题又又能能够够得得到到解解决决。我我们们称寻找这样路线的过程为搜索。称寻找这样路线的过程为搜索。搜搜索索分分为为盲盲目目搜搜索索和和启启发发式式搜搜索索：盲盲目目搜搜索索是是按按预预定定的的控控制制策策略略进进行行，在在搜搜索索的的过过程程中中所所获获得得的的信信息息不不用用来来改改进进控控制制策策略略的的一一种种搜搜索索。启启发发式式搜搜索索是是在在搜搜索索中中加加入入了了与与问问题题有有关关的的启启发发式式信信息息，用用来来指指导导搜搜索索朝朝着着最最有有希希望望的的方方向向前前进进，加加速速问问题题的的求求解解过过程程，并并找到最优解。找到最优解。2022/11/1838WeiChanghua 状状态态空空间间表表示示法法：状状态态空空间间表表示示法法是是用用“状状态态”和和“算算符符”来来表表示问题的一种方法。示问题的一种方法。状态：状态是描述问题求解过程中任一时刻状况的数据结构。状态：状态是描述问题求解过程中任一时刻状况的数据结构。算算符符：引引起起状状态态的的某某些些分分量量变变化化，从从而而使使问问题题从从一一个个状状态态变变为为另一个状态的操作称为算符。另一个状态的操作称为算符。状状态态空空间间：问问题题的的全全部部状状态态和和一一切切算算符符所所构构成成的的集集合合成成为为状状态态空间。空间。例如例如 二阶梵塔问题。二阶梵塔问题。解：设立柱解：设立柱 1 1、2 2和和3 3以及两个圆盘以及两个圆盘A A和和B B 。用用S Sk k=(S=(Sk0k0,S,Sk1k1)表示问题状态，表示问题状态，S Sk0k0表示圆盘表示圆盘A A所在的立柱，所在的立柱，S Sk1k1表示圆盘表示圆盘B B所在的立柱，全部可能的状所在的立柱，全部可能的状态共有九种：态共有九种：S S0 0=(1=(1，1)1)，S S1 1=(1=(1，2)2)，S S2 2=(1=(1，3)3)S S3 3=(2=(2，1)1)，S S4 4=(2=(2，2)2)，S S5 5=(2=(2，3)3)S S6 6=(3=(3，1)1)，S S7 7=(3=(3，2)2)，S S8 8=(3=(3，3)3)问题的初始状态集合是问题的初始状态集合是S=SS=S0 0，目标状态集合是目标状态集合是G=SG=S4 4，S S8 8。2022/11/1839WeiChanghuaS S0 0=（1 1，1 1）S S1 1=（1 1，2 2）S S2 2=（1 1，3 3）S S3 3=（2 2，1 1）S S4 4=（2 2，2 2）S S5 5=（2 2，3 3）S S6 6=（3 3，1 1）S S7 7=（3 3，2 2）S S8 8=（3 3，3 3）二阶梵塔问题状态表示二阶梵塔问题状态表示2022/11/1840WeiChanghua 与与/或或树树表表示示法法：对对于于一一个个复复杂杂的的问问题题，可可以以通通过过“分分解解”和和“等等价变换价变换”两种手段相结合使用，得到一个图，这个图就是与两种手段相结合使用，得到一个图，这个图就是与/或图。或图。等价变换：等价变换：是一种同构或同态的变换。是一种同构或同态的变换。本本原原问问题题：不不能能再再分分解解或或变变换换，而而且且直直接接可可以以求求解解的的子子问问题题，称为本原问题。称为本原问题。终终端端节节点点与与终终止止节节点点：在在一一棵棵与与/或或树树中中，没没有有子子节节点点的的节节点点称为终端节点；本原问题所对应的节点称为终止节点。称为终端节点；本原问题所对应的节点称为终止节点。可可解解节节点点：在在与与/或或树树中中，满满足足下下列列条条件件之之一一者者就就称称为为可可解节点：解节点：它是一个终止节点它是一个终止节点 它它是是一一个个“或或”节节点点，且且其其子子节节点点中中至至少少有有一一个个是是可可解解节节点点 它是一个它是一个“与与”节点，且其子节点全部是可解节点节点，且其子节点全部是可解节点 不不可可解解节节点点：关关于于可可解解节节点点的的三三个个条条件件全全部部不不满满足足的的节节点点称称为不可解节点。为不可解节点。解树：解树：由可解节点构成，且由这些可解节点可推出初始节点由可解节点构成，且由这些可解节点可推出初始节点（它对应于原始问题）为可解节点的子树称为解树。（它对应于原始问题）为可解节点的子树称为解树。2022/11/1841WeiChanghua2 2 状态空间搜索状态空间搜索 状态空间搜索的一般过程状态空间搜索的一般过程 OPENOPEN表表 和和 CLOSEDCLOSED表表：OPENOPEN表表 是是 用用 于于 存存 放放 刚刚 生生 成成 的的 节节 点点；CLOSEDCLOSED表用于存放将要扩展的节点。表用于存放将要扩展的节点。搜索的一般过程搜索的一般过程 广广度度优优先先搜搜索索：从从初初始始节节点点S S0 0开开始始，逐逐层层地地对对节节点点进进行行扩扩展展并并考考查查它它是是否否为为目目标标节节点点。在在第第n n层层的的节节点点没没有有全全部部扩扩展展并并考考查查之之前前，不不对对第第 n+1n+1层层节节点点进进行行扩扩展展。OPENOPEN表表中中的的节节点点总总是是按按进进入入的的先先后后顺顺序序排排列列，先先进进入入的的节节点排在前面，后进入的节点在后。点排在前面，后进入的节点在后。深深度度优优先先搜搜索索：从从初初始始节节点点S S0 0开开始始，在在其其子子节节点点中中选选择择一一个个子子节节点点进进行行考考查查，若若不不是是目目标标节节点点，则则再再在在该该子子节节点点中中选选择择一一个个子子节节点点进进行行考考查查，一一直直如如此此向向下下搜搜索索。当当到到达达某某个个子子节节点点，且且该该子子节节点点既既不不是是目目标标节节点点又又不不能能继继续扩展时，才选择其兄弟节点进行考察。续扩展时，才选择其兄弟节点进行考察。与与广广度度优优先先搜搜索索不不同同，深深度度优优先先搜搜索索是是把把节节点点n n的的子子节节点点放放入入OPENOPEN表的首部。表的首部。2022/11/1842WeiChanghua 有有界界的的深深度度优优先先：对对深深度度优优先先搜搜索索引引入入搜搜索索深深度度的的界界限限，当当搜搜索索深深度度达达到到了了深深度度界界限限，而而尚尚未未出现目标节点，就换一个分支进行搜索。出现目标节点，就换一个分支进行搜索。代代价价树树的的广广度度优优先先搜搜索索：与与/或或树树中中，边边上上有有代代价（或费用）的树称为代价树。价（或费用）的树称为代价树。代代价价树树的的广广度度优优先先搜搜索索的的基基本本思思想想是是每每次次从从OPENOPEN表表中中选选择择节节点点往往CLOSEDCLOSED表表中中传传送送时时，总总是是选选择择其其代价最小的节点。代价最小的节点。代代价价树树的的深深度度优优先先搜搜索索：基基本本思思想想是是从从刚刚扩扩展展的的 子子 节节 点点 中中 选选 择择 一一 个个 代代 价价 最最 小小 的的 节节 点点 送送 入入CLOSEDCLOSED表进行考查。表进行考查。2022/11/1843WeiChanghua 启启发发式式搜搜索索：启启发发式式搜搜索索是是利利用用问问题题本本身身的的某某些些启启发发信信息，以制导搜索朝着最有希望的方向前进。息，以制导搜索朝着最有希望的方向前进。估估价价函函数数：用用于于估估价价节节点点重重要要性性的的函函数数称称为为估估价价函数。它的一般形式为函数。它的一般形式为 局局部部择择优优搜搜索索：当当一一个个节节点点被被扩扩