知识表示3.状态空间问题归约表示法.ppt

2019/6/19,1,人工智能原理,第二讲 知识表示 之 状态空间/问题归约表示,主讲：王祖喜 华中科技大学图像所,2019/6/19,2,知识的表示方法,谓词逻辑法 状态空间法 问题归约法 语义网络法 框架表示法 面向对象表示 剧本(script)表示 过程(procedure)表示 小结,2019/6/19,3,状态空间法,问题求解(problem solving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。,2019/6/19,4,问题求解技术两个主要的方面 问题的表示：如果描述方法不对，对问题求解会带来很大的困难 求解的方法：采用试探搜索方法。,2019/6/19,5,状态空间法三要点 状态（state）：表示问题解法中每一步问题状况的数据结构； 算符（operator）：把问题从一种状态变换为另一种状态的手段； 状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。,2019/6/19,6,1.问题状态描述,要完成某个问题的状态描述，必须确定三件事： 1.该状态描述方式，特别是初始状态描述； 2.操作符集合及其对状态描述的作用； 3.目标状态描述的特性。,2019/6/19,7,定义 : 状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合，其矢量形式如下： 式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。,2019/6/19,8,给定每个变量的一组值就得到一个具体的状态，如 Qk=q0k，q1k，. ，qnkT 它只是问题所有可能状态的罗列，还必须描述这些状态之间的可能变化。 所谓操作，或称为算子是引起状态中的某分量发生改变，从而使问题由一个具体状态A变化为另一具体状态B的作用。,2019/6/19,9,算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。 问题的状态空间(state space)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S(初始状态S0S)、操作符集合F以及目标状态集合G(GS)。可把状态空间记为三元状态(S，F，G)。 状态空间可用有向图来表示,2019/6/19,10,状态空间的一个解 使一个有限的操作算子序列，它使初始状态转化为目标状态：S0-f1-S1-f2-.fk-G,2019/6/19,11,状态空间表示详释,让我们先用数码难题(puzzle problem)来说明状态空间表示的概念。由15个编有1至15并放在44方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。 如何把初始棋局变换为目标棋局呢？问题的解答就是某个合适的棋子走步序列，如“左移棋子12，下移棋子15，右移棋子4，“等等。,2019/6/19,12,（a）初始棋局 （b）目标棋局 十五数码难题,2019/6/19,13,总状态为16!20922789888000 由于棋盘的对称性，实际状态数减半 上、下、左、右移动四种操作,2019/6/19,14,十五数码难题最直接的求解方法是尝试各种不同的走步，直到偶然得到该目标棋局为止。这种尝试本质上涉及某种试探搜索。从初始棋局开始，试探(对于一般问题实际上是由计算机进行计算和执行的)由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。 部分状态图为：,2019/6/19,15,2019/6/19,16,我们一般用状态空间法这一术语来表示下述方法： 从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到目标状态为止。 寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述，以及此后检验这些新的状态描述，看其是否描述了该目标。这种检验往往只是查看某个状态是否与给定的 目标状态描述相匹配。,2019/6/19,17,要完成某个问题的状态描述，必须确定三件事： 1.该状态描述方式，特别是初始状态描述； 2.操作符集合及其对状态描述的作用； 3.目标状态描述的特性。,2019/6/19,18,2.状态图示法,图论中的几个术语 节点(node)：图形上的汇合点，用来表示状态、事件和时 间关系的汇合，也可用来指示通路的汇合； 弧线(arc)：节点间的连接线； 有向图(directed graph)：一对节点用弧线连接起来，从一个节点指向另一个节点。,2019/6/19,19,后继节点(descendant node)与父辈节点(parent node)：如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。 路径：某个节点序列(ni1,ni2,nik)当j=2，3，k时，如果对于每一个ni,j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。 代价：用c(ni,nj)来表示从节点ni指向节点nj的那段弧线的代价。,2019/6/19,20,如果从节点ni至节点nj存在有一条路径，那么就称节点nj 是从节点ni可达到的节点。 两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。最小者称为最小代价的路径。,2019/6/19,21,显式表示：各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。 隐式表示：节点的无限集合si作为起始节点是已知的。后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。,2019/6/19,22,图的显式和隐式表示,一个图可由显式说明也可由隐式说明。显然，显式说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。 此外，引入后继节点算符的概念是方便的。后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价(用我们的状态空间术语来说，后继算符是由适用于已知状态描述的算符集合所确定的)。把后继算符应用于si的成员和它们的后继节点以及这些后继节点的后继节点，如此无限制地进行下去，最后使得由和si所规定的隐式图变为显示图。把后继算符应用于节点的过程，就是扩展一个节点的过程。,2019/6/19,23,因此，搜索某个状态空间以求得算符序列的一个解答的过程，就对应于使隐式图足够大一部分变为显式以便包含目标的过程。这样的搜索图是状态空间问题求解的主要基础。 问题的表示对求解工作量有很大的影响。人们显然希望有较小的状态空间表示。许多似乎很难的问题，当表示适当时就可能具有小而简单的状态空间。,2019/6/19,24,3.状态空间表示举例,各种问题都可用状态空间加以表示，并用状态空间搜索法来求解。 如果能够用一种不同的表示方法来求解用一问题，也不必感到惊讶。 产生式系统（Production System） 是描述搜索过程的方法。,2019/6/19,25,一个产生式系统由下面三部分组成： 一个总数据库(global database)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。 一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库，就象应用算符来改变状态一样 一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。,2019/6/19,26,状态空间表示举例,猴子和香蕉问题(monkey and banana problem) 在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?图中表示出猴子、香蕉和箱子在房间内的相对位置。,猴子和香蕉问题,2019/6/19,27,用一个四元表列(W,x,Y,z)来表示这个问题的状态， 其中 W猴子的水平位置 X当猴子在箱子顶上时取X=1；否则取X=0 Y箱子的水平位置 Z当猴子摘到香蕉时取Z=1；否则取Z=0,2019/6/19,28,这个问题中的操作(算符)如下： (1) goto(U)猴子走到水平位置U，或者用产生式规则表示为 (W，0，Y，z) (U，0，Y，z) 即应用操作goto(U)，能把状态(W，0，Y，z)变换为状态(U，0，Y，z)。 (2) pushbox(V)猴子把箱子推到水平位置V，即有 (W，0，W，z) (V，0，V，z) 应当注意的是，要应用算符pushbox(V)，就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。,2019/6/19,29,(3) climbbox猴子爬上箱顶，即有 (W，0，W，z) (W，1，W，z) 在应用算符climbbox时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上 。 (4) grasp猴子摘到香蕉，即有 (c,1,c,0) (c,1,c,1) 其中，c是香蕉正下方的地板位置，在应用算符grasp时，要求猴子和箱子都在位置c上，并且猴子已在箱子顶上。,2019/6/19,30,应当说明的是，在这种情况下，算符(操作)的适用性及作用均由产生式规则表示。例如，对于规则(2)，只有当算符pushbox(V)的先决条件，即猴子与箱子在同一位置上而且猴子不在箱顶上这些条件得到满足时，算符pushbox(V)才是适用的。这一操作算符的作用是猴子把箱子推到位置V。在这一表示中，目标状态的集合可由任何最后元素为1的表列来描述。,2019/6/19,31,令初始状态为(a,0,b,0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U,0,b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。 把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图。从图不难看出，把该初始状态变换为目标状态的操作序列为 goto(b),pushbox(c),climbbox,grasp,2019/6/19,32,猴子和香蕉问题的状态空间图,2019/6/19,33,问题归约法,问题归约(problem reduction)是另一种问题描述与求解方法。 先把问题分解为子问题和子-子问题，然后解决较小的问题。 对该问题的某个具体子集的解答就意味着对原始问题的一个解答。,2019/6/19,34,1. 问题归约描述,问题归约表示的组成部分： 一个初始问题描述； 一套把问题变换为子问题的操作符； 一套本原问题描述。 其中的每一个问题是不证明的，自然成立的，如公理、已知的实事等（本原问题集） 问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。,2019/6/19,35,梵塔难题,有3个柱子(1，2和3)和3个不同尺寸的圆盘（A，B和C）。在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。最初，3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。这个问题的初始配置和目标配置如图所示。,图 梵塔问题,2019/6/19,36,解题过程： 将原始问题归约为一个较简单问题集合，要把所有圆盘都移至柱子3，我们必须首先把圆盘C移至柱子3；而且在移动圆盘C至柱子3之前，要求柱子3必须是空的。只有在移开圆盘A和B之后，才能移动圆盘C；而且圆盘A和B最好不要移至柱子3就不能把圆盘C移至柱子3。因此，首先应该把圆盘A和B移到柱子2上。然后才能够进行关键的一步，把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。 将原始难题归约（简化）为下列子难题：移动圆盘A和B至柱子2的双圆盘难题，如图(a)所示。,2019/6/19,37,把原始难题归约（简化）为以下三个子难题： 移动圆盘A和B至柱子2的双圆盘难题；如图(a)所示 移动圆盘C至柱子3的单圆盘难题 ；如图(b)所示 移动圆盘A和B至柱子3双圆盘难题；如图(c)所示,2019/6/19,38,图 2.7 梵塔问题解答(a),图 2.8 梵塔问题解答(b),图 2.9 梵塔问题解答(c),2019/6/19,39,梵塔问题归约图：子问题2可作为本原问题考虑，因为它的解只包含一步移动。应用一系列相似的推理，子问题1和子问题3也可被归约为本原问题，如图2.10所示。这种图式结构，叫做与或图(AND/OR graph)。 它能有效地说明如何由问题归约法求得问题的解答。,图 2.10 梵塔问题归约图,2019/6/19,40,把一个问题描述变换为一个归约或后继问题描述的集合，这是由问题归约算符进行的。变换所得所有后继问题的解就意味着父辈问题的一个解。 所有问题归约的目的是最终产生具有明显解答的本原问题。这些问题可能是能够由状态空间搜索中走动一步来解决的问题，或者可能是别的具有已知解答的更复杂的问题。,2019/6/19,41,2. 与或图表示,一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。如下图所示:,图 2.13 子问题集合,图 2.14 与或图,2019/6/19,42,一些关于与或图的术语： 父节点、子（后继）节点、弧线、起始节点。 终叶节点：对应于原问题的本原节点。 或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。 与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和（D,E,F）各个结点之间用一端小圆弧连接标记。 与或图：由与节点及或节点组成的结构图。,2019/6/19,43,可解节点的一般定义 (1) 终叶节点是可解节点(因为它们与本原问题相关连)。 (2) 如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。 (3) 如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是可解的。,2019/6/19,44,不可解节点的一般定义: (1) 没有后裔的非终叶节点为不可解节点。 (2) 如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。 (3) 如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。,2019/6/19,45,图2.15 中，终叶节点用字母t表示，有解节点用小原点表示，而解图用粗线分支表示。,图 2.15 与或图例子,2019/6/19,46,与或图构成规则,(1) 与或图中的每个节点代表一个要解决的单一问题或问题集合。图中所含起始节点对应于原始问题。 (2) 对应于本原问题的节点，叫做终叶节点，它没有后裔。 (3) 对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A 指向后继节点表示所求得的子问题集合。 (4) 一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。由于只有当集合中所有的项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。 (5) 在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。 因此，代表子问题集合的中间或节点可以被略去，如右图所示。,图 2.16 与或树,2019/6/19,47,3. 问题归约机理,关键算符 对于许多状态空间的搜索问题，要推测一个状态空间算符的特性并不是太困难的。也就是说，尽管寻求某个解答中整个算符序列的问题是困难的，但是规定这些算符中的一个却往往是容易的。当应用该算符中的一个被认为是问题求解的决定性步骤时，寻找这样一个算符的可能性就增加了。例如，对我们前面讨论过的梵塔问题，“移动圆盘C至柱子3“这个算符可被选为问题求解的决定性步骤(见图2.9)，我们把这种具有决定性作用的算符叫做关键算符。,2019/6/19,48,当某个关键算符被决定时，它可被用来辨别问题归约过程中的路标。假设F中的某个f是由三元状态(S，F，G)表示的问题的关键算符。既然我们认为f必定要应用，所以(S，F，G)表示第一个后裔问题是一个对应于寻找一条通向某一f适用的状态的路径问题。令Gf表示f适用的所有状态的集合。由此，我们设立了一个由(S，F，Gf)描述的子问题。一旦这个子问题获得解决，规定一个状态gGf,我们就能够设立由(g,F,f(g)表示的本原问题，其中，f(g)表示把f应用于g而得到的状态。因为这个问题仅仅由应用关键算符f来解决，所以它是本原的。于是，剩下的(未解决的)是由三元状态(f(g),F,G)描述的问题。 当某个状态空间的关键算符能够被规定时，我们就能应用下列问题归约(见图2.17)。,2019/6/19,49,我们没有表示出本原问题(g,F,f(g)而简化了这个图。然后，这两个后裔问题能够用直接的状态空间搜索技术或进一步的问题归约来求解。如果采用进一步的归约策略，我们必定能够辨识问题(S，F，Gf)的某个关键算符，并继续归约下去。,图 2.17,2019/6/19,50,对于许多问题，我们往往无法辨别某单个关键算符和预先知道其为某个问题解答的决定性步骤。我们只能推测某个算符的子集合，其中某个算符很有可能是决定性的。该子集合中的每个算符产生一对后裔问题。当从各种替换算符中寻求某个解答时，从一个应用这种想法的搜索过程可建立起一个与或图。 要应用这个方法，首先我们必须有某种方法用来计算任何状态空间搜索问题的候选关键算符集合。下面我们要叙述以差别为基础的一种特别方法。,2019/6/19,51,差别 寻找候选关键算符的一种方法涉及计算某个问题(S，F，G)的差别。粗略地说，问题(S，F，G)的差别就是用S的元对由集合G规定的目标进行测试失败原因的部分表列(如果S的某个元是在G中，那么此问题就获得解决，也就不存在差别)。举例来说，如果目标集合G由某个状态条件集合所规定，而且某个sS满足这些条件中的某些但不是全部条件，那么，差别可由不能被s满足的条件的部分表列组成。如果这些条件能够按其重要性分类，那么我们宁愿选用最重要的不满足条件作为差别。,2019/6/19,52,其次，我们把某些状态空间算符或算符集合与每个可能的差别结合起来。这些算符是候选关键算符。只有当应用某个算符是与消去某个差别相关时，此算符才与那个差别结合在一起。,2019/6/19,53,猴子和香蕉问题的与或图,2019/6/19,54,解答序列： goto(b),pushbox(c),climbbox,grasp 1.关键算符 在问题求解过程中，具有决定性作用的算符叫做关键算符。 2.差别 寻找候选关键算符的一种方法就是要计算某个问题(S,F,G)的差别.不能被S满足的条件的部分表列就组成了差别。我们选择最重要的不满足条件作为差别。,2019/6/19,55,猴子和香蕉问题把4个算符的作用结果和适用条件重写如下： f1:(W,0,Y,z)-goto(U)(U,0,Y,z) f2:(W,0,W,z