智能控制 复习提纲

1智能控制基础上海大学机电工程与自动化学院杜鑫2智能控制基础自动化系仪自教研室内容提要人工智能简介智能控制简介人获取、处理、应用和再生信息（知识），并用之达到预定目的的能力。人应用知识解决问题的能力。人工智能简介什么是智能？顾名思义，人工智能就是人造智能，当然，这只是人工智能的字面解释或广义解释。

目前的“人工智能”一词是指用计算机模拟或实现的智能，同时，人工智能又是一个学科名称。人工智能简介什么是人工智能？人工智能专家系统机器人神经网络计算机视觉模式识别机器学习人工智能简介人工智能涉及的领域1956年Dartmoth会议1956年夏季,在美国Dartmoth(达特默思)大学,由年轻数学助教J.McCarthy(斯坦福大学教授)和他的三位朋友M.Minsky(哈佛大学数学神经学家,MIT教授),N.Lochester(IBM公司信息研究中心负责人)、C.Shannon(申农)(贝尔实验室信息部数学研究员)共同发起，邀请IBM公司的T.Moore(摩尔)和A.Samuel(塞缪尔)、MIT的O.Selfridge和R.Solomonff(索罗蒙佛)以及RAND公司和Carnagie工科大学的A.Newell(艾伦.钮厄尔)和H.A.Simon(西蒙)(现均为CMU教授)等人参加夏季学术讨论会,历时二个月。在这次历史性的聚会上,第一次正式使用了"人工智能(AI)"这一术语,从而开创了人工智能的研究方向和学科。人工智能之父人工智能简介---发展史二、形成期[第一兴盛期]（1956-1961）7控制理论发展简史古典控制理论(20~50年代)火炮控制器(1925)控制蒸汽机的速度的离心式调速器(1788年，J.Watt)发展背景工业过程控制气动控制阀(1922)8控制理论发展简史古典控制理论(20~50年代)火炮控制器(1925)控制蒸汽机的速度的离心式调速器(1788年，J.Watt)发展背景工业过程控制气动控制阀(现代)9控制理论发展简史

标志性成果N.B.Nichols1938年美国贝尔实验室的波德（H.Bode），1940年奈奎斯特（Nyquist）提出频率响应法1942年美国泰勒（Taylor）仪器公司的齐格勒（J.G.Ziegler）和尼科尔斯（N.B.Nichols）提出PID参数的最佳调整法古典控制理论(20~50年代)10控制理论发展简史

N.WienerMIT的维纳（N.Wiener）研究随机过程的预测，1942年提出Wiener滤波理论，1948年发表《控制论》《Cybernetics》）一书，标志着控制论学科的诞生。美国W.Evans提出根轨迹法(RootLocusMethod)(1948)，以单输入线性系统为对象的经典控制研究工作完成。古典控制理论(20~50年代)标志性成果11控制理论发展简史传递函数模型古典控制理论(20~50年代)关键词单输入单输出(SISO)频域法闭环控制(反馈)12控制理论发展简史现代控制理论(50~70年代)标志性成果1956年苏联庞特里亚金（L.S.Pontryagin）发表“最优过程数学理论”，提出极大值原理(MaximumPrinciple)1957年美国贝尔曼（R.Bellman）发表著名的动态规划（DynamicProgramming），建立最优控制的基础L.S.Pontryagin13控制理论发展简史现代控制理论(50~70年代)标志性成果1960年美籍匈牙利人卡尔曼（R.E.Kalman）发表“控制系统全面理论”（“OntheGeneralTheoryofControlSystems”）等论文，引入状态空间法分析系统，提出能控性，能观测性，最佳调节器和kalman滤波等概念，奠定了现代控制理论的基础R.E.Kalman14控制理论发展简史现代控制理论(50~70年代)标志性成果1967年瑞典奥斯特隆姆（KarlJ.Astrom）提出最小二乘辩识，解决了线性定常系统参数估计问题和定阶方法，六年后，提出了自启调节器，建立自适应控制的基础。Astrom于1993年获得IEEE荣誉奖章（IEEEMedalofHonor）。KarlJ.Astrom15控制理论发展简史现代控制理论(50~70年代)标志性成果1970年英国罗森布拉克（H.HRosenbrock）发表“状态矢量空间与多变量理论”（StateSpaceandMultivariableTheory）。1974年加拿大旺纳姆（W.MWonham）发表“线性多变量控制：一种几何方法”（LinearMultivariableControl:AGeometricApproach）W.MWonham

16随着柔性制造、虚拟工厂、CIMS，现场总线技术等大规模自动化生产的发展，控制系统日趋复杂化控制理论发展简史后现代控制理论(70年代~至今)发展背景日本Fanuc公司研制的柔性制造单元（1976）基于现场总线技术的企业自动化生产17控制理论发展简史后现代控制理论(70年代~至今)复杂控制系统带来的挑战？模型（参数，结构）的不确定性;高维;时变高度的非线性分布式的传感器和执行机构复杂的控制目标

……18分布式控制，网络协同控制鲁棒控制非线性控制控制理论发展简史后现代控制理论(70年代~至今)发展方向之一：(对现代控制理论的进一步发展和完善)基于模型的控制……19神经网络控制专家控制模糊控制控制理论发展简史后现代控制理论(70年代~至今)发展方向之二：(模拟人类思维和活动的智能控制)递阶控制学习控制仿生控制基于知识的控制20控制理论发展简史自动控制的发展过程1经典控制理论单变量控制，随动/调节，微分方程和传递函数，频率响应法3后现代控制理论2现代控制理论

多变量控制、最优控制，时域法，状态方程传统控制智能控制211.1智能控制的产生与发展

进展方向开环控制确定性反馈控制最优控制随机控制自适应/鲁棒控制自学习控制智能控制控制复杂性控制理论发展简史自动控制的发展过程22智能控制简介智能控制---二元交集结构傅京孙(1930—1985)AIACIC智能控制的二元结构含有拟人控制器的控制系统含有人－机控制器的控制系统自主机器人系统

AritificalIntelligent

AutomaticControl

IntelligentControl23智能控制简介智能控制---三元交集结构GeorgeN.Saridis(1931—2006)智能控制的三元结构ACAIORIC

AritificalIntelligent

AutomaticControl

IntelligentControl

OperationResearch24智能控制简介智能控制---四元交集结构蔡自兴(1938—)AIICORITCTICAICTIT智能控制看做自动控制、人工智能、信息论和运筹学四个学科的交集25智能控制基础上海大学机电工程与自动化学院杜鑫26智能控制教学课件第2章智能控制的知识工程基础2.1知识的基本概念2.2知识的表示2.3知识的获取2.4知识的运用内容提要272.1知识的基本概念2.1.1知识的定义把识别万物实体与性质的是与不是，定义为知识

-【百度百科-知识】知识是人们在改造世界的实践中所获得的认识和经验的总和。即，知识是人们在长期生活，社会实践，科学研究和实验中积累起来的对客观世界的任何和总结282.1知识的基本概念2.1.1知识的定义知识阶梯图29

数据信息知识定义数据是可定义为意义的实体，它涉及到事物的存在形式。它是关于事件的一组离散的客观的事实描述，是构成信息和知识的原始材料。具有特定含义的、彼此有关联的数据。从数学的观点看，信息是用来消除不确定性的一个物理量结构化的、具有指导意义的信息。从数学的观点看，知识是用来消除信息的无结构性的一个物理量存储形式数据库信息库知识库集成状态数据集成信息集成知识集成涉及学科数学――算法，图形学，拓扑学等信息科学――信息论、系统论，编码技术等（以及前项）知识科学――本体论，TRIZ、语义解析技术等（以及前项）2.1知识的基本概念2.1.1知识的定义30智能控制教学课件第2章智能控制的知识工程基础2.1知识的基本概念2.2知识的表示2.3知识的获取2.4知识的运用内容提要312.2知识的表示为什么要进行知识表示？原始解答原始问题同态问题同态解答TT-1困难容易同构问题同构映射对复杂的智能型问题进行机器求解-知识的映射322.2知识的表示什么是知识表示？知识表示，对智能机器系统而言，实际上就是对知识的一种描述或约定。其本质，就是采用某种技术模式，把所要求解问题的相关知识，映射为一种便于找到该问题解的数据结构。知识表示是知识信息处理系统中必不可少的关键环节。对知识进行表示的过程，实质上就是把相关知识映射为该数据结构的过程。332.2知识的表示知识表示法2.2.1一阶谓词知识表示法2.2.2产生式知识表示法2.2.3语义网络知识表示法2.2.4框架知识表示法2.2.5状态空间法2.2.6问题规约法34谓词公式2.2.1一阶谓词知识表示法原子(简单)谓词公式分子（复合）谓词公式用P(x1，x2，…，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,…，xn为客体变量或变元。通常把P(x1,x2,…,xn)叫做谓词演算的原子公式，或原子谓词公式。可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。35原子谓词公式2.2.1一阶谓词知识表示法有些陈述语句在特定情况下都具有“真”或“假”的含义，在逻辑上称这些语句为“命题”。如：A。天在下雨。B。天晴C。人是会死的D。他在哭表达单一意义的命题称为“原子命题（谓词公式）”36原子谓词公式2.2.1一阶谓词知识表示法在谓词公式P（x）中，P称为谓词，x称为个体变元，若x是一元的，称为一元谓词，P（x,y）称为二元谓词。在谓词中，个体可以为常量，变量，函数。若谓词中的个体都为常量，变量或函数，则称它为一阶谓词，如果个体本身是谓词，称为二阶谓词，依次类推。372.2.1一阶谓词知识表示法连词与(合取)（conjunction)或(析取)（disjunction）蕴涵（Implication）非(否定)（Not）等价(Equivalence)量词全称量词（UniversalQuantifiers)存在量词(ExistentialQuantifiers)连词和量词(Connective&Quantifiers)382.2.1一阶谓词知识表示法合取联接词∧合取：用连词∧把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫合取项。例如“我喜爱音乐和绘画”可写成：

LIKE（I，MUSIC）∧LIKE（I，PAINTING）又如“李住在一幢黄色的房子里”

LIVES（LI，HOUSE-1）∧COLOR（HOUSE-1,YELLOW)392.2.1一阶谓词知识表示法析取联接词∨析取：连词∨用来表示“或”关系。用连词∨把几个公式连接起来所构成的公式叫做析取,而次析取式的每一组成部分叫做析取项例如，句子“李明打篮球或踢足球”可表示为：PLAYS（LIMING，BASKETBALL）∨PLAYS(LIMING,FOOTBALL)402.2.1一阶谓词知识表示法蕴含联接词→蕴含：如果P→Q恒为真，则称“PQ”为“P永真蕴含Q”如：如果天下大雨，则停止足球赛；（P→Q）天正在下大雨；（P）所以停止足球赛。（Q）可以表示为：P，P→QQ

例：如果是鸟，那么就会飞。（P→Q）驼鸟是鸟（P）所以驼鸟就会飞（Q）这个推理就不正确，原因是P→Q不是永真的。412.2.1一阶谓词知识表示法否定联接词﹁否定：﹁

（非）用来否定一个公式的真值，也就是说，把一个合适公式的取值从T变为F，或从F变为T。例如，“机器人不在2号房间内”可表示为

﹁

INROOM（ROBOT，r2)

前面具有符号﹁的公式叫做否定。一个复合公式的否定也是合适公式。42﹁：“否定”联结词，当命题P为真时，则﹁P为假，反之为真∧：“合取”联结词，它表示两个命题之间具有“与”关系。∨：“析取”联结词，它表示两个命题存在“或”的关系。→：“蕴含”联接词、“单条件”，P→Q表示“如果P，则Q”。其中P为前件，Q为后件。：“等价”联接词、“双条件”，PQ表示“P当且仅当Q”。2.2.1一阶谓词知识表示法连词(联接词）432.2.1一阶谓词知识表示法连词(联接词）44全称量词：一个原子公式P(x)，对于所有可能的变量x都具有值T。这个特性可由在P(x)前面加上全称量词(x)来表示。存在量词：如果至少有一个x值可使P(x)成立，则可以在其前面加上存在量词(x)来表示。例:句子“所有的机器人是灰色的”可表示为

（x）(Robot（x）→Color(x，gray))量词句子“1号房间内有个物体”可表示为

（x）Inroom（x，r1）2.2.1一阶谓词知识表示法45用谓词公式表示知识的步骤2.2.1一阶谓词知识表示法根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值定义谓词及个体，确定每个谓词及个体的确切含义根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式46【例2.2.1.1】用一阶谓词法表示下列语句（1）上海房价比纽约房价高（2）小王是计算机系的一名学生，但他不喜欢编程（3）人人爱劳动Higher(x,y):x比y高Computer(x):x是自动化系的学生Like(x,y):x喜欢yM(x):x是人首先定义下列谓词2.2.1一阶谓词知识表示法Love(x,y):x爱y47（1）上海房价比纽约房价高（2）小王是计算机系的一名学生，但他不喜欢编程（3）人人爱劳动2.2.1一阶谓词知识表示法【例2.2.1.1】用一阶谓词法表示下列语句Higher(上海房价,纽约房价)Computer（小王)∧﹁Like（小王，编程）（x）(M(x)→LOVE（x，labour))48（1）自然数都是大于零的整数（2）所有整数不是偶数就是奇数（3）偶数除以2是整数N（x）:x是自然数I（x）:x是整数E（x）:x是偶数O（x）：x是奇数GZ（x）：x大于零S（x）:x除以2首先定义下列谓词2.2.1一阶谓词知识表示法【例2.2.1.2】用一阶谓词法表示下列语句49（1）自然数都是大于零的整数（2）所有整数不是偶数就是奇数（3）偶数除以2是整数(x)(N(x)→GZ(x)∧I(x))(x)(I(x)→E(x)∨O(x))(x)(E(x)→I(S(x)))2.2.1一阶谓词知识表示法【例2.2.1.2】用一阶谓词法表示下列语句502.2知识的表示知识表示法2.2.1一阶谓词知识表示法2.2.2产生式知识表示法2.2.3语义网络知识表示法2.2.4框架知识表示法2.2.5状态空间法2.2.6问题规约法512.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念2.2.3.2

事务和概念的语义网络表示2.2.3.3

情况和动作的语义网络表示2.2.3.4

逻辑关系的语义网络表示2.2.3.5

语义网络的推理过程2.2.3.6

语义网络表示法的特征522.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念什么是语义网络

语义网络是一种用实体及其语义关系来表达知识的有向图。

结点代表实体，表示各种事物、概念、情况、属性、状态、事件、动作等；弧代表语义关系，表示它所连结的两个实体之间的语义联系。在语义网络中，每一个结点和弧都必须带有标识，这些标识用来说明它所代表的实体或语义。

532.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念什么是语义网络

语义基元从结构上看，语义网络一般是由一些最基本的语义单元构成的，这种最基本的语义单元被称为语义基元。其三元组表示为：（结点1，弧，结点2）基本网元一个语义基元的有向图表示就成为一个基本网元例如：若有语义基元（A,R,B）其中，A、B分别表示两个结点，R表示A与B之间的某种语义联系，则它所对应的基本网元如下图所示。ABR542.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念语义网络的简单例子例：“鸵鸟是一种鸟”鸵鸟鸟是一种55当把多个基本网元用相应的语义联系关联在一起时，就可得到一个语义网络。在语义网络中，节点还可以是一个语义子网络，所以，语义网络实质上可以是一种多层次的嵌套结构。2.2.3语义网络表示法2.2.3.1

语义网络的基本概念562.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念语义网络表示能力的比较与产生式有着对应的表示能力

事实的表示：例：“雪的颜色是白的”

规则的表示：例：规则R的含义是“如果A则B”雪白颜色ABR572.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念（基本语义关系）类属关系指具有共同属性的不同事物间的“具体与抽象”、“个体与集体”的关系分类关系：

A-Kind-of

含义为“是一种”，表示一个事物是另一个事物的一种类型。例成员关系：

A-Member-of

含义为“是一员”，表示一个事物是另一个事物的一个成员。例实例关系：

Is-a

含义为“是一个”，表示一个事物是另一个事物的一个实例。例类属关系的主要特征最主要特征是属性的继承性，处在具体层的结点可以继承抽象层结点的所有属性。如以上例子鸟动物A-Kind-of张强共青团员A-Member-of李刚人Is-a582.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念（基本语义关系）包含关系亦称聚类关系。指具有组织或结构特征的“部分与整体”之间的关系。常用的包含关系是：

Part-of：含义为“是一部分”，表示一个事物是另一个事物的一部分。例如，“大脑是人体的一部分”再如，“黑板是墙体的一部分”包含关系与类属关系的区别最主要区别是包含关系一般不具备属性的继承性。如上两个例子，大脑不一定具有人的各种属性黑板也不具有墙的各种属性。大脑人体Part-of黑板墙体Part-of592.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念（基本语义关系）属性关系指事物和其属性之间的关系。常用的属性关系有：

Have：含义为“有”，表示一个结点具有另一个结点所描述的属性

Can：含义是“能”、“会”，表示一个结点能做另一个结点的事情例如，“鸟有翅膀”鸟翅膀Have602.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念（基本语义关系）时间关系指不同事件在其发生时间方面的先后次序关系。常用的时间关系有：

Before：含义为“在前”，表示一个事件在另一个事件之前发生

After:含义为“在后”，表示一个事件在另一个事件之后发生例如，“澳门回归在香港回归之后”澳门回归香港回归After612.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念（基本语义关系）位置关系指不同事物在位置方面的关系。常用的位置关系有：

Located-on：含义为“在上”，表示某一物体在另一物体之上

Located-at：含义为“在”，表示某一物体所在的位置

Located-under：含义为“在下”，表示某一物体在另一物体之下

Located-inside：含义为“在内”，表示某一物体在另一物体之内；

Located-outside：含义为“在外”，表示某一物体在另一物体之外。例如，“书在桌子上”书桌子Located-on622.2.3语义网络知识表示法2.2.3.2

语义网络的基本概念（基本语义关系）相近关系指不同事物在形状、内容等方面相似或接近。常用的相近关系有：

Similar-to：含义为“相似”，表示某一事物与另一事物相似

Near-to：含义为“接近”，表示某一事物与另一事物接近例如，“猫似虎”猫虎Similar-to632.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念（基本语义关系）推论关系指从一个概念推出另一个概念的语义关系。常用的推论关系是Fetch

例如：“由成绩好推出学习努力”成绩好学习努力Fetch64语义网络表示知识的步骤确定问题中的所有对象及其属性；分析并确定语义网络中所论对象间的关系；根据语义网络中所涉及的关系，对节点及弧进行整理。2.2.3.1

语义网络的基本概念2.2.3语义网络知识表示法652.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念2.2.3.2

事务和概念的语义网络表示662.2.3语义网络知识表示法2.2.3.2

事物和概念的语义网络表示一元关系指可以用一元谓词P(x)表示的关系。谓词P说明实体的性质、属性等。描述的是一些最简单、最直观的事物或概念，常用：“是”、“有”、“会”、“能”等语义关系来说明。如，“雪是白的”。一元关系的描述应该说，语义网络表示的是二元关系。如何用它来描述一元关系？结点1表示实体，结点2表示实体的性质或属性等，弧表示语义关系。例如，“李刚是一个人”为一元关系，其语义网络如前所示。再例，“动物能运动、会吃”。运动吃动物能会672.2.3语义网络知识表示法2.2.3.2

事物和概念的语义网络表示二元关系可用二元谓词P(x,y)表示的关系。其中，x,y为实体，P实体之间的关系。单个二元关系可直接用一个基本网元来表示，如前介绍的一些常用的二元关系及其表示。下面讨论一些较复杂关系的表示方法。对复杂关系，可通过一些相对独立的二元或一元关系的组合来实现。例2.2.3.1：

用语义网络表示：动物能运动、会吃。鸟是一种动物，鸟有翅膀、会飞。鱼是一种动物，鱼生活在水中、会游泳。对于这个问题，各种动物的属性按属性关系描述，动物之间的分类关系用类属关系描述。682.2.3语义网络知识表示法2.2.3.2

事物和概念的语义网络表示动物运动能吃会鸟是一种飞翅膀有会鱼是一种水中游泳生活在会例2.2.3.1的语义网络表示

692.2.3语义网络知识表示法2.2.3.2

事物和概念的语义网络表示

例2.2.3.2用语义网络表示：王强是理想公司的经理；理想公司在中关村；王强28岁。

中关村理想公司王强经理28岁位于工作在是一位年龄702.2.3语义网络知识表示法2.2.3.2

事物和概念的语义网络表示

例2.2.3.3若在例2.2.3.2中增加以下事实：另有一位王强是理想公司经理聘用的职员；职员王强22岁

王强职员王-2王-1经理22岁理想公司28岁中关村姓名姓名是一位聘用是一位年龄年龄工作在工作在位于712.2.3语义网络知识表示法2.2.3.2

事物和概念的语义网络表示多元关系可用多元谓词P(x1，x2，……)表示的关系。其中，个体x1，x2，……为实体，谓词P说明这些实体之间的关系。用语义网络表示多元关系时，一般采用增加关系结点的办法。722.2.3语义网络知识表示法2.2.3.2

事物和概念的语义网络表示例2.3.2.4用语义网络表示以下事实：北京位于沈阳和郑州之间这是一种“……在……和……之间”的三元关系。它不能直接用简单的二元关系来表示，需要在语义网络中增加一个位置关系的结点。沈阳北京郑州位置关系边界1居中边界2732.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念2.2.3.2

事务和概念的语义网络表示2.2.3.3

情况和动作的语义网络表示742.2.3语义网络知识表示法2.2.3.3

情况和动作的语义网络表示表示方法：为描述复杂情况和动作，西蒙提出了增加情况和动作结点用语义网络表示事件或动作时，需要设立一个事件或动作结点动作结点：由一些向外引出的弧来指出动作的主体与客体。

例2-3.2.5：用语义网络表示：“常河给江涛一张磁盘”一张磁盘常河给江涛客体2客体1主体752.2.3语义网络知识表示法2.2.3.3

情况和动作的语义网络表示事件结点：例2.3.2.6：（同上例2-3.2.5）用语义网络表示：

“常河给江涛一张磁盘”一张磁盘给予事件给常河江涛客体2客体1主体动作762.2.3语义网络知识表示法2.2.3.3

情况和动作的语义网络表示例2.2.3.7：用语义网络描述如下事实：

“神州大学和东方大学两校篮球队在东方大学进行一场比赛，比分是85：89”。在这个问题的语义网络中，可以设立一个事件结点“球赛”，用来表示这场特定的球赛，然后把与这场球赛有关的信息都和该结点联系起来。比赛篮球赛东方大学神州大学85：89是一种主队客队结局77

例2.2.3.8：用语义网络表示：“小燕子这只燕子从春天到秋天占有一个巢”需要设立一个占有权结点，表示占有物和占有时间等。

小燕子燕子鸟巢鸟窝春天时间秋天情况占有权占有资格ISAAKOOwneeStarAKOAKOEndAKOAKOOwnerAKO2.2.3.3

情况和动作的语义网络表示2.2.3语义网络知识表示法78对上述问题，也可以把占有作为一种关系，并用一条弧来表示，但在这种表示方法下，占有关系的具体情况就无法表示了小燕子燕子鸟巢鸟窝ISAAKOOwnsAKO2.2.3.3

情况和动作的语义网络表示2.2.3语义网络知识表示法792.2.3语义网络知识表示法2.2.3.1

语义网络的基本概念2.2.3.2

事务和概念的语义网络表示2.2.3.3

情况和动作的语义网络表示2.2.3.4

逻辑关系的语义网络表示802.2.3语义网络知识表示法2.2.3.4

逻辑关系的语义网络表示表示合取及析取的方法：可通过增加合取结点和析取结点来实现例2.2.3.8：用语义网络表示如下事实：“参赛者有教师、有学生、有高、有低”分析参赛者的不同情况，可得到以下四种情况：A教师、高；B

教师、低；C

学生、高；D

学生、低；然后在按照他们的逻辑关系用语义网络表示出来。人参赛者ABCD或或教师学生高低与是部分部分部分部分状态状态状态状态812.2.3语义网络知识表示法2.2.3.4

逻辑关系的语义网络表示表示否定的方法：可分为基本语义关系的否定和一般语义关系的否定

基本语义关系的否定的表示

可通过在有向弧上直接标注该基本语义关系的否定的方法来解决。例2-15:用语义网络表示：书不在桌子上采用在有向弧上直接标注该基本语义关系的否定的方法，该语义网络为

书桌子¬Located-on822.2.3语义网络知识表示法2.2.3.4

逻辑关系的语义网络表示表示否定的方法：一般语义关系的否定的表示对一般语义关系的否定，通常需要引进“非”节点来表示。例2-16：用语义网络表示：

常河没有给江涛一张磁盘采用引进“非”节点的方法，其语义网络如下图一张磁盘

给非常河江涛GiftGiverReceiver832.2.3语义网络知识表示法2.2.3.4

逻辑关系的语义网络表示表示蕴含的方法：通过增加蕴含关系节点来实现在蕴含关系中，有两条指向蕴含节点的弧，一条代表前提条件，标记为ANTE；另一条代表结论，标记为CONSE。842.2.3语义网络知识表示法2.2.3.4

逻辑关系的语义网络表示表示蕴含的方法：例2.2.3.9：用语义网络表示如下知识：“如果学校组织大学生机器人竞赛活动，那么李强就参加比赛”该蕴含关系的语义网络如下图。其中，在前提条件中，机器人竞赛的组织者是学校，参赛对象是学生操纵的机器人，而机器人只不过是一种智能机器。学校比赛活动机器人机器人竞赛蕴含参加比赛学生智能机器李强人RacerAKOConstitutionManipulatorANTECONSEISAAKOAKOJoiner85存在量词：可直接用“ISA”、“AKO”等这样的语义关系来表示全称量词：可采用亨德里克提出的网络分区技术基本思想：把一个复杂命题划分为若干个子命题，每个子命题用一个较简单的语义网络表示，称为一个子空间，多个子空间构成一个大空间。每个子空间看作是大空间中的一个结点，称作超结点。空间可逐层嵌套，子空间之间用弧互相连结。例2-19用语义网络表示如下事实：“每个学生都学习了一门程序设计语言”其语义网络如下图。在该图中：

GS是一个概念结点，它表示具有全称量化的一般事件。

g是一个实例结点，代表GS

中的一个具体例子，如上所提到的事实。

s是一个全称变量，表示任意一个学生。

l是一个存在变量，表示某一次学习。

P是一个存在变量，表示某一门程序设计语言。这样，s、l、p之间的语义联系就构成一个子空间，它表示对每一个学生s，都存在一个学习事件l和一门程序设计语言p。2.2.3.4

逻辑关系的语义网络表示2.2.3语义网络知识表示法存在和全称量词的表示(14)86

在从结点g引出的三条弧中，弧“ISA”说明结点g是GS中一个实例；弧“F”说明它所代表的子空间及其具体形式；弧“”说明它所代表的全称量词。GSg+slp学生学习程序语言ISAISAISAFSubjectObjectISA存在和全称量词的表示(2/4)2.2.3.4

逻辑关系的语义网络表示2.2.3语义网络知识表示法87

每一个全称量词都需要一条这样的弧，子空间中有多少个全称量词，就需要有多少条这样的弧。例2-19用语义网络表示事实：“每个学生都学习了所有的程序设计课程”其语义网络如下图所示。其中，结点g有两条指向全称变量的弧。学生学习程序设计课gGSslpISAISAISASubjectObjectISAF存在和全称量词的表示(3/4)2.2.3.4

逻辑关系的语义网络表示2.2.3语义网络知识表示法88

另外，在网络分区技术中，要求F指向的子空间中的所有非全称变量结点都应该是存在量词约束的变量，否则应放在子空间的外面。例2-21:用语义网络表示事实：“每个学生都学习了C++语言”其语义网络如下图所示。结点“C++语言”代表一门具体的程序设计语言，是结点“程序语言”的一个实例，故被放到F所指的子空间的外边

GSgsl学生学习C++语言程序语言ISAISASubjectObjectFISAISA存在和全称量词的表示(4/4)2.2.3.4

逻辑关系的语义网络表示2.2.3语义网络知识表示法第2章智能控制的知识工程基础2.1知识的基本概念2.2知识的表示2.3知识的获取2.4知识的运用内容提要2.3.1机器学习概述2.3.2机器学习的主要策略机械学习指导式学习2.3知识的获取归纳学习示例学习观察与发现学习1.按学习方法分类（温斯顿，1977

）：机械式学习指导式学习示例学习类比学习等2.3.1机器学习概述2.按学习能力分类：监督学习（有教师学习）再励学习、非监督学习2.3.1机器学习概述3.按推理方式分类：基于演绎的学习（解释学习）。基于归纳的学习（示例学习、发现学习等）4.按综合属性分类：归纳学习、分析学习、连接学习等。2.3.1机器学习概述第2章智能控制的知识工程基础2.1知识的基本概念2.2知识的表示2.3知识的获取2.4知识的运用内容提要2.4.1知识推理的概念和类型2.4.2搜索的基本概念2.4.3常见的知识推理技术知识推理技术2.4知识的运用2.4.1知识推理的概念和类型（1）推理算法

若问题求解的知识推理过程是完备的，则对于可解的问题从任意初始状态出发，通过这种推理过程，总可以找到一条求解路线，经过有限的、确定的操作序列，转移所要求的目标状态，保证推理过程的收敛性，求得问题的解答。这种推理过程具有完备性，而完备的推理过程称为“推理算法”。

例如：王浩算法就是一种知识推理算法。又如广度优先搜索推理方法具有完备性，也是一种知识推理的搜索算法。二、知识推理技术的类型根据问题求解过程的完备性分类

根据问题求解过程是否完备，可将知识推理方法分为：2.4.1知识推理的概念和类型（2）推理步骤若问题求解的推理过程是不完备的，则不能保证其推理过程的收敛性，以任意初始状态转移到目标态，不一定能求得问题的解答。这种推理过程是不完备的、非算法的，称为“推理步骤”。例如：深度优先算法就是不完备的，它的搜索过程可能会进入无穷的分支，而达不到目标态，所以是一种推理步骤。二、知识推理技术的类型根据问题求解过程的完备性分类

根据问题求解过程是否完备，可将知识推理方法分为：2.4.1知识推理的概念和类型（1）启发性推理在问题求解的推理过程中，运用与问题有关的启发性知识，即解决问题的策略、技巧、窍门，对解的特性及规律的估计等实践经验知识，以加快推理过程，提高搜索效率，这种推理过程称为“启发性推理”。例如：在图的搜索推理方法中，利用启发性知识改进的深度优先搜索法，如局部择优搜索法（瞎子爬山法）、最好优先搜索法等，只需要对部分状态空间进行搜索，大大提高了搜索效率。二、知识推理技术的类型根据启发性知识的运用分类根据在问题求解的过程中是否运用启发性知识，可将知识推理方法分为：2.4.1知识推理的概念和类型（2）非启发推理

在问题求解的推理过程中，不运用启发性知识，而是按照一般的逻辑法则或控制性知识，进行通用性的推理。这种方法缺乏对求解问题的针对性，需要对全状态空间进行搜索，所以，推理效率较低，容易出现“组合爆炸”。二、知识推理技术的类型根据启发性知识的运用分类根据在问题求解的过程中是否运用启发性知识，可将知识推理方法分为：2.4.1知识推理的概念和类型分类依据类

别示

例知识表达方式图搜索法广度、深度优先搜索法逻辑论证法王浩命题逻辑算法鲁宾逊谓词逻辑推理过程完备性推理算法广度优先推理步骤深度优先启发知识利用启发推理局部择优、最好优先搜索法非启发推理广度优先搜索法知识推理技术分类表二、知识推理技术的类型2.4.1知识推理的概念和类型2.4.2搜索的基本概念知识推理技术2.4知识的运用2.4.2搜索的基本概念搜索技术，特别是启发式搜索，在人工智能的研究中，被看成各种问题求解的主要工具，因此从一开始就受到了极大的重视。在人工智能研究开始的第一个十年左右的时间里，问题求解的研究几乎就是搜索过程研究的同义语。一些早期著名的人工智能程序，如理论家程序（LT）、通用问题求解程序(GPS)、符号积分程序、几何定理证明程序、跳棋程序都是以搜索为基础的程序。既然求解被作为问题求解的主要工具，那么一个问题求解系统也可以看成是一个搜索系统。对问题求解可以狭义的理解，也可广义的理解。狭义理解时，就是解决某种特定问题，如数学求解问题、证明几何定理、逻辑推理、下棋等。广义理解时，可把问题求解看作为达到所期望的目标而进行的知识推理及其运用。所以，广义的问题求解可看作是人工智能的核心课题。2.4.2搜索的基本概念和搜索相关的概念一．显式图与隐式图为求解问题，需要把有关的知识存储在计算机的知识库中，一般有两种存储方式：2．隐式存储

只存储与问题有关的部分知识，称为“隐式存储”。其它知识则靠规则等来推导出，这样可节省内存。在求解过程中，由初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，逐步转移到要求解的目标状态，只需在知识库中存储局部状态空间图，称为“隐式图”。1．显式存储

把与问题有关的全部状态空间图，即相应的全部有关知识（叙述、过程和控制三方面的知识），都直接存入到计算机中，称为“显式存储”或“显式图”。

2.4.2搜索的基本概念和搜索相关的概念二．隐式图搜索法一般地说，无法把问题的全部知识（或状态空间）直接存入计算机而是存入与问题有关的部分知识。这是因为：一方面某些问题的信息量太大，二方面计算机的存储容量是有限的。通常的人工智能程序大多采用隐式图搜索推理方法。要成功地求解只拥有隐式图的问题，初始存入的部分知识很重要，必须包含或覆盖全部要用到的知识，否则造成推理失败。此外还必须有一个产生新知识或生成状态空间的方法。在计算机中，利用有关知识逐步产生新的知识或状态空间，并检查问题是否解决的过程，叫隐式图搜索过程。这个问题和人解决问题的过程十分相似。如果计算机能按此过程工作，计算机也就有了一定的智慧。人工智能感兴趣的问题就是如何运用局部知识去解决给定的问题。2.4.2搜索的基本概念和搜索相关的概念二．隐式图搜索法用隐式图搜索法求解问题的方法与过程如下：

①运用叙述性知识，给出问题的部分状态描述，包括初始状态So、目标状态Sg和某些中间状态Sh；③运用控制性知识：给出评价函数E（x）（EvaluationFunction），用于评价新生成的结点，控制继续搜索的前进方向。②运用过程性知识，给出“生成器”函数G（x）（GeneratorFunction），即由状态空间图的“父结点”生成“子结点”的操作或算子；

搜索方法：

2.4.2搜索的基本概念和搜索相关的概念二．隐式图搜索法用隐式图搜索法求解问题的方法与过程如下：

相应的过程：

③若目标状态Sg未出现，则继续搜索，用评价函数E（x）对Sh的各节点进行评价，选取适当的或最有希望的结点，再用G（x）生成其子结点（状态S2），再检查是否为目标状态Sg。如此下去，直到找到目标状态Sg为止，若所有可生成的结点均已扩展，仍无Sg出现，则搜索失败。

②用生成器函数G（x），由So出发生成中间状态Sh（各子结点），并检索每个中间状态是否为目标状态，若是则搜索成功。①给定求解问题的初始状态（So、初始结点）；2.4.1知识推理的概念和类型2.4.2搜索的基本概念2.4.3常见的知识推理技术知识推理技术2.4知识的运用2.4.3常见的知识推理技术2.4.3.1状态空间图搜索技术2.4.3.2与或树图搜索法2.4.3.3博弈问题求解2.4.3.4通用问题求解2.4.3.5关于搜索的一些问题2.4.3常见的知识推理技术2.4.3.1状态空间图搜索技术2.4.3.2与或树图搜索法2.4.3.3博弈问题求解2.4.3.4通用问题求解2.4.3.5关于搜索的一些问题搜索的主要过程：(1)从初始或目的状态出发，并将它作为当前状态。(2)扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针。(3)检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第(2)步再进行搜索。2.4.3.1状态空间图搜索技术搜索方向：正向搜索——从问题给出的条件（一个用于状态转换的操作算子集合）出发。2.4.3.1状态空间图搜索技术

(1)数据驱动：从初始状态出发的正向搜索。逆向搜索：先从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。(2)目的驱动：从目的状态出发的逆向搜索。2.4.3.1状态空间图搜索技术搜索方向：

(3)双向搜索

双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。搜索方向：2.4.3.1状态空间图搜索技术（2）启发式搜索：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态。盲目搜索与启发式搜索:（1）盲目搜索：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。2.4.3.1状态空间图搜索技术状态：表示系统状态、事实等叙述型知识的一组

变量或数组：操作：表示引起状态变化的过程型知识的一组关系或函数：T2.4.3.1状态空间图搜索技术状态空间图的基本概念状态空间：利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组：

：状态集合。：操作算子的集合。：包含问题的初始状态是的非空子集。：若干具体状态或满足某些性质的路径信息描述。2.4.3.1状态空间图搜索技术状态空间图的基本概念求解路径：从结点到结点的路径。

：状态空间的一个解。

状态空间的一个解：一个有限的操作算子序列。2.4.3.1状态空间图搜索技术状态空间图的基本概念2.4.3.1状态空间图搜索技术宽度优先搜索法深度优先搜索法有序搜索法盲目搜索启发式搜索2.4.3.1状态空间图搜索技术宽度优先搜索法

定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)。

基本思想：从初始节点S开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n＋1层的节点进行扩展。OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。宽度优先搜索示意图2.4.3.1状态空间图搜索技术宽度优先搜索法2.4.3.1状态空间图搜索技术宽度优先搜索算法：

(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。

(2)如果OPEN是个空表，则没有解，失败退出；否则继续。

(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。

(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。

(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。

(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。宽度优先搜索算法框图2.4.3.1状态空间图搜索技术宽度优先搜索方法分析：宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，就说该法失败退出；对于无限图来说，则永远不会终止)。宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。2.4.3.1状态空间图搜索技术

例如：宽度优先搜索用于八数码难题。这个问题就是要把初始棋局变为如下目标棋局的问题：

搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序(按顺时针方向移动空格)。图中最后一个节点是目标节点。2.4.3.1状态空间图搜索技术八数码难题的宽度优先搜索树

262.4.3.1状态空间图搜索技术2023/5/14126对应动态演示图2.4.3.1状态空间图搜索技术宽度优先搜索法深度优先搜索法有序搜索法盲目搜索启发式搜索2.4.3.1状态空间图搜索技术基本思想：从初始节点S开始，在其子节点中选择一个节点进行考察，若不是目标节点，则再在该子节点中选择一个节点进行考察，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。深度优先搜索法

深度优先搜索示意图

2.4.3.1状态空间图搜索技术2.4.3.1状态空间图搜索技术深度优先搜索法

在深度优先搜索中，首先扩展最新产生的(即最深的)节点（深度相等的节点可以任意排列）。其结果是搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能小。2.4.3.1状态空间图搜索技术2.4.3.1状态空间图搜索技术（有界）深度优先搜索法对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度——深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。

定义节点的深度如下：

(1)起始节点(即根节点)的深度为0。

(2)任何其它节点的深度等于其父辈节点深度加上1。2.4.3.1状态空间图搜索技术（有界）深度优先搜索法含有深度界限的深度优先搜索算法：

(1)把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。

(2)如果OPEN为一空表，则失败退出。

(3)把第一个节点(节点n)从OPEN表移到CLOSED表。

(4)如果节点n的深度等于最大深度，则转向(2)。

(5)扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。

(6)如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。2023/5/14134（有界）深度优先搜索法算法动态演示图2023/5/14135

例如：按深度优先搜索生成八数码难题搜索树，设置深度界限为5。

下图绘出了搜索树，粗线条的路径表明含有5条应用规则的一个解。从图可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，然后再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最后两步有差别的那些路径，等等。2.4.3.1状态空间图搜索技术八数码难题的深度优先搜索树

2.4.3.1状态空间图搜索技术2.4.3.1状态空间图搜索技术宽度优先搜索法深度优先搜索法有序搜索法盲目搜索启发式搜索启发式搜索

盲目搜索的不足：效率低，耗费过多的计算空间与时间。宽度优先搜索、深度优先搜索，或等代价搜索算法,是按事先规定的路线进行搜索，或按已经付出的代价决定下一步要搜索的节点，其主要差别是OPEN表中待扩展节点的顺序问题。如果找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。2.4.3.1状态空间图搜索技术2023/5/14139盲目搜索的共同特点：没有利用问题本身的特性信息，在决定要被扩展的节点时，都没有考虑该节点在解的路径上的可能性有多大，它是否有利于问题求解以及求出的解是否为最优解等。启发式搜索

2.4.3.1状态空间图搜索技术2023/5/14140

启发信息进行搜索技术一般需要某些有关具体问题领域特性的、与具体问题求解过程有关的、并可指导搜索过程朝着最有希望方向前进的控制信息，把此种信息叫做启发信息。

把利用启发信息的搜索方法叫做启发性搜索方法启发式搜索

2.4.3.1状态空间图搜索技术

启发信息按其用途可分为3种：

(1)用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。

(2)在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。

(3)用于决定某些应该从搜索树中抛弃或修剪的节点。启发式搜索策略

2.4.3.1状态空间图搜索技术2023/5/14142在本课程中，只讨论利用上述第一种启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索(orderedsearch)。启发式搜索策略

2.4.3.1状态空间图搜索技术用来估算节点希望程度的量度，叫做估价函数(evaluationfunction)。估价函数的任务就是估计OPEN表中各节点的重要程度。一个节点的“希望”(promise)有几种不同的定义方法:1)估算目标节点到此节点的距离；

2)解答路径包括被估价过的节点，并计算全条路径的长度或难度。估价函数2.4.3.1状态空间图搜索技术

用符号f来标记估价函数，用f(n)表示节点n的估价函数值。暂时令f为任意函数，以后将会提出f是从起始节点约束地通过节点n而到达目标节点的最小代价路径上的一个估算代价。

一般形式：

f(n)=g(n)+h(n)g(n)是从s0到n的实际代价。

h(n)是从节点n到目标节点sg的估计代价。估价函数2.4.3.1状态空间图搜索技术

用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。根据习惯，OPEN表上的节点按照它们f函数值的递增顺序排列。根据推测，某个具有低估价值的节点较有可能处在最佳路径上。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索，而其算法就叫做有序搜索算法或最佳优先算法。可见它总是选择最有希望的节点作为下一个要扩展的节点。有序搜索(orderedsearch)又称为最好优先搜索(best-firstsearch)。启发式搜索---有序搜索2.4.3.1状态空间图搜索技术2023/5/14146

尼尔逊（Nilsson）曾提出一个有序搜索的基本算法。估价函数f按照如下方法确定：一个节点希望程度越大，其f值就越小。被选为扩展的节点，是估价函数最小的节点。启发式搜索---有序搜索2.4.3.1状态空间图搜索技术有序状态空间搜索算法(1)把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。(2)如果OPEN是个空表，则失败退出，无解。(3)从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。(4)把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。(5)如果i是个目标节点，则成功退出，求得一个解。

启发式搜索---有序搜索2.4.3.1状态空间图搜索技术(6)扩展节点i生成其全部后继节点。对于i的每一个后继节点j：(a)计算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。(c)如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则(i)以此新值取代旧值。(ii)从j指向i，而不是指向它的父辈节点。(iii)如果节点j在CLOSED表中，则把它移回OPEN表(7)转向(2)，即GOTO(2)。有序状态空间搜索算法2.4.3.1状态空间图搜索技术2023/5/14149注释：步骤（6.c）是一般搜索图所需要的，该图中可能有一个以上的父辈节点。具有最小估价函数f（j）的节点被选作父辈节点。但是，由于搜索树，它最多只有一个父辈节点，所以步骤（6.c）可以略去。启发式搜索---有序搜索2.4.3.1状态空间图搜索技术2023/5/14150

有序搜索算法框图

2.4.3.1状态空间图搜索技术宽度优先搜索、深度优先搜索是有序搜索技术的特例。对于宽度优先搜索，选择f(i)作为节点i的深度。

启发式搜索---有序搜索2.4.3.1状态空间图搜索技术有序搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解有序搜索例子使用八数码难题例子说明过程GRAPHSEARCH是如何应用估价函数排列节点的。采用简单的估价函数

f(n)=d(n)+W(n)

其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。启发式搜索---有序搜索2.4.3.1状态空间图搜索技术起始节点棋局28316475的f值等于0+4=4。有序搜索例子启发式搜索---有序搜索2.4.3.1状态空间图搜索技术八数码难题的有序搜索树从图可见，这里所求得的解答路径和用其它搜索方法找到的解答路径相同。不过，估价函数的应用显著地减少了被扩展的节点数(如果我们只用估价函数f(n)=d(n)，那么我们就得到宽度优先搜索过程)启发式搜索---有序搜索2.4.3.1状态空间图搜索技术正确地选择估价函数对确定搜索结果具有决定性的作用。使用不能识别某些节点真实希望的估价函数会形成非最小代价路径；而使用一个过多地估计了全部节点希望的估价函数(就像宽度优先搜索方法得到的估价函数一样)又会扩展过多的节点。状态空间图搜索算法小结树搜索-----盲目搜索----------广度优先搜索

---深度优先搜索---有界深度优先

---代价树搜索

---启发式搜索-----全局择优搜索(最好优先)---局部择优搜索(爬山法)---A算法(基于:f(n)=g(n)+h(n)) A*算法(最佳搜索:h(n)<=h*(n))2.4.3.1状态空间图搜索技术2.4.3常见的知识推理技术2.4.3.1状态空间图搜索技术2.4.3.