第二讲-知识表示-3.状态空间&问题归约表示法

2020/3/131人工智能原理第二讲知识表示之状态空间/问题归约表示主讲：王祖喜[e-mail]华中科技大学图像所2020/3/132知识的表示方法谓词逻辑法状态空间法问题归约法语义网络法框架表示法面向对象表示剧本(script)表示过程(procedure)表示小结2020/3/133§状态空间法问题求解(problemsolving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。2020/3/134问题求解技术两个主要的方面问题的表示：如果描述方法不对，对问题求解会带来很大的困难求解的方法：采用试探搜索方法。2020/3/135状态空间法三要点状态（state）：表示问题解法中每一步问题状况的数据结构；算符（operator）：把问题从一种状态变换为另一种状态的手段；状态空间方法：基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。2020/3/1361.问题状态描述要完成某个问题的状态描述，必须确定三件事：1.该状态描述方式，特别是初始状态描述；2.操作符集合及其对状态描述的作用；3.目标状态描述的特性。2020/3/137定义:状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。2020/3/138给定每个变量的一组值就得到一个具体的状态，如Qk=[q0k，q1k，...，qnk]T它只是问题所有可能状态的罗列，还必须描述这些状态之间的可能变化。所谓操作，或称为算子是引起状态中的某分量发生改变，从而使问题由一个具体状态A变化为另一具体状态B的作用。2020/3/139算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间(statespace)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S(初始状态S0∈S)、操作符集合F以及目标状态集合G(GS)。可把状态空间记为三元状态(S，F，G)。状态空间可用有向图来表示2020/3/1310状态空间的一个解使一个有限的操作算子序列，它使初始状态转化为目标状态：S0-f1-S1-f2-...fk-G2020/3/1311状态空间表示详释让我们先用数码难题(puzzleproblem)来说明状态空间表示的概念。由15个编有1至15并放在4×4方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。如何把初始棋局变换为目标棋局呢？问题的解答就是某个合适的棋子走步序列，如左移棋子12，下移棋子15，右移棋子4，…等等。2020/3/1312（a）初始棋局（b）目标棋局十五数码难题1410213685712311549111514131211109876543212020/3/1313总状态为16!＝20922789888000由于棋盘的对称性，实际状态数减半上、下、左、右移动四种操作2020/3/1314十五数码难题最直接的求解方法是尝试各种不同的走步，直到偶然得到该目标棋局为止。这种尝试本质上涉及某种试探搜索。从初始棋局开始，试探(对于一般问题实际上是由计算机进行计算和执行的)由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。部分状态图为：2020/3/13151410213685712311549111410213685712311549111410213685712431159111410213685712311549111410213657128311549111410213685712431159111410213685712431159111410213857612311549112020/3/1316我们一般用状态空间法这一术语来表示下述方法：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到目标状态为止。寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述，以及此后检验这些新的状态描述，看其是否描述了该目标。这种检验往往只是查看某个状态是否与给定的目标状态描述相匹配。2020/3/1317要完成某个问题的状态描述，必须确定三件事：1.该状态描述方式，特别是初始状态描述；2.操作符集合及其对状态描述的作用；3.目标状态描述的特性。2020/3/13182.状态图示法图论中的几个术语节点(node)：图形上的汇合点，用来表示状态、事件和时间关系的汇合，也可用来指示通路的汇合；弧线(arc)：节点间的连接线；有向图(directedgraph)：一对节点用弧线连接起来，从一个节点指向另一个节点。2020/3/1319后继节点(descendantnode)与父辈节点(parentnode)：如果某条弧线从节点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的那段弧线的代价。2020/3/1320如果从节点ni至节点nj存在有一条路径，那么就称节点nj是从节点ni可达到的节点。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。最小者称为最小代价的路径。2020/3/1321显式表示：各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。隐式表示：节点的无限集合{si}作为起始节点是已知的。后继节点算符Γ也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。2020/3/1322图的显式和隐式表示一个图可由显式说明也可由隐式说明。显然，显式说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。此外，引入后继节点算符的概念是方便的。后继节点算符Γ也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价(用我们的状态空间术语来说，后继算符是由适用于已知状态描述的算符集合所确定的)。把后继算符应用于{si}的成员和它们的后继节点以及这些后继节点的后继节点，如此无限制地进行下去，最后使得由Γ和{si}所规定的隐式图变为显示图。把后继算符应用于节点的过程，就是扩展一个节点的过程。2020/3/1323因此，搜索某个状态空间以求得算符序列的一个解答的过程，就对应于使隐式图足够大一部分变为显式以便包含目标的过程。这样的搜索图是状态空间问题求解的主要基础。问题的表示对求解工作量有很大的影响。人们显然希望有较小的状态空间表示。许多似乎很难的问题，当表示适当时就可能具有小而简单的状态空间。2020/3/13243.状态空间表示举例各种问题都可用状态空间加以表示，并用状态空间搜索法来求解。如果能够用一种不同的表示方法来求解用一问题，也不必感到惊讶。产生式系统（ProductionSystem）是描述搜索过程的方法。2020/3/1325一个产生式系统由下面三部分组成：一个总数据库(globaldatabase)：它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。一套规则：它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库，就象应用算符来改变状态一样一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。控制策略由控制系统选择和确定。2020/3/1326状态空间表示举例猴子和香蕉问题(monkeyandbananaproblem)在一个房间内有一只猴子(可把这只猴子看做一个机器人)、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?图中表示出猴子、香蕉和箱子在房间内的相对位置。2020/3/1327用一个四元表列(W,x,Y,z)来表示这个问题的状态，其中W－猴子的水平位置X－当猴子在箱子顶上时取X=1；否则取X=0Y－箱子的水平位置Z－当猴子摘到香蕉时取Z=1；否则取Z=02020/3/1328这个问题中的操作(算符)如下：(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)，就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。这种强加于操作的适用性条件，叫做产生式规则的先决条件。2020/3/1329(3)climbbox猴子爬上箱顶，即有(W，0，W，z)(W，1，W，z)在应用算符climbbox时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上。(4)grasp猴子摘到香蕉，即有(c,1,c,0)(c,1,c,1)其中，c是香蕉正下方的地板位置，在应用算符grasp时，要求猴子和箱子都在位置c上，并且猴子已在箱子顶上。2020/3/1330应当说明的是，在这种情况下，算符(操作)的适用性及作用均由产生式规则表示。例如，对于规则(2)，只有当算符pushbox(V)的先决条件，即猴子与箱子在同一位置上而且猴子不在箱顶上这些条件得到满足时，算符pushbox(V)才是适用的。这一操作算符的作用是猴子把箱子推到位置V。在这一表示中，目标状态的集合可由任何最后元素为1的表列来描述。2020/3/1331令初始状态为(a,0,b,0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U,0,b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有适用的操作继续应用于每个状态，我们就能够得到状态空间图。从图不难看出，把该初始状态变换为目标状态的操作序列为｛goto(b),pushbox(c),climbbox,grasp｝2020/3/13322020/3/1333§问题归约法问题归约(problemreduction)是另一种问题描述与求解方法。先把问题分解为子问题和子-子问题，然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答。2020/3/13341.问题归约描述问题归约表示的组成部分：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。其中的每一个问题是不证明的，自然成立的，如公理、已知的实事等（本原问题集）问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2020/3/1335梵塔难题有3个柱子(1，2和3)