《第03讲问题归约法.ppt》由会员分享，可在线阅读，更多相关《第03讲问题归约法.ppt（58页珍藏版）》请在三一文库上搜索。
1、第三讲 知识表示方法 -问题归约法,Problem Reduction Method - One of Knowledge Represent Methods,目录(1/1),目 录 引言 问题归约描述 梵塔难题 问题归约描述 与或图表示 问题归约机理 关键算符 差别,1 引言(1/3),1 引言 问题归约(reduction)是另一种问题描述与求解方法. 所谓归约,即降阶. 简单地说,问题归约是通过系列变换将问题变换为一个可以直接求解的本原问题的集合,从而解决了初始问题. 这里,所谓本原问题就是不可或不需再通过变换化简的“原子”问题， 本原问题的解可以直接得到或通过一个“黑箱“操作得到。,1
2、 引言(2/3),采用问题归约表示可由下列3部分组成: 一个初始问题描述; 将问题变换为子问题的操作集; 一系列本原问题描述. 从目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题,直至最后把初始问题归约为一个平凡的本原问题集合. 这就是问题归约的实质.,1 引言(3/3),这里值得指出的是: 问题归约与前面状态空间描述不同的是,主要其在问题空间中展开对问题的描述和求解. 状态空间法只是研究对问题所陈述的事实状态如何表示,以及如何搜索状态空间求解; 而问题归约法则是对问题求解中如何将问题逐步分解为一系列子问题本原问题的集合. 对实际问题求解,可将这两种方法有机结合,如后面讨论到的与
3、或图表示与搜索.,2 问题归约描述(1/1),2 问题归约描述 本节通过介绍“梵塔难题”(Tower-of-Hanoi Puzzle)及其求解来讨论问题归约描述,主要内容有: 梵塔难题 问题归约描述,2.1 梵塔难题(1/9),2.1 梵塔难题 为了说明如何用问题归约法求解问题,下面考虑著名的AI问题-“梵塔难题”(Tower-of-Hanoi Puzzle),其提法如下: 有3个柱子(1,2和3)和3个不同尺寸的圆盘(A,B和C).圆盘的中心有个孔,圆盘可以堆叠在柱子上. 最初,全部3个圆盘都堆在柱子1上;最大的圆盘C在底部,最小的圆盘A在顶部. 现要求把所有圆盘都移到柱子3上,每次只许移动
4、一个,而且圆盘只能从上到下移动,且堆放只能从小到大.,2.1 梵塔难题(2/9),梵塔难题的初始配置和目标配置如图1所示.,2.1 梵塔难题(3/9),梵塔难题可采用前一讲的状态空间法来求解. 其状态空间图每个节点代表柱子上圆盘的一种状态,共含有27个节点,其节点(状态)数、规则数多,求解较复杂. 本讲讨论对梵塔难题而言,问题表述和求解更简洁的问题归约法.,2.1 梵塔难题(4/9),图1所示的原始梵塔问题可归约为如下较简单的问题集合: 要把所有圆盘都移至柱子3,必须首先把圆盘C移至柱子3;而且此前,要求柱子3必须是空的. 只有在移开圆盘A和B之后,才能移动圆盘C; 而且圆盘A和B不要移至柱子
5、3,否则就不能尽快把圆盘C移至柱子3. 因此,首先应该把圆盘A和B移到柱子2上. 然后才能够进行关键的一步,把圆盘C从柱子1移至柱子3,并继续解决难题的其余部分.,2.1 梵塔难题(5/9),上述论证允许把原始问题归约(简化)为下列3个子问题; 1. 移动圆盘A和B至柱子2的双圆盘问题,如图2(a)所示.,图2(a) 移动圆盘A和B至柱子2,2.1 梵塔难题(6/9),2. 移动圆盘C至柱子3的单圆盘问题,如图2(b)所示.,图2(b) 移动圆盘C至柱子3,2.1 梵塔难题(7/9),3. 移动圆盘A和B至柱子3的双圆盘问题,如图2(c)所示.,图2(C) 移动圆盘A和B至柱子3,2.1 梵塔
6、难题(8/9),由于3个简化了的问题都较小,都比原始问题容易解决. 子问题2为本原问题,因为它的解只包含一步移动. 应用一系列相似的推理,子问题1和子问题3也可被归约为本原问题,如图3a所示.,2.1 梵塔难题(9/9),这种图式结构,叫做与或图. 它能有效地说明如何由问题归约法求得问题的解答. 顺序解读与或图,按问题归约顺序将其本原问题及其解组合,即可得到原问题的解. 如,对该梵塔问题,从与或图读得的解为如下操作顺序:,2.2 问题归约描述(1/5),2.2 问题归约描述 问题归约方法应用算符来把问题描述变换为子问题描述. 问题描述可以有各种数据结构形式,表列、树、字符串、矢量、数组等都曾被
7、采用过. 对于梵塔难题可用一个包含两个数列的表列来描述. (113)(333) 就意味着 “把配置(113)变换为配置(333)”.,2.2 问题归约描述(2/5),可以用状态空间表示的三元组合(S,F,G)来规定与描述问题. 有关子问题可当作状态空间中两个的“路标”(对问题求解有重要作用的中间状态)之间寻找路径的问题来辨别. 对梵塔问题,子问题 (111)(122), (122)(322)和 (322) (333) 规定了解答路径将要通过的路标(122)和(322).,2.2 问题归约描述(3/5),问题归约方法可以应用状态、算符和目标这些表示法来描述问题,这并不意味着问题归约法和状态空间法
8、是一样的. 实际上,可以把问题归约法看做比状态空间法更通用的问题求解方法.,2.2 问题归约描述(4/5),归约算符将问题描述变换为一个归约或子问题描述的集合. 变换所得所有子问题的解就意味着父辈问题的一个解. 所有问题归约的目的是最终产生具有明显解答的本原问题, 这些问题可能是能够由状态空间搜索中走动一步来解决的问题, 或者可能是别的具有已知解答的更复杂的问题. 本原问题除了对终止搜索过程起着明显的作用外,有时还被用来限制归约过程中产生子问题的替换集合. 当一个或多个子问题属于某个本原问题的指定子集时,就出现这种限制.,2.2 问题归约描述(5/5),下面再介绍基于问题归约的 符号积分系统和
9、 非线性系统的最优控制 的例子.,2.2 问题归约描述-符号积分问题(1/4),例1 符号积分问题 所谓符号积分是求不定积分原函数的符号运算问题. 符号积分为通过应用各种 代数变换 三角变换以及 不定积分性质,如 函数和积分、 分部积分等 可以把复杂的积分问题逐步归约为若干个本原积分问题（可利用积分表直接求出原函数）。,2.2 问题归约描述-符号积分问题(2/4),上世纪六十年代开发的SAINT系统就是一个应用问题归约的符号积分系统。 下图为一个符号积分的问题归约图.,2.2 问题归约描述-符号积分问题(3/4),2.2 问题归约描述-符号积分问题(4/4),由该问题归约的与或图,可读出该符号
10、积分的解为:,2.2 问题归约描述非线性系统的最优控制(1/4),例2 非线性系统控制 非线性控制问题求解也可采用AI的问题归约来描述与求解,下面简单介绍之。 某多变量非线性系统的控制求解问题描述： 多变量被控对象模型与初始状态 x(k+1)=F(x(k),u(k) x(0)=x0 控制策略 u(k)=u1, u2, , un 其中ui表示控制状态变迁满足如下条件的控制策略 |x(k+1)|a|x(k)| 控制的目标为使如下二次型性能指标函数最小：,2.2 问题归约描述-符号积分问题(1/4),由该问题归约的与或图,可读出该符号积分的解为:,3 与或图表示(1/1),3 与或图表示 对归约问题
11、,可采用图的结构来表示把问题归约为子问题的替换集合. 表示问题规约的图称为与或图. 下面介绍： 与或图的结构 节点可解性的定义,3.1 与或图的结构 考虑某归约问题,问题A 既可由求解问题B和C, 也可由求解D、E和F, 或者由单独求解H来解决.,3.1 与或图的结构(1/6),这一问题归约为子问题的替换集合关系可由图4所示的结构来表示. 图中各节点由它们所表示的问题来标记.,3.1 与或图的结构(2/6),从该图可读得: 问题B和C构成子问题的一个集合; D、E和F构成另一子问题集合; 而H则为第3个集合.,对应于某个给定集合的各节点,用连接弧线的标记来指明.,3.1 与或图的结构(3/6)
12、,为了不出现既有与子节点又有或子节点的节点,使得状态图更规范,更容易被计算机所存储与处理,通常把某些附加节点引入此结构图. 这样便使含有一个以上子问题的每个集合能够聚集在它们各自的父节点之下.,根据这一约定,图4的结构变为图5所示的结构.,其中,标记为N和M的附加节点分别作为集合B,C和D,E,F的唯一父节点,具有辅助问题描述的作用.,3.1 与或图的结构(4/6),对于图5,问题A被归约为单一替换子问题N、M和H.因此,把节点N、M和H叫做或节点. 然而,N被归约为子问题B和C的单一集合,要求解N就必须求解所有的子问题.因此,把节点B和C叫做与节点.,同理,节点D、E和F也叫做与节点. 各个
13、与节点用跨接指向他们子节点的弧线的小段圆弧加以标记,如图4和图5所示. 这种结构图叫做与或图.,3.1 与或图的结构(5/6),在与或图中, 当某节点只含有单个子节点时,这个子节点既可视为或节点,也可视为与节点. 对某些问题的图结构,如状态空间搜索问题,亦可归结为与或图问题. 状态空间搜索问题与与或图问题的区别在于其不存在任何与节点. 由于与或图中出现与节点,其结构与其它图结构大为不同. 因此,与或图需要有其特有的搜索技术,而且是否存在与节点也就成为区别两种问题求解方法的主要依据. 在描述与或图时,将继续采用如父节点、子节点和连接节点的弧线等术语,给予它们以明确的意义.,3.1 与或图的结构(
14、6/6),通过与或图,把某个单一问题归约算符具体应用于某个问题描述,依次产生出一个中间或节点及其与节点后裔(例外的情况是当子问题集合只含有单项时,在这种情况下,只产生或节点). 这样,模拟问题归约方法的相关结构是一个与或图. 与或图中的节点之一-初始节点对应于原始问题描述. 图中那些对应于本原问题的节点叫做终叶节点.,3.2 节点可解性的定义(1/8),3.2 节点可解性的定义 在与或图上执行的搜索过程,其目的在于表明初始节点是有解的. 下面给出可解节点的定义.,3.2 节点可解性的定义(2/8)可解节点定义,定义1 与或图中可解节点可以归纳定义如下: 终叶节点是可解节点(因为它们与本原问题相
15、关连). 如果某个非终叶节点含有或子节点,那么只有当其子节点至少有一个是可解的时,此非终叶节点才是可解的. 如果某个非终叶节点含有与子节点,那么只要当其子节点全部为可解时,此非终叶节点才是可解的. 于是,一个解图被定义为那些可解节点的子图,这些节点能够(按上述定义)证明其初始节点是可解的. 图6给出与或图的一些例子. 图中,终叶节点用字母t标示,有解节点用小圆点表示,而解图用绿线分支表示.,3.2 节点可解性的定义(3/8),图6 与或图例子(图(c)有一个以上的解),3.2 节点可解性的定义(4/8) -不可解节点的定义,当非终叶节点没有子节点时,该节点称为不可解. 这种不可解节点的出现可能
16、意味着另外一些节点(甚至初始节点)也是不可解的. 下面给出不可解节点的定义. 定义2 与或图中不可解节点的归纳定义于下: 没有子节点的非终叶节点为不可解节点. 如果某个非终叶节点含有或子节点,那么只有当其全部子为不可解时,此非终叶节点才是不可解的. 如果某个非终叶节点含有与子节点,那么只要当其子节点至少有一个为不可解时,此非终叶节点才是不可解的.,3.2 节点可解性的定义(5/8),在图6中,不可解节点用小圆圈表示. 图6所示的与或图为显式图. 与状态空间问题求解一样,很少用显式图来搜索,而是用由初始问题描述和消解算符所定义的隐式图来搜索. 这样,一个问题求解过程是由生成与或图的足够部分,并证
17、明初始节点是有解而得以完成的.,3.2 节点可解性的定义(6/8),综上所述,可把与或图的构成规则概括如下: 与或图中的每个节点代表一个要解决的单一问题或问题集合.图中所含初始节点对应于原始问题. 对应于本原问题的节点,叫做终叶节点,它没有子节点. 对于把算符应用于问题A的每种可能情况,都把问题变换为一个子问题集合,有向弧线自A指向子节点,表示所求得的子问题集合. 例如图5说明把问题A归结为3个不同的子问题集合:N、M和H. 如果集合N、M或H中有一个能够解答,则问题A可解. 所以把N、M和H叫做或节点.,3.2 节点可解性的定义(7/8),图5进一步表示集合N、M和H的组成情况.图中, N=
18、B, C, M=D, E,F,而H由单一问题构成. 对于代表两个或两个以上子问题集合的每个节点,有向弧线从此节点指向此子问题集合中的各个节点. 由于只有当集合中所有的项都有解时,这个子问题的集合才能获得解答,所以这些子问题节点叫做与节点. 为了区别于或节点,把具有共同父辈的与子节点的所有弧线用另外一段小弧线连接起来. 当只有一个算符可应用于问题A,而且这个算符产生具有一个以上子问题的集合时,由上述规则3和4所产生的图可简化表示如下. 代表子问题集合的中间或节点可被略去,如图7所示.,3.2 节点可解性的定义(8/8),图7 单算符与或树 在上述图形中,每个节点代表一个显示问题或问题集合. 除初
19、始节点外,每个节点只有一个父节点.因此,这些图亦称为与或树.,4 问题归约机理(1/3),4 问题归约机理 本节将叙述另一种问题归约技术. 该归约方法它能把状态空间搜索问题归约为越来越简单的搜索问题,直至所有问题能被归约为平凡解为止. 此外,该归约过程可由AI规划机理来引导. 如,三元状态(S,F,G)规定的状态空间搜索问题可以归约为比较简单的状态空间搜索问题的集合,其思想如下:,4 问题归约机理(2/3),采用g1,gn来标记“路标”(中间状态)序列,则能够把初始问题归约为由三元状态(S,F,g1),.,(gn,F,G)规定的问题集合. 解答所有这些问题就等价于解答该初始问题. 当路标g1,
20、gn为显式规定时,子问题的求解次序不造成差别. 不过有时可以规定状态集合G1中的任一个状态都可能作为第一个路标,规定状态集合G2为第二个路标,等等. 于是,由三元状态(S,F,G2)所描述的问题必须首先加以解决,以便在下一个问题(g1,F,G2)建立之前,确定某个具体的g1G1,等等.,4 问题归约机理(3/3),在上述过程中,重要的是 如何通过差别确定所谓的“路标”, 以及消除差别的关键算符. 下面将详细讨论该归约技术,主要内容为: 关键算符 差别,4.1 关键算符(1/4),4.1 关键算符 对于许多状态空间的搜索问题,要推测一个状态空间算符的特性并不是太困难的. 也就是说,尽管寻求某个解
21、答中整个算符序列的问题是困难的,但是规定这些算符中的一个却往往是容易的. 当应用该算符中的一个被认为是问题求解的决定性步骤时,寻找这样一个算符的可能性就增加了. 例如,对前面讨论过的梵塔问题, “移动圆盘C至柱子3” 这个算符可被选为问题求解的决定性步骤(见图2),这种具有决定性作用的算符叫做关健算符.,4.1 关键算符(2/4),当关键算符被确定时,它可被用来辨别问题归约过程中的路标. 设F中的f是由三元状态(S,F,G)表示的问题的关键算符. 既然f必定要采用,所以(S,F,G)的第一个子问题是对应于寻找一条通向f适用的某一状态的路径问题. 令Gf表示f适用的所有状态的集合. 由此,设立了
22、一个由(S,F, Gf)描述的子问题. 一旦该问题获得解决,能够设立由(g,F,f(g)表示的本原问题,其中状态gGf,f(g)表示把f应用于g而得到的状态. 因为该问题仅仅由应用关键算符f来解决,所以它是本原的. 于是,剩下未解决的是由三元状态(f(g),F,G)描述的问题.,4.1 关键算符(3/4),然后,这两个子问题能够用直接的状态空间搜索技术或进一步的问题归约来求解. 如果采用进一步的归约策略,必定能够辨识问题(S,F,G)的某个关键算符,并继续归约下去.,当状态空间的关键算符能够确定时,则就能应用问题归约如图8所示.,图中没有表示出本原问题(g,F,f(g)而简化了这个图.,4.1
23、 关键算符(4/4),对于许多问题,往往无法辨别某单个关键算符和预先知道其为某个问题解答的决定性步骤. 只能推测某个算符的子集合,其中某个算符很有可能是决定性的.该子集合中的每个算符产生一对子问题. 当从各种替换算符中寻求某个解答时,从一个应用这种想法的搜索过程可建立起一个与或图. 要应用这个方法,首先必须有某种方法用来计算任何状态空间搜索问题的候选关键算符集合. 下面叙述以差别为基础的一种特别方法.,4.2 差别(1/10),4.2 差别 寻找候选关键算符的一种方法涉及计算问题的差别. 粗略地说,问题(S,F,G)的差别就是用S的元对由集合G规定的目标进行测试失败原因的部分表列. 如果S的某
24、个元是在G中,那么该问题为成功解决,也就不存在差别. 举例来说,如果目标集合G由某个状态条件集合所规定,而且某个sS满足这些条件中的某些但不是全部条件, 那么,差别可由不能被s满足的条件的部分表列组成. 如果这些条件能够按其重要性分类,那么选用最重要的不满足条件作为差别.,4.2 差别(2/10),其次,将状态空间算符或算符集合与每个可能的差别结合起来. 这些算符是候选关键算符. 只有当应用某个算符是与消去某个差别相关时,此算符才与那个差别结合在一起. 下面以猴子和香蕉问题为例来说明该过程,见第二讲图5. 猴子和香蕉问题已在第二讲中介绍过,该问题的4个算符的作用结果和适用条件为: goto(U
25、): (W,0,Y,z)(U,0,Y,z) pushbox(V): (W,0,W,z)(V,0,V,z) climbbox: (W,0,W,z)(W,1,W,z) grasp: (c,1,c,0)(c,1,c,1) 其中c是香蕉正下方的地板位置.,4.2 差别(3/10),只有当状态描述四元表中的最后一元等于1时,状态描述中的目标条件才得到满足. 初始状态由表(a,0,b,0)描述,见第二讲图6. 如果F=f1,f2,f3,f4是4个算符的集合,G是满足目标条件的状态集合.那么初始问题变为 (a,0,b,0),F,G) (1) 由于算符集合F在本问题中不变,因此可把符号F从表示式中删去,而简单
26、地用(a,0,b,0),G)来表示该问题. 于是,应用关键算符和差别表示法的归约过程可以解释于下:,(1) 首先,计算初始问题的差别. 表列(a,0,b,0)不满足目标测试在于其最后一个元素不是1. 与归约这个差别相关的关键算符是f4=grasp. 用f4来归约初始问题,得到下列一对子问题: (a,0,b,0),Gf4) 和 (f4(S1),G) (2) 其中Gf4是适用于算符f4的状态描述集合(此状态描述在域f4内),而S1是Gf4中由求解(a,0,b,0),)而得到的状态.,4.2 差别(4/10),要求解问题(a,0,b,0),Gf4),需要先计算它的差别. 由(a,0, b,0)所描述
27、的状态不在Gf4中,因为: 1. 箱子不在c处; 2. 猴子不在c处; 3. 猴子不在箱子上. 把这些说明列出作为这种情况下的差别,可辨别出下列关键算符: f2: pushbox(c) f1: goto(c) f3: climbbox,4.2 差别(5/10),4.2 差别(6/10),(2) 然后,依次应用这些关键算符,以产生各归约问题的替换对. 这些关键算符的第一个,用来把问题(a,0,b,0),Gf4)归约为一对子问题: (1-1) (a,0,b,0),Gf2) (1-2) (f2(Sll),Gf4) 其中,SllGf2是由求解(1-1)得到的.,现在必须先求解(1-1),所以计算它的差
28、别,此差别为:猴子不在b处. 这个差别给出关键算符 f1: goto(b) 该关键算符又被用来把问题(a,0,b,0),Gf2)归结为一对子问题 (1-11) (a,0,b,0),Gf1) (1-12) (f1(S11l),Gf2),4.2 差别(7/10),第一个问题(1-11)已是本原问题,f1是此问题的解. 由于f1(S11l)=(b,0,b,0),所以问题(1-12)变为: (b,0,b,0,),Gf2) (3) 该问题也是本原问题,f2是此问题的解. 把早先产生的问题求解过程继续进行下去,直到最后解答此初始问题为止.,4.2 差别(8/10),4.2 差别(9/10),图9表示出这个问题求解的与或图.节点左上方的数字表示用搜索过程对问题进行测试的顺序. 这里给出的排序是正好在没有标示数字的问题被测试之前就得到的一个解答. 不过,一般说来,进一步的搜索必定是需要的. 由图9可知,以得到算符的解答序列: goto(b), pushbox(c), climbbox, grasp (4),4.2 差别(10/10),