环境决策支持系统技术基础之三

1、环境决策支持系统技术基础之三模型与知识北京大学环境工程系2007年4月交通导航辅助决策系统n数据库基础信息、路网信息、公交系统信息、历史路况信息、路况实时信息n方法库最短路径算法、空间Buffer方法等n模型库针对不等交通方式的交通方案生成与评估模型等交通导航辅助决策系统与模型模型:提供方案生成和选择的功能模型与模型库系统决策对模型管理系统的要求 n模型库技术要求为存储量小，组合方案多。与建模者的素质要求相矛盾。n决策问题难以预见性，不可能预建完整的模型。建模过程与决策过程相伴随。n建模支持的目标：使决策者成为建模者。n建模支持的方法：通过对模型的有序管理和对决策者的训练和启发，将其领域知识转

2、变为模型。模型分类及其描述方法 n 模型是客观事物在建模者主观认识上的反映。从建模支持的角度看模型的分类。管理形式基本模型启发存储空间特征关系建模以多维基本特征坐标构成形式空间，进行模型分类管理。以基本特征形成模型间的关系纽带，进行建模启发。 模型基本特征客观变量离散连续运动静态动态主观视角宏观微观认识定性定量模型分类及其描述方法 n特征变量可分为：定类、定量、结构化图序集。n其中定类变量为无序变量，定量变量为全序变量，结构化图序变量可分有序与无序。 例：图形 有 细 多边形 卵形 序 化 三角形四边形 圆 椭圆 正三角 直三角 矩形 棱形 无序 有序关系形成粗化与细化的启发，无序关系形成类比

3、启发。宏观与微观，定性与定量均是粗、细化关系。 模型的粗（细）化变换 n有序关系形成粗化与细化的启发，无序关系形成类比启发。宏观与微观，定性与定量均是粗、细化关系。n粗化归纳推理过程。n细化演绎推理过程。建模方法n建模的理想方法：分析问题概念集（论域）内的全部元素的变化规律，及它们之间的关系，并描述之。n建模的实用方法：分析问题的若干典型元素 假设（默认）模型（建模启发） 更新模型。 n启发式建模方法：模型由若干算子（元模型）组合而成，算子的可用条件为P（前提）。 启发规则：IF 现问题状态结构与P相匹配，THEN 应用算子OP，并将其变量限于B（定义域）。 反例建模方法n启发最终成立的判断准

4、则：可否达到最终目标n对问题求解器的一般化讨论 ：模型是对复杂对象的简化描述，简化必存在前提条件，即作假设前提的匹配；在满足前提的情况下进行模型搜索选择，即作输出输入的匹配。输出输入匹配过程可有下述情况： 建模方法输出输入匹配过程可有下述情况： 模型方案选择-不确定证据处理 模型库子系统（1） n现实数据表示的是过去已经发生了的事实，因此数据必然是面向历史的。我们利用各种模型，就可以把面向过去的数据变换成面向现在或者将来的有意义的信息。在DSS中，决策支持模型体现了管理者解决问题的途径，所以随着管理者对问题认识程度的深化，他们所使用的模型也必然会跟着产生相应的变化。模型库子系统应能够灵活地完成

5、模型的存储和管理功能。n模型库子系统包括模型库（MB）和模型库管理系统（MBMS），它是决策支持系统的核心，是最重要的也是较难实现的部分。n模型库管理系统管理的模型有两类：一类是标准模型（如规划模型、网络模型等），这些模型按照某些常用的程序设计语言编程，并存在库中。n另一类是由用户应用建模语言而建立的模型，即使是标准模型也有个再开发的过程模型库子系统（2）n模型不同于数据，模型库也不同于数据库。如何表示模型，如何组织模型库，模型库管理系统的功能要求有哪些，这些问题是决策支持系统开发的关键。目前尚未出现成熟的商品软件，也没有关于模型库系统的统一标准，模型库系统的开发是由研制者自行完成的。n模型种

6、类很多，有数学模型、数据处理模型、智能模型、图形模型、图像模型等。数学模型可以用数学方程形式表达，也可以用算法形式描述。数据处理模型一般用数据处理过程来说明。它们在计算机中均以计算机程序的形式表示。而图形、图像模型等在计算机中都是以数据文件形式表示。模型库既包含数据文件，又包含程序文件，需要设计统一的格式进行存储，以便使模型库管理系统对它们进行有效的管理。n模型库管理系统可以参照数据库管理系统的功能，如库的建立、模型的查询、增加、删除、修改等。由于模型比数据复杂，模型库比数据库复杂得多，模型库管理系统的功能相应地也复杂许多。n数据库管理系统是通过数据库语言来完成各项管理功能，模型库管理系统同样

7、需要设计一套语言来完成模型库的各项管理功能，模型库语言比数据库语言复杂。模型库子系统（3）n模型库管理系统支持决策问题的定义和概念模型化、维护模型，包括联结、修改、增删等。n模型库子系统与对话子系统的交互作用，可使用户控制对模型的操作、处置和使用；n它与数据库子系统交互作用，以便提供各种模型所需的数据，实现模型输入、输出和中间结果存取自动化；n它与方法库子系统交互作用，实行目标搜索、灵敏度分析和仿真运行自动化等。n模型库子系统的主要作用是通过人机交互语言使决策者能方便利用模型库中各种模型支持决策，引导决策者应用建模语言和自己熟悉的专业语言建立、修改和运行模型。环境模型规范化 n环境方面的各种模

8、型在EDSS中起到极为重要的作用，因此，充分、高效利用模型库中的模型就显得尤为重要。为了实现对模型库中诸模型实体及描述信息的统一、规范化管理，避免模型库中的模型相互重复、使用率不高和难于共享的缺点，就必须模型标准化，使环境影响评价中的各种模型有统一的格式、表达方式、结构和要求。 模型库及其管理系统 n模型库是模型模块的集合。每一个模块具有单独的功能，也可能与其它模块组合成一个较大的模块。nEDSS采用可二级框架结构来描述每一个模型，n第一层框架结构主要描述模型的外部特征，包括模型名、类型、用途、可执行文件名、模型的实体参数，如输入项、输出项、约束条件等，n第二层框架结构主要描述模型的运行环境，

9、包括输入、输出数据文件的类型以及是否需要预处理，模型主体以可执行文件的形式存在于文件中。n模型库管理功能包括模型库维护、模型操纵和模型结果显示等功能。模型n模型是客观系统在人们头脑中的简化描述，是对问题领域中的实际问题的抽象。它的信息表示形式可以是一组相互关联的数据，或者是表达式、方程组、规则、关系、程序模块。模型 n数值模型的形成是随计算机模拟技术的发展而来的。计算机模拟是将一个子程序进程视为模型，设置模型的各种参数变量，通过运行模型来观察模型的各种行为。随着计算机模拟技术的深入应用，形成了模拟系统。模拟系统是用来处理模型集合的软件系统，提供通用的数据输入和报表格式。模型的建立在整个模拟系统

10、研制中所投入的精力占的比重过大，模型相互重复、使用率不高的现象比较严重。在很多情况下，模型都是被作为应用程序的组成部分，嵌入应用程序，在这种管理下的模型，其共享性和灵活性较差。模型库及其管理系统 n随着应用模型的需求量不断增大，为了更有效地管理和使用模型，提出了模型库系统的概念。关于模型的管理经历了以下三个发展阶段：n第一阶段：模型数据n第二阶段：数据库系统模型软件包n第三阶段：模型库系统数据库系统模型库及其管理系统 n第一阶段的特点是模型和数据无公用性，使模型的应用受到很大限制；n第二阶段以数据库系统的引入为特点，但缺乏对大批模型的有效管理，不利于用户选择自己需要的模型；n第三阶段实现了数据

11、库和模型库两者之间的通讯，减少了模型存储的冗余度，为模型的操纵提供了良好的环境，使模型应用的灵活性大大加强。模型库及其管理系统 n通常认为模型库系统是由模型构件库、应用模型库、模型库管理系统及综合环境这四部分组成。 模型构件库 应用模型库 模型库管理系统 综合环境 构模工具 模型库及其管理系统 n模型构件库存贮通用的、规范的、可重用的、标准化的“原子”模型；n应用模型则是用户自己开发的、针对某些具体问题的模型集。它由代码库、源库、模型属性库以及应用模型库索引四部分组成，其中代码库和源库属于子程序级的文本库，前者存贮模型的执行代码，后者存贮模型的源代码，考虑到应用模型的复杂性和可执行代码和源代码

12、在操作系统中均以文件方式管理的特点，故代码库和源库均可以以软件包形式管理，以便充分利用操作系统的文件管理功能，n属性库和库索引文件则引入关系的概念，将模型属性及库说明以关系方式存于各自的库中，通过对属性库和索引库的操作进入相应代码库中的相应地址，从而可执行所选的模型，应用模型库中的层次结构见图。模型库及其管理系统 应用模型库模型目录文件模型描述文件模型帮助文件模型源文件库模型目标文件库模型库及其管理系统 n模型库管理系统是管理、维护和操纵模型构件库和应用模型库两库的软件集。它们集成于综合环境之内，以提供友好的用户界面；n综合环境是模型库系统的运行环境，由模型库管理系统和构模工具等组成，是模型库

13、系统的用户界面。模型库系统的功能应具备下列功能 。n（1）辅助规划与决策。n（2）构造新模型。根据用户自己的目标制定分目标，利用构模工具和模型构件库构造用户自己的模型。n（3）模型库的维护。 模型的管理 n（一）关系方法：当今模型管理的一个主要特征是借用数据库管理的理论和方法，将其扩展到模型管理；一个模型库管理系统首先必须具有类似于数据库管理系统的功能。R. W. Blanning提出了模型管理的关系方法。它不将模型视为一计算过程，而是视为一个关系，其属性分别为输入、输出变量。关系作为模型的一种表示方法，特别是作为用户视图中的模型，可大大地方便非专业用户；而且由于它和关系数据库的表示方法一致，

14、人们可集中管理数据和模型。关系方法提供了一个一致的用户使用界面。 模型的管理n（二）E-R方法：R.W.Blanning继提出了模型管理的关系方法后，又将数据库中的E-R方法加以扩展，将模型及其存贮的数据视为互补资源，利用E-R方法共同管理。与关系方法不同，E-R方法提供了一种全局视图。E-R方法中，以实体集表示客观世界的实体集合，有关它们的数据保存于文件中，一个实体集对应于一个文件；实体类表示物理客体或相对于模型的过程，更明确地说，实体集与文件对应，实体类与模型对应。E-R方法提供了一个良好的全局视图。模型的管理n（三）抽象表示方法：模型抽象类似于程序设计语言中的数据抽象，它包括客体、过程和

15、断言三个部分。数据客体部分列出构成模型的所有数据项及其类型，类型本身可以是另一个抽象表示；过程部分列出每一个过程、它所访问的数据、返回的结果；断言部分表示有关数据客体、过程及其相互关系的一些信息。数据项、数据类型、过程及断言均采用谓词形式。抽象表示方法提供了一个良好的全局视图 。模型的管理n（四）视数据为模型：将数据视为模型，这样做不仅扩大了模型管理的范畴，也为模型管理提供了一个更一致的概念基础。组织上，将模型从软件包的形式化模拟转换到将模型作为一个与数据相关联的信息资源来管理，引入信息管理员的概念；技术上，有一个一般化的模型库管理系统来支持组织模拟活动。将数据视为模型的确扩大了模型管理的范畴

16、。将数据视为模型为实现数据和模型的一致管理提供了良好的途径 。模型库中模型的构造 新模型词法分析语法分析语义分析中间代码生成代码生成目标程序（可执行代码）各种信息表的管理错误诊断及处理程序的流向信息的流向分析综合编译程序模型库功能简述 模型库管理系统用 户 或 决策者系统员模型查找模型信息查询修改模型删除模型增加模型删除模型库创建模型库模型运行yunxing模型库功能n1、模型查找：用户或决策者给出要查找的模型名，系统自动找出该模型所属的数据库，进而可以查找该模型的相关信息。用户或决策者可以进行匹配查询，输入不完整的模型名，系统也能找到与不完整的模型名相匹配的相关模型的相关信息。模型库功能n2

17、、模型运行：用户或决策者选择合适的模型后，进行参数选择和参数值的确定，从数据库和标准库中读出合适的数据转存为文本文件（如果数据库中存在无实测值、无资料等情况时，系统能进行插值或由用户或决策者临时确定该值，然后转储为文本文件。可以这样认为：文本文件中的数据是经过处理后得到的完整的、正确的、模型运行所需的数据。），运行模型时，从文本文件中得到数据从而得到模型的计算结果。模型的计算结果既可以用表表示，也可以用图表示。模型库功能n3、模型信息查询：用户、决策者和其它人员对某个模型的有关描述信息进行查询；n4、修改模型：系统员对模型的模型体的修改和模型描述信息的修改。不管是修改模型体还是模型描述信息都是

18、删除旧的内容和增加新的内容；n5、删除模型：从指定的模型库中删除一个模型。在EDSS中，这种删除只是逻辑上的删除，模型体及模型描述仍留在库中； 模型库功能n6、增加模型：系统员向指定的模型库中增加一个模型。包括模型体和模型描述的入库；n7、创建模型库：系统员建立一个新的模型库，这里是指建立用户自己的模型库；n8、删除模型库：系统员把用户认为已经无用的模型库删除。模型库文件操作功能 模型库管理系统 模型库系统的模型操作 模型库之难点 n模型构件库的最大困难是创建一种强有力的模型构造语言和模型描述语言；n其次，在编译新模型的过程中，怎样减少用数学或逻辑等表示的模型转换为计算机内部的二进制表示时的信

19、息损失；n最后，必须根据模型构造语言和模型描述语言的定义，构造一个功能强大的编辑器，同时，这个编辑器应嵌入到模型构件库中。 知识表示与专家系统智能支持 n为实现决策支持，提供有效的、主动的支持信息，系统必须具备一定的智能性功能，即系统能存储人们在处理同类问题时的经验，在遇到此类问题时运用所存的知识提供服务。如何把人的经验以知识的形式表达，使其便于存储和应用是关键。 人人机机接接口口知识获取知识获取推理机推理机解释机解释机知识库知识库事实库事实库专家系统的基本结构专家系统的基本结构 知识表示是基础知识表示是基础 搜索技术是核心搜索技术是核心 专家系统是目标专家系统是目标 各部分间的关系各部分间的

20、关系 1 什么是人工智能？ 人工智能是研究知识的一门科学，即如何表示知识，如何获取知识和如何利用知识的科学。 2 人工智能研究的目标近期目标：在近期，人工智能研究的任务是利用冯.偌依曼型计算机模拟人类智力行为，研制智能程序；远期目标：远期是研制全新的计算机，即智能计算机。知识表示知识表示1 知识与知识表示知识是人类认识自然界的精神产物，是人类进行智能活动的基础。知识可以分为五类： 描述性知识 判断性知识 过程性知识 对象级知识，或称为领域相关的知识 元级知识 2 对知识表示的要求 表示能力 可理解性 可访问性 可扩展性 3 知识表示方法 一阶谓词逻辑：它是一种描述性的表示方法，它的推理机制是归

21、结原理。主要应用于定理证明。 语义网络：是由Quillian等人于1968年提出的，它在知识表示中可以表示对象、概念及其相互间的关系。它广泛用于基于知识的系统。 产生式规则：产生式系统把知识表示成“模式动作”对，表示方式自然、简洁。它的推理机制以演绎为基础。它是专家系统的知识表示的主要方法。 框架：框架理论是Minsky于1974年提出的，它将知识表示成高度模块的结构，它是把关于一个概念或对象的所有信息和知识都存储在一起的数据结构。框架的层次结构可以表示对象之间的相互关系，用框架表示知识的系统称为框架的系统。 状态空间：状态空间表示法把求解问题表示成问题状态、操作、约束、初始状态和目标状态。状

22、态空间是所有状态的集合。 脚本：脚本也称为剧本。它是用来描述固定事件序列，它的结构类似于框架。剧本更强调事件间的因果关系。 Petri网：Petri网是由德国计算机科学家Petri提出的，由于它很好的模拟异步操作，所以在并行处理和分布式计算机领域中应用很多。 一阶谓词逻辑表示法：谓词逻辑适合于表示事物的状态、属性、概念等事物之间的知识，也可以用来表示事物之间的因果关系，谓词公式一般用合适公式表示。 谓词的选取 量词的选取（作用的范围） 从自然语言翻译成谓词公式不能丢失信息 易于理解 谓词公式表示法的特点：自然性、精确性、严密性、容易实现。 产生式表示法：产生式表示具有因果关系的知识，其基本形式

23、是 或者 其中P是产生式前提，Q是一组结论或操作。 产生式组成：规则库，综合数据库，控制系统。 产生式系统分类：可交换的产生式系统，可分解的产生式系统，可恢复的产生式系统 产生式表示法的特点：自然性，有效性，模块性，清晰性，效率不高，不能表示具有结构性的知识 QP QTHENPIFn知识表示的目的知识表示的目的 使用知识。它是问题求解和专家系统的基础。n知识表示遵循的思路知识表示遵循的思路产生式规则产生式规则 与或图与或图 状态空间状态空间等等 人工智能语言人工智能语言 （如（如Prolog语言）语言） 通用程序设计语言通用程序设计语言（如（如C、C+）自然语言表示自然语言表示 格式化表示格式

24、化表示 计算机语言表示计算机语言表示难点分析难点分析 如果有毛发或者产奶，那么它是哺育动物；如果有毛发或者产奶，那么它是哺育动物； 如果吃肉，那么它是食肉动物；如果吃肉，那么它是食肉动物； 如果有犬齿、有爪、眼视前方，那么它是食肉动物；如果有犬齿、有爪、眼视前方，那么它是食肉动物； 如果是哺育动物、食肉动物、黄褐色、有黑色条纹，如果是哺育动物、食肉动物、黄褐色、有黑色条纹，那么它是老虎。那么它是老虎。自然语言描述知识自然语言描述知识 if 有毛发或者产奶有毛发或者产奶 then 它是哺育动物；它是哺育动物； if 吃肉吃肉 then 它是食肉动物；它是食肉动物； if 有犬齿，且有爪，且眼视前

25、方有犬齿，且有爪，且眼视前方 then 它是食肉动物；它是食肉动物； if 是哺育动物，且是食肉动物，且是黄褐色，且有黑是哺育动物，且是食肉动物，且是黄褐色，且有黑色条纹色条纹 then 它是老虎。它是老虎。产生式规则表示知识产生式规则表示知识产生式规则的基本形式：产生式规则的基本形式：If P then Q或者或者PQ老虎老虎黄褐色黄褐色黑色条纹黑色条纹食肉动物食肉动物吃肉吃肉有犬牙有犬牙有爪有爪眼睛向前眼睛向前哺育动物哺育动物产奶产奶有毛发有毛发产生式规则表示知识的网络产生式规则表示知识的网络框架：框架是一种描述所论对象（一个事物、一个事件、一个概念）属性的数据结构。 框架的结构：一个框架

26、是由若干槽组成，每个槽又可以有若干个侧面。槽用来描述所论对象的某方面的属性，侧面用来描述相应属性的一个方面。槽和侧面所具有的属性值分别称为槽值和侧面值。 框架网络：框架中的槽值或侧面值可以是另一个框架的名字，这就在框架之间建立了联系，构成了框架网络。通过框架网络可以找到另一个框架。 继承性是框架表示法的一个重要特征。它不仅可以在两层框架之间实现继承关系，而且可以通过两两的继承关系，从最底层追溯到最高层，使最高层的信息逐层向底层传递。 框架中槽的设置与组织： 充分表达事物个有关方面的属性 充分表达相关事物间的各种关系 ISA槽 AKO槽 Subclass槽 Instance槽 Part of槽

27、Infer槽 Possible-Reason槽 有利于进行框架的推理框架表示法的特点 结构性 继承性 自然性 语义网络表示法：语义网络是通过概念及其语义关系表达知识的一种网络图。最简单的语义网络是如下的三元组： （节点1，弧，节点2） 知识的语义网络表示 用语义网络表示有关事实间的关系：分类关系；聚集关系；推论关系；时间、位置关系；多元关系 用语义网络表示比较复杂的知识：把一个复杂的知识命题划分为若干个子命题，每个子命题用一个较简单的语义网络表示，称为子空间，多个子空间构成一个大空间。 常用的语义联系 A-Member-of Composed-of Have Before,After,At L

28、ocated-on(-at,-under,-inside,-outside)等 Similar-to, Near-to 语义网络系统中求解问题的基本过程 用语义网络表示知识的问题求解系统称为语义网络系统。 系统由语义网络构成的知识库；问题求解的解释程序（语义网络推理机）组成。 问题求解一般是通过匹配实现的。 语义网络表示法的特点 结构性 联想性 自然性 脚 本 表 示 法 ： 脚 本 的 知 识 表 示 方 法 是R.C.Schank 根据他的概念依赖理论提出的一种知识表示方法。它与框架类似，由一组槽组成，用来表示特定领域内一些事件的发生序列。 概念依赖理论：把人类生活中的各类故事情节的基本概

29、念抽取出来，构成一组原子概念，确定这些原子概念之间的相互依赖关系，然后把所有故事情节都用这组原子概念及其依赖关系表示出来。 脚本一般由以下几部分组成：进入条件；角色；道具；场景；结局。 过程表示法：过程性表示方法着重于对知识的利用，它把问题有关的知识以及如何应用这些知识求解问题的控制策略都表述为一个或多个求解问题的过程。每一个过程是一个程序，用于完成对一个具体事件或情况的处理。 用过程规则表示过程 过程规则的一般结构： 激发条件 演绎操作 状态转换 返回 过程表示法的特点：效率较高；控制系统容易设计 Petri网表示法：对于不同的应用Petri网的构成及构成元素的意义均不相同，但有三种元素是基

30、本的：位置、转换、标记。 Petri网的特点 便于描述系统状态的变化 便于对系统特点进行分析 可以在不同层次上变换描述，而不必注意细节几相应的物理表示。 面向对象表示法：对象、类、封装、继承是面向对象技术的基本概念。 在面向对象方法中，类、子类、具体对象构成了一个层次结构，而且子类可以继承父类的数据和操作。这种层次结构及继承机制直接支持了分类知识的表示。问题求解方法问题求解方法 1 基本概念 什么是搜索人工智能要解决的问题大多数是结构不良或者非结构的问题，对这样的问题一般不存在成熟的求解算法，而只能利用已有的知识一步步地摸索着前进。在这个过程中，存在着如何寻找一条推理路线，使得付出的代价尽可能

31、地少，而问题又能够得到解决。我们称寻找这样路线的过程为搜索。搜索分为盲目搜索和启发式搜索：盲目搜索是按预定的控制策略进行，在搜索的过程中所获得的信息不用来改进控制策略的一种搜索。启发式搜索是在搜索中加入了与问题有关的启发式信息，用来指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解。 状态空间表示法：状态空间表示法是用“状态”和“算符”来表示问题的一种方法。 状态：状态是描述问题求解过程中任一时刻状况的数据结构。 算符：引起状态的某些分量变化，从而使问题从一个状态变为另一个状态的操作称为算符。 状态空间：问题的全部状态和一切算符所构成的集合成为状态空间。 例如 二阶梵塔问题。解：

32、设立柱 1、2和3以及两个圆盘A和B 。用Sk=( Sk0, Sk1)表示问题状态，Sk0表示圆盘A所在的立柱，Sk1表示圆盘B所在的立柱，全部可能的状态共有九种： S0=( 1，1)， S1=( 1，2)， S2=( 1，3) S3=( 2，1)， S4=( 2，2)， S5=( 2，3) S6=( 3，1)， S7=( 3，2)， S8=( 3，3) 问题的初始状态集合是S=S0，目标状态集合是G=S4，S8。 与/或树表示法：对于一个复杂的问题，可以通过“分解”和“等价变换”两种手段相结合使用，得到一个图，这个图就是与/或图。 等价变换：是一种同构或同态的变换。 本原问题：不能再分解或变

33、换，而且直接可以求解的子问题，称为本原问题。 终端节点与终止节点：在一棵与/或树中，没有子节点的节点称为终端节点；本原问题所对应的节点称为终止节点。 可解节点：在与/或树中，满足下列条件之一者就称为可解节点： 它是一个终止节点 它是一个“或”节点，且其子节点中至少有一个是可解节点 它是一个“与”节点，且其子节点全部是可解节点 不可解节点：关于可解节点的三个条件全部不满足的节点称为不可解节点。 解树：由可解节点构成，且由这些可解节点可推出初始节点（它对应于原始问题）为可解节点的子树称为解树。 2 状态空间搜索 状态空间搜索的一般过程 OPEN表和CLOSED表：OPEN表是用于存放刚生成的节点；

34、CLOSED表用于存放将要扩展的节点。 搜索的一般过程 广度优先搜索：从初始节点S0开始，逐层地对节点进行扩展并考查它是否为目标节点。在第n 层的节点没有全部扩展并考查之前，不对第 n+1层节点进行扩展。OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的节点在后。 深度优先搜索：从初始节点S0开始，在其子节点中选择一个子节点进行考查，若不是目标节点，则再在该子节点中选择一个子节点进行考查，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。 与广度优先搜索不同，深度优先搜索是把节点n的子节点放入OPEN表的首部。 有界

35、的深度优先：对深度优先搜索引入搜索深度的界限，当搜索深度达到了深度界限，而尚未出现目标节点，就换一个分支进行搜索。 代价树的广度优先搜索：与/或树中，边上有代价（或费用）的树称为代价树。代价树的广度优先搜索的基本思想是每次从OPEN表中选择节点往CLOSED表中传送时，总是选择其代价最小的节点。 代价树的深度优先搜索：基本思想是从刚扩展的子节点中选择一个代价最小的节点送入CLOSED表进行考查。 启发式搜索：启发式搜索是利用问题本身的某些启发信息，以制导搜索朝着最有希望的方向前进。 估价函数：用于估价节点重要性的函数称为估价函数。它的一般形式为 局部择优搜索：当一个节点被扩展后，按f(x)对每

36、个子节点计算估价值，并选择最小者作为下一个要考查的节点。由于它每次都只是在子节点的范围中选择要考查的子节点，所以称为局部择优搜索。 全局择优搜索：每次都是从OPEN表的全体节点中选择一个估价值最小的节点进行扩展。)()()(xhxgxf 算法：把OPEN表中的节点按估价函数的值从小到大进行排序；g(x)是对g*(x)的估计，g(x)0；h(x)是h*(x)的下界，即对所有x的均有： 。其中g*(x)是从初始节点S0到节点x的最小代价； g*(x)是从x节点到目标节点的最小代价，若多个目标节点，则为其中的一个。*A)()(*xhxh3 与/或树搜索 与/或树搜索的一般过程 与/或树搜索的广度优先

37、搜索 与/或树搜索的深度优先搜索 与/或树搜索的有序搜索4 博弈树的启发式搜索 博弈树的概念：博弈树是与/或树的一个特例；博弈的初始格局是初始节点；在博弈树中与节点和或节点总是逐层交替出现的；所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点。所有使对方获胜的终局都是不可解节点。 极大极小法 -剪枝技术 值：对于一个或节点来说，取当前子节点中的最大倒推值作为它倒推值的下界，称此值为值。 值：对于一个与节点来说，取当前子节点中的最小倒推值作为它倒推值的上界，称此值为值。 -剪枝技术：任何或节点x的值如果不能降低其父辈节点的值，则对节点x以下的分支可停止搜索，并使的倒推值为 ，这种剪枝称

38、为剪枝； 任何“与”节点x的值如果不能升高其父辈节点的值，则对节点x以下的分支可停止搜索，并使的倒推值为 ，这种剪枝称为剪枝。基本推理方法基本推理方法1 推理的基本概念推理通常是指从已知的事实出发，通过运用已掌握的知识，找出其中蕴藏的事实，或归纳出新的事实，这一过程就称为推理。推理包括两种判断：一种是已知的判断，它包括已掌握的求解问题有关的知识和关于问题的已知事实；另一种是由已知判断推出新的判断，即推理的结论。2 推理方式和分类 按推理机制划分，可以有 演绎推理：演绎推理是从全称判断推导出特称或单称判断的过程。 归纳推理：归纳推理是从足够的事例中归纳出一般性结论的推理过程。 默认推理：默认推理

39、又称缺省推理。它是在知识不完全的情况下假设某些条件已经具备所进行的推理。 按所用知识的确定性划分，可以有 确定性推理：确定性推理是指推理时所用的知识都是精确的，推理出的结论也是精确的。 不精确推理：不精确推理是指在推理时所用到的知识不都是精确的，推理出的结论也不完全是肯定的。 按推理过程划分，可以有 单调推理：单调推理是指在推理的过程中随着推理的向前推进及新知识的加入，推理的结论呈单调增长的趋势，并越来越接近最终目标。 非单调推理：非单调推理是指在推理的过程中，由于新的知识的加入，不仅没有加强推出的结论，反而要否定它，使得推理退回到前面的一步，重新开始。 按启发性知识划分，可以有 启发式推理：

40、在推理的过程中利用了能够加快推理进程、求得最优解的启发性知识的推理。 非启发性推理：在推理的过程中并不利用能够加快推理进程、求得最优解的启发性知识的推理。 按方法论划分，可以有 基于知识的推理 统计推理 直觉推理：直觉推理又称为常识性推理，是根据常识进行的一种推理。3 推理控制策略 正向推理：从用户提供的初始事实出发，在知识库中找出当前可适合的知识，构成可适用的知识集，然后按某种冲突消解策略从知识集中选出一条知识进行推理，并将推理出的新事实加入到数据库作为下一步推理的已知事实，如此重复这一过程。 逆向推理：首先选定一个假设目标，然后寻找支持该假设的证据，若所需要的证据都能找到，则说明假设是成立

41、的；若无论如何都找不到所需要的证据，说明原假设不成立。 混合推理：即有正向推理又有逆向推理的推理方法就是混合推理。 双向推理：所谓双向推理是指正向推理和逆向推理同时进行，且在某一步骤上相遇。基本思想是：一方面根据已知事实进行正向推理，但并不推到最终目标；另一方面，从某一假设目标出发进行逆向推理，但并不推至原始事实，而是让它们在途中相遇，既正向推理所得的中间结论恰好是逆向推理此时所需要求的证据。 4 归结反演 归结反演就是用归结和反演的方法实现定理证明。 子句定义为由文字的析取组成的公式谓词公式化为子句集的过程 消去蕴涵符号 把否定符号移到每个谓词符号的前面 变量标准化 消去存在量词 将公式化为

42、前束形 把母式化为合取范式 略去全称量词 把母式用子句表示 子句变量标准化 归结反演的一般过程：设有公式集S，希望从S证明某个目标公式W，证明的过程如下： 将W加入到S集合 将新的集合S转换成一组子句，应用归结原理推导出一个空子句 归结反演过程主要就是证明一个集合是不可满足的过程，即从集合归结出空子句的过程。 归结反演的控制策略 宽度优先策略 支持集策略 单元优先策略 线性输入策略 祖先过滤策略5 基于规则的演绎系统 将问题的知识和信息划分为规则和事实两种类型。规则有包含蕴涵形式的表达式，事实由无蕴涵形式的表达式表示。这样的推理系统称为基于规则的演绎系统。 正向演绎系统：从事实出发，正向地使用

43、蕴涵式（F规则）进行演绎推理，直到某个目标公式的一个终止条件为止。 事实表达式：事实表达式为无蕴涵的任意与或形。 利用规则转换与或图：正向演绎系统应用规则作用于事实的与或图，改变与或图的结构，从而产生新的事实。规则形式为 其中L是单文字，W是任意的与或形表达式。L和W中的所有变量都是全称量化的。 利用目标公式做结束条件：正向演绎系统的目标公式定义为文字的析取，当一个目标文字与与或图中的文字匹配时，系统便成功结束。WL 逆向演绎系统：在逆向演绎系统从目标表达式出发，应用逆向规则（规则），直到事实表达式。 目标表达式：在逆向演绎系统中，目标公式为无蕴涵的任意与或形。 规则应用：逆向演绎系统的规则称

44、为规则，形为 其中W为任意的与或形，L为单文字。 结束条件：逆向演绎系统的事实表达式限制为文字的合取，可表示为文字的集合。逆向演绎系统的结束条件就是与或图中包括一个结束在事实结点上的一致解图，该解图的合一复合作用于目标表达式就是解答语句。LW 不确定性推理不确定性推理1 不确定性推理的基本概念 什么是不确定性推理所谓不确定性推理就是从不确定性的初始证据出发，通过运用不确定性的知识，最终推理出具有一定程度的不确定性，但又是合理或者似乎合理的结论的思维过程。 不确定性推理的一般算法 根据规则前提E的不确定性C(E)和规则强度f(H，E),求出假设H的不确定性C(H)，即定义一函数g1，使C(H)=

45、g1C(E),f(H,E) 根据分别由独立的证据E1和E2,求得的假设H的不确定性C1(H)和C2(H)， 求得证据E1和E2的组合所导致的假设的不确定性C(H)，即定义一函数g2，使C(H)=g2C1(H),C2(H) 根据两个证据E1和E2的不确定性C(E1)和C(E2)，求出证据E1和E2的合取E1E2的不确定性，即定义一函数g3，使C(E1E2)=g3C(E1),C(E2) 根据两个证据E1和E2的不确定性C(E1)和C(E2)，求出证据 E1和 E2的 析 取 的 不 确 定 性 ， 即 定 义 函 数 g4， 使C(E1E2)=g4C(E1),C(E2) 几种主要的不确定性推理方法

46、 确定因子法（可信度方法） 主观Bayes方法 证据理论 可能性理论 粗集理论 批注理论 2 确定因子法 知识的不确定性表示 MYCIN系统称规则强度为规则确定性因子（Certainty Factor）CF(H,E)，它表示在已知证据的情况下，对假设的确信程度。 CF(H,E)定义如下： 证据的不确定性),(),(),(EHMDEHMBEHCF)(1)()(),|(max1),(HpHPHPEHPEHMB)()()(),|(min1),(HPHPHPEHPEHMD 不确定性推理 根据证据和规则的不确定性求假设的不确定性： 组合两个独立证据导出的同一个假设的不确定性： 由此计算： )(, 0ma

47、x),()(ECFEHCFHCF其他当);,(),(),(),(1),(; 0),(21212121EHMBEHMBEHMBEHMBandEEHMDandEEHMB其他当);,(),(),(),(1),(; 0),(21212121EHMDEHMDEHMDEHMDandEEHMBandEEHMD),(),(),(212121andEEHMDandEEHMBandEEHCF 证据的合取 证据的析取 )(,),(),(min)()(2121nnECFECFECFandEandandEECFECF)(,),(),(max),()(2121nnECFECFECForEororEECFECF3 主观Ba

48、yes方法 主观Bayes方法是以概率论中的Bayes公式为基础的一 种 不 确 定 性 推 理 算 法 ， 首 先 应 用 于 专 家 系 统PROSPECTOR系统。 知识不确定性的表示：在该方法中知识的不确定性表示为其中规则强度由LS和LN表示。 证据的不确定性：证据的不确定性用证据的概率P(E)表示，或者用证据的几率(E) ),(LNLSHTHENEIF)|()|(HEPHEPLS)|()|(HEPHEPLN)(1)()(EPEPE 不确定性推理算法：采用三点的线性插值方法。即 当 时，有 当 时，有 当 时，有 分段插值的解析式为： 1)|(SEP)|()|(EHPSEP)()|(E

49、PSEP)()|(HPSEP)()|(EPSEP)()|(HPSEP1)|()(),()|()(1)()|()()()|(0),|()()|()()|()|(SEPEPEPSEPEPHPEHPHPEPSEPSEPEPEHPHPEHPSEP当当4 证据理论 证据理论是由Dempster和他的学生Shafer共同提出来的一种不确定性推理模型，所以也称为D-S证据理论。证据理论可以满足比概率更加弱的公里体系，当概率值已知的时候，证据理论就变成为概率论了。 证据的不确定性 设U的幂集2U上定义了一个基本概率赋值函数m：2U 0,1，使满足 ，基本概率赋值函数m(A)表示了证据对U的子集A成立的一种信任

50、程度。UAAmm1)(, 0)( 信任函数：信任函数定义为 似然函数：似然函数定义为 信任函数与似然函数的关系 ABUBmABelBel)()(,1 , 02:)(1)(,1 , 02:ABelAPlPlU)()(ABelAPl0)()(BelPl1)()(UBelUPl)(1)(ABelAPl1)()(ABelABel1)()(APlAPl)()()(APlAPABel 证据组合：对于相同的证据，由于来源不同，可能得到不同的基本概率赋值函数。D-S证据理论采取正交和来组合这些函数。 设 是 上的个基本概率赋值函数，它们的正交和 ，且定义为 其中 证据理论的推理 知识表示：系统的推理规则表示为

51、 证据的描述：对于任何命题 ，其信任函数为nmmm,21U2mmmm21 AAniiiiAAmKAmm1),()(0)( AAniAniiiiiiiAmAmK111)()(1CFHTHENEIFA,:UA 似然函数为 类概率函数： 不确定性推理 匹配度函数： ABAaamBmABel)()()(UBUaUmamBmUBel1)()()()(AaABelUmamABelAPl)()()(1)(1)(1)(1)(1)(BelUBelUPl)()()()(ABelAPlUAABelAf；其他中的所有元素都出现在如果0; 1),(EAEAMD)() ,()(AfEAMDACER 命题的逻辑组合的情况

52、合取： 析取： 如果几种规则支持同一命题，总的概率赋值函数定义为各规则假设得到的基本概率赋值函数的正交和，即 )(,),(),(min)()(2121nnACERACERACERandAandandAACERACER)(,),(),(max)()(2121nnACERACERACERorAororAACERACERmmmm215 可能性理论 Zadeh在1965年提出了模糊集合论，1978年又提出了可能性理论。 模糊命题：含有模糊概念、模糊数据或带有确信程度的语句称为模糊命题。形式化为：x is A或者x is A (CF) 其中，X是论域上的变量，用来代表所论对象的属性；A是模糊概念或模糊数

53、；CF是该模糊命题的确信度，它可以是一个确定的数，也可以是模糊数，还可以是模糊语言值。 模糊知识的表示：模糊产生式规则的一般形式为 其中E是用模糊命题表示的模糊条件；H是用模糊命题表示的模糊结论；CF是该产生式规则所表示的知识可信度因子。 ),(CFHTHENEIF 语义距离：设A、B分别是论域上 相应的模糊概念的模糊集，而 和 分别是它们的隶属函数，则有 海明距离：海明距离定义为 欧几里德距离 明可夫斯基距离,21nuuuUABniiBiAuunBAd1)()(1),(niiBiAuunBAd12)()(1),(qqniiBiAuunBAd11)()(1),( 切比雪夫距离 语言变量：用语言

54、而不是用数字来表示变量的值和变量之间的关系，这种变量称为语言变量。 模糊命题的转换规则 修正规则 合取、析取和蕴含规则 量化规则 模糊推理 广义假言推理 模糊量词的近似推理 模糊真值限定的近似推理)()(),(1iBiAniuuMaxBAd 6 粗集理论 粗集理论是波兰华沙理工大学的Z. Pawlak教授1982年首先提出的处理不确定性信息的理论。该方法特别实用于观察和测量获得的不精确数据的分类问题。 专家系统n专家系统（Expert System，简称ES）是人工智能应用研究最活跃和最广泛的课题之一。n专家系统专家系统是一个含有大量的某个领域专家水平的知识与经验智能计算机程序系统，能够利用人

55、类专家的知识和解决问题的方法来处理该领域问题。n简而言之，专家系统是一种模拟人类专家解决领域问题的计算机程序系统。 专家系统的特点n三大特点n启发性n透明性n灵活性专家系统的类型n解释专家系统n预测专家系统n诊断专家系统n设计专家系统n规划专家系统n监视专家系统n控制专家系统n调试专家系统n教学专家系统n修理专家系统解释专家系统解释专家系统n任务任务 通过对过去和现在已知状况的分析，推断未来可能发生的情况n特点特点 数据量很大，常不准确、有错误、不完全能从不完全的信息中得出解释，并能对数据做出某些假设，推理过程可能很复杂和很长n例子例子 语音理解、图象分析、系统监视、化学结构分析和信号解释等。

56、预测专家系统 n任务任务 通过对已知信息和数据的分析与解释，确定它们的涵义。n特点特点 系统处理的数据随时间变化，且可能是不准确和不完全，系统需要有适应时间变化的动态模型n例子例子 有气象预报、军事预测、人口预测、交通预测、经济预测和谷物产量预测等诊断专家系统 n任务任务 根据观察到的情况(数据)来推断出某个对象机能失常(即故障)的原因n特点特点 能够了解被诊断对象或客体各组成部分的特性以及它们之间的联系，能够区分一种现象及其所掩盖的另一种现象，能够向用户提出测量的数据，并从不确切信息中得出尽可能正确的诊断n例子例子 医疗诊断、电子机械和软件故障诊断以及材料失效诊断等。设计专家系统 n任务任务

57、 寻找出某个能够达到给定目标的动作序列或步骤。n特点特点 从多种约束中得到符合要求的设计；系统需要检索较大的可能解空间；能试验性地构造出可能设计；易于修改；能够使用已有设计来解释当前新的设计。n例子例子 VAX计算机结构设计专家系统等。 规划专家系统 n任务任务 寻找出某个能够达到给定目标的动作序列或步骤。n特点特点 所要规划的目标可能是动态的或静态的，需要对未来动作做出预测，所涉及的问题可能很复杂 。n例子例子 军事指挥调度系统、ROPES机器人规划专家系统、汽车和火车运行调度专家系统等。监视专家系统n任务任务 对系统、对象或过程的行为进行不断观察，并把观察到的行为与其应当具有的行为进行比较

58、，以发现异常情况，发出警报。n特点特点 系统具有快速反应能力，发出的警报要有很高的准确性，能够动态地处理其输入信息。n例子例子 粘虫测报专家系统。控制专家系统 n任务任务 自适应地管理一个受控对象或客体的全面行为，使之满足预期要求。n特点特点 控制专家系统具有解释、预报、诊断、规划和执行等多种功能。n例子例子 空中交通管制、商业管理、自主机器人控制、作战管理、生产过程控制和质量控制等。调试专家系统 n任务任务 对失灵的对象给出处理意见和方法。n特点特点 同时具有规划、设计、预报和诊断等专家系统的功能。n例子例子 在这方面的实例还比较少见。教学专家系统 n任务任务:教学专家系统的任务是根据学生的

59、特点、弱点和基础知识，以最适当的教案和教学方法对学生进行教学和辅导。n特点特点(1)同时具有诊断和调试等功能。(2)具有良好的人机界面。n例子例子 MACSYMA符号积分与定理证明系统，计算机程序设计语言和物理智能计算机辅助教学系统以及聋哑人语言训练专家系统等。 修理专家系统 n任务任务 对发生故障的对象(系统或设备)进行处理，使其恢复正常工作。修理专家系统具有诊断、调试、计划和执行等功能。n例子例子 美国贝尔实验室的ACI电话和有线电视维护修理系统。n此外，还有决策专家系统和咨询专家系统等。专家系统的结构和建造步骤专家系统的结构专家系统的结构n定义：定义：专家系统各部分的构造方法和组织形式n

60、专家系统结构图已学过的知识表示方法有哪些呢？已学过的知识表示方法有哪些呢？理想专家系统结构图理想专家系统结构图n专家系统的定义？n专家系统程序与常规的应用程序之间有何不同呢?一般应用程序与专家系统的区别一般应用程序一般应用程序专家系统专家系统把问题求解的知识隐含地编入程序 知识组织为两级：数据级和程序级 把其应用领域的问题求解知识单独组成一个实体，即为知识库。 将知识组织成三级；数据、知识库和控制。 n专家系统构造步骤基于规则的专家系统n基于规则的专家系统的工作模型n基于规则的专家系统采用下面的模块来建立产基于规则的专家系统采用下面的模块来建立产生式系统的模型：生式系统的模型：n知识库：知识库