问题归约法(共9页).doc

《问题归约法(共9页).doc》由会员分享，可在线阅读，更多相关《问题归约法(共9页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上教案名称知识表示方法-问题归约法科目教学对象主讲人课时一、教学目标1. 通过梵塔难题重点掌握问题归约法的机理和问题归约描述方法2.学会用与或图表示归约问题。二、教学流程（教学策略选择与设计）一、引言 通过一个状态空间法的例子，看出状态空间法的局限性，从而引出问题归约法。 二、问题归约描述由上述说明，给出一个具体的梵塔问题。通过同学之间谈论思考后，给出一个利用问题归约法的解题步骤，从而引出问题归约法的一些概念。再给出问题归约法的标准定义和具体细节。三、 与或图表示 由上述梵塔问题的解题过程初步了解了与或图表示，本节通过一个具体的例子给出了与或图表示的概念，同时思考问题归

2、约法、与或图表示之间的对应关系，并给出其的对应关系。给出节点可解和不可解的定义，进一步了解与或图表示。给出例子让同学们判断节点是否可解。总结问题归约法和与或图表示，给出几道题，让同学们思考并解题，进一步了解问题归约法和与或图表示，并熟练掌握。四、 问题归约机理 以上内容我们了解并学习了问题归约法和与或图表示，为了进一步了解其内容。我们通过两篇论文来讨论分析。上节课老师给我们讲了知识表示方法中的状态空间法，本节课开始我们先通过二阶梵塔问题再来复习一下状态空间法。教学过程（引言）教学过程（问题归约描述）通过介绍“梵塔难题”(Tower-of-Hanoi Puzzle)及其求解来讨论问题归约描述,梵

3、塔难题为了说明如何用问题归约法求解问题,下面考虑著名的AI问题-“梵塔难题”(Tower-of-Hanoi Puzzle),其提法如下:1有3个柱子(1,2和3)和3个不同尺寸的圆盘(A,B和C).圆盘的中心有个孔,圆盘可以堆叠在柱子上.2最初,全部3个圆盘都堆在柱子1上;最大的圆盘C在底部,最小的圆盘A在顶部。3现要求把所有圆盘都移到柱子3上,每次只许移动一个,而且圆盘只能从上到下移动,且堆放只能从小到大.梵塔难题的初始配置和目标配置如图1所示. 思考此问题，并由此问题了解梵塔难题和问题规约法（同学讨论）（5分钟）给出具体解： 梵塔难题可采用前一讲的状态空间法来求解. 其状态空间图每个节点代

4、表柱子上圆盘的一种状态,共含有27个节点,其节点(状态)数、规则数多,求解较复杂. 本讲讨论对梵塔难题而言,问题表述和求解更简洁的问题归约法. 状态空间描述： 三个盘子的位置列表(a, b, c) a=1,2,3; b=1,2,3; c=1,2,3 初始状态：S = (1, 1, 1) 目标状态：G = (3, 3, 3)算符集合：Move (x, i, j)： x = A,B,C; i= 1,2,3; j= 1,2,3上述论证允许把原始问题归约(简化)为下列3个子问题;1. 移动圆盘A和B至柱子2的双圆盘问题,如图2(a)所示. 图2(a) 移动圆盘A和B至柱子22. 移动圆盘C至柱子3的单

5、圆盘问题,如图2(b)所示. 图2(b) 移动圆盘C至柱子33. 移动圆盘A和B至柱子3的双圆盘问题,如图2(c)所示. 图2(C) 移动圆盘A和B至柱子3问题归约 双圆盘问题 : (111) (122) 单圆盘问题 : (122) (322） 本原 双圆盘问题 : (322) (333）由于3个简化了的问题都较小,都比原始问题容易解决.子问题2为本原问题,因为它的解只包含一步移动.应用一系列相似的推理,子问题1和子问题3也可被归约为本原问题,如图3a所示问题归约描述 由以上例子，我们给出了问题归约法的一些概念。（1） 问题规约法的基本概念问题规约是人类处理或求解大问题或复杂问题的一种常用的方

6、式。人们常常将大的问题或复杂的问题分解为一系列小的或简单的问题，然后，分别加以处理或求解。一个大的问题常常是由一些小的问题构成的，一个复杂的问题常常是由一些简单问题构成的。这些小的问题或简单的问题就是大问题或复杂问题的子问题。问题规约方法模拟人类处理大问题或复杂问题的智能行为，将大问题或复杂问题分解为较小或较简单的问题，将较小或较简单的问题再分解为更小或更简单的问题，直至所有的问题都易于处理或求解为止。问题规约法：从已知问题的描述出发，通过一系列变换或分解将问题最终变为一个子问题集合，这些子问题的解可以直接得到，从而解决初始问题。问题规约法的实质：从目标（要解决的问题）出发逆向推理，建立子问题

7、以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。最小的问题或具有明显解答的问题被称为本原问题。例如，对于不定积分问题， dx 就是一个本原问题，其答案是显而易见的，即 dx=x。一般地，本原问题是原始问题的子孙问题。因此，问题规约的过程就是在问题空间中不断搜索问题的子问题和子问题的子问题的过程，直至将原始问题分解为本原问题集合。本原问题的解可以直接得到或通过一个黑箱操作得到。（2）问题归约表示可由下列3部分组成: 一个初始问题描述; 将问题变换为子问题的操作集; 一系列本原问题描述.问题的归约描述 初始问题集合：初始状态集合 S 算符集合：将问题分解为若干子问题的变换集合F

8、 本原问题集合：目标状态集合G 三元组合：（S , F, G）（3）问题规约法与状态空间法 问题归约与前面状态空间描述不同的是,主要其在问题空间中展开对问题的描述和求解。 状态空间法只是研究对问题所陈述的事实状态如何表示,以及如何搜索状态空间求解;而问题归约法则是对问题求解中如何将问题逐步分解为一系列子问题本原问题的集合。 对实际问题求解,可将这两种方法有机结合,如后面讨论到的与或图表示与搜索。1 与或图的概念用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。例：有一个问题A，它可以通过三种途径来求解： （1）、求解问题B和C （2）、求解问题D、E和F （3）、求解问题

9、H这一问题归约为子问题的替换集合关系可由图4所示的结构来表示.图中各节点由它们所表示的问题来标记从该图可读得:问题B和C构成子问题的一个集合;D、E和F构成另一子问题集合;而H则为第3个集合.对应于某个给定集合的各节点,用连接弧线的标记来指明. 为了不出现既有与子节点又有或子节点的节点,使得状态图更规范,更容易被计算机所存储与处理,通常把某些附加节点引入此结构图.这样便使含有一个以上子问题的每个集合能够聚集在它们各自的父节点之下.根据这一约定,图4的结构变为图5所示的结构. 其中,标记为N和M的附加节点分别作为集合B,C和D,E,F的唯一父节点,具有辅助问题描述的作用.对于图5,问题A被归约为

10、单一替换子问题N、M和H.因此,把节点N、M和H叫做或节点.然而,N被归约为子问题B和C的单一集合,要求解N就必须求解所有的子问题.因此,把节点B和C叫做与节点.定义： 父节点是一个初始问题或是可分解为子问题的问题节点； 子节点是一个初始问题或是子问题分解的子问题的节点； 或节点只要解决某个问题就可解决其父辈问题的节点集合； 与节点只有解决所有子问题，才能解决其父辈问题的节点集合； 弧线是父辈节点指向子节点的圆弧连线； 终叶节点是对应于本原问题的本原节点。2 问题归约法、与或图表示之间的对应关系： 问题归约法 与或图表示 原始问题 起始问题 本原问题 终叶节点 操作符 与、或关系的弧线 中间问

11、题 非终叶节点3 节点可解性和不可解性的定义在与或图上执行的搜索过程,其目的在于表明初始节点是有解的.下面给出可解节点的定义.定义1 与或图中可解节点可以归纳定义如下:终叶节点是可解节点(因为它们与本原问题相关连).如果某个非终叶节点含有或子节点,那么只有当其子节点至少有一个是可解的时,此非终叶节点才是可解的.如果某个非终叶节点含有与子节点,那么只要当其子节点全部为可解时,此非终叶节点才是可解的.于是,一个解图被定义为那些可解节点的子图,这些节点能够(按上述定义)证明其初始节点是可解的.定义2 与或图中不可解节点的归纳定义于下:没有子节点的非终叶节点为不可解节点.如果某个非终叶节点含有或子节点

12、,那么只有当其全部子为不可解时,此非终叶节点才是不可解的.如果某个非终叶节点含有与子节点,那么只要当其子节点至少有一个为不可解时,此非终叶节点才是不可解的.图6给出与或图的一些例子.图中,终叶节点用字母t标示,有解节点用小圆点表示,而解图用绿线分支表示.不可解节点用小圆圈表示 由以上概念给出几道题，用问题归约法和与或图表示的方法解题。（思考并求解）（5分钟） 一下给出求解过程：由该问题归约的与或图,可读出该符号积分的解为:(1) 原始问题 p(o)： 此不定积分问题的描述示例如下： (2) 本原问题 p(p)： dz (3) 算子空间 WO： 积分规则不定积分问题规约过程的与或搜索图 专心-专注-专业