《人工智能原理》PPT课件.ppt

人工智能原理,考试说明,1、考试形式：,开卷,2、考试内容：,讲课的讲授内容,3、类型：,简答题-20%,知识表示-20%,子句化简-15%,定理证明-25%,问题求解-20%,重点章节,第1章: 人工智能概述,第2章：知识表示,第3章： 确定性推理,第4章：状态空间法,第5章：问题规约法,该们课程的授课思路,1、什么是人工智能以及研究机制 2、知识表示 3、解决问题（确定性推理、状态空间、问题规约） 4、专家系统,第1章 人工智能概述,主要内容： 一、什么是智能？什么是人工智能？,一、什么是智能？什么是人工智能？,1、智能：通俗地说：智能是一种认识客观事物和运用知识解决问题的综合能力。 2、人工智能：Artificial Intelligence(AI) 其中 Artificial 就意味着这种智能是人造的 智能。 从本质上讲，人工智能是研究如何制造出人造的智能机器或智能系统，来模拟人类智能活动的能力，以延伸人们智能的科学。,第2章 知识表达,重点内容： 一、一阶谓词逻辑表达知识 二、语义网络表达知识 三、产生式表达知识,一、一阶谓词逻辑表达知识,主要步骤： 1、定义合适的谓词：用事先定义好的字母或词汇表达谓词，用小写字母或词汇表示客体，或用客体变元表示客体。例如： 花是红的 ： red(花） 2、选择合适量词： 量词有两个： （1）全称量词：表示“所有的”，“任何的”等。 （2）存在量词：表示“存在一些”等,一、一阶谓词逻辑表达知识,3、选择合适逻辑运算符：,二、语义网络表达知识,1.基本定义： 语义网络是一种用实体及其语义关系来表达知识的有向图。其基本要素是： （1）结点：描述实体，表示各种事物、概念、情况、属性、状态等。 （2）有向弧：描述事物间的关系。,二、语义网络表达知识,2、基本语义关系： (1),ISA弧,表示：A是B的一个子类。 例如：“鸟是一种动物”,2019/7/30,语义网络,12,（2）EL弧： 表示：A是B的一个元素。 例如“张三是一个人”,二、语义网络表达知识,A,B,EL,2019/7/30,语义网络,13,（3）其他的语义关系可以利用谓词 例如：“张三领导李四”,二、语义网络表达知识,A,B,pred,三、产生式表达知识,产生式的基本形式是IF-THEN结构，即： 如果：条件 那么：结论 一个一般的产生式规则可表述为： IF条件1条件2条件n THEN ,第3章 确定性推理,重点内容： 1、子句及其化简（置换和合一） 2、归结原理的基本思想 3、归结的基本步骤 4、用归结原理求解问题和进行答案提取,一、子句及其化简,原子谓词公式及其否定称为文字。 例如： 定义：任何文字的析取式称为子句。 例如： 化简分为8个步骤,一、子句及其化简,几点注意： 化简后的子句之间是合取关系，即与的关系，所以只要有一个子句是假的，则整个子句集就是不可满足的。 空子句是不可满足的，所以一个子句集中只要含有一个空子句，则子句集就是不可满足的。,二、归结原理的基本思想及步骤,基本思想： 有一个二元组，其中 A: 由一阶谓词逻辑表达的公理系统 T: 一阶谓词逻辑表达的待证明的定理或命题。 要证明T是A的逻辑结论，即 。 采用的思想是： 如果要证明T是A的逻辑结论，则证明T的否定 与公理系统不相容。,归结的步骤： （1）否定定理T, (2)将 与公理系统A合并，构成 （3）将 中的谓词逻辑公式子句化 （4）对子句化的 中的字句进行归结反演，力求归结出表示矛盾的空子句。,二、归结原理的基本思想及步骤,二、归结原理的基本思想及步骤,归结规则： 归结的核心就是消去子句中互补的子句。 子句归结的规则的一般表达式：,用归结原理 三、求解问题,利用归结原理可以求解某些问题，实际上，也是在已知一些前提条件的情况下，来利用归结原理求证一定结论。具体的步骤如下： （1）用一阶谓词逻辑描述待求解问题，提出公理系统T; (2)知识表达：用一阶谓词逻辑表达相关知识，构造公理系统A; （3）谓词演算：利用归结原理求解问题，求证定理T。,四、用归结原理进行答案提取,答案提取的一般步骤： （1）把问题的已知条件用谓词公式表示出来，并化为相应的子句集； （2）把代求解的目标问题用谓词公式表示出来，并进行否定。然后把否定后的目标问题化为子句集。 （3）把否定的目标子句，同目标子句进行析取，构成永真式。并把这些重言式加入到前提子句集中，得到一个新的子句集。,四、用归结原理进行答案提取,答案提取的步骤： （4）对这个新的子句集，应用归结原理进行归结，形成一个证明树； （5）证明树根部的子句，就是待求的答案。,第4章 状态空间法 -基本思想,状态空间法的基本思想是：问题是状态空间法处理的对象，是状态空间中的点。状态空间中不同的点具有不同的状态，表现了问题的不同状态。原始问题对应的状态点即初始状态，而问题的解所对应的状态点即目标状态。应用可行操作将初始状态转移至目标状态的过程就是问题求解的过程。如果问题存在解，则状态空间中一定存在一条由初始状态至目标状态的轨迹，使初始状态在可行操作的作用下运动至目标状态。,第4章 状态空间法,重点内容：,一、状态空间法求解问题的基本思想,四、宽度优先搜索算法,五、深度优先搜索算法,六、 A* 算法,二、问题的形式化,三、几个概念,第4章 状态空间法 -问题的形式化,问题的三要素：,（1）状态：,表示问题求解过程中每一步问题状况的数据结构，它可以被形象地表示为：,其中，每个分量都给予确定的值时，就得到了一个具体的状态。,第4章 状态空间法 -问题的形式化,问题的三要素：,（2）操作：,它是把问题从一种状态变换为另一种状态的手段。,当对一个问题状态使用某个可用操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。,第4章 状态空间法 -问题的形式化,问题的三要素：,（3）状态空间：,用来描述一个问题的全部状态以及这些状态之间的相互关系。状态空间常用一个三元组表示：,S 为问题的所有初始状态的集合,F 为操作的集合,G 为目标状态的集合,第4章 状态空间法,重点内容：,一、状态空间法求解问题的基本思想,四、宽度优先搜索算法,五、深度优先搜索算法,六、 A* 算法,二、问题的形式化,三、几个概念,第4章 状态空间法 -宽度优先搜索算法,在宽度优先搜索算法中设置有两个表：,(1) OPEN 表：用以存放状态树的开节点,(2) CLOSED 表：用以存放状态树的闭节点,问题的初始状态 So 是状态树的根，也即搜索起点。,OPEN 的数据结构：,队,第4章 状态空间法 -宽度优先搜索算法,开始,将 So 放入 OPEN,OPEN 空,SgSUBNODES,将 SUBNODES 中的成员 放入 OPEN 的末端 并设置其通向 n 的指针,扩展节点 n ，生成其不在 OPEN 和 CLOSED 中的 子节点结合 SUBNODES,No,So,S11,S12,S21,S22,S23,S24,S31,S32,S33,S34,S35,S36,S37,S38,S41,S42,S43,S44,S45,S46,S47,S48,第4章 状态空间法 -宽度优先搜索算法,第4章 状态空间法,重点内容：,一、状态空间法求解问题的基本思想,四、宽度优先搜索算法,五、深度优先搜索算法,六、 A* 算法,二、问题的形式化,三、几个概念,第4章 状态空间法 -深度优先搜索算法,（1）把初始节点S0放入Open表中；,（2）如果Open表为空，则问题无解，失败退出。,（3）把Open表中的第一个节点取出方入closed表中，并记该节点为n.,（4）考察节点n是否为目标节点。若是，则得到问题的解，成功退出。,（5）若节点n不可扩展，则转第（2）步。,（6）扩展节点n，将其子节点方入open表的首部，并为每个子节点设置指向父节点的指针。,第4章 状态空间法 -深度优先搜索算法,So,S11,S12,S23,S24,S35,S36,S37,S38,S45,S46,S47,S48,Open表的结构为栈,第4章 状态空间法,重点内容：,一、状态空间法求解问题的基本思想,四、宽度优先搜索算法,五、深度优先搜索算法,六、 A* 算法,二、问题的形式化,三、几个概念,第4章 状态空间法 - A* 算法,类 型：,启发式搜索算法,启发式信息：,与求解问题相关的先验信息,A* 算法中也设置有两个表：,(1) OPEN 表：用以存放状态树的开节点,(2) CLOSED 表：用以存放状态树的闭节点,搜索的费用计算,(1) 节点 ni 到 nj 的费用：,c(ni,nj) (0),(2) 节点 ni 到 nj 的最小费用：,c* (ni,nj) (0),(3) So 到 n 的最佳路径的费用：,g* (n) = c* (So,n),(4) n 到 Sg 的最佳路径的费用：,h* (n) = c* (n,Sg),So 经节点 n 到 Sg 的最佳路径的费用：,f * (n) = g* (n) + h* (n),第4章 状态空间法 - A* 算法,搜索的费用估计,f (n) = g(n) + h(n),其中：,g(n)： g* (n) 函数的估计函数,So,n,Sg,So 经节点 n 到 Sg 的最佳路径的费用 f * (n) 的估计函数 f (n) 被定义为：,h(n)： h* (n) 函数的估计函数,f (n) 函数又称为 A* 算法的评价函数，既是 So 经 n 到 Sg 的最佳路径的费用估计，又是对 So 经 n 到 Sg 的可能性和最佳性的评价。,第4章 状态空间法 - A* 算法,Step 1.,将起始节点 So 放入 OPEN，计算 f(So)；,Step 3.,Step 4.,若 BESTNODE 是目标节点，则成功退出；,Step 2.,若 OPEN 空，则失败退出；,Step 5.,扩展 BESTNODE，生成其全部子节点，并将它们放入子节点集合 SUBNODES；,Step 6.,对于每一个子节点 SON SUBNODES，计算f(SON)，并设置 SON 指向 BESTNODE 的指针；,Step 7.,将 BESTNODE 移出 OPEN 并移入 CLOSED；将 SUBNODES 的成员放入 OPEN；,Step 8.,转向 Step 2。,将 OPEN 中 f 值最小的节点 n 记作 BESTNODE；,第4章 状态空间法 - A* 算法,第4章 状态空间法 - A* 算法,A*搜索算法中OPEN中的数据结构是：表,第5章 问题规约,重点内容：,1、问题规约法的相关概念。,2、问题规约法的求解过程。,第5章 问题规约 -基本概念,问题规约的基本思想：,将大问题或复杂问题分解为易于处理或求解的子问题集合。,问题规约的