《人工智能原理》PPT课件
时间:2020-05-12 17:27

  《人工智能原理》PPT课件_IT认证_资格考试/认证_教育专区。人工智能原理 考试说明 1、考试形式: 开卷 2、考试内容: 讲课的讲授内容 3、类型: 简答题----20% 知识表示----20% 子句化简----15% 证明----25%

  人工智能原理 考试说明 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弧 ISA B A 表示:A是B的一个子类。 ISA 例如:“鸟是一种动物” 鸟 动物 二、语义网络表达知识 (2)EL弧: EL B A 表示:A是B的一个元素。 例如“张三是一个人” EL 张三 2019/5/5 语义网络 人 12 二、语义网络表达知识 (3)其他的语义关系可以利用谓词 pred B A 例如:“张三领导李四” Lead 张三 2019/5/5 语义网络 李四 13 三、产生式表达知识 产生式的基本形式是IF-THEN结构,即: 如果:{条件} 那么:{结论} 一个一般的产生式规则可表述为: IF{条件1}{条件2}…{条件n} THEN {结论1 结论2…结论 m} 第3章 确定性推理 重点内容: 1、子句及其化简(置换和合一) 2、归结原理的基本思想 3、归结的基本步骤 4、用归结原理求解问题和进行答案提取 一、子句及其化简 原子谓词公式及其否定称为文字。 例如:P(x), Q(x), ?P(x)等 定义:任字的析取式称为子句。 例如: P(x) ? Q(x),P(x, f (x))? Q(x, g(x)) 化简分为8个步骤 一、子句及其化简 几点注意: 化简后的子句之间是合取关系,即 与的关系,所以只要有一个子句是假的, 则整个子句集就是不可满足的。 句是不可满足的,所以一个子 句集中只要含有一个句,则子句集 就是不可满足的。 二、归结原理的基本思想及步骤 基本思想: 有一个二元组A,T,其中 A: 由一阶谓词逻辑表达的系统 T: 一阶谓词逻辑表达的待证明的或命题。 要证明T是A的逻辑结论,即 A ? T 。 采用的思想是: 如果要证明T是A的逻辑结论,则证明T的否定?T 与系统不相容。 二、归结原理的基本思想及步骤 归结的步骤: (1)否定T, ?T (2)将 ?T 与系统A合并,构成 {A,?T} (3)将 {A,?T} 中的谓词逻辑公式子句化 (4)对子句化的 {A,?T} 中的字句进行 归结反演,力求归结出表示矛盾的 句。 二、归结原理的基本思想及步骤 归结规则: 归结的核心就是消去子句中互补的子句。 子句归结的规则的一般表达式: ?R ? P1 ? P2... ? Pm ? R ? Q1 ? Q2... ? Qn P1 ? P2... ? Pm ? Q1 ? Q2... ? Qn 用归结原理 三、求解问题 利用归结原理可以求解某些问题,实际上, 也是在已知一些前提条件的情况下,来利用归结 原理求证一定结论。具体的步骤如下: (1)用一阶谓词逻辑描述待求解问题,提出公 理系统T; (2)知识表达:用一阶谓词逻辑表达相关知识, 构造系统A; (3)谓词演算:利用归结原理求解问题,求证 T。 四、用归结原理进行答案提取 答案提取的一般步骤: (1)把问题的已知条件用谓词公式表示出来, 并化为相应的子句集; (2)把代求解的目标问题用谓词公式表示出 来,并进行否定。然后把否定后的目标问题化 为子句集。 (3)把否定的目标子句,同目标子句进行析 取,构成永真式。并把这些重言式加入到前提 子句集中,得到一个新的子句集。 四、用归结原理进行答案提取 答案提取的步骤: (4)对这个新的子句集,应用归结原 理进行归结,形成一个证明树; (5)证明树根部的子句,就是待求的 答案。 第4章 状态空间法 ---基本思想 状态空间法的基本思想是:问题是状态空间 法处理的对象,是状态空间中的点。状态空间中 不同的点具有不同的状态,表现了问题的不同状 态。原始问题对应的状态点即初始状态,而问题 的解所对应的状态点即目标状态。应用可行操作 将初始状态转移至目标状态的过程就是问题求解 的过程。如果问题存在解,则状态空间中一定存 在一条由初始状态至目标状态的轨迹,使初始状 态在可行操作的作用下运动至目标状态。 第4章 状态空间法 重点内容: 一、状态空间法求解问题的基本思想 二、问题的形式化 三、几个概念 四、宽度优先搜索算法 五、深度优先搜索算法 六、 A* 算法 第4章 状态空间法 ---问题的形式化 问题的三要素: (1)状态: 表示问题求解过程中每一步问题状况的数据结 构,它可以被形象地表示为: S ? {s1, s2 ,..., sn} 其中,每个分量都给予确定的值时,就得 到了一个具体的状态。 第4章 状态空间法 ---问题的形式化 问题的三要素: (2)操作: 它是把问题从一种状态变换为另一种状态的手段。 当对一个问题状态使用某个可用操作时,它将引 起该状态中某些分量值的变化,从而使问题从一 个具体状态变为另一个具体状态。 第4章 状态空间法 ---问题的形式化 问题的三要素: (3)状态空间: 用来描述一个问题的全部状态以及这些状态之间 的相互关系。状态空间常用一个三元组表示: S, F,G S 为问题的所有初始状态的集合 F 为操作的集合 G 为目标状态的集合 第4章 状态空间法 重点内容: 一、状态空间法求解问题的基本思想 二、问题的形式化 三、几个概念 四、宽度优先搜索算法 五、深度优先搜索算法 六、 A* 算法 第4章 状态空间法 ---宽度优先搜索算法 在宽度优先搜索算法中设置有两个表: (1) OPEN 表:用以存放状态树的开节点 (2) CLOSED 表:用以存放状态树的闭节点 问题的初始状态 So 是状态树的根,也即搜 索起点。 OPEN 的数据结构: 队 第4章 状态空间法 ---宽度优先搜索算法 开始 将 So 放入 OPEN No Yes OPEN 空 将 OPEN 中的第一个节点 n 送入 CLOSED No Yes Sg?SUBNODES 失败 成功 扩展节点 n ,生成其不在 OPEN 和 CLOSED 中的 子节点结合 SUBNODES 将 SUBNODES 中的 放入 OPEN 的末端 并设置其通向 n 的指针 第4章 状态空间法 ---宽度优先搜索算法 宽度方向 So 深 度 方 向 S11 S12 S21 S22 S23 S24 S31 S32 S33 S34 S35 S36 S37 S38 S41 S42 S43 S44 S45 S46 S47 S48 第4章 状态空间法 重点内容: 一、状态空间法求解问题的基本思想 二、问题的形式化 三、几个概念 四、宽度优先搜索算法 五、深度优先搜索算法 六、 A* 算法 第4章 状态空间法 ---深度优先搜索算法 (1)把初始节点S0放入Open表中; (2)如果Open表为空,则问题无解,失败退出。 (3)把Open表中的第一个节点取出方入closed 表中,并记该节点为n. (4)考察节点n是否为目标节点。若是,则得到 问题的解,成功退出。 (5)若节点n不可扩展,则转第(2)步。 (6)扩展节点n,将其子节点方入open表的首 部,并为每个子节点设置指向父节点的指针。 第4章 状态空间法 ---深度优先搜索算法 宽度方向 深 度 方 S11 向 So S12 S23 S24 Open表的结构为栈 S35 S36 S37 S38 S45 S46 S47 S48 第4章 状态空间法 重点内容: 一、状态空间法求解问题的基本思想 二、问题的形式化 三、几个概念 四、宽度优先搜索算法 五、深度优先搜索算法 六、 A* 算法 第4章 状态空间法 --- A* 算法 类 型: 式搜索算法 式信息: 与求解问题相关的先验信息 A* 算法中也设置有两个表: (1) OPEN 表:用以存放状态树的开节点 (2) CLOSED 表:用以存放状态树的闭节点 第4章 状态空间法 --- A* 算法 搜索的费用计算 (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* 算法 搜索的费用估计 So So 经节点 n 到 Sg 的最佳径的费用 f * (n) 的估计函数 f (n) 被定义为: f (n) = g(n) + h(n) n 其中: g(n): g* (n) 函数的估计函数 h(n): h* (n) 函数的估计函数 Sg f (n) 函数又称为 A* 算法的评价函数,既是 So 经 n 到 Sg 的最佳径的费用估计,又是对 So 经 n 到 Sg 的 可能性和最佳性的评价。 第4章 状态空间法 --- A* 算法 Step 1. 将起始节点 So 放入 OPEN,计算 f(So); Step 2. 若 OPEN 空,则失败退出; Step 3. 将 OPEN 中 f 值最小的节点 n 记作 BESTNODE; Step 4. 若 BESTNODE 是目标节点,则成功退出; Step 5. 扩展 BESTNODE,生成其全部子节点,并将它 们放入子节点集合 SUBNODES; Step 6. 对于每一个子节点 SON ? SUBNODES,计算 f(SON),并设置 SON 指向 BESTNODE 的指针; Step 7. 将 BESTNODE 移出 OPEN 并移入 CLOSED;将 SUBNODES 的放入 OPEN; Step 8. 转向 Step 2。 第4章 状态空间法 --- A* 算法 A*搜索算法中OPEN中的数据结构是:表 第5章 问题规约 重点内容: 1、问题规约法的相关概念。 2、问题规约法的求解过程。 第5章 问题规约 ---基本概念 问题规约的基本思想: 将大问题或复杂问题分解为易于处 理或求解的子问题集合。 问题规约的过程是,在问题空间中, 从原始问题 (即待求解问题) 出发,搜索其 本原问题 (即最小问题或具有明显解答的 问题) 集合的过程。 第5章 问题规约 ---基本概念 把一个问题规约为子问题 P1, P2,..., Pn 有两种办法: 分解 这些子问题之间的关系是“与”的关系。 等价变换 这些子问题之间的关系是“或”的关 系 第5章 问题规约 ---求解过程 无论是可解标记过程和不可解标记过 程都是自下而上进行的,既由子节点的可 解性确定其父节点和祖先节点的可解性, 由子节点的不可解性确定其父节点和祖先 节点的不可解性。