ch04决策支持系统(新)课件.ppt

1、决策支持系统决策支持系统系统工程专业本科学员必修课系统工程专业本科学员必修课第四章第四章 智能决策支持系智能决策支持系统和智能技术的决策支持统和智能技术的决策支持人工智能基本原理人工智能基本原理本章内容本章内容智能决策支持系统概述智能决策支持系统概述专家系统与智能决策支持系统专家系统与智能决策支持系统神经网络的决策支持神经网络的决策支持遗传算法的决策支持遗传算法的决策支持机器学习的决策支持机器学习的决策支持4.1 智能决策支持系统概述智能决策支持系统概述4.1.1 智能决策支持系统概念4.1.2 智能决策支持系统结构 1981年，Bonczek提出了DSS三系统结构，该结构中有“知识系统”，使

2、得不少学者将DSS划为人工智能的范畴，研究知识表示与知识推理，这样，DSS与人工智能的专家系统的界限变得模糊了。1980年，Spraque提出DSS的三部件结构，是传统DSS结构的典型代表。IDSS实际上就是在DSS基础上增加了知识部件。4.1.1 智能决策支持系统概念知识部件知识部件知识库知识管理系统推理机4.1.2 智能决策支持系统结构1.人工智能的决策支持技术（1 1）专家系统）专家系统（2 2）神经网络）神经网络（3 3）遗传算法）遗传算法（4 4）机器学习）机器学习（5 5）自然语言理解）自然语言理解2.智能决策支持系统结构形式（1）IDSS的基本结构形式问题综合与交互系统模型库管理

3、系统数据库管理系统人工智能技术专家系统 神经网络遗传算法 机器学习自然语言理解模型库模型库数据库数据库（2）IDSS的简化结构图问题综合与交互系统模型库管理系统数据库管理系统知识库管理系统推理机模型库模型库数据库数据库知识库知识库用户4.2 4.2 人工智能基本原理人工智能基本原理4.2.1 逻辑推理4.2.2 知识表示与知识推理4.2.3 搜索技术4.2.1 4.2.1 逻辑推理逻辑推理1.形式逻辑（1）概念：概念反映事物的特有属性和属性的取值。（3）推理：从一个或多个判断推出一个新判断的过程。（2）判断：对概念的肯定或否定；是研究人的思维形式及其规律的科学，主要用于是研究人的思维形式及其规

4、律的科学，主要用于形成形成概念概念，作出，作出判断判断，进行，进行推理推理。2 推理的种类演绎推理归纳推理类比推理假言推理三段论推理数学归纳法假言易位推理枚举归纳推理（1）假言推理：“如果p，那么q”为真，同时“p”为真，则推出“q”为真。pq，p q （2）三段论推理：“如果p，那么q”为真，同时“如果q，那么r”为真，则推出“如果p，那么r”为真。pq，q r p r（3）假言易位推理：“如果p，那么q”为真，同时“非q”为真，则推出“非p”为真。pq，q p演绎推理（1）数学归纳法：A包含B1、B2，A真B1真，Bn Bn1归纳推理（2）枚举归纳推理：由所见的某一类事物的部分分子具有某种

5、属性，而且没有遇到相反的情况，于是得出这一类事物都具有这种属性的一般性结论。S1是P，S2 是P Sn是P，S1Sn是S类中的部分分子，而且没有遇到相反的事例 所以，S类事物都是P类比推理：A事物有a、b、c、d属性，B事物有a、b、c属性（或a，、b，、c，相似属性）所以，B事物也可能有d 属性（或d，相似属性）由两个（或两类）事物在某些属性上相同，进而推断它们在另一个属性也可能相同的推理。3.总结（1）演绎推理的结论没有超出已知的知识范围，而归纳推理和类比推理的结论超出了已知的知识范围；（2）演绎推理中由于前提和结论有必然联系，只要前提为真，结论一定为真。归纳推理和类比推理中前提和结论，不

6、能保证有必然联系，具有或然性。这样的结论未必是可靠的，需要经过严格的验证和证明。4.2.2 4.2.2 知识、知识表示知识、知识表示 知识是加工了的、深思熟虑过的、经过推理了的、知识是加工了的、深思熟虑过的、经过推理了的、已经达成共识的关于实体的状态以及实体之间的联系已经达成共识的关于实体的状态以及实体之间的联系的一系列事实，可以用来指导行动，是理解自然规律的一系列事实，可以用来指导行动，是理解自然规律并根据自然规律预测实际系统行为的能力。并根据自然规律预测实际系统行为的能力。：是以各种不同方式把多个信息关联在一起的信息结是以各种不同方式把多个信息关联在一起的信息结构。是人们对客观事物及其规律

7、的认识，知识还包括人构。是人们对客观事物及其规律的认识，知识还包括人们利用客观规律解决实际问题的方法和策略等。们利用客观规律解决实际问题的方法和策略等。描述性知识描述性知识：表示对象及概念的特征及其相互关系的知识，：表示对象及概念的特征及其相互关系的知识，及问题求解状况的知识，也称为事实性知识。及问题求解状况的知识，也称为事实性知识。判断性知识判断性知识：表示与领域有关的问题求解知识，如推理规则：表示与领域有关的问题求解知识，如推理规则等，也称启发性知识。等，也称启发性知识。过程性知识过程性知识：表示问题求解的控制策略，即如何应用判断性：表示问题求解的控制策略，即如何应用判断性知识进行推理的知

8、识。知识进行推理的知识。F计算机所处理的知识，按其作用可大致分为三类：计算机所处理的知识，按其作用可大致分为三类：F知识按其作用的层次可分为两类：知识按其作用的层次可分为两类：对象级知识对象级知识：直接描述有关领域对象的知识：直接描述有关领域对象的知识元级知识元级知识：描述对象级知识的知识：描述对象级知识的知识4.2.2 4.2.2 知识、知识表示知识、知识表示4.2.2 4.2.2 知识、知识表示知识、知识表示F知识表示：知识表示：知识表示是对知识的一种描述，或者说是一组知识表示是对知识的一种描述，或者说是一组约定，是一种计算机可以接受的、用于描述知识的约定，是一种计算机可以接受的、用于描述

9、知识的数据结构，对知识进行表示就是把知识表示成便于数据结构，对知识进行表示就是把知识表示成便于计算机存储和利用的某种数据结构。计算机存储和利用的某种数据结构。F知识表示的要求知识表示的要求1）表示能力：能够将问题求解所需的知识正确有）表示能力：能够将问题求解所需的知识正确有 效地表达出来；效地表达出来；2）可理解性：所表达的知识简单、易于理解；）可理解性：所表达的知识简单、易于理解；3）可访问性：能够有效地利用所表达的知识；）可访问性：能够有效地利用所表达的知识；4）可扩充性：能够方便地对知识进行扩充。）可扩充性：能够方便地对知识进行扩充。4.2.2 4.2.2 知识、知识表示知识、知识表示谓

10、词逻辑谓词逻辑产生式规则产生式规则语义网络语义网络框架框架剧本剧本 谓词逻辑的合法表达式也称合式公式。它由原子公式、谓词逻辑的合法表达式也称合式公式。它由原子公式、连接词和量词组成。连接词和量词组成。办公地点关系办公地点关系刘凌刘凌401401陈东华陈东华402402张明亮张明亮418418办公地点（刘凌、办公地点（刘凌、401401）办公地点（陈东华、办公地点（陈东华、402402）办公地点（张明亮、办公地点（张明亮、418418）1 1 一阶谓词逻辑一阶谓词逻辑兰色（盒子）兰色（盒子）颜色（盒子、兰色）颜色（盒子、兰色）值（颜色、盒子、兰色）值（颜色、盒子、兰色）盒子是兰色的盒子是兰色的

11、谓词逻辑的合法表达式也称合式公式。它由原子公式、谓词逻辑的合法表达式也称合式公式。它由原子公式、连接词和量词组成。连接词和量词组成。1 1 一阶谓词逻辑一阶谓词逻辑连接词：用来组合原子公式以形成较复杂的合式公式。连接词：用来组合原子公式以形成较复杂的合式公式。合取：合取：PQPQ，当，当P P、Q Q皆为真时，才为真，否则为假；皆为真时，才为真，否则为假；类似类似“AND”AND”析取：析取：PQPQ，当，当P P、Q Q皆为假时，则为假，否则为真；皆为假时，则为假，否则为真；类似类似“OR”OR”蕴涵：蕴涵：P=Q,P=Q,只有只有P P为真，为真，Q Q为假时，蕴涵式为假，否为假时，蕴涵式

12、为假，否则为真；则为真；否定：否定：PP，当，当P P为假时，才为真，否则为假。为假时，才为真，否则为假。1 1 一阶谓词逻辑一阶谓词逻辑PQP=QTTTTFFFTTFFT1 1 一阶谓词逻辑一阶谓词逻辑量词：量词：、，分别为全称量词和存在量词。，分别为全称量词和存在量词。例子：例子：“张某送给屋里的每个人一件礼物张某送给屋里的每个人一件礼物”（y y）IN(y,ROOM)HUMAN(y)=IN(y,ROOM)HUMAN(y)=(x x)GIVE(ZHANG,x,y)PRESENT(x)GIVE(ZHANG,x,y)PRESENT(x)1 1 一阶谓词逻辑一阶谓词逻辑2 2 产生式规则产生式规

13、则 产生式(Production)一词，首先是由美国数学家波斯特（E.Post）提出来的。波斯特根据替换规则提出了一种称为波斯特机的计算模型，模型中的每一条规则当时被称为一个产生式。后来，这一术语几经修改扩充，被用到许多领域。例如，形式语言中的文法规则就称为产生式。产生式也称为产生式规则，或简称规则。2 2 产生式规则产生式规则产生式规则的一般形式为：前件后件 其中，前件就是前提，后件是结论或动作，前件和后件可以是由逻辑运算符AND、OR、NOT组成的表达式。2 2 产生式规则产生式规则产生式规则知识一般表示为：if A then B 产生式规则的语义：如果前提满足，则可得结论或者执行相应的动

14、作，即后件由前件来触发。所以，前件是规则的执行条件，后件是规则体。例如，下面就是几个产生式规则：(1)如果银行存款利率下调，那么股票价格上涨；(2)如果炉温超过上限，则立即关闭风门；(3)如果键盘突然失灵且屏幕上出现怪字符，则是病毒发作；一条产生式规则就是一条知识。用产生式可以实现推理和操作，产生式规则是知识表示形式产生式规则是知识表示形式。产生式规则知识有产生式规则知识有正向正向和和逆向逆向两种推理方式两种推理方式。（1）正向推理v 逐条搜索规则库，对每一条规则的前提条件都检查事实库中是否存在；v 对前提条件中各子项，若事实库中不是全部都存在，放弃该条规则；v 若在事实库中全部存在，则执行该

15、条规则，并结论放入到事实库中；v 反复执行上述过程，直至推出目标，并存放入事实库中。算法：例如：在产生式规则库中有3条规则，在事实库中存在B、C、E3个事实，且它们均为真。希望通过正向推理，证明目标G为真。B、C、E1、A B-G2、C D-A3、E-DVV产生式规则库事实库推理过程：（1）正向推理（2）逆向推理v从目标开始，寻找以此目标为结论的规则，并对该规则的前提进行判断；v若该规则的前提中某个子项是另一规则的结论，再找此结论的规则；v重复上述过程，直到对某个规则的前提能够进行判断；v按此规则前提的判断得出结论的判断，由此回溯到上一个规则的推理，一直回溯到目标的判断。算法：B、C、E1、A

16、 B-G2、C D-A3、E-DVV产生式规则库事实库推理过程：GBACDE（2）逆向推理 从概念结点间问它们之间的关系 通过概念和关系问其他结点 由J.R.Quilian于1968年在研究人类联想记忆时提出的一种心理学模型。3 3 语义网络语义网络基本思想：v 用结点表示概念，用弧线表示概念之间的关系，将领域知识表示成一种结构图形式；v 在语义网络中，寻找概念之间的内在联系，主要通过语义网络的形式推理来回答两类问题：3 3 语义网络语义网络结点代表实体，表示各种事物、概念、情况、属性、状态、事件、动作等；语义单元是由有向图表示的三元组(结点1,弧,结点2)结点1结点2语义关系弧是有方向和标注

17、的，方向体现了结点所代表的实体的主次关系，即结点1为主，结点2为辅；标注表示所连接的两个实体之间的语义联系。试用语义网络表示命题“某学校小学生坐车去春游”。动作方式某学校小学生动作目的春游坐车属于3 3 语义网络语义网络基本的语义关系(1)Is-a(1)Is-a和和Part-ofPart-of型关系型关系Is-a：表示一个事物是另一个事物的实例，表示具体与抽象关系，此关系的一个最主要的特点是属性的继承关系。灵长类动物Is-aIs-a型语义网络3 3 语义网络语义网络轮胎汽车Part-ofPart-of型语义网络(1)Is-a(1)Is-a和和Part-ofPart-of型关系型关系Part-o

18、f：表示一个事物是另一个事物的一部分，是部分与整体的关系。基本的语义关系3 3 语义网络语义网络Is：表示一个结点是另一个结点的属性中国的陆地面积960万平方公里IsIs型语义网络(1)Is-a(1)Is-a和和Part-ofPart-of型关系型关系基本的语义关系3 3 语义网络语义网络(2)(2)属性属性(类属类属)关系关系Have：表示一个结点具有另一个结点所描述的属性 Have属性关系语义网络鸟翅膀Have基本的语义关系3 3 语义网络语义网络(2)(2)属性属性(类属类属)关系关系A-Kind-of：表示一个事物是另一个事物的一种类型，表示隶属关系。AKO属性关系语义网络鸭嘴兽哺乳动

19、物A-Kind-of基本的语义关系3 3 语义网络语义网络(2)(2)属性属性(类属类属)关系关系Can：表示一个结点能做另一个结点的事情。Can属性关系语义网络草鱼水草eat基本的语义关系3 3 语义网络语义网络(3)(3)其他关系其他关系时间关系：指不同事物在其发生时间方面的先后关系。Before：表示一个事物在一个事物之前发生；After：表示一个事物在一个事物之后发生；位置关系：指不同事物在位置方面的关系。Located-onLocated-atLocated-underLocated-insideLocated-outside3 3 语义网络语义网络语义网络的推理语义的推理过程主要有

20、两种：继承和匹配 继承的思想：对事物的描述从抽象结点传递到具体结点，从而得到所需结点的属性值，通常是沿着Is-a，A-Kind-of等继承弧进行。3 3 语义网络语义网络语义网络的推理3 3 语义网络语义网络语义网络继承推理示意图 小米谷物麻雀1麻雀鸟动物翅膀飞行工具AKOAKOAKOIs-aIs-aeatHave 匹配的思想：在知识库的语义网络中寻找与待求问题相符的语义网络模式。小米谷物麻雀1麻雀鸟动物翅膀飞行工具AKOAKOAKOIs-aIs-aeatHave举例：已知麻雀是一种鸟，求麻雀的特点。某港海浪动作对象海浪战舰轻轻isa动作方式晃动isa某港战舰 动作主体语义网的推理试用语义网络

21、表示命题“海浪把战舰轻轻地摇”问1 海浪和战舰有什么关系？(寻找概念间的关系)问2 怎样晃动？(通过概念和关系寻找其他结点)问3 晃动哪些战舰？(寻找概念间的关系)框架框架 框架是描述对象（一个事物、事件或概念）属框架是描述对象（一个事物、事件或概念）属性的一种数据结构，由一组描述物体的各个方面的性的一种数据结构，由一组描述物体的各个方面的槽（属性）所组成。每个槽（属性）又可包含若干槽（属性）所组成。每个槽（属性）又可包含若干侧面（属性的一个方面），每个侧面都有自己的名侧面（属性的一个方面），每个侧面都有自己的名字和填入的值。字和填入的值。明斯基明斯基1975年提出，年提出，用来表示经验性知识

22、用来表示经验性知识一般框架的结构:frame slotslot 值21 值22 值11 值12下面是一个描述下面是一个描述“教师教师”的框架：的框架：框架名：框架名：类属：类属：工作：工作：(教学，科研教学，科研)缺省：教学缺省：教学 性别：性别：(男，女男，女)学历：学历：(中师，高师中师，高师)类型：类型：(，)框架框架框架框架槽值可以有如下几种类型：槽值可以有如下几种类型：具体值具体值value默认值默认值default过程值过程值procedure：该值是一个计算过程，它利该值是一个计算过程，它利用该框架的其它槽值，按给定计算过程（公式）用该框架的其它槽值，按给定计算过程（公式）进行计

23、算得出具体值。进行计算得出具体值。另一框架名：当槽值是另一框架名时，就构成另一框架名：当槽值是另一框架名时，就构成了框架调用，这样就连成了一个框架链。有关框了框架调用，这样就连成了一个框架链。有关框架聚集起来就组成框架系统。架聚集起来就组成框架系统。空（待填入）空（待填入）框架框架 框架是知识表示的基本单位。框架是知识表示的基本单位。不同的框架之间可以通过属性之间关系建立联不同的框架之间可以通过属性之间关系建立联系，从而构成一个框架网络，充分表达相关对象间系，从而构成一个框架网络，充分表达相关对象间的各种关系。的各种关系。特点：主要描述事物的内部结构及事物之间的类特点：主要描述事物的内部结构及

24、事物之间的类属关系。属关系。框架名：框架名：动作：攻打动作：攻打动作发出者：美国动作发出者：美国动作接受者：伊拉克动作接受者：伊拉克后果：后果：，框架名：框架名：动作：抵抗动作：抵抗动作发出者：伊拉克动作发出者：伊拉克动作接受者：美国动作接受者：美国后果：后果：，框架名：框架名：动作：投降动作：投降动作发出者：伊拉克动作发出者：伊拉克动作接受者：美国动作接受者：美国后果后果:萨达姆政府垮台萨达姆政府垮台框架名：框架名：动作：撤军动作：撤军动作发出者：美国动作发出者：美国后果：遭国际社会谴责后果：遭国际社会谴责框架推理的主要形式为：填充槽值。框架推理的主要形式为：填充槽值。填充槽值的主要方法为：

25、匹配、继承。填充槽值的主要方法为：匹配、继承。匹配：在求解某个问题时，先把问题用一个框架表示出匹配：在求解某个问题时，先把问题用一个框架表示出来，然后与知识库中的已有框架进行匹配。如果匹配成功，来，然后与知识库中的已有框架进行匹配。如果匹配成功，就可获得有关信息。就可获得有关信息。继承：子框架可以拥有其父框架的槽及其槽值。继承：子框架可以拥有其父框架的槽及其槽值。框架框架(1)匹配匹配 框架是一类事物的完整描框架是一类事物的完整描述。事物之间匹配只能是部述。事物之间匹配只能是部分相同槽的匹配。分相同槽的匹配。框架框架1：王强：王强是是 人人性别性别 男男行动行动 音量音量 进取心进取心 中等中

26、等框架框架2：消防车：消防车是是 车辆车辆颜色颜色 红红行动行动 快快音量音量 极高极高载物载物 水水匹配此两框架的槽：行动和音量。匹配此两框架的槽：行动和音量。得到王强的行动是快的，音量是极高的。得到王强的行动是快的，音量是极高的。框架框架 例：王强的行动和音量象例：王强的行动和音量象消防车。我们要知道王强的消防车。我们要知道王强的行动和音量究竟是什么，应行动和音量究竟是什么，应该对两个框架进行匹配。该对两个框架进行匹配。框架框架 (2)继承继承 有两种继承，即直接继承和时序继承。直接继承：在框架网络中下层框架直接从上层 框架中继承所有的属性值和条件。如“墙”继承“房子”的所有属性时序继承：

27、有条件的继承。框架框架例：框架名：旧中国例：框架名：旧中国政体：资产阶级专政政体：资产阶级专政面积：面积：960万平方公里万平方公里人口：人口：4亿亿5千万千万领导党派：国民党领导党派：国民党框架名：新中国框架名：新中国政体：人民民主专政政体：人民民主专政面积：面积：人口：人口：4亿亿5千万（当时千万（当时1949年）年）领导党派：共产党领导党派：共产党其中，面积和人口是相同的，其它槽值就改变了。这就是有其中，面积和人口是相同的，其它槽值就改变了。这就是有条件的继承。条件的继承。关于框架的例子例例 描述学校的框架描述学校的框架框架名：类属：类型：范围(大学，中学，小学)位置：(省(直辖市)，市

28、)面积：单位(平方米)教工人数：学生人数：例例 描述大学的框架描述大学的框架框架名：类属：类型：范围(综合性大学，专科性大学)专业：默认值：综合 学院数：教学楼：教工人数：学生人数：位置：(省(直辖市)，市)面积：单位(平方米)例例 描述某所大学的框架描述某所大学的框架框架名：类属：姓名：中国医科大学 专业：医学 学院数：13 教学楼：20 办公楼：40 学生宿舍：20 教工宿舍：60 教工人数：4000 职工人数：5000 学生人数：20000 位置：北京市 面积：10000万平方米 创建时间：2002年4月 1、有的槽有槽值，有的槽值不明显，有的槽没有槽值，有的槽值是一个框架名；2、这3个

29、框架是层层嵌套的，上位框所具有的属性，下位框也一定具有，下位框可以从上位框继承某些槽值和侧面值。3、框架的推理基于匹配和继承的原则。剧本剧本是描述一定范围内一串原型事物的结构。剧本是描述一定范围内一串原型事物的结构。剧本由六部分组成：剧本由六部分组成：(1)开场条件开场条件：事件发生之前必须满足的条件。：事件发生之前必须满足的条件。例如，肚子饿了需要进餐，且有钱等。例如，肚子饿了需要进餐，且有钱等。(2)结局结局：事件发生之后，通常会成为现实的情况。：事件发生之后，通常会成为现实的情况。例如，肚子不再饿了，花了钱等。例如，肚子不再饿了，花了钱等。(3)道具道具：用来表示与剧本所描述的事件有关的

30、物体。：用来表示与剧本所描述的事件有关的物体。例如，餐桌、菜单、食物等。例如，餐桌、菜单、食物等。(4)角色角色：剧本中描述事件中的人物。：剧本中描述事件中的人物。例如，经理、顾客、服务员等。例如，经理、顾客、服务员等。(5)线索线索：剧本表达事件的时序模式。：剧本表达事件的时序模式。例如，小食店、餐厅、酒家等。例如，小食店、餐厅、酒家等。(6)场次场次：事件发生的顺序。每个场次可用框架描述。：事件发生的顺序。每个场次可用框架描述。剧本剧本特点剧本特点：结构呆板，知识表示范围窄，不适合用于表达各种知识，但对于表达事先构思好的特定知识非常有效。回顾回顾人工智能基本原理人工智能基本原理v知识表示与

31、知识推理谓词逻辑产生式规则语义网络框架剧本智能决策支持系统结构智能决策支持系统结构4.2.3 4.2.3 搜索技术搜索技术1.1.问题求解过程的形式表示问题求解过程的形式表示2.2.盲目搜索方法盲目搜索方法3.3.启发式搜索启发式搜索v状态空间表示法状态空间表示法v与或树表示法与或树表示法v 广度优先搜索法广度优先搜索法v 生成测试法生成测试法v 深度优先搜索法深度优先搜索法 v 爬山法爬山法状态空间表示法的基本思想：状态空间表示法的基本思想：定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来；定义一组算符，通过使用算符可把问题由一种状态转变为另种状态。问题的求解过程是个不断

32、把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成的序列。例子例子1 1：重排九宫问题，在3x3的方格棋盘上放置分别标有数字1、2、3、4、5、6、7、8共8个棋子，初始状态为S0，目标状态为Sg，如图所示。可使用的算符有：空格左移，空格上移，空格右移，空格下移。即只允许把位于空格左、上、右、下的邻近棋子移入空格。要求寻找从初始状态到目标状态的路径。由图2可以看出，解的路径是：S0381626 该路径使用的算符序列：空格上移，空格左移，空格下移，空格右移。“与或树与或树”表示法的基本思想表示法的基本思想 “与或树与

33、或树”表示法也称为问题归约方法（包括分解与表示法也称为问题归约方法（包括分解与等价变换）。等价变换）。分解：把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干个更为简单的子问题。重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。例如，把问题P分解为三个子问题P1，P2，P3，可用图表示。P1，P2，P3是问题P的三个子问题，只有当这三个子问题都可解时，问题P才可解，称P1，P2，P3之间存在“与”关系；称节点P为“与”节点；由P、P1，P2，P3所构成的图称为“与”树。在图中，为了标明某个节点是“与

34、”节点，通常用一条弧把各条边连接起来。等价变换：对于一个复杂问题，除了可用“分解”方法进行求解外，还可利用同构或同态的等价变换，把它变换成若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。问题的等价变换过程也可用一个图表示出来，称为“或”树。分解和等价变换也可结合起来使用，此时的图称为“与/或”树。其中既有“或”节点，也有“与”节点，如右图所示。4.2.3 4.2.3 搜索技术搜索技术1.1.问题求解过程的形式表示问题求解过程的形式表示2.2.盲目搜索方法盲目搜索方法3.3.启发式搜索启发式搜索v 状态空间表示法状态空间表示法 v 与或树表示法与或树表示法 v 广度优先搜

35、索法广度优先搜索法v 生成测试法生成测试法v 深度优先搜索法深度优先搜索法 v 爬山法爬山法广度优先搜索法广度优先搜索法（1 1）基本思想）基本思想 从初始状态S0开始，利用算符，生成所有可能的后继状态，构成下一层节点，检查目标节点G是否出现，若未出现，就对该层所有的状态节点，分别顺序利用算符，成生该层所有节点的后继节点，再检查是否出现G，若未出现，继续生成再下层的所有状态节点，这样一层一层展开，直到目标出现。S0S1S2S3S11S12S21S22S31S111S121S122S221S311G（2 2）算法）算法1)把初始节点S0故入OPEN表。2)如果OPEN表为空，则问题无解，退出。3

36、)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表。4)考察节点n是否为目标节点。若是，则求得了问题的解，退出。5)若节点n不可扩展，则转第2)步。6)扩展节点n，将其子节点放入OPEN表的尾部，并为每一 个子节点都配置指向父节点的指针，然后转第2)步。广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许多无用节点，因此搜索效率低，但是，只要问题有解，用宽度优先搜索总可以得到解，而且得到的是路径最短的路径。深度优先搜索法深度优先搜索法（1 1）基本思想）基本思想 从初始状态S0开始，利用算符，生成搜索树下一层的任意一个节点，检查目标节点是否出现，若未出现，以此节点利用一

37、个算符生成再下一层的任一节点，然后再检查目标节点是否出现，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新的状态节点），当它仍不是目标节点时，回溯到上一层，取另一可能扩展搜索的分支。生成新的状态节点。仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态节点。如此一直下去，直到目标节点出现。S0S1S2S3S11S12S21S22S31S111S121S122S221S311G（2 2）算法）算法1)把初始节点S0故入OPEN表。2)如果OPEN表为空，则问题无解，退出。3)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表。4)考察节点n是否为目标节点。

38、若是，则求得了问题的解，退出。5)若节点n不可扩展，则转第2)步。6)扩展展节点n，将其全部子节点放入到OPEN表的首部，并为其配置指向父节点的指针，然后转第2)步。例子例子2 2：对图所示的重排九宫问题进行深度优先搜索，可得到的搜索树这只是搜索树的一部分，尚未到达目标节点，仍需继续往下搜索。在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。显然，用深度优先求得的解，也不一定是路径最短的解。4.2

39、.3 4.2.3 搜索技术搜索技术1.1.问题求解过程的形式表示问题求解过程的形式表示2.2.盲目搜索方法盲目搜索方法3.3.启发式搜索启发式搜索v 状态空间表示法状态空间表示法 v 与或树表示法与或树表示法 v 广度优先搜索法广度优先搜索法v 生成测试法生成测试法v 深度优先搜索法深度优先搜索法 v 爬山法爬山法启发式搜索启发式搜索 基本思想：对每个在搜索过程中遇到的新状态，用一个估计函数（启发式函数）并计算其值的大小，确定下一步将从哪个状态开始继续前进。v 启发式函数的一般形式为：f(x)g(x)h(x)g(x)为从初始节点S0到节点x已经实际付出的代价；h(x)是从节点x到目标节点Sg的

40、最优路径的估计代价。f(x)为从初始节点S0到目标节点Sg的总代价；例例3 3：重排九宫问题，在3x3的方格棋盘上放置分别标有数字1、2、3、4、5、6、7、8共8个棋子，初始状态为S0，目标状态为Sg，如图所示。要求用启发式搜索从初始状态到目标状态的路径。6 64个不在位g(n)代表结点搜索的深度，表示单位消耗的情况；h(n)代表结点“不在位”的棋子数；f(n)可估计出通向目标结点的希望程度；设计估计函数：设计估计函数：f(n)=g(n)+h(n)不在位棋子数的计算方法：6 621348765初始初始S0C213487562134865721348765AB216 6h=4f(n)=4213

41、874562138745621347856DEF43h=3h=3h=4f(n)=5f(n)=5f(n)=6h=3h=4h=2h=4f(n)=6f(n)=7f(n)=5f(n)=71734285618342756MN7h=0h=2f(n)=5f(n)=782437156273486152143785621437856GHIJ5183274566K1 8327456Lh=1f(n)=5h=3f(n)=7h=5h=3h=5f(n)=6f(n)=6f(n)=44.3 4.3 专家系统与智能决策支持系统专家系统与智能决策支持系统4.3.1 专家系统的原理4.3.2 产生式规则专家系统4.3.3 专家系统

42、与决策支持系统的集成4.3.4 建模专家系统定义：定义：专家系统（专家系统（Expert SystemExpert System，ESES）是指具有大量专门知识，）是指具有大量专门知识，并能运用这些知识解决特定领域中实际问题的计算机程序系统。并能运用这些知识解决特定领域中实际问题的计算机程序系统。近年来这个术语已经被一个更中性的术语近年来这个术语已经被一个更中性的术语“基于知识的系统基于知识的系统”（Knowledge-Based SystemsKnowledge-Based Systems，KBSKBS）或）或“知识系统知识系统”（Knowledge Knowledge SystemsSys

43、tems，KSKS）替代了）替代了 。ESES模仿专家的推理过程进行专门问题的求解，它的能力来源于它所模仿专家的推理过程进行专门问题的求解，它的能力来源于它所拥有的专门知识和推理机制。拥有的专门知识和推理机制。定义：定义：专家，是指掌握了某一特定领域的专业知识、解决问题的能专家，是指掌握了某一特定领域的专业知识、解决问题的能力达到了一定水平、拥有丰富的实践经验的学者。力达到了一定水平、拥有丰富的实践经验的学者。4.3.1 专家系统的原理1、1968年，DENDRAL系统是一种帮助化学家判断某待定物质的分子结构专家系统。1965年在美国斯坦福大学研制，用lisp语言编写；2、1971年，MACS

44、YMA符号数学专家系统；3、1973年，MYCIN医疗系统；4、1976年，PROSPETOR地质勘探专家系统。专家系统的产生与发展专家系统的产生与发展 专家系统已成为世界各国最热门的竞争性研究课题，日专家系统已成为世界各国最热门的竞争性研究课题，日本、美国、英国等国家纷纷将其列为国家重点研究项目，投本、美国、英国等国家纷纷将其列为国家重点研究项目，投入了大量的人力和资金，入了大量的人力和资金，日本把专家系统作为第五代计算机日本把专家系统作为第五代计算机研究的核心内容，英国已将专家系统智能数据库列入国家研究的核心内容，英国已将专家系统智能数据库列入国家四大重点项目四大重点项目。我国对于专家系统

45、的研究工作起步较晚，但经过我国对于专家系统的研究工作起步较晚，但经过2020年的年的艰苦努力，已经在理论研究和应用开发方面取得了很大进展，艰苦努力，已经在理论研究和应用开发方面取得了很大进展，在在中医治疗、油井记录分析、地震预测、气象预报、军事指中医治疗、油井记录分析、地震预测、气象预报、军事指挥、作战模拟、战场管理挥、作战模拟、战场管理等方面研制了一批专家系统。等方面研制了一批专家系统。专家系统的产生与发展专家系统的产生与发展专家系统应该具备以下四个要素专家系统应该具备以下四个要素:(1)(1)应用于某专门领域；应用于某专门领域；(2)(2)拥有专家级知识；拥有专家级知识；(3)(3)能模拟

46、专家的思维；能模拟专家的思维；(4)(4)能达到专家级水平。能达到专家级水平。专家系统专家系统是应用于某一专门领域、拥有该领域相当是应用于某一专门领域、拥有该领域相当数量的专家级知识、能模拟专家的思维、能达到专家级数量的专家级知识、能模拟专家的思维、能达到专家级水平、能像专家一样解决困难和复杂的实际问题的计算水平、能像专家一样解决困难和复杂的实际问题的计算机机(软件软件)系统。系统。专家系统的基本概念专家系统的基本概念p专家专家能够认识并描述问题；能够认识并描述问题；能够快速并恰当地处理问题；能够快速并恰当地处理问题；解释问题解决方案；解释问题解决方案；能从实践中学习；能从实践中学习；调整知识

47、；调整知识；能够打破规则。能够打破规则。专家专家 、专家知识、专家知识的转化、专家知识、专家知识的转化专家系统的基本概念专家系统的基本概念p专家知识：通过训练、阅读和实践而获得的广泛专家知识：通过训练、阅读和实践而获得的广泛的、与问题有关的专门知识。的、与问题有关的专门知识。问题的领域知识问题的领域知识规则（启发性）规则（启发性）全局策略全局策略元知识元知识 事实事实专家系统的基本概念专家系统的基本概念p专家知识的转化专家知识的转化ESES的目标的目标 把专家的知识转化到计算机中，并为非专家使用。把专家的知识转化到计算机中，并为非专家使用。活动活动知识获取知识获取知识表示知识表示知识推理知识推

48、理 知识转换知识转换知识存于知识库中知识存于知识库中p专家系统的特点专家系统的特点具有丰富的经验和知识，能运用知识高效地推出结论；具有丰富的经验和知识，能运用知识高效地推出结论；能进行符号处理；能进行符号处理；能根据不确定的知识进行推理；能根据不确定的知识进行推理；具有元知识；具有元知识；知识的独立性；知识的独立性；推理不是固定形式。推理不是固定形式。专家系统的基本概念专家系统的基本概念专家系统与知识系统的关系专家系统与知识系统的关系 专家系统拥有的知识是专家知识，而且主要是经验性知专家系统拥有的知识是专家知识，而且主要是经验性知识。识。知识系统知识系统(KnowledgeBasedKnowl

49、edgeBased System)System)的知识已不限于专的知识已不限于专家的经验知识，可以是领域知识或通过机器学习所获得的知家的经验知识，可以是领域知识或通过机器学习所获得的知识等。识等。专家系统不会疲劳、遗忘，不受环境、情绪的影响，具专家系统不会疲劳、遗忘，不受环境、情绪的影响，具有计算速度快、计算结果准确等优点；有计算速度快、计算结果准确等优点；专家系统可以快速升级与复制。专家系统可以快速升级与复制。专家系统与专家的比较专家系统与专家的比较专家系统与数据库检索的关系专家系统与数据库检索的关系数据库中存放的记录可以看成是事实性知识。如果把数据库中存放的记录可以看成是事实性知识。如果把

50、检索数据库记录看成是推理的话，它也是一种知识推理。检索数据库记录看成是推理的话，它也是一种知识推理。它与专家系统的不同在于：它与专家系统的不同在于：知识只含事实性知识，不包含规律性知识。知识只含事实性知识，不包含规律性知识。推理是对已有记录的检索，记录不存在，则检索推理是对已有记录的检索，记录不存在，则检索不到。不能适应变化的事实，推理不出新事实。不到。不能适应变化的事实，推理不出新事实。算法（推理过程）是固定形式的。算法一经确定，推算法（推理过程）是固定形式的。算法一经确定，推理过程就固定了。而专家系统的推理是不固定形式的，理过程就固定了。而专家系统的推理是不固定形式的，随着问题不同，推理过