《人工智能》课程Powerpoint课件.ppt

1、人 工 智 能Powerpoint第一章 绪论1.1 人工智能的定义和发展1.2 人类智能和人工智能1.3 人工智能的各种认知观1.4 人工智能的研究与应用领域1.5 课程概要CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.1.1 人工智能的定义几种定义v 智能机器（intelligent machine）v 人工智能（学科）v 人工智能（能力）v 人工智能（拟人思维、行为）v 人工智能（理性思维、行为）1.1 定义和发展3CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.1.2 人工智能的起源与发展v

2、孕育期（1956年前）v 数理逻辑学科（弗雷治、维纳等）v 计算的新思想（丘奇、图灵 等）v 形成期（1956-1970年）v 1956年，第一次人工智能的研讨会v 1969年，第一届国际人工智能联合会议v 1970年，人工智能国际杂志创刊1.1 定义和发展4CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.1.2 人工智能的起源与发展v发展期（1970年）v 进一步研究AI基本原理方法和技术v 进行实用化研究v 专家系统与知识工程v 智能机器人v 智能控制等v 从“一枝独秀”到“百花齐放”1.1 定义和发展5CISICCISICCISICCISIC

3、CISICCISICCISICCISICCISIC1.2 人类智能和人工智能1.2.1 智能信息处理系统的假设 v 人是一种智能信息处理系统v 物理符号系统的六种基本功能v 物理符号系统的假设v 推论一v 推论二v 推论三6CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.2.1 智能信息处理系统的假设v 人类的认知行为具有不同层次v 认知生理学v 认知心理学v 认知信息学v 认知工程学1.2 人类智能和人工智能7CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.2.2 人类智能的计算机模拟v 机器智能可以

4、模拟人类智能v 智能计算机v 下棋v 定理证明v 语言翻译v 新型智能计算机v 神经计算机v量子计算机1.2 人类智能和人工智能8CISICCISICCISICCISICCISICCISICCISICCISICCISIC 1.2.3 人工智能的研究目标v 近期目标建造智能计算机代替人类的部分智力劳动v 远期目标用自动机模仿人类的思维过程和智能行为1.2 人类智能和人工智能9CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.3 人工智能的各种认知观v 符号主义（Symbolicism）基于物理符号系统假设和有限合理性原理v 连接主义（Connectio

5、nism）基于神经网络及其间的连接机制与学习算法v 行为主义（Actionism）基于控制论及感知动作型控制系统 10CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4 人工智能的研究及应用领域v 人工智能的基本技术v 知识表示（Knowledge Representation）状态空间法、问题归约法、谓词逻辑法v 推理搜索（Searching&Reasoning）启发式搜索、消解原理、不确定性推理v 计算智能（Computational Intelligence）模糊计算、神经计算、进化计算v 构成技术（系统与语言）产生式系统、LISP语言、Pr

6、olog语言11CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.1 问题求解v 问题的表示、分解、搜索、归约等v 进行复杂的数学公式符号运算求解1.4.2 逻辑推理与定理证明v 通过对事实数据库的操作来证明定理v 多种证明方法v 几何定理证明的“吴氏方法”1.4 研究及应用12CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.3 自然语言理解v 语言v 自然语言、人造语言、机器语言v“理解”的标准1.4.4 自动程序设计v 根据不同目的描述来编写的计算机程序v 促进人工智能系统的发展1.4 研究及

7、应用13CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.5 专家系统v 是一个智能化的计算机程序系统v 和传统的计算机程序之间有本质区别1.4.6 机器学习v 是机器获取智能的途径v 学习是一个有特定目的的知识获取过程v 学习的本质是对信息的理解与应用v 有多种学习方法1.4 研究及应用14CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.7 神经网络v 神经计算机v 在其它领域中的广泛应用1.4.8 机器人学 v 操作机器人v 智能机器人v 机器人的广泛应用v 促进人工智能的发展1.4 研究及应

8、用15CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.9 模式识别v 是计算机对环境识别的需要v 是对人类环境的感知模拟1.4.10 机器视觉v 人类80以上的外部信息来自视觉v 低层视觉与高层视觉v 前沿研究领域v 广泛应用1.4 研究及应用16CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.11 智能控制v 驱动智能机器自主地实现其目标的过程v 是一个定性和定量的混合控制过程v 是当今自动控制的最高水平1.4.12 智能检索v 是信息时代来临的需要v 智能检索系统所面临的三大问题1.4 研究

9、及应用17CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.13 智能调度与指挥v 寻找最佳调度和组合v NP完全类问题的求解v 军事指挥系统等领域1.4.14 分布式人工智能与Agentv 是传统人工智能的延伸和扩展v 研究目标是创建一种能描述自然系统和社会系统的精确概念模型1.4 研究及应用18CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.15 计算智能与进化计算v 计算智能v包括神经计算、模糊计算、进化计算等v 进化计算的理论基础是生物进化论1.4.16 数据挖掘与知识发现v 知识获取v

10、数据库知识挖掘v 数据库中知识发现的四个特征1.4 研究及应用19CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.4.17 人工生命v 人工生命概念的提出v 理论基础与研究方法v 研究内容1.4.18 系统与语言工具 v 计算机系统的一些概念得到发展v 新的编程语言与专用开发工具1.4 研究及应用20CISICCISICCISICCISICCISICCISICCISICCISICCISIC1.5 课程概要v 简述人工智能的起源与发展v 概括地论述知识表示的各种主要方法v 讨论常用的搜索原理和推理求解技术v 介绍近期人工智能技术和方法的热点v 详细地

11、分析人工智能的主要应用领域v 叙述人工智能的争议与展望 21第二章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.1状态空间法（State Space Representation）v问题求解技术主要是两个方面：v问题的表示v求解的方法v状态空间法v状态（state）v算符（operator）v状态空间方法23CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.1.1 问题状态描述v定义v状态：

12、描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。v算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。v问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。2.1 状态空间法24CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.状态空间表示概念详释v例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.1 状态空间法25CISICCISICCISICCISICCISICCISICCISICCISICCISIC例:三数码难题

13、（3 puzzle problem）123123123312312312初始棋局目标棋局2.1 状态空间法26CISICCISICCISICCISICCISICCISICCISICCISICCISICv有向图v路径v代价v图的显示说明v图的隐示说明2.1.2 状态图示法AB2.1 状态空间法27CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.1.3 状态空间表示举例v产生式系统（production system）v一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。v一套规则：它对数据库进行操作运算。每条规则

14、由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。v一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法28CISICCISICCISICCISICCISICCISICCISICCISICCISIC 状态空间表示举例状态空间表示举例v例：猴子和香蕉问题2.1 状态空间法29CISICCISICCISICCISICCISICCISICCISICCISICCISIC解题过程v 用一个四元表列（W，x，Y，z）来表示这个问题状态.v这个问题的操作（算符）如下：v2 goto（U）表示猴子走到水平位置Uv或者用产生式规则表示为（W，

15、0，Y，z）goto（U）（U，0，Y，z）2.1 状态空间法30CISICCISICCISICCISICCISICCISICCISICCISICCISICvpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）vclimbbox猴子爬上箱顶，即有（W，0，W，z）climbbox （W，1，W，z）2.1 状态空间法31CISICCISICCISICCISICCISICCISICCISICCISICCISICvgrasp猴子摘到香蕉，即有（c，1，c，0）grasp （c，1，c，1）v该初始状态变换为目标状态的操作序列为goto(b),p

16、ushbox(c),climbbox,grasp2.1 状态空间法32CISICCISICCISICCISICCISICCISICCISICCISICCISIC(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目标状态目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法33CISICCISICCISICCISICCISICCISICCISICCISICCISIC猴子和香蕉问题自动演示

17、：猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!2.1 状态空间法34CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.2 问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题35CISICCISICCISICCISICCISICCISICCISICCISICCISICv 问题归约表示的组成部分：v一个初始问题描述；v一套把问题变换为子问题的操作符；v一套本原问题描述。v问题归约的实质：v从目标(要解决的问题)出发逆向推理，建立子问题以及子

18、问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法36CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.2.1 问题归约描述（Problem Reduction Description）v梵塔难题123CBA2.2 问题规约法37CISICCISICCISICCISICCISICCISICCISICCISICCISIC解题过程（3个圆盘问题）1231231231231231231231232.2 问题规约法38CISICCISICCISICCISICCISICCISICCISICCISICCISIC多圆盘梵塔难题演示2.

19、2 问题规约法39CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.2.2与或图表示v1.与图、或图、与或图2.2 问题规约法ABCD与图ABC或图40CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.2 问题规约法BCDEFGAHMBCDEFGAN41CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点42CISICCISICCISICCISICCISICCISICCIS

20、ICCISICCISIC3.定义2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点43CISICCISICCISICCISICCISICCISICCISICCISICCISICv不可解节点的一般定义v没有后裔的非终叶节点为不可解节点。v全部后裔为不可解的非终叶节点且含有或后继节点，此非终叶节点才是不可解的。v后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。v与或图构成规则2.2 问题规约法44CISICCISICCISICCISICCISICCISICCISICCISICCISIC梵塔问题归约图（113）（123）（111

21、）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321）（331）（322）（321）（331）（333）2.2 问题规约法45CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.3 谓词逻辑法v逻辑语句v形式语言2.3.1 谓词演算v 1.语法和语义v基本符号v谓词符号、变量符号、函数符号、常量符号、括号和逗号v原子公式46CISICCISICCISICCISICCISICCISICCISICCISICCISICv连词和量词(Connective&Quantifiers)v连词v与及合

22、取（conjunction)v或及析取（disjunction）v蕴涵（Implication）v非（Not）v量词v全称量词（Universal Quantifiers)v存在量词(Existential Quantifiers)2.3 谓词逻辑法47CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.3.2 谓词公式v原子公式的的定义：v用P(x1，x2，xn)表示一个n元谓词公式，其中P为n元谓词，x1,x2,，xn为客体变量或变元。通常把P(x1,x2,xn)叫做谓词演算的原子公式，或原子谓词公式。v分子谓词公式v可以用连词把原子谓词公式组成复

23、合谓词公式，并把它叫做分子谓词公式。2.3 谓词逻辑法48CISICCISICCISICCISICCISICCISICCISICCISICCISICv合适公式（WFF，well-formed formulas）v合适公式的递归定义v合适公式的性质v合适公式的真值v等价（Equivalence)2.3 谓词逻辑法49CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.3.3 置换与合一v置换v概念v假元推理v全称化推理v综合推理v定义v就是在该表达式中用置换项置换变量v性质v可结合的v不可交换的2.3 谓词逻辑法50CISICCISICCISICCISI

24、CCISICCISICCISICCISICCISICv合一（Unification)v合一：寻找项对变量的置换，以使两表达式一致。v可合一：如果一个置换s作用于表达式集Ei的每个元素，则我们用Ei s来表示置换例的集。我们称表达式集Ei是可合一的。2.3 谓词逻辑法51CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.4 语义网络法 （Semantic Network Representation）v语义网络的结构v定义v组成部分v词法v结构v过程v语义52CISICCISICCISICCISICCISICCISICCISICCISICCISICv表

25、示占有关系和其它情况v例：小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。v选择语义基元v试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。2.4 语义网络法2.4.1 二元语义网络的表示53CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.4.2 多元语义网络的表示v谓词逻辑与语义网络等效LIMINGMANISAISA（LIMING，MAN）或或 MAN（LIMING）（语义网络）（语义网络）（谓词逻辑）（谓词逻辑）2.4 语义网络法54CISICCISICCISICCISICCISICCISICCISIC

26、CISICCISICv多元语义网络表示的实质v把多元关系转化为一组二元关系的组合，或二元关系的合取。R(XR(X1 1，X X2 2，X Xn n)R R1212(X(X1 1，X X2 2)R)R1313(X(X1 1，X X3 3)R)R1n1n(X(X1 1，X Xn n).R Rn n-1 n-1 n(X(Xn-1n-1，X Xn n)可转换为可转换为2.4 语义网络法55CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.4.3 连接词和量化的表示v合取v三元变为二元组合v析取v加注析取界限，并标记DIS，以免引起混淆。v否定v两种表示方式：

27、或标注NEG界限。2.4 语义网络法56CISICCISICCISICCISICCISICCISICCISICCISICCISICv蕴涵v在语义网络中可用标注ANTE和CONSE界限来表示蕴涵关系。ANTE和CONSE界限分别用来把与先决条件(antecedent)及与结果(consequence)相关的链联系在一起。v量化v存在量化ISA链v全称量化分割法2.4 语义网络法57CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.5其他方法（Others)v框架（Frame）表示v框架是一种结构化表示法，通常采用语义网络中的节点-槽-值表示结构。v剧本

28、（Script）表示v剧本是框架的一种特殊形式，它用一组槽来描述某些事件的发生序列。v过程（Procedure）表示v过程式表示就是将有关某一问题领域的知识，连同如何使用这些知识的方法，均隐式地表达为一个求解问题的过程。58CISICCISICCISICCISICCISICCISICCISICCISICCISIC2.6 小结（Summary）v本章所讨论的知识表示问题是人工智能研究的核心问题之一。知识表示方法很多，本章介绍了其中的7种，有图示法和公式法，陈述式表示和过程式表示等。59CISICCISICCISICCISICCISICCISICCISICCISICCISIC方法 初始问题算符目标

29、结果 状态 空间法 归约法 谓词逻辑法 语义网络法状态状态结点结点合适公式合适公式结点结点算符算符弧弧 子句集子句集（set of clause）置换合一置换合一消解反演消解反演链链目标状态目标状态结点结点根结点根结点目标网络目标网络解答路径解答路径 （path）解答树解答树 （tree）nil语义网络语义网络知识表示方法间的关系知识表示方法间的关系60第三章 搜索推理技术3.6 产生式系统3.7 系统组织技术3.8 不确定性推理3.9 非单调推理3.10 小结3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索3.4 消解原理3.5 规则演绎系统CISICCISICCISICCISICCIS

30、ICCISICCISICCISICCISIC3.1 图搜索策略 v图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。v图搜索过程图62CISICCISICCISICCISICCISICCISICCISICCISICCISIC开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把把第一个节点第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后

31、继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功图图3.1 图搜索过程框图图搜索过程框图是是是是否否否否3.1 图搜索策略63CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.2 盲目搜索 v特点：不需重排OPEN表v种类：宽度优先、深度优先、等代价搜索等。3.2.1 宽度优先搜索v 定义 以接近起始节点的程度逐层扩展节点的搜索方法。v 特点：一种高代价搜索，但若有解存在，则必能找到它。v 算法64CISICCISICCISICCISICCISICCISICCIS

32、ICCISICCISIC开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把把n的后继节点放入的后继节点放入OPEN表的末端，提供返回节点表的末端，提供返回节点n的指针的指针失败失败成功成功图图3.2 宽度优先算法框图宽度优先算法框图是是否否是是否否3.2 盲目搜索65CISICCISICCISICCISICCISICCISICCISICCISICCISICv 例子八数码难题（8-puzzle problem）1238456712384567（目标状

33、态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。3.2 盲目搜索66CISICCISICCISICCISICCISICCISICCISICCISICCISIC1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图3.4 八数码难题的宽度优先搜索树1345612384567123845

34、6712384567123845671 238456723242526271236782212384567123845671 238456712 3845671238456712384567123845671415161718192021123845673.2 盲目搜索67CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.2.2 深度优先搜索v 定义 首先扩展最新产生的(即最深的)节点。v 算法 防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法

35、框图见教材）3.2 盲目搜索68CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.2.3 等代价搜索v 定义 是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。v 算法 若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。3.2 盲目搜索69CISICCISICCISICCISICCISICCISICCISICCISICCISIC开始把S放入OPEN表OPEN表为空表？把具有最小g(i)值的节点i从OPEN表移至CLOSED表是否有后继节点为目标节点？失

36、败成功图图3.2 等代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表否否3.2 盲目搜索70CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.3 启发式搜索v特点：重排OPEN表，选择最有希望的节点加以扩展v种类：有序搜索、A*算法等3.3.1 启发式搜索策略和估价函数v盲目搜索可能带来组合爆炸v启发式信息 用来加速搜索过程的有关问题领域的特征信息。71CISICCISICCISICCISICCISICCISICCISICCISIC

37、CISICv估价函数 为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 v应用节点“希望”程度（估价函数值）重排OPEN表3.3.2 有序搜索v实质 选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。3.3 启发式搜索72CISICCISICCISICCISICCISICCISICCISICCISICCISIC开始开始把把S放入放入OPEN表，表，计算估价函数计算估价函数 f(s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CLOSED表表i为目标

38、节点吗？为目标节点吗？扩展扩展i，得后继节点得后继节点j，计算计算f(j)，提供返回提供返回节点节点i的指针，利用的指针，利用f(j)对对OPEN表重新排表重新排序，调整亲子关系及指针序，调整亲子关系及指针失败失败成功成功图图3.9 有序搜索算法框图有序搜索算法框图是是否否是是否否3.3 启发式搜索v算法73CISICCISICCISICCISICCISICCISICCISICCISICCISICv 例子八数码难题（8-puzzle problem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：3.3 启发式搜索74CISICCISICCISICCISI

39、CCISICCISICCISICCISICCISIC5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712 384567（5）（7）1238456712384567（6）（7）12384567（5）813245671 2384567（5）（7）图3.10 八数码难题的有序搜索树123846（4）73.3 启发式搜索75CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.3.3 A*算法v估价函数的定义：对节点n定义f f*(n)=g(n)=

40、g*(n)+h(n)+h*(n)(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f 定义为：f(n)=g(n)+h(n)g是g*的估计，h是h*的估计vA*算法的定义：定义定义1 1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定义定义2 2 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义定义3 3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。3.3 启发式搜索76CISICC

41、ISICCISICCISICCISICCISICCISICCISICCISIC3.4 消解原理回顾：原子公式（atomic formulas）文字一个原子公式及其否定。子句由文字的析取组成的合适公式。消解对谓词演算公式进行分解和化简，消去一些符号，以求得导出子句。3.4.1 子句集的求取v 步骤：共9步。77CISICCISICCISICCISICCISICCISICCISICCISICCISICv 例子:将下列谓词演算公式化为一个子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)开始：(1)消去蕴涵符号 只应用和符号，以AB替换AB。(1)(x)P(x)(y)P(y

42、)P(f(x,y)(y)Q(x,y)P(y)3.4 消解原理78CISICCISICCISICCISICCISICCISICCISICCISICCISIC(2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。(3)对变量标准化 对哑元（虚构变量）改名，以保证每个量词有其自己唯一的哑元。3.4 消解原理(2)(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)(3)(x)P(x)(y)P(y)P(f(x,y)(w)Q(x,w)P(w)79CISICCISICCISICCISICCISICCISICCISICCISICCISIC(4)消去存在量词

43、以Skolem函数代替存在量词内的约束变量，然后消去存在量词(5)化为前束形 把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形=前缀 母式 全称量词串 无量词公式(4)(x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x)式中，w=g(x)为一Skolem函数。(5)(x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x)3.4 消解原理80CISICCISICCISICCISICCISICCISICCISICCISICCISIC(6)把母式化为合取范式 任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集

44、组成的合取。(7)消去全称量词 所有余下的量词均被全称量词量化了。消去前缀，即消去明显出现的全称量词。3.4 消解原理(6)(x)(y)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(7)P(x)P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)81CISICCISICCISICCISICCISICCISICCISICCISICCISIC(8)消去连词符号 用A,B代替(AB)，消去符号。最后得到一个有限集，其中每个公式是文字的析取。(9)更换变量名称 可以更换变量符号的名称，使一个变量符号不出现在一个以上的子句中。3.4 消解原理(8)P(x)

45、P(y)P(f(x,y)P(x)Q(x,g(x)P(x)P(g(x)(9)P(x1)P(y)Pf(x1,y)P(x2)Qx2,g(x2)P(x3)Pg(x3)82CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.4.2 消解推理规则v消解式的定义令L1，L2为两任意原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。已知两子句L1和L2,如果L1和L2具有最一般合一，那么通过消解可以从这两个父辈子句推导出一个新子句()。这个新子句叫做消解式。v 消解式求法取各子句的析取，然后消去互补对。3.4 消解原理83CISICCISICCISICCI

46、SICCISICCISICCISICCISICCISIC3.4.3 含有变量的消解式 要把消解推理规则推广到含有变量的子句，必须找到一个作用于父辈子句的置换，使父辈子句含有互补文字。v 含有变量的子句之消解式v 例子Px,f(y)Q(x)Rf(a),y Pf(f(a),zR(z，w)Q f(f(a)R(f(a)，y)R(f(y)，w)=f(f(a)/x,f(y)/z3.4 消解原理84CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.4.4 消解反演求解过程v消解反演 给出S，Lv否定L，得L；v把L添加到S中去；v把新产生的集合L，S化成子句集；v

47、应用消解原理，力图推导出一个表示矛盾的空子句v 例子储蓄问题 前提：每个储蓄钱的人都获得利息。结论：如果没有利息，那么就没有人去储蓄钱3.4 消解原理85CISICCISICCISICCISICCISICCISICCISICCISICCISIC(1）规定原子公式：S(x,y)S(x,y)表示“x储蓄y”M(x)M(x)表示“x是钱”I(x)I(x)表示“x是利息”E(xE(x，y)y)表示“x获得y”(2）用谓词公式表示前提和结论：前提：前提：(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)结论：结论：(x)I(x)(x)(y)(M(y)S(x,y)(3)化为子句形证明证明：3.

48、4 消解原理86CISICCISICCISICCISICCISICCISICCISICCISICCISIC把前提化为子句形：1)S(x,y)M(y)I(f(x)2)S(x,y)M(y)E(x,f(x)把结论化为子句形：3)I(z)4)S(a,b)5)M(b)(4)消解反演求NIL图3.12 储蓄问题反演树子句（1）子句（3）f(x)/zM(b)NIL子句（5）子句（7）子句（4）a/x,b/yS(x,y)M(y)子句子句（6）3.4 消解原理87CISICCISICCISICCISICCISICCISICCISICCISICCISICv反演求解过程v从反演树求取答案步骤v把由目标公式的否定产生

49、的每个子句添加到目标公式否定之否定的子句中去。v按照反演树，执行和以前相同的消解，直至在根部得到某个子句止。v用根部的子句作为一个回答语句。v实质v把一棵根部有NIL的反演树变换为根部带有回 答语句的一棵证明树。3.4 消解原理88CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.5 规则演绎系统v 定义 基于规则的问题求解系统运用IfThen规则来建立，每个if可能与某断言(assertion)集中的一个或多个断言匹配。有时把该断言集称为工作内存，then部分用于规定放入工作内存的新断言。这种基于规则的系统叫做规则演绎系统。在这种系统中，通常称每个

50、if部分为前项，称每个then部分为后项。89CISICCISICCISICCISICCISICCISICCISICCISICCISIC3.5.1 规则正向演绎系统v定义 正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。v求解过程v事实表达式的与或形变换 在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。3.5 规则演绎系统90CISICCISICCISICCISICCISICCISICCISICCISICCISICv事实表达式的与或图表示Q(w,A)R(v)P(v)S(A,v)Q(w,A)R(v