人工智能幻灯片2

《人工智能幻灯片2》由会员分享，可在线阅读，更多相关《人工智能幻灯片2（61页珍藏版）》请在金锄头文库上搜索。

1、人工智能及其应用,第二章 知识表示与推理,目录,知识表示的一般方法 图搜索策略 一般搜索与推理技术 A*算法 消解原理 规则演绎系统 产生式系统 系统组织技术,2.1 知识表示的一般方法,每种以符号和逻辑为基础的智能系统，其问题求解方法都需要某种对解答的搜索。在搜索之前，必须先用某种方法或某几种方法的混合来表示问题。 对同一问题可以有不同的表示方法，问题表示的优劣，对求解结果及求解工程量的影响甚大。 问题求解大多采用试控搜索的方法，即通过在某个可能的解空间内寻找一个解来求解问题。,使用行之有效的知识表示方法解决所面临的问题。,2.1.1 状态空间法,一种基于解答空间的问题表示和求解方法，是以状

2、态和操作符为基础的。 方法：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。 由于状态空间法需要扩展过多的节点，容易出现“组合爆炸”，因而只适用于表示比较简单的问题。,2.1.1状态空间法,状态： 描述某类不同事物间的差别而引入的一组最少变量 q0，q1，qn的有序集合。 矢量形式： 式中每个元素 为集合的分量，称为状态变量。 给定每个分量的一组值就得到一个具体的状态，如： 操作符： 使问题从一种状态描述变化为另一种状态描述的运算。 操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。,2.1.1状态空间法,三数码难题（3 Puzzle Pro

3、blem）,2.1.1状态空间法,对一个问题的状态描述，必须确定 3 件事： 1.该状态描述的方式，特别是初始状态描述； 2.算符集合及其对状态描述的作用； 3.目标状态描述的特性。,2.1.1状态空间法,状态图示法： 是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。 S ： 初始状态集合； F ： 操作符集合； G ：目标状态集合。,2.1.1状态空间法,有向图 (directed graph) 图：由节点（不一定是有限的节点）的集合构成。 有向图：是指图中的一对节点用弧线连接起来，从一个节点指向另一个节点。 路径 某个节点序列（ ）当j=2，3，k

4、时，如果对于每一个 都有一个后继节点 存在，那么就把这个节点序列叫做从节点 至节点 的长度为k的路径。,2.1.1状态空间法,寻求一种状态变换为另一种状态的某个算符序列问题等价于寻求图的某一路径问题。 代价 从节点 指向节点 的那段弧线的指定数值/费用。用 表示。 两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。 最优化问题，即找到两节点间具有最小代价的路径。,11,2.1.1状态空间法,问题求解：即求某指定节点S（初始状态）与另一节点T（目标状态）之间的一条路径。 求得节点S与节点集合 中任一节点之间的距离。 求得节点集合 中任一节点与节点集合 中任一节点之间的路径。,2.1.1

5、状态空间法,猴子和香蕉问题,2.1.1状态空间法,用一个四元表列（W，x，Y，z）来表示问题状态。 操作（算符）： 1.goto（U）表示猴子走到水平位置U或者用产生式规则表示为: 2.pushbox（V）猴子把箱子推到水平位置V，即有:,2.1.1状态空间法,3.climbbox猴子爬上箱顶，即有： 4.grasp猴子摘到香蕉，即有： 该初始状态变换为目标状态的操作序列为： goto(b), pushbox(c), climbbox, grasp ,2.1.2 问题归约法,从目标（要解决的问题）出发，逆向推理，通过一系列变化把初始问题变换为子问题集合和子子问题集合，直至最后归约为一个平凡的本

6、原问题集合。这些本原问题的解可以直接得到，从而解决了初始问题。 比状态空间法更有效地表示问题。状态空间法是问题归约法的一种特例。 问题归约法的与或图中包含与节点和或节点，而状态空间法的状态图示法只含有或节点。,2.1.2问题归约法,2.1.2问题归约法,梵塔难题 把所有的圆盘都移动到柱子3上。 每次只能移动一个圆盘。 只能先搬动柱子顶部的圆盘。 不允许把较大的圆盘放在较小的圆盘上。,2.1.2 问题归约法,2.1.2 问题归约法,原始的樊塔问题归约为一个较为简单的问题集合，其方法之一为： 要把所有圆盘都移至柱子3，首先需把圆盘C移至柱子3，而且在移动圆盘C至柱子3之前，柱子3必须是空的。 需把

7、圆盘A和B移动至柱子2之后，才能移动圆盘C。 把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。,2.1.2问题归约法,把原始难题归约（简化）为下列三个子难题 移动圆盘A和B至柱子2的双圆盘难题 移动圆盘C至柱子3的单圆盘难题（本原问题） 移动圆盘A和B至柱子3的双圆盘难题,2.1.2问题归约法,与或图,2.1.2问题归约法,2.1.2问题归约法,父节点，一个初始问题或是可分解为子问题的问题节点； 子节点，一个初始问题或是子问题分解的子问题节点； 或节点，只要解决某个问题就可解决其父辈问题的节点集合； 与节点，只有解决所有子问题，才能解决其父辈问题的节点集合； 弧线，是父辈节点指向子节点的

8、圆弧连线； 终叶节点，是对应于原问题的本原节点。,2.1.2问题归约法,可解节点 1.终叶节点是可解节点（因为它们与本原问题相关连）。 2.如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。 3.如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。 不可解节点 1.没有后裔的非终叶节点为不可解节点。 2.全部后裔为不可解的非终叶节点且含有为或后继节点，此非终叶节点才是不可解的。 3.后裔至少有一个为不可解的非终叶节点且含有与后继节点，此非终叶节点才是不可解的。,2.1.2问题归约法,2.1.2 问题归约法

9、,与或图构成规则 与或图中所含起始节点对应于原始问题。 终叶节点对应于本原问题的节点。 将某一算符作用于问题A，其目的是把问题A变换为一个子问题集合；有向弧线自A 指向后继节点，表示所求得的子问题（或子问题集合）。 一般对于代表两个或两个以上子问题集合的节点，有向弧线就需从此节点指向此子问题集合中的每个节点。,2.1.2问题归约法,樊塔问题与或图,2.1.2问题归约法,樊塔问题状态空间法,2.1.2问题归约法,猴子和香蕉问题与或图,2.1.2 问题归约法,2.1.3 谓词逻辑法,一种形式语言，能够把数学中的逻辑论证符号化。 采用谓词合式公式和一阶谓词演算把要解决的问题变为一个有待证明的问题，然

10、后采用消解定理和消解反演来证明一个新语句是从已知的正确语句导出的，从而证明这个新语句也是正确的。 常与其他方法混合使用，表示比较复杂的问题。,2.1.4 语义网络法,一种结构化表示方法。 由节点和弧线或链线组成。 节点：表示物体、概念和状态。 弧线：表示节点间的关系。 语义网络的解答是一个经过推理和匹配而得到的具有明确结果的新的语义网络。 可表示多元关系，扩展后可表示更复杂的问题。,2.1.5 框架,一种结构化表示方法。 通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又拥有若干个值。 大多数实用系统必须同时使用许多框架，可联成一个框架系统。 剧本是框架的一种特殊形式，使用一组

11、槽来描述事件的发生序列，特别适用于描述顺序性动作或事件。,2.1.6 过程,一种知识的过程式表示方法。 将某一有关问题领域知识与这些使用方法一起，隐式地表示为一个问题求解过程。 用程序来描述问题，具有很高的问题求解效率。 由于知识隐含在程序中难以操作，适用范围较窄。,2.2 图搜索策略,搜索过程既是一个问题求解的过程。 搜索过程可采用适当的搜索技术，如各种规则、过程和算法等推理技术，力求找到问题的解答。 图搜索策略可看成是一种在图中寻找路径的方法。 图搜索策略最终生成一个明确的搜索图（图G）和搜索树（G的一个子集T）。,2.2 图搜索策略,从某王姓家族的四代中找王A的后代且其寿命为X=57的人

12、。,2.2 图搜索策略,建立一个只含有起始节点 S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。 建立一个叫做 CLOSED的已扩展节点表，其初始为空表。 LOOP：若OPEN表是空表，则失败退出。 选择OPEN表上的第一个节点，把它从 OPEN表移出并放进 CLOSED表中。 称此节点为节点n。 若n为一目标节点，则有解并成功退出，此解是搜索图G中沿着指针从n到S 这条路径而得到（指针将在第 7步中设置）。,2.2 图搜索策略,扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图 G中。 对那些未曾在 G中出现过的（既未曾在 OPEN表上或 C

13、LOSED表上出现过的） M成员设置一个通向n的指针 ，把M的这些成员加进 OPEN表。对已经在 OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在 CLOSED表上的每个M成员，确定是否需要更改图 G中通向它的每个后裔节点的指针方向。 按某一任意方式或按某个探试值，重排OPEN表。 GO LOOP,CLOSED中的节点是搜索树中的非端节点,OPEN中的节点是搜索树上未被扩展的节点,决定该过程是盲目搜索还是启发式搜索,2.2 图搜索策略,将牌移入空格的顺序： 从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。 从图可见，要扩展 26个节点，共生成 46个

14、节点之后才求得解（目标节点）。,2.3 一般搜索与推理技术,启发式搜索： 特点：运用启发信息，引用某些准则或经验来重新排列OPEN表中节点的顺序，使搜索沿着某个被认为最有希望的前沿区段扩展。 关键点：正确选择估价函数，以寻求最小代价路径或解树。 方法： 有序搜索（最好优先搜索） 最优搜索A*算法 AO*算法,2.3 一般搜索与推理技术,盲目搜索：“盲目”穷举，不重排OPEN表 宽度优先搜索：搜索效率次之； 深度优先搜索：搜索效率较差； 等代价搜索（有界深度优先搜索）：具有一定的启发性，搜索效率较高，但可能丢失某些解。,2.3 一般搜索与推理技术,高级求解系统 规则演绎系统：采用if-then规

15、则来求解问题。又分为正向、逆向和双向规则演绎系统。 产生式系统：由总数据库、产生式规则和控制策略三部分组成，也分为正向、逆向和双向推理三种形式。 系统组织技术 将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后考虑各子模块在求解时的合作问题。,2.4 A*算法,一种有序搜索算法，总是选择估价函数值最小的节点作为扩展节点。 定义： 任一节点上函数值 表示从节点S开始约束通过节点n的一条最佳路径的代价。 表示从节点S到节点n的一条最佳路径的实际代价。 表示从节点n到某目标节点的一条最佳路径的代价。,2.4 A*算法,希望估价函数 是 的一个估计。 是 的估计，表示用搜索算法找到的从节点S

16、到节点n的最小代价路径，并且 是 的估计，依赖于有关问题领域的启发信息，因此 又叫做启发函数。,2.4 A*算法,2.5 消解原理,采用谓词演算方法求解问题时，首先把要解决的问题表示为一个待证明的问题，然后采用消解原理和消解反演过程来证明该问题。 消解原理：采用推理规则进行正向搜索，最终证明该问题（定理）成立 。 消解反演过程：采用反演方法来证明某个定理的否定是不成立的，从而证明该 定理必定是成立的。,2.6 产生式系统,由Post于1943年提出的产生式规则而得名。 美国纽厄尔和西蒙于1965年利用这个原理建立了一个人类的认知模型。 斯坦福大学利用产生式系统结构设计出第一个专家系统DENDRAL。,2.6 产生式系统,产生式系统用来描述若干个不同的以一个基本概念（产生式条件和操作对）为基础的系统。 产生式系统中，论域被分为2部分： 用事实表示静态知识，如事物、事件和它们之间的关系； 用产生式规则表示推理