人工智能课件2.ppt

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

2、。使用行之有效的知识表示方法解决所面临的问题。使用行之有效的知识表示方法解决所面临的问题。2.1.1 状态空间法 一种基于解答空间的问题表示和求解方法，是以状态状态和操作符操作符为基础的。 方法：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。 由于状态空间法需要扩展过多的节点，容易出现“组合爆炸”，因而只适用于表示比较简单表示比较简单的问题的问题。2.1.1状态空间法 状态状态： 描述某类不同事物间的差别而引入的一组最少变量 q0，q1，qn的有序集合。 矢量形式： 式中每个元素 为集合的分量，称为状态变量。 给定每个分量的一组值就得到一个具体的状态

3、，如： 操作符操作符： 使问题从一种状态描述变化为另一种状态描述的运算。 操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。 iq01,TkkknkQqqq01,TnQqqq2.1.1状态空间法 三数码难题（3 Puzzle Problem）2.1.1状态空间法 对一个问题的状态描述，必须确定 3 件事：1.该状态描述的方式，特别是初始状态描述；2.算符集合及其对状态描述的作用；3.目标状态描述的特性。2.1.1状态空间法 状态图示法： 是一个表示该问题全部可能状态及其关系的图图，它包含三种说明的集合，即三元状态（S，F，G）。 S ： 初始状态集合； F ： 操作符集合； G ：目

4、标状态集合。2.1.1状态空间法 有向图有向图 (directed graph) 图图：由节点（不一定是有限的节点）的集合构成。 有向图：有向图：是指图中的一对节点用弧线连接起来，从一个节点指向另一个节点。 路径路径 某个节点序列（ ）当j=2，3，k时，如果对于每一个 都有一个后继节点 存在，那么就把这个节点序列叫做从节点 至节点 的长度为k的路径。ikiinnn,21jin,ikn1, jin1 in2.1.1状态空间法 寻求一种状态变换为另一种状态的某个算符某个算符序列问题等价于寻求图的某一路径问题序列问题等价于寻求图的某一路径问题。 代价代价 从节点 指向节点 的那段弧线的指定数值/费

5、用。用 表示。 两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。 最优化问题，即找到两节点间具有最小代价的路径。injn),(jnnci2.1.1状态空间法 问题求解：问题求解：即求某指定节点S（初始状态）与另一节点T（目标状态）之间的一条路径。 求得节点S与节点集合 中任一节点之间的距离。 求得节点集合 中任一节点与节点集合 中任一节点之间的路径。 it11 it is2.1.1状态空间法 猴子和香蕉问题2.1.1状态空间法 用一个四元表列（W，x，Y，z）来表示问题状态。 操作（算符）：1.goto（U）表示猴子走到水平位置U或者用产生式规则表示为:2.pushbox（V）猴子

6、把箱子推到水平位置V，即有:2.1.1状态空间法3.climbbox猴子爬上箱顶，即有：4.grasp猴子摘到香蕉，即有： 该初始状态变换为目标状态的操作序列为： goto(b), pushbox(c), climbbox, grasp 2.1.2 问题归约法 从目标（要解决的问题）出发，逆向推理逆向推理，通过一系列变化把初始问题变换为子问题集合和子子问题集合，直至最后归约为一个平凡的本一个平凡的本原问题集合原问题集合。这些本原问题的解可以直接得到，从而解决了初始问题。 比状态空间法更有效地表示问题。状态空间法是问题归约法的一种特例。 问题归约法的与或图与或图中包含与节点和或节点，而状态空间法

7、的状态图示法状态图示法只含有或节点。2.1.2问题归约法2.1.2问题归约法 梵塔难题 把所有的圆盘都移动到柱子3上。 每次只能移动一个圆盘。 只能先搬动柱子顶部的圆盘。 不允许把较大的圆盘放在较小的圆盘上。2.1.2 问题归约法2.1.2 问题归约法 原始的樊塔问题归约为一个较为简单的问题集合，其方法之一为： 要把所有圆盘都移至柱子3，首先需把圆盘C移至柱子3，而且在移动圆盘C至柱子3之前，柱子3必须是空的。 需把圆盘A和B移动至柱子2之后，才能移动圆盘C。 把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。2.1.2问题归约法 把原始难题归约（简化）为下列三个子难题 移动圆盘A和B至柱

8、子2的双圆盘难题 移动圆盘C至柱子3的单圆盘难题（本原本原问题问题） 移动圆盘A和B至柱子3的双圆盘难题2.1.2问题归约法 与或图2.1.2问题归约法2.1.2问题归约法 父节点，一个初始问题或是可分解为子问题的问题节点； 子节点，一个初始问题或是子问题分解的子问题节点； 或节点，只要解决某个问题就可解决其父辈问题的节点集合； 与节点，只有解决所有子问题，才能解决其父辈问题的节点集合； 弧线，是父辈节点指向子节点的圆弧连线； 终叶节点，是对应于原问题的本原节点。2.1.2问题归约法 可解节点可解节点1.终叶节点终叶节点是可解节点（因为它们与本原问题相关连）。2.如果某个非终叶节点含有或或后继

9、节点后继节点，那么只有当其后继节点至少至少有一个是可解的时，此非终叶节点才是可解的。3.如果某个非终叶节点含有与与后继节点后继节点，那么只要当其后继节点全部全部为可解时，此非终叶节点才是可解的。 不可解节点不可解节点1.没有后裔的非终叶节点非终叶节点为不可解节点。2.全部后裔全部后裔为不可解的非终叶节点且含有为或或后继节点后继节点，此非终叶节点才是不可解的。3.后裔至少有一个后裔至少有一个为不可解的非终叶节点且含有与与后继节后继节点点，此非终叶节点才是不可解的。2.1.2问题归约法2.1.2 问题归约法l与或图构成规则l与或图中所含起始节点对应于原始问题原始问题。l终叶节点终叶节点对应于本原问

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

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

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

13、代中找王A的后代且其寿命为X=57的人。2.2 图搜索策略1. 建立一个只含有起始节点起始节点 S的搜索图搜索图G，把S放到一个叫做OPEN的未扩展节点表中。2. 建立一个叫做 CLOSED的已扩展节点表，其初始为空表。 3. LOOP：若OPEN表是空表，则失败退出。 4. 选择OPEN表上的第一个节点，把它从 OPEN表移出并放进 CLOSED表中。 称此节点为节点节点n。5. 若n为一目标节点，则有解并成功退出，此解是搜索图G中沿着指针从沿着指针从n到到S 这条路径而得到这条路径而得到（指针将在第 7步中设置）。 2.2 图搜索策略6. 扩展节点n，同时生成不是n的祖先的那些后继节点的集

14、合M。把M的这些成员作为n的后继节点的后继节点添入图 G中。 7. 对那些未曾在 G中出现过的（既未曾在 OPEN表上或 CLOSED表上出现过的） M成员设置一个通向n的指针 ，把M的这些成员加进 OPEN表。对已经在 OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在 CLOSED表上的每个M成员，确定是否需要更改图 G中通向它的每个后裔节点的指针方向。8. 按某一任意方式或按某个探试值，重排重排OPEN表表。 9. GO LOOP CLOSED中的中的节点是搜索树节点是搜索树中的非端节点中的非端节点OPEN中的节点中的节点是搜索树上未被是搜索树上未被扩展的

15、节点扩展的节点决定该过程是决定该过程是盲目搜索还是盲目搜索还是启发式搜索启发式搜索2.2 图搜索策略 将牌移入空格的顺序： 从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。 从图可见，要扩展 26个节点，共生成 46个节点之后才求得解（目标节点）。2.3 一般搜索与推理技术 启发式搜索： 特点：运用启发信息，引用某些准则或经验引用某些准则或经验来重新排列来重新排列OPEN表中节点的顺序表中节点的顺序，使搜索沿着某个被认为最有希望的前沿区段扩展。 关键点：正确选择估价函数，以寻求最小代价路径或解树。 方法： 有序搜索（最好优先搜索） 最优搜索A*算法 AO*算法2.3 一般搜索与推理技

16、术 盲目搜索：“盲目”穷举，不重排OPEN表 宽度优先搜索：搜索效率次之； 深度优先搜索：搜索效率较差； 等代价搜索（有界深度优先搜索）：具有一定的启发性，搜索效率较高，但可能丢失某些解。2.3 一般搜索与推理技术 高级求解系统 规则演绎系统：采用if-then规则来求解问题。又分为正向、逆向和双向规则演绎系统。 产生式系统：由总数据库、产生式规则和控制策略三部分组成，也分为正向、逆向和双向推理三种形式。 系统组织技术 将一个大系统或复杂系统中的知识划分为一组相对独立的模块，然后考虑各子模块在求解时的合作问题。2.4 A*算法 一种有序搜索算法，总是选择估价函数值最小的节点作为扩展节点。 定义

17、： 任一节点上函数值 表示从节点从节点S开始约束通过节点开始约束通过节点n的一条最佳路的一条最佳路径的代价径的代价。 表示从节点S到节点n的一条最佳路径的实际实际代价。 表示从节点n到某目标节点的一条最佳路径的代价。f*( )( )( )fng nh n*( )g n*( )h n2.4 A*算法 希望估价函数 是 的一个估计。 是 的估计，表示用搜索算法找到的从节点S到节点n的最小代价路径，并且 是 的估计，依赖于有关问题领域的启发信息，因此 又叫做启发函数。f( )( )( )f ng nh n*( )g n*( )h n*f( )g n*( )( )g ng n( )h n( )h n2

18、.4 A*算法( )g n( )h n2.5 消解原理 采用谓词演算方法求解问题时，首先把要解决的问题表示为一个待证明的问题，然后采用消解原理和消解反演过程来证明该问题。 消解原理：采用推理规则进行正向搜索，最终证明该问题（定理）成立 。 消解反演过程：采用反演方法来证明某个定理的否定是不成立的，从而证明该 定理必定是成立的。2.6 产生式系统 由Post于1943年提出的产生式规则而得名。 美国纽厄尔和西蒙于1965年利用这个原理建立了一个人类的认知模型。 斯坦福大学利用产生式系统结构设计出第一个专家系统DENDRAL。2.6 产生式系统 产生式系统用来描述若干个不同的以一个基本概念（产生式

19、条件和操作对）为基础的系统。 产生式系统中，论域被分为2部分： 用事实表示静态知识，如事物、事件和它们之间的关系； 用产生式规则表示推理过程和行为。 求解效率低和无法表示结构性知识，不适用于求解复杂系统。2.6.1 产生式系统组成 总数据库：综合数据库综合数据库，用于存放求解过程中各种当前信息的数据结构，如问题的初始状态、事实或证据、中间推理结论和最后结果等。 产生式规则：一个规则库一个规则库，用于存放与求解问题有关的某个领域知识的规则之集合及其交换规则。 控制策略：一个推理机构一个推理机构，由一组程序组成，用来控制产生式系统的运行，决定问题求解过程的推理线路，实现对问题的求解。2.6.1 产

20、生式系统组成 产生式规则是一个以“如果满足某个条如果满足某个条件，就应当采取某些操作件，就应当采取某些操作”形式表示的语句，其基本形式为： IF 前提 THEN 结论 如： IF 某种动物是哺乳动物，并且吃肉 THEN 这种动物被称为食肉动物条件、前项条件、前项操作、后项操作、后项2.6.1 产生式系统组成 在产生式系统的执行过程中，如果某条规则的条件满足了，则系统的控制部分就可以执行规则的操作部分，并且其结论作为新的事实存入总数据库。控制策略控制策略产生式规则产生式规则总数据库总数据库2.6.1 产生式系统组成 控制策略的作用是说明下一步应该选用什么规则，如何应用规则。 从选择规则到执行操作

21、分为三步： 匹配匹配：把当前数据库与规则的条件部分相匹配。 冲突解决冲突解决：当有一条以上规则的条件部分和当前数据库相匹配时，需要决定首先使用哪一条规则。其策略包括：专一性排序、规则排序、数据排序、规模排序和就近排序等。 操作操作：执行规则的操作部分，经过操作后，当前数据将被修改。2.6.2 产生式系统的推理 正向推理： 从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。 设有下列规则集合13RR112223334:RPPRPPRPP 是谓词公式或命题。设总数据库中已存在事实 ，则应用规则 进行正向推理。14PP1P13RR2.6.2 产生式系统的推理 逆向

22、推理： 首先提出一批假设目标，然后逐一验证这些假设。 设有下列规则集合13RR112223334:RPPRPPRPP 是谓词公式或命题。设总数据库中已存在事实 ，则应用规则 进行逆向推理。14PP1P13RR2.6.2 产生式系统的推理项目项目正向推理正向推理逆向推理逆向推理驱动方式数据驱动目标驱动推理方式从一组数据出发向前推导结论从可能的解答出发，向后推理验证解答启动方式从一个事件启动由询问关于目标状态的一个问题而启动透明程度不能解释其推理过程可解释其推理过程缺点盲目搜索，推理效率低目标的选择盲目性大适用场合用于已知初始数据，无法提供推理目标时，如监控、预测、规划等。用于结论单一或已知结论，而要求验证系统时，如选择、分类、故障诊断等。典型系统CLIPS、OPSPROLOG2.6.2 产生式系统的推理 双向推理： 同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个，实现事实与目标的匹配。总结 本章讨论的推理方法属于确定性推理确定性推理 建立在经典逻辑基础上，运用确定性知识进行精确推理。 又称为单调性推理，即随知识的增加而单调增加。