例 3-4：八数码问题(1) 操作规定: 允许空格四周上、下、左、右的数码块移入空格中，不许斜方向 移动，不许返回先辈结点。 初始布局 S 和目标状态 D 如下图所示：
2 1 7 6 S 8 3 4 5 1 8 7 2 3 4 6 5 D
全局择优搜索 特点： 在 OPEN 表中保留所有已生成而未扩展的节点，并用估价函数 f(n)对它们全 部进行估计，从中选出最优的节点进行扩展，因此，亦称“最好优先搜索 法” 。 得到的不一定是实际上的最佳解。 全局择优搜索流程
第1章
人工智能 以思维与智能为核心。 是计算机科学、逻辑学、思维学、生理学、心理学、电子学、语言学、教育学等 多学科相互渗透的结果。 人工智能原理的四大问题 知识表示，人工智能研究的最基本问题 问题求解，人工智能的根本问题 机器学习，人工智能产生的核心问题 系统构成，人工智能的中心问题 已有的知识表示法：谓词逻辑表示法、模糊逻辑表示法、产生式表示法、状态空间表示法、 与/或图表示法、语义网络表示法，框架表示法等。 问题的求解与表示 (1) 问题用谓词公式表示，用演绎推理来求解。 (2) 问题用状态空间法表示，用搜索法求解。 机器学习常用方法有：死记硬背法、参数修正法、问题求解法、概念法、发现法等。 系统构成 人工智能的工作需要硬件、软件、接口等多方面的支持与配合。
知识表示体系：
表 示 方 法 替 代 表 示 直 接 表 示 分 布 表 示
局 部 表 示 过 程 性 表 示 语 义 网 络 表 示 框 架 表 示 脚 本 表 示
叙 述 性 表 示 逻 辑 表 示 产 生 式 表 示
状态 状态空间法表示问题基本步骤： (1) 定义状态的描述形式。 (2) 用所定义的状态描述形式把问题的所有可能状态都表示出来，并确定出问题的初 始状态描述和目标状态描述。 (3) 定义一组算符，使得利用这组算符可把问题由一种状态转变为另一种状态。 例 2-9：用谓词逻辑公式表示命题“任何整数或是正的或是负的”。 integer ( x )表示“是整数”， positive( x ) 表示“是正 解：设 数”，negative ( x ) 表示“是负数”。 于是根据给定命题，可用谓词逻辑公式表示如下：
第 3 章 智能求解及其搜索策略
搜索系统由以下三大成分构成 ： 知识库：描述当前任务的范围以及要求解问题的目标。 规则 :用于对数据库的加工处理。 控制性知识：决定下一步应如何做？选择什么操作？在何处使用此控制？
同构同态变换
原始问题 h 同态问题
难解
原始解答 h-1
易解
同态解答
状态空间求解法 用状态描述与问题相关的事实和事实间的关系。 状态常表示为矢量。 问题的状态空间可记为三元组(S，F，G)。
(2)若 OPEN 为空，则搜索失败，问题无解； (3)弹出 OPEN 中栈顶结点 n，放入 CLOSE 表中，并给出顺序编号 n； (4)若 n 为目标结点 D，则搜索成功，问题有解； (5)若 n 的深度 d(n)=d，则转(2) ； (6)若 n 无子结点，即不可扩展，转(2) ； (7)扩展结点 n，将其所有子结点配上返回 n 的指针，并压入 OPEN 堆栈，转(2) 。 特点： 节点间有向边的代价不同 算法修改： (1)广度优先搜索法：每次从 OPEN 表中取出具有最小代价的节点进行扩展 。 (2)有界深度优先搜索法： 用代价限制 g 代替深度限制 d， 用代价 g(n)代替节点深度 d(n)。 基本思想 ： 选择一个节点的后继节点， 是在它的所有子节点中， 选估价函数 f(n)最优者。 因此， 亦称“瞎子爬山法”。 特点： 可以取消 OPEN 表，每次扩展后只保留一个最优子节点，直接放入 CLOSE 表中，丢掉其它子节点。 主要在单因素、单极值情况下使用；在多因素，多极值情况下，找不到最佳 解。 什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？ 用状态空间法表示问题时，什么是问题的解？求解过程的本质是什么？什么是最优 解？最优解唯一吗？ 请写与状态空间图的一般搜索过程。在搜索过程中 OPEN 表和 CLOSE 表的作用分 别是什么？有何区别？
推理 定义： 从已有事实和知识中推出结论。 推理方法分类： 按途径分： 演绎推理、归纳推理、默认推理。 按所用知识的确定性分：
确定性推理、不确定推理。 按结论是否单调增加分： 单调推理、非单调推理。 按推理中是否运用启发性知识分： 启发式推理、非启发式推理。 推理系统构成： 知识库 、数据库 、推理机。
开始 把 S 放入 OPEN 表，计算 f(S),置 n=0 OPEN=NULL 取出 OPEN 表中最前的结点放入 CLOSE 表中，并寇以顺序编号 n n=目标结点 D？ n 可以扩展？ 扩展 n,将其子结点 ni 依次放入 OPEN 表中， 并配上指向 n 的返回指针，计算 f(ni),并按 f(ni)值对 OPEN 表重新排序（小的在前） 成功 失败
专家 知识获取设 施（工具）
用户 输入/输出 系 统 建议 说明 具体事实 与数据
知识库
推理系统
知识工程师
人工智能应用系统的结构特征（特点）是： (1)系统要有智能就必须拥有知识。 (2)系统应具备某种推理的能力。 (3)具备某种继续获取知识的功能。 什么是人工智能？人工智能的意义和目标是什么？ 人工智能系统的特点有哪些？
第2章
知识是经过筛选和整理的信息，是对事物运动变化规律的表述，是人类对客观世界一种较 为准确、全面的认识和理解。 知识按问题求解要求分为： 叙述型知识、过程型知识、控制型知识。 知识按其作用分为： 描述性知识、判断性知识、过程性知识。 知识按其描述对象分为： 对象级知识、元知识 。 元知识：Ravis,1997 提出。是关于知识的知识。 叙述型知识: 描述有关系统状态、环境和条件，问题的概念、定义和事实的知识。 过程型知识: 描述有关系统状态变化、问题求解过程的操作、演算和行动的知识。 控制型知识: 描述有关如何选择相应的操作、演算和行动的比较、判断、管理和决 策的知识。 例：对于从北京到大庆，是乘飞机还是坐火车的问题，有关的知识可以归纳为： 叙述型知识: 北京、大庆、飞机、火车、时间费用。 过程型知识: 乘飞机、坐火车。 控制型知识: 乘飞机较快、较贵；坐火车较慢、较便宜。 同构变换与同态变换： 同构问题的解答等价于原始问题的解答。 原始问题有解，则同态问题有解；同态问题无解，则原始问题
使用自然语言、专门语言、图象的人机对话接口 人机 接口
知识库 管理软件
解题推理 软件
智能接口 软件
软件
知识库硬件 关系代数 关系数据库
解题推理硬件 逻辑程序 设计语言 逻辑机 智能接口 硬件 硬件
超大规模集成电路体系结构
系统构成包括以下五个方面： 人工智能语言 智能应用软件 软件开发环境与工具 硬件支持环境 人机智能接口 专家系统是指一类计算机智能程序，可从事特定的、难度较高的专业工作。 基本结构：如图。
大 小 结构程序 所属类型 类似于 说 明 对象框架 对象 长方块 姿态 水平 对象框架 对象 长方块 姿态 垂直 关系框架 顶 be-supported-by 柱 1 not-touch 柱 2
什么是知识？它有哪些特征？有哪几种主要的知识分类？ 什么是知识表示？知识表示有哪些要求？ 什么是状态空间？状态空间是怎样构成的？给出状态空间法表示问题的一般步骤。 一阶谓词表示法适合于表示哪种类型的知识？它有哪些特点？ 何谓语义网络？它有哪些基本的语义关系？
已扩展节点、未扩展节点的数据结构
OPEN表结构 状态结点 父结点 编号
CLOSED表结构 状态结点 父结点
状态空间搜索算法流程：
开 始
初始化：S放入OPEN表，CLOES表置空, n=1 Y
OPEN为空表NULL ？ N
失败
OPEN表中的第一个结点n移至CLOSE表 n=目标结点D吗 ? N 若n的后继未曾在搜索图G中出现，则将其放入OPEN 表的末端，并提供返回结点n的指针, 置n=n+1 根据后继结点在搜索图G中的出现情况 修改指针方向 依某种准则重新排序OPEN表 Y 成功
搜索策略： 状态空间搜索(广度优先搜索、深度优先搜索、有界深度优先搜索等 )、启发式搜索 等。 广度优先搜索 搜索原则： 深度越小、越早生成结点的优先级越高。 当最低层不止一个结点时，它选择最先生成的结点进行搜索。 广度优先算法步骤： (1) 初始结点 S 加入到队列 OPEN 的尾部； (2) 若 OPEN 为空，则搜索失败，问题无解； (3) 取出 OPEN 队头的结点 n，并放入 CLOSE 队列中； (4) 若 n 是目标结点 D，则搜索成功，问题有解； (5) 若 n 是叶结点，则转(2)； (6) 扩展 n 结点(即找出它的所有直接后继)，并把它的诸子结点依次加入 OPEN 队尾，修改 这些子结点的返回指针，使其指向结点 n。转(2)。 穿透率 反映目标搜索时的搜索范围。定义为：P=L/T L 是到达目标的长度；T 是在整个搜索过程中产生的结点总数，显然 P≤1。 P 还和问题的难度相关，一般是 L 越大，问题越困难，P 值越小；反之 P 则越大。 局部择优搜索 基本思想 ： 选择一个节点的后继节点， 是在它的所有子节点中， 选估价函数 f(n)最优者。 因此， 亦称“瞎子爬山法”。 特点： 可以取消 OPEN 表，每次扩展后只保留一个最优子节点，直接放入 CLOSE 表中，丢掉其它子节点。 主要在单因素、单极值情况下使用；在多因素，多极值情况下，找不到最佳 解。 局部择优算法步骤： 流程：
is-a
楔形块
长方块
楔形块
长方块
（d）A是一个楔形块，B是一个长方块
（e）一个完整的房子概念
例 2-17： 用框架表示拱的概念。下图为拱的框架表示法，左边是拱的主框架，另 外三个子框架用来描述它的组成对象和关系，其中有两个各说明一个终端，另一个 则被两个终端所共享。