人工智能知识表示系列课件第二讲知识表示_1

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