ch决策支持系统新

决策支持系统系统工程专业本科学员必修课第四章智能决策支持系统和智能技术的决策支持人工智能基本原理本章内容智能决策支持系统概述专家系统与智能决策支持系统神经网络的决策支持遗传算法的决策支持机器学习的决策支持4.1智能决策支持系统概述4.1.1智能决策支持系统概念4.1.2智能决策支持系统结构1981年，Bonczek提出了DSS三系统结构，该结构中有“知识系统”，使得不少学者将DSS划为人工智能的范畴，研究知识表示与知识推理，这样，DSS与人工智能的专家系统的界限变得模糊了。1980年，Spraque提出DSS的三部件结构，是传统DSS结构的典型代表。

IDSS实际上就是在DSS基础上增加了知识部件。4.1.1智能决策支持系统概念知识部件知识库知识管理系统推理机4.1.2智能决策支持系统结构1.人工智能的决策支持技术（1）专家系统（2）神经网络（3）遗传算法（4）机器学习（5）自然语言理解2.智能决策支持系统结构形式（1）IDSS的基本结构形式问题综合与交互系统模型库管理系统数据库管理系统人工智能技术专家系统神经网络遗传算法机器学习自然语言理解模型库数据库（2）IDSS的简化结构图问题综合与交互系统模型库管理系统数据库管理系统知识库管理系统推理机模型库数据库知识库用户4.2人工智能基本原理4.2.1逻辑推理4.2.2知识表示与知识推理4.2.3搜索技术4.2.1逻辑推理1.形式逻辑（1）概念：概念反映事物的特有属性和属性的取值。（3）推理：从一个或多个判断推出一个新判断的过程。（2）判断：对概念的肯定或否定；是研究人的思维形式及其规律的科学，主要用于形成概念，作出判断，进行推理。2推理的种类演绎推理归纳推理类比推理假言推理三段论推理数学归纳法假言易位推理枚举归纳推理（1）假言推推理：“如果p，那么q”为真，同时“p”为真，则推出出“q”为真。p→q，p┝q（2）三段论论推理：“如果p，那么q”为真，同时“如果q，那么r”为真，则推出出“如果p，那么r”为真。p→q，q→→r┝p→r（3）假言易位推理理：“如果p，那么q”为真，同时“非q”为真，则推出出“非p”为真。p→q，～q┝～p演绎推理（1）数学归纳法：A包含B1、B2，……A真B1真，Bn

→Bn＋1归纳推理（2）枚举归纳推理：由所见的某一类事物的部分分子具有某种属性，而且没有遇到相反的情况，于是得出这一类事物都具有这种属性的一般性结论。S1是P，S2

是P……Sn是P，S1…Sn是S类中的部分分子，而且没有遇到相反的事例

所以，S类事物都是P类比推理：A事物有a、b、c、、d属性，B事物有a、b、c属性（或a，、b，、c，相似属性）所以，B事物也可能有有d属性（或d，相似属性）由两个（或两两类）事物在在某些属性上上相同，进而而推断它们在在另一个属性性也可能相同同的推理。3.总结（1）演绎推推理的结论没没有超出已知知的知识范围围，而归纳推推理和类比推推理的结论超超出了已知的的知识范围；；（2）演绎推推理中由于前前提和结论有有必然联系，，只要前提为为真，结论一一定为真。归归纳推理和类类比推理中前前提和结论，，不能保证有有必然联系，，具有或然性性。这样的结结论未必是可可靠的，需要要经过严格的的验证和证明明。4.2.2知知识、知知识表示

知识是加工了的、深思熟虑过的、经过推理了的、已经达成共识的关于实体的状态以及实体之间的联系的一系列事实，可以用来指导行动，是理解自然规律并根据自然规律预测实际系统行为的能力。知识的概念：是以各种不同同方式把多个个信息关联在在一起的信息息结构。是人人们对客观事事物及其规律律的认识，知知识还包括人人们利用客观观规律解决实实际问题的方方法和策略等等。描述性知识：表示对象及概念的特征及其相互关系的知识，及问题求解状况的知识，也称为事实性知识。判断性知识：表示与领域有关的问题求解知识，如推理规则等，也称启发性知识。过程性知识：表示问题求解的控制策略，即如何应用判断性知识进行推理的知识。计算机所处理的知识，按其作用可大致分为三类：知识按其作用的层次可分为两类：对象级知识：直接描述有关领域对象的知识元级知识：描述对象级知识的知识4.2.2知知识、知知识表示4.2.2知知识、知知识表示知识表示：知识表示是对对知识的一种种描述，或者者说是一组约约定，是一种种计算机可以以接受的、用用于描述知识识的数据结构构，对知识进进行表示就是是把知识表示示成便于计算算机存储和利利用的某种数数据结构。知识表示的要要求1）表示能力：：能够将问题题求解所需的的知识正确有有效地表达达出来；2）可理解性：：所表达的知知识简单、易易于理解；3）可访问性：：能够有效地地利用所表达达的知识；4）可扩充性：：能够方便地地对知识进行行扩充。4.2.2知知识、知知识表示知识表示的方法谓词逻辑产生式规则语义网络框架剧本谓词逻辑的合合法表达式也也称合式公式式。它由原子子公式、连接接词和量词组组成。原子公式：由由谓词、括号号和括号中的的项组成办公地点关系刘凌401陈东华402张明亮418办公地点（刘刘凌、401）办公地点（陈陈东华、402）办公地点（张张明亮、418）1一阶谓词逻辑辑兰色（盒子））颜色（盒子、、兰色）值（颜色、盒盒子、兰色））盒子是兰色的的原子公式：由由谓词、括号号和括号中的的项组成谓词逻辑的合合法表达式也也称合式公式式。它由原子子公式、连接接词和量词组组成。1一阶谓词逻辑辑连接词：用来来组合原子公公式以形成较较复杂的合式式公式。∧—合取：P∧Q，当P、Q皆为真时，才才为真，否则则为假；类似似“AND”∨—析取：P∨Q，当P、Q皆为假时，则则为假，否则则为真；类似似“OR”—蕴涵：P=>Q,只有P为真，Q为假时，蕴涵涵式为假，否否则为真；~—否定：~P，当P为假时，才为为真，否则为为假。1一阶谓词逻辑辑PQP=>QTTTTFFFTTFFT1一阶谓词逻辑辑量词：、，分分别为全称量量词和存在量量词。例子：“张张某送给屋屋里的每个个人一件礼礼物”（y）{[IN(y,ROOM)∧∧HUMAN(y)]=>(x)[GIVE(ZHANG,x,y)∧∧PRESENT(x)]}1一阶谓词逻逻辑2产生式式规则产生式(Production)一词，首先先是由美国国数学家波波斯特（E.Post）提出来的。。波斯特根根据替换规规则提出了了一种称为为波斯特机机的计算模模型，模型型中的每一一条规则当当时被称为为一个产生生式。后来来，这一术术语几经修修改扩充，，被用到许许多领域。。例如，形形式语言中中的文法规规则就称为为产生式。。产生式也称称为产生式式规则，或或简称规则则。2产生式式规则产生式规则则的一般形形式为：前件→后件件其中，前件件就是前提提，后件是是结论或动动作，前件件和后件可可以是由逻逻辑运算符符AND、OR、NOT组成的表达达式。2产生式式规则产生式规则则知识一般般表示为：：ifAthenB产生式规则则的语义：如果前提满满足，则可可得结论或或者执行相相应的动作作，即后件件由前件来来触发。所所以，前件件是规则的的执行条件件，后件是是规则体。。例如，下面面就是几个个产生式规规则：(1)如果果银行存款款利率下调调，那么股股票价格上上涨；(2)如果果炉温超过过上限，则则立即关闭闭风门；(3)如果果键盘突然然失灵且屏屏幕上出现现怪字符，，则是病毒毒发作；一条产生式式规则就是是一条知识识。用产生生式可以实实现推理和和操作，产生式规则则是知识表表示形式。产生式规则则知识有正向和逆向两种推理方方式。（1）正向向推理逐条搜索规规则库，对对每一条规规则的前提提条件都检检查事实库库中是否存存在；对前提条件件中各子项项，若事实实库中不是是全部都存存在，放弃弃该条规则则；若在事实库库中全部存存在，则执执行该条规规则，并结结论放入到到事实库中中；反复执行上上述过程，，直至推出出目标，并并存放入事事实库中。。算法：例如：在产产生式规则则库中有3条规则，，在事实库库中存在B、C、E3个事实，且且它们均为为真。希望望通过正向向推理，证证明目标G为真。B、C、E1、AB->G2、CD->A3、E->DVV产生式规则库事实库推理过程：：（1）正向向推理（2）逆向向推理从目标开始始，寻找以以此目标为为结论的规规则，并对对该规则的的前提进行行判断；若该规则的的前提中某某个子项是是另一规则则的结论，，再找此结结论的规则则；重复上述过过程，直到到对某个规规则的前提提能够进行行判断；按此规则前前提的判断断得出结论论的判断，，由此回溯溯到上一个个规则的推推理，一直直回溯到目目标的判断断。算法：B、C、E1、AB->G2、CD->A3、E->DVV产生式规则库事实库推理过程：GBACDE（2）逆向向推理从概念结点点间问它们们之间的关关系通过概念和和关系问其其他结点由J.R.Quilian于1968年在研究究人类联想想记忆时提提出的一种种心理学模模型。3语义网网络基本思想：

用结点表示概念，用弧线表示概念之间的关系，将领域知识表示成一种结构图形式；在语义网络中，寻找概念之间的内在联系，主要通过语义网络的形式推理来回答两类问题：3语义网网络结点代表实体，，表示各种种事物、概概念、情况况、属性、、状态、事事件、动作作等；语义单元是由有向图图表示的三三元组(结结点1,弧弧,结点2)结点1结点2语义关系弧是有方向和和标注的，，方向体现现了结点所所代表的实实体的主次次关系，即即结点1为为主，结点点2为辅；；标注表示所连接接的两个实实体之间的的语义联系系。试用语义网网络表示命命题“某学校小学学生坐车去去春游”。动作方式某学校小学生动作目的春游坐车属于3语义网网络基本的语义义关系(1)Is-a和Part-of型关系Is-a：表示一个事物是另一个事物的实例，表示具体与抽象关系，此关系的一个最主要的特点是属性的继承关系。灵长类动物Is-aIs-a型语义网络3语义网网络轮胎汽车Part-ofPart-of型语义网络(1)Is-a和Part-of型关系Part-of：表示一个个事物是另另一个事物物的一部分分，是部分分与整体的的关系。基本的语义义关系3语义网网络Is：表示一个个结点是另另一个结点点的属性中国的陆地面积960万平方公里IsIs型语义网络(1)Is-a和Part-of型关系基本的语义义关系3语义网网络(2)属性性(类属)关系Have：表示一个个结点具有有另一个结结点所描述述的属性

Have属性关系语义网络鸟翅膀Have基本的语义义关系3语义网网络(2)属性性(类属)关系A-Kind-of：表示一个个事物是另另一个事物物的一种类类型，表示示隶属关系系。

AKO属性关系语义网络鸭嘴兽哺乳动物A-Kind-of基本的语义义关系3语义网网络(2)属性性(类属)关系Can：表示一个个结点能做做另一个结结点的事情情。

Can属性关系语义网络草鱼水草eat基本的语义义关系3语义网网络(3)其他他关系时间关系：指不同事事物在其发发生时间方方面的先后后关系。Before：表示一个事物在一个事物之前发生；After：表示一个事物在一个事物之后发生；位置关系：指不同事事物在位置置方面的关关系。Located-onLocated-atLocated-underLocated-insideLocated-outside3语义网网络语义网络的的推理语义的推理理过程主要要有两种：：继承和匹配

继承的思想：对事物的描述从抽象结点传递到具体结点，从而得到所需结点的属性值，通常是沿着Is-a，A-Kind-of等继承弧进行。3语义网网络语义网络的的推理3语义网网络语义网络继承推理示意图

小米谷物麻雀1麻雀鸟动物翅膀飞行工具AKOAKOAKOIs-aIs-aeatHave匹配的思想：在知识库的语义网络中寻找与待求问题相符的语义网络模式。

小米谷物麻雀1麻雀鸟动物翅膀飞行工具AKOAKOAKOIs-aIs-aeatHave举例：已知知麻雀是一一种鸟，求求麻雀的特特点。某港海浪动作对象海浪战舰轻轻isa动作方式晃动isa某港战舰

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

<槽名1>slot<槽名2>slot<侧面21>值21<侧面22>值22……<侧面11>值11<侧面12>值12……下面是一个个描述“教教师”的框框架：框架名：<教师>类属：<知知识分子>工作：(教学，科科研)缺省：教学学性别：(男男，女)学历：(中中师，高师师)类型：(<小学教师师>，<中中学教师>，<大学学教师>)框架架框架架槽值可以以有如下下几种类类型：具体值value默认值default过程值procedure：：该值是一一个计算算过程，，它利用用该框架架的其它它槽值，，按给定定计算过过程（公公式）进进行计算算得出具具体值。。另一框架架名：当当槽值是是另一框框架名时时，就构构成了框框架调用用，这样样就连成成了一个个框架链链。有关关框架聚聚集起来来就组成成框架系系统。空（待填填入）框架框架是知知识表示示的基本本单位。。不同的框框架之间间可以通通过属性性之间关关系建立立联系，，从而构构成一个个框架网网络，充充分表达达相关对对象间的的各种关关系。特点：主主要描述述事物的的内部结结构及事事物之间间的类属属关系。。框架名：：<倒萨萨>动作：攻攻打动作发出出者：美美国动作接受受者：伊伊拉克后果：<反击>，<成成功>框架名：：<反击击>动作：抵抵抗动作发出出者：伊伊拉克动作接受受者：美美国后果：<倒萨>，<失失败>框架名：：<成功功>动作：投投降动作发出出者：伊伊拉克动作接受受者：美美国后果:萨达达姆政府府垮台框架名：：<失败败>动作：撤撤军动作发出出者：美美国后果：遭遭国际社社会谴责责框架推理理的主要要形式为为：填充充槽值。。填充槽值值的主要要方法为为：匹配配、继承承。匹配：在在求解某某个问题题时，先先把问题题用一个个框架表表示出来来，然后后与知识识库中的的已有框框架进行行匹配。。如果匹匹配成功功，就可可获得有有关信息息。继承：子子框架可可以拥有有其父框框架的槽槽及其槽槽值。框架(1)匹匹配配框架是一一类事物物的完整整描述。。事物之之间匹配配只能是是部分相相同槽的的匹配。。框架1：：王强是人人性别男男行动音量进取心中中等等框架2：：消防车车是车车辆颜色红红行动快快音量极极高载物水水匹配此两框架的槽：行动和音量。得到王强的行动是快的，音量是极高的。框架例：王强强的行动动和音量量象消防防车。我我们要知知道王强强的行动动和音量量究竟是是什么，，应该对对两个框框架进行行匹配。。框架(2)继继承承有两种继继承，即即直接继继承和时时序继承承。直接继承承：在框架架网络中中下层框框架直接接从上层层框架架中继承承所有的的属性值值和条件件。如““墙”继继承“房房子”的的所有属属性时序继继承：有条条件的的继承承。框架例：框框架名名：旧旧中国国政体：：资产产阶级级专政政面积：：960万万平方方公里里人口：：4亿亿5千千万领导党党派：：国民民党框架名名：新新中国国政体：：人民民民主主专政政面积：：人口：：4亿亿5千千万（（当时时1949年））领导党党派：：共产产党其中，，面积积和人人口是是相同同的，，其它它槽值值就改改变了了。这这就是是有条条件的的继承承。关于框框架的的例子子例描描述学学校的的框架架框架名名：<学校校>类属：：<教教育机机构>类型型：：范范围围(大大学学，，中中学学，，小小学学)位置置：：(省省(直直辖辖市市)，，市市)面积积：：单单位位(平平方方米米)教工工人人数数：：学生生人人数数：：例描描述述大大学学的的框框架架框架架名名：：<大大学学>类属属：：<学学校校>类型型：：范范围围(综综合合性性大大学学，，专专科科性性大大学学)专业业：：默默认认值值：：综综合合学院院数数：：教学学楼楼：：教工工人人数数：：学生生人人数数：：位置置：：(省省(直直辖辖市市)，，市市)面积积：：单单位位(平平方方米米)例描描述述某某所所大大学学的的框框架架框架架名名：：<大大学学1>类属属：：<大大学学>姓名名：：中中国国医医科科大学学专业业：：医医学学学院院数数：：13教学学楼楼：：20办公公楼楼：：40学生生宿宿舍舍：：20教工工宿宿舍舍：：60教工工人人数数：：4000职工工人人数数：：5000学生生人人数数：：20000位置置：：北北京京市市面积积：：10000万万平平方方米米创建时间：2002年4月1、有的槽有有槽值，有的的槽值不明显显，有的槽没没有槽值，有有的槽值是一一个框架名；；2、这3个框框架是层层嵌嵌套的，上位位框所具有的的属性，下位位框也一定具具有，下位框框可以从上位位框继承某些些槽值和侧面面值。3、框架的推推理基于匹配配和继承的原原则。剧本剧本是描述一一定范围内一一串原型事物物的结构。剧本由六部分分组成：(1)开场场条件：事件发生之之前必须满足足的条件。例如，肚子饿饿了需要进餐餐，且有钱等等。(2)结局局：事件发生之之后，通常会会成为现实的的情况。例如，肚子不不再饿了，花花了钱等。(3)道具具：用来表示与与剧本所描述述的事件有关关的物体。例如，餐桌、、菜单、食物物等。(4)角色色：剧本中描述述事件中的人人物。例如，经理、、顾客、服务务员等。(5)线索索：剧本表达事事件的时序模模式。例如，小食店店、餐厅、酒酒家等。(6)场次次：事件发生的的顺序。每个个场次可用框框架描述。剧本剧本特点：结构呆板，，知识表示范范围窄，不适适合用于表达达各种知识，，但对于表达达事先构思好好的特定知识识非常有效。。回顾人工智能基本原理知识表示与知识推理谓词逻辑产生式规则语义网络框架剧本智能决策支持持系统结构4.2.3搜搜索技术术1.问题求解解过程的形式式表示2.盲目搜索索方法3.启发式搜搜索状态空间表示示法与或树表示法法

广度优先搜索法生成测试法

深度优先搜索法

爬山法状态空间表示示法的基本思思想：定义状态的描描述形式，通通过使用这种种描述形式可可把问题的一一切状态都表表示出来；定定义一组算符符，通过使用用算符可把问问题由一种状状态转变为另另—种状态。问题题的求解过程程是—个不断把算符符作用于状态态的过程。如果在使用某某个算符后得得到的新状态态是目标状态态，就得到了了问题的一个个解。这个解解是从初始状态到目目标状态所用用算符构成的的序列。例子1：重排九宫问题题，在3x3的方格棋盘上上放置分别标标有数字1、、2、3、4、5、6、、7、8共8个棋子，初初始状态为S0，目标状态为Sg，如图所示。可使用的算符符有：空格左移，空空格上移，空空格右移，空空格下移。即即只允许把位位于空格左、、上、右、下下的邻近棋子子移入空格。。要求寻找从从初始状态到到目标状态的的路径。由图2可以看看出，解的路路径是：S0——3——8——16——26该路径径使用用的算算符序序列：：空格格上移移，空空格左左移，，空格格下移移，空空格右右移。。“与或树树”表示法法的基基本思思想“与或树树”表示法法也称称为问问题归归约方方法（（包括括分解解与等等价变变换））。分解：把一一个复复杂问问题分分解为为若干干个较较为简简单的的子问问题，，每个个子问问题又又可继继续分分解为为若干干个更更为简简单的的子问问题。。重复复此过过程，，直到到不需需要再再分解解或者者不能能再分分解为为止。。然后后对每每个子子问题题分别别进行行求解解，最最后把把各子子问题题的解解复合合起来来就得得到了了原问问题的的解。。例如如，，把把问问题题P分解解为为三三个个子子问问题题P1，P2，P3，可用用图图表表示示。。P1，P2，P3是问问题题P的三三个个子子问问题题，，只只有有当当这这三三个个子子问问题题都都可可解解时时，，问问题题P才可可解解，，称称P1，P2，P3之间间存存在在“与”关系系；；称称节节点点P为“与”节点点；；由由P、、P1，P2，P3所构构成成的的图图称称为为“与”树。。在在图图中中，，为为了了标标明明某某个个节节点点是是“与”节点点，，通通常常用用一一条条弧弧把把各各条条边边连连接接起起来来。。等价价变变换换：对对于于一一个个复复杂杂问问题题，，除除了了可可用用“分解解”方法法进进行行求求解解外外，，还还可可利利用用同同构构或或同同态态的的等等价价变变换换，，把把它它变变换换成成若若干干个个较较容容易易求求解解的的新新问问题题。。若若新新问问题题中中有有一一个个可可求求解解，，则则就就得得到到了了原原问问题题的的解解。。问问题题的的等等价价变变换换过过程程也也可可用用一一个个图图表表示示出出来来，，称称为为“或”树。。分解解和和等等价价变变换换也也可可结结合合起起来来使使用用，，此此时时的的图图称称为为“与/或或”树。。其其中中既既有有“或”节点点，，也也有有“与”节点点，，如如右右图图所所示示。。4.2.3搜搜索索技技术术1.问题求解过程的形式表示2.盲目搜索方法3.启发式搜索

状态空间表示法

与或树表示法

广度优先搜索法生成测试法

深度优先搜索法

爬山法广度度优优先先搜搜索索法法（1））基基本本思思想想从初初始始状状态态S0开始始，，利利用用算算符符，，生生成成所所有有可可能能的的后后继继状状态态，，构构成成下下一一层层节节点点，，检检查查目目标标节节点点G是否否出出现现，，若若未未出出现现，，就就对对该该层层所所有有的的状状态态节节点点，，分分别别顺顺序序利利用用算算符符，，成成生生该该层层所所有有节节点点的的后后继继节节点点，，再再检检查查是是否否出出现现G，，若未未出出现现，，继继续续生生成成再再下下层层的的所所有有状状态态节节点点，，这这样样一一层层一一层层展展开开，，直直到到目目标标出出现现。。S0S1S2S3S11S12S21S22S31S111S121S122S221S311G（2））算算法法1)把把初初始始节节点点S0故入入OPEN表。。2)如如果果OPEN表为为空空，，则则问问题题无无解解，，退退出出。。3)把把OPEN表的的第第一一个个节节点点(记记为为节节点点n)取出出放放入入CLOSED表。。4)考考察察节节点点n是否否为为目目标标节节点点。。若若是是，，则则求求得得了了问问题题的的解解，，退退出出。。5)若若节节点点n不可可扩扩展展，，则则转转第第2)步步。。6)扩扩展展节节点点n，，将其其子子节节点点放放入入OPEN表的的尾尾部部，，并并为为每每一一个个子子节节点点都都配配置置指指向向父父节节点点的的指指针针，，然然后后转转第第2)步步。。广度度优优先先搜搜索索的的盲目目性性较较大大，当当目目标标节节点点距距离离初初始始节节点点较较远远时时将将会会产产生生许许多多无无用用节节点点，，因因此此搜搜索索效效率率低低，，但但是是，，只只要要问问题题有有解解，，用用宽宽度度优优先先搜搜索索总可以以得得到到解解，，而而且且得得到到的的是是路路径径最短短的的路路径径。深度度优优先先搜搜索索法法（1））基基本本思思想想从初初始始状状态态S0开始始，，利利用用算算符符，，生生成成搜搜索索树树下下一一层层的的任任意意一一个个节节点点，，检检查查目目标标节节点点是是否否出出现现，，若若未未出出现现，，以以此此节节点点利利用用一一个个算算符符生生成成再再下下一一层层的的任任一一节节点点，，然然后后再再检检查查目目标标节节点点是是否否出出现现，，若若未未出出现现，，继继续续以以上上操操作作过过程程，，一一直直进进行行到到叶叶节节点点（（即即不不能能再再生生成成新新的的状状态态节节点点）），，当当它它仍仍不不是是目目标标节节点点时时，，回回溯溯到到上上一一层层，，取取另另一一可可能能扩扩展展搜搜索索的的分分支支。。生生成成新新的的状状态态节节点点。。仍仍不不是是目目标标，，采采用用相相同同的的回回溯溯办办法法回回退退到到上上层层节节点点，，扩扩展展可可能能的的分分支支生生成成新新状状态态节节点点。。如如此此一一直直下下去去，，直直到到目目标标节节点点出出现现。。S0S1S2S3S11S12S21S22S31S111S121S122S221S311G（2）算算法1)把初初始节点点S0故入OPEN表。2)如果果OPEN表为空，，则问题题无解，，退出。。3)把OPEN表的第一一个节点点(记为为节点n)取出放入入CLOSED表。4)考察察节点n是否为目目标节点点。若是是，则求求得了问问题的解解，退出出。5)若节节点n不可扩展展，则转转第2)步。6)扩展展展节点点n，将其全部部子节点点放入到到OPEN表的首部部，并为为其配置置指向父父节点的的指针，，然后转转第2)步。例子2：：对图所示示的重排排九宫问问题进行行深度优优先搜索索，可得得到的搜搜索树这这只是搜搜索树的的一部分分，尚未未到达目目标节点点，仍需需继续往往下搜索索。在深度优先先搜索中，，搜索一旦旦进入某个个分支，就就将沿着该该分支一直直向下搜索索。如果目目标节点恰恰好在此分分支上，则则可较快地地得到解。。但是，如如果目标节节点不在此此分支上，，而该分支支又是一个个无穷分支支，则就不不能得到解解。所以深深度优先搜搜索是不完完备的，即即使问题有有解，它也也不一定能能求得解。。显然，用用深度优先先求得的解解，也不一一定是路径径最短的解解。4.2.3搜索索技术1.问题求解过程的形式表示2.盲目搜索方法3.启发式搜索

状态空间表示法

与或树表示法

广度优先搜索法生成测试法

深度优先搜索法

爬山法启发式搜索索基本思想：对每个在在搜索过程程中遇到的的新状态，，用一个估估计函数（（启发式函函数）并计计算其值的的大小，确确定下一步步将从哪个个状态开始始继续前进进。启发式函数的一般形式为：

f(x)＝g(x)＋h(x)g(x)为从初始节点S0到节点x已经实际付出的代价；h(x)是从节点x到目标节点Sg的最优路径的估计代价。f(x)为从初始节点S0到目标节点Sg的总代价；例3：重排九宫问问题，在3x3的方格棋盘盘上放置分分别标有数数字1、2、3、4、5、6、7、8共8个棋棋子，初始始状态为S0，目标状态为为Sg，如图所示。。要求用启发式搜索索从初始状态态到目标状状态的路径径。64个不在位位g(n)代表结点搜索的深度，表示单位消耗的情况；h(n)代表结点“不在位”的棋子数；f(n)可估计出通向目标结点的希望程度；设计估计函数：f(n)=g(n)+h(n)不在位棋子数的计算方法：621348765初始S0C213487562134865721348765AB216h=4f(n)=4213874562138745621347856DEF43h=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)=782437156273486152143785621437856GHIJ5183274566K18327456Lh=1f(n)=5h=3f(n)=7h=5h=3h=5f(n)=6f(n)=6f(n)=44.3专专家系统与与智能决策策支持系统统4.3.1专家家系统的原原理4.3.2产生生式规则专专家系统4.3.3专家家系统与决决策支持系系统的集成成4.3.4建模模专家系统统定义：专家系统（（ExpertSystem，ES）是指具有有大量专门门知识，并并能运用这这些知识解解决特定领领域中实际际问题的计计算机程序序系统。近年来这个个术语已经经被一个更更中性的术术语“基于于知识的系系统”（Knowledge-BasedSystems，KBS）或“知识识系统”（（KnowledgeSystems，KS）替代了。。ES模仿专家的的推理过程程进行专门门问题的求求解，它的的能力来源源于它所拥拥有的专门门知识和推推理机制。。定义：专家，是指指掌握了某某一特定领领域的专业业知识、解解决问题的的能力达到到了一定水水平、拥有有丰富的实实践经验的的学者。4.3.1专家家系统的原原理1、1968年，DENDRAL系统是是一种种帮助助化学学家判判断某某待定定物质质的分分子结结构专专家系系统。。1965年在美美国斯斯坦福福大学学研制制，用用lisp语言编编写；；2、1971年，MACSYMA符号数数学专专家系系统；；3、1973年，MYCIN医疗系系统；；4、1976年，PROSPETOR地质勘勘探专专家系系统。。1.专家系系统的的概念念与特特点专家系系统的的产生生与发发展专家系系统已已成为为世界界各国国最热热门的的竞争争性研研究课课题，，日本本、美美国、、英国国等国国家纷纷纷将将其列列为国国家重重点研研究项项目，，投入入了大大量的的人力力和资资金，，日本把把专家家系统统作为为第五五代计计算机机研究究的核核心内内容，，英国国已将将专家家系统统／智智能数数据库库列入入国家家四大大重点点项目目。我国对对于专专家系系统的的研究究工作作起步步较晚晚，但但经过过20年的艰艰苦努努力，，已经经在理理论研研究和和应用用开发发方面面取得得了很很大进进展，，在中医治治疗、、油井井记录录分析析、地地震预预测、、气象象预报报、军军事指指挥、、作战战模拟拟、战战场管管理等方面面研制制了一一批专专家系系统。。1.专家系系统的的概念念与特特点专家系系统的的产生生与发发展专家系系统应应该具具备以以下四四个要要素:(1)应用于于某专专门领领域；；(2)拥有专专家级级知识识；(3)能模拟拟专家家的思思维；；(4)能达到到专家家级水水平。。1.专家系系统的的概念念与特特点专家系系统的的基本本概念念专家能够认识并描述问题；能够快速并恰当地处理问题；解释问题解决方案；能从实践中学习；调整知识；能够打破规则。专家、、专专家知知识、、专家家知识识的转转化专家系系统的的基本本概念念专家知知识：：通过过训练练、阅阅读和和实践践而获获得的的广泛泛的、、与问问题有有关的的专门门知识识。问题的的领域域知识识规则（（启发发性））全局策策略元知识识事实专家系系统的的基本本概念念专家知知识的的转化化ES的目标标把专家家的知知识转转化到到计算算机中中，并并为非非专家家使用用。活动知识获获取知识表表示知识推推理知识转转换知识存存于知知识库库中专家系系统的的特点点具有丰丰富的的经验验和知知识，，能运运用知知识高高效地地推出出结论论；能进行行符号号处理理；能根据据不确确定的的知识识进行行推理理；具有元元知识识；知识的的独立立性；；推理不不是固固定形形式。。专家系系统的的基本本概念念专家系系统与与知识识系统统的关关系专家系系统拥拥有的的知识识是专专家知知识，，而且且主要要是经经验性性知识识。知识系系统(KnowledgeBasedSystem)的知识识已不不限于于专家家的经经验知知识，，可以以是领领域知知识或或通过过机器器学习习所获获得的的知识识等。。专家系系统不不会疲疲劳、、遗忘忘，不不受环环境、、情绪绪的影影响，，具有有计算算速度度快、、计算算结果果准确确等优优点；；专家系系统可可以快快速升升级与与复制制。专家系系统与与专家家的比比较专家系系统与与数据据库检检索的的关系系数据库库中存存放的的记录录可以以看成成是事事实性性知识识。如如果把把检索索数据据库记记录看看成是是推理理的话话，它它也是是一种种知识识推理理。它与专专家系系统的的不同同在于于：知识只只含事事实性性知识识，不不包含含规律律性知知识。。推理是是对已已有记记录的的检索索，记记录不不存在在，则则检索索不到到。不不能适适应变变化的的事实实，推推理不不出新新事实实。1.专家系系统的的概念念与特特点算法（（推理理过程程）是是固定定形式式的。。算法法一经经确定定，推推理过过程就就固定定了。。而专专家系系统的的推理理是不不固定定形式式的，，随着着问题题不同同，推推理过过程也也不一一样。。数值计计算只只能处处理数数值，，不能能处理理符号号。数值计计算是是用算算法解解决实实际问问题，，对不不同的的数据据可以以算出出不同同的结结果。。如果果把数数据看看成是是知识识，算算法看看成推推理的的话，，它也也是一一种知知识推推理。。它与与专家家系统统的不不同在在于：：专家系系统与与数值计计算的关系系1.专家系系统的的概念念与特特点专家系系统与与数值计计算和和数值值处理理区别别专家系系统特特点：知识识包括括事实实和规规则；；适合合于符符号处处理；；推理理不固固定于于形式式；能能得出出未知知的事事实；；数值计算和数值处理专家系统数据库检索事实性知识规律性知识推理是对已有记录的检索，记录没有则检索不到能推理出新事实数值计算推理过程固定推理过程不固定只能处理数值既能处理数值，又能处理符号1.专家系系统的的概念念与特特点2.专家系系统的的功能能和结结构存储问问题求求解所所需的的知识识；存储具具体问问题求求解的的初始始数据据和推推理过过程中中的各各种信信息；；利用已已有知知识，，进行行问题题求解解，并并控制制和协协调系系统运运行；；能够对对推理理过程程、结结论或或系统统自身身行为为做出出必要要的解解释；；提供知知识获获取，，机器器学习习以及及知识识库的的维护护手段段；提供用用户接接口，，便于于用户户使用用以及及分析析和理理解用用户的的各种种要求求和请请求。。专家系系统应应具备备功能能：专家系系统的的基本本结构构专家知识获取用户人机接口知识库推理机咨询建议全局数据库2.专家系系统的的功能能和结结构122专家系系统一一般结结构：：基本任任务是是把知知识输输入到到知识识库中中，并并负责责维持持知识识的一一致性性及完完整性性，建建立起起良好好的知知识库库推理机机是专专家系系统的的思维维机构构，其其任务务是模模拟领领域专专家的的思维维过程程，控控制并并执行行对问问题的的求解解。能够对对自己己的行行为做做出解解释，，回答答用户户提出出的“WHYHOW”等问题题，是是专家家系统统区别别于一一般程程序的的重要要特征征之一一，也也是取取信于于用户户的一一个重重要措措施。。人机接接口是是专家家系统统与领领域专专家、、知识识工程程师及及一般般用户户之间间的界界面，，由一一组程程序及及相应应的硬硬件组组成，，用于于完成成输入入输出出工作作。综合数数据库库是初初始事事实、、问题题描述述以及及系统统运行行过程程中的的中间间结果果、最最终结结果、、运行行信息息等的的工作作存储储器。。综合合数据据库是是推理理机不不可缺缺少的的一个个工作作场地地，同同时由由于它它可记记录推推理过过程中中的各各有关关信息息，又又为解解释机机构提提供了了回答答用户户咨询询的依依据。。知识库库是合合理组组织的的关于于某一一特定定领域域的陈陈述型型知识识和过过程型型知识识的集集合。。知识识库和和传统统数据据库的的区别别在于于它不不但包包含了了大量量的简简单事事实，，而且且包含含了规规则和和过程程型知知识。。123专家系统由两两大部分组成成：开发环境、应应用环境知识获取人机接口解释机制推理机专家用户知识库知识工程师文档数据库知识获取的主主要手段（1）面谈法（2）模拟法知识获取（3）机器学习环境学习知识库执行监督选例机器学习系统的结构知识获取的困困难知识获取获取专家启发发性知识是十十分困难的，，其原因：（1）知识表示失失配。（2）专家的启发发性知识是不不精确的。（3）有些启发性性知识表示的的不可能性。。（4）缺乏开发专专家系统的现现代技术。（5）知识测试与与调试的困难难性。知识库(KnowledgeBase)知识库是合理理组织的关于于某一特定领领域的陈述型型知识和过程程型知识的集集合；知识库有两个个主要问题：：知识表示和知识的精确程程度。知识库中知识表示知识表示产生式规则（IF__THEN）谓词逻辑模糊逻辑（真假二值）（0,1连续值）框架语义网络过程性知识剧本知识库中知识识表示的精度度精确知识公式公理原理性不精确知识经验性可信度概率证据理论模糊数学知识精确度知识库管理知识管理包括括：知识的分分类、知识的的组织和存储储、知识的检检索、知识的的增加、知识识的删除、知知识的修改、、知识的拷贝贝和转储、知知识的一致性性、完整性和和无冗余性检检查等。知识库的组织织知识库的组织织应确保知识识库与推理机机的独立；便于知识的扩扩充、维护与与修改；便于知识的运运用和输入／／输出操作；；便于系统中采采用多种知识识表示模式；；便于知识的一一致性、完整整性、无冗余余性的检查与与维护；便于知识的检检索与匹配，，充分考虑知知识运用和处处理的效率；；尽量节省知识识库的占用空空间。知识库管理知识库的管理理与维护知识库的建立立与撤销；知识的增加、、插入、删除除、修改和检检索；知识的一致性性、完整性、、无冗余性检检查与维护；；友好的输出方方式；提供知识字典典，用于知识识的管理与控控制；知识库分块交交换功能；知识库的重组组；知识库的安全全与保密；知识库恢复。。知识库管理（1）在对知识库库进行调试时时，要求解释释系统具有这这样的功能，，即检索知识识库中已有的的内容，跟踪踪专家系统的的运行，并能能记录知识的的运用情况、、上下文中的的各种参数、、中间结果的的演变等，还还能提供出错错信息，能对知识库中中的错误方便便地进行定位位和修改。解释系统这这种辅助发现现和更正知识识库中错误的的作用，对于于专家系统设设计者来说，，起到了“助助手”的作用用。解释机制解释系统的作作用（2）用户操作使使用专家系统统时，要求系系统在问题求求解过程中，，给出推理过过程和推理结结论合理的、、正确的解释释，提高用户户对系统求解解的信赖度，，便于推广应应用并起到辅辅助决策的作作用。（3）由于专家系系统知识库中中的知识一般般是领域专家家的专门知识识，应对非领领域专家的用用户得到一些些直觉的知识识训练，以便便掌握专门知知识，起到““教师”的作作用。解释机制解释系统的作作用准确性。解释释机制对系统统所做的工作作应能给出准准确的描述，，避免解释内内容的冗余和和繁杂；可理解性。解解释机制的解解释应易于理理解，应尽可可能接近自然然语言或领域域的形式语言言；智能性。包括括两个方面：：解释机制尽尽可能易于使使用；尽可能能对用户提出出的问题生成成合理且较快快的解释。解释系统的设设计要求解释机制元知识：关于知识的知知识。知识分为两级级：领域级知识：：特定领域的的知识。元级知识：说说明如何运用用领域知识的的知识。元知识一般采采用与领域级级知识相同的的表示形式，，并作为一个个知识实体与与领域级知识识共存于知识识库中。元知识从领域专家获获取知识工程师在在开发实际系系统过程中获获取从系统的运行行结果中获取取元知识的获取：指导规则的选选择记录与领域知知识有关的事事实规则的论证检查规则中的的错误描述领域知识识表示的结构构论证系统的体体系结构辅助优化系统统说明系统的能能力元知识分类1）指导知识的的选择有一条以上规规则的前提部部分和当前事事实匹配时，，选择规则策策略：策略1：如果某一规规则的前提比比另一规则的的前提更专门门，则则先选用更专专门的规则。。策略2：按规则排列列顺序，先选选用前一条规规则。策略3：优先选用被被满足的条件件较多的规则则。策略4：首先选择执执行代价小的的规则。如有两条规则则AH，ABK，若A，B成立，应先选选第2条。元知识的作用用2）记录与领域域知识有关的的事实记录某种处理理方法的平均均运行时间；；统计一个程序序在运行过程程中询问用户户的次数；统计规则的成成功与失败的的比率等，提提供有关与领领域知识的信信息。3）规则的论证证指出某些规则则存在的理由由，用于推理理的解释。如：R1：如果果溢出液是硫硫酸，则用石石灰。理由：石灰能能中和硫酸，，且所形成的的化合物是不不溶的，能沉淀出出来。4）检查规则中中的错误……4.3.2产产生式规规则专家系统统目前，用于产产生式规则知知识形式建立立专家系统是是最广泛和最最流行。原因：产生式规则知知识表示容易易被人理解；；它是基于于演绎推推理的，，保证了了推理结结果的正正确性；；大量产生生式规则则所连成成的推理理树可以以是多棵棵树，宽宽度反映映实际问问题的范范围，深深度反映映实际问问题的难难度。4.3.2产产生式式规则专专家系统统一.产生生式规则则产生式规规则知识识一般表表示为：：ifAthenB或表示为为“如果A成立则B成立，简简化为A→B。产生式规规则知识识的特点点：(1)相相同的的条件可可以得出出不同的的结论。。如：A─→BA─→C规则集能能描述和和解决各各种不同同的灵活活的实际际问题；；把规则则知识集集中的所所有规则则连成一一棵“与或”树（知识识树），建立这这些规则则之间的的关联。。(4)一条规则则中的结结论，可可以是另另一条规规则中的的条件。。如C∧D→→F，F∧B→→Z(2)相同的结结论可以以由不同同的条件件来得到到。如A─→GB─→G(3)条件之间间可以是是“与”连接和“或”连接如A∧B──→G，，A∨B→G（（相当于A→G，，B→G）知识精确确程度由于专家家的大部部分决策策都是在在知识不不确定的的情况下下作出的的，因此此，在决决策模型型的实际际应用过过程中，，经常使使用可信信度（CF）来表示事事实和规规则的确确信程度度。CF的取值范范围为：：0≤CF≤1或0≤CF≤100二.推理理树（与与或树））基本思想想：按逆向向推理思思想把规规则库所所含的总总目标（（它是某某些规则则的结论论）作为为根结点点，按规规则的前前提和结结论展开开成一棵树的形式。。这棵树一一般称为为推理树树或知识识树，它它把规则则库中的的所有规规则都连连结起来来。由于于连结时时有“与”关系和“或”关系，从从而构成成了“与/或”推理树。。二.推理理树（与与或树））例：若有有规则集集为：A∨（B∧C））→G（I∧J）∨K→AX∧F→→JL→BM∨E→→CW∧Z→→MP∧Q→→E画出“与与、或””推理树树。用规则的的前提和和结论形形式画出出一般的的推理树树形式总目标G(结论)前提A(结论)前提B(结论)前提C(结论)前提J(结论)前提I前提L前提M(结论)前提E(结论)?前提X前提F前提Z前提P前提Q?前提W??????（1）每每条规则则对应的的节点分分支有“与”关系、“或”关系；（2）树树的根节节点是推推理树的的总目标标；（3）相相邻两层层是一条条或多条条规则连连接；（4）每每个节点点可以是是单值，，也可以以是多值值；（5）所所有的叶叶节点，，都安排排向用户户提问，，或者把把它的值值直接存存放在全全局数据据库中。。推理树的的特点：：总目标G(结论)前提A(结论)前提B(结论)前提C(结论)前提J(结论)前提I前提L前提M(结论)前提E(结论)?前提X前提F前提Z前提P前提Q?前提W??????逆向推理理过程在在推理树树中反映映为推理理树的深深度优先先搜索过过程。三逆向向推理过过程N17982GABCJIKLME45YXFZPQ1011123YWYYYN6在计算机机中实现现时，并并不把规规则连成成推理树树，而是是利用规规则栈来来完成。。当调用用此规则则时，把把它压入入栈内（（相当于于对树的的搜索）），当此此规则的的结论已已求出（（yes或no）时，需要要将此规规则退栈栈（相当当于对树树的回溯溯）。规则栈注意对中间结结点的否否定需要要注意的的是，若若当该结结点还有有其它“或条件”分枝时，，不能立立即确定定该结点点为n