人工智能-第二章知识表示方法.

第二章知识表示方法第二章知识表示方法信息科学与技术学院2015.2第二章知识表示方法知识是一切智能行为的基础，也是人工智能的重要研究对象。要使计算机具有智能，就必须使它具有知识，而要使计算机具有知识，首先解决知识的表示问题。知识表示是对知识的一种描述：也就是用一些约定的符号把知识编码成一组计算机可以接受的数据结构第二章知识表示方法对于同一问题有多种不同的表示方法，常用的几种知识表示方法包括：状态空间法问题归约法谓词逻辑法语义网络表示法框架表示法本体技术过程表示法第二章知识表示方法问题求解涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。问题求解技术两个主要的方面问题的表示：如果描述方法不对，对问题求解会带来很大的困难；求解的方法：采用试探搜索方法。一、状态空间法第二章知识表示方法1.状态空间表示法定义状态(state)：表示问题解法中每一步问题状况的数据结构状态，它可形式化表示为一组最少变量q0,q1,…,qn的有序集合，其矢量形式为Q=[q0,q1,…，qn]T其中的每个元素qi（i=0,1,2,…）为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=[q0k,q1k,…，qnk]T第二章知识表示方法初始状态：由问题已知的前提、初始条件的原始描述所构成的状态目标状态：问题解决时应该到达的状态操作符(算符)：引起状态中的某些分量发生改变，从而使问题由一个具体状态变化到另一个具体状态的手段称为操作符或算符。问题的状态空间：用来描述一个问题的全部可能的状态及其相互关系。常记为三元组S,F,G，其中S：问题的所有的初始状态的集合F：操作符的集合G：目标状态的集合状态空间一般用赋值有向图表示，节点表示问题的状态，有向边表示操作符。第二章知识表示方法十五数码难题119415131275861321014123456789101112131415初始状态S目标状态G操作集合F把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图，这种图称为状态图。完成一个问题的状态描述，必须确定3件事：(1)该状态描述方式，特别是初始状态描述；(2)操作符集合及其对状态描述的作用；(3)目标状态描述的特性。第二章知识表示方法2、状态图示法图由节点（不一定是有限的节点）的集合构成。有向图：一对节点用弧线连接起来，从一个节点指向另一个节点。后继节点与父辈节点：如果某条弧线从节点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的那段弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。显式表示：各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。隐式表示：节点的无限集合{si}作为起始节点是已知的。后继节点算符Γ也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。第二章知识表示方法3.状态空间问题求解状态空间法问题求解基本过程：建立初始状态，在状态空间中进行搜索，以找到一条从初始状态到达目标状态的（最佳）路径。这条路径（即达到目标状态的操作序列）就是问题的解。[例1]二阶Hanoi塔问题设有三根柱子，编号分别为1号，2号和3号。初始情况下，1号柱子上穿有A，B两个盘子，A比B小，A位于B的上面。要求把这两个盘子全部移到另一根柱子上，且规定每次只能移动一个盘子，任何时刻都不能使大片位于小片的上面。第二章知识表示方法第一步：定义问题状态的描述形式：用Sk=(SkA，SkB)表示问题的状态SkA表示A所在柱子号SkB表示B所在柱子号第二步：用所定义的状态描述形式把问题的所有可能的状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述。本问题所有可能的状态共有九种，如图2.1所示。第二章知识表示方法123123123S0:(1,1)S1:(1,2)S2:(1,3)S3:(2,1)S4:(2,2)S5:(2,3)S6:(3,1)S7:(3,2)S8:(3,3)123123123123123123初始状态集合S={S0}，目标状态集合G={S4，S8}。第二章知识表示方法第三步：定义一组操作符F。定义操作符R(i,j)表示盘子R从i柱移到j柱；允许的操作共有12个。F={R(i,j)|R=A,B;i,j=1,2,3}它们分别是:A(1,2)，A(1,3)，A(2,1)，A(2,3)，A(3,1)，A(3,2)B(1,2)，B(1,3)，B(2,1)，B(2,3)，B(3,1)，B(3,2)至此，该问题的状态空间(S,F,G)构造完成。这就完成了对问题的状态空间表示。为了求解该问题，根据该状态空间的9种可能状态和12种算符，构造它的状态空间图，如图2.2所示。第二章知识表示方法图中从初始节点（1，1）到目标节点（2，2）和（3，3）的任何一条路径都是问题的一个解。最短路径长度为3。2阶Hanoi塔的状态空间图(1,1)(3,1)(3,2)(2,2)(2,1)(2,3)(3,3)(1,2)(1,3)A(1,3)B(1,2)A(3,2)A(2,1)B(3,1)A(3,2)A(2,1)A(1,3)B(2,3)第二章知识表示方法状态空间的问题求解过程：定义状态描述，定义一组算符问题的求解过程是一个不断把算符作用于状态的过程算符的一次使用，就使得问题从一种状态转变成另一种状态，使用算符最少的解称为最优解对任何一种状态，可使用的算符不止一个，生成的后继状态可能有多个，涉及到搜索策略问题第二章知识表示方法画出3阶Hanoi塔问题的状态空间图。(1,1,1)(3,1,1)(3,2,1)(2,2,1)(2,2,3)(1,2,3)(1,3,3)(3,3,3)(2,1,1)(2,3,1)(3,3,1)(3,3,2)(1,3,2)(1,2,2)(2,2,2)(2,3,3)(2,1,3)(1,1,3)(1,1,2)(3,1,2)(3,2,2)第二章知识表示方法[例2]修道士(Missionaries)和野人(Cannibals)问题在河的左岸有N个传教士、N个野人和一条船，传教士们想用这条船把所有人都运过河去，但有以下条件限制：（1）修道士和野人都会划船，但船每次最多只能运K个人；（2）在任何岸边野人数目都不能超过修道士，否则修道士会被野人吃掉。假定野人会服从任何一种过河安排，请规划出一个确保修道士安全过河的计划。第二章知识表示方法约束条件：①M≧C任何时刻两岸、船上都必须满足传教士人数不少于野人数（M=0时除外，既没有传教士）②M+C≦K船上人数限制在K以内求解：传教士与野人全部安全渡到对岸的解决方案。解：设N=3，K=2（三个M和三个C，每次渡河二人以下）L：左岸，R：右岸，B：是否有船（0：无船，1：有船）LRLRM30M03C30C03B10B01S状态G状态第二章知识表示方法①状态表示定义：用三元组（ML，CL，BL）表示左岸状态，其中：0≦ML,CL≦3，BL∈｛0,1｝如：（0，3，1）表示左岸有三个野人，船在左岸。M&C的问题描述：从（3，3，1）到（0，0，0）的状态转换状态空间：32种状态，其中：12种不合理状态：如（1，0，1）说明右岸有2个M，3个C；4种不可能状态：如（3，3，0）说明所有M和C都在左岸，而船在右岸∴可用的状态共16种，组成合理的状态空间第二章知识表示方法(m,c,b)(m,c,b)(001)达不到(000)(011)(010)(021)(020)(031)(030)达不到(101)不合法(100)不合法(111)(110)(121)不合法(120)不合法(131)不合法(130)不合法(201)不合法(200)不合法(211)不合法(210)不合法(221)(220)(231)不合法(230)不合法(301)达不到(300)(311)(310)(321)(320)(331)(330)达不到第二章知识表示方法②操作集定义：Pmc操作：从左岸划向右岸Qmc操作：从右岸划向左岸船上人数组合（m，c）共5种（1，0）,（1，1）,（2，0）,（0，1）,（0，2）∵每一种船上的人数组合同时对应P，Q二种操作∴系统共有5×2＝10种操作（规则）如：P01：if（ML=0，3，CL=1，BL=1）then（ML，CL-1，BL-1）如果船在左岸，那么一个野人划船到右岸Q01：if（ML=0，3，CL=2，BL=0）then（ML，CL+1，BL+1）如果船在右岸，那么一个野人划船回到左岸总共有10种操作F={P10,P20,P11,P01,P02,Q10,Q20,Q11,Q01,Q02}第二章知识表示方法(3,3,1)(1,3,0)(3,1,0)(2,2,0)(2,3,0)(3,2,0)(3,2,1)(2,3,1)(1,2,0)(3,0,0)(2,1,0)(3,1,1)(1,1,0)(2,0,0)(1,2,1)(2,1,1)(2,2,1)P20P02P11P10P01Q01Q10(2,1,0)Q01P20P02P11Q01P20P11P10Q01Q10Q11③状态空间图第二章知识表示方法(2,2,1)(0,2,0)P20Q01(0,3,1)P02(0,1,0)(0,2,1)(1,1,0)Q01Q10(0,0,0)(0,0,0)P02P11(2,0,0)P02第二章知识表示方法（3，3，1）（2，2，0）（3，1，0）（3，2，1）（3，0，0）（3，1，1）（1，1，0）（2，2，1）（0，2，0）（0，3，1）（0，1，0）（0，2，1）（1，1，1）（0，0，0）P11P02Q10Q01最短路径有4条，由11次操作构成。(P11、Q10、P02、Q01、P20、Q11、P20、Q01、P02、Q01、P02)(P11、Q10、P02、Q01、P20、Q11、P20、Q01、P02、Q10、P11)(P02、Q01、P02、Q01、P20、Q11、P20、Q01、P02、Q01、P02)(P02、Q01、P02、Q01、P20、Q11、P20、Q01、P02、Q10、P11)Q01（3，1，1）P02P20P20P02Q11Q01Q01Q10P02P11第二章知识表示方法思考题：1．在修道士和野人问题中，假设只有三个修道士和一个野人会划船，求它的状态空间。2．在修道士和野人问题中，假设只有三个修道士会划船，求它的状态空间。第二章知识表示方法练习：1.有一农夫带一条狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：(1)船太小，农夫每次只能带一样东西过河；(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。设计一个过河方案，使得农夫、狼、羊都能不受损失地过河，画出相应的状态空间图。2.(分油问题)有A、B、C三个不带刻度的瓶子，分别能装8kg,5kg和3kg油。如果A瓶装满油，B和C是空瓶，怎样操作三个瓶，使A中的油平分两份？(假设分油过程中不耗油),画出相应的状态空间图。第二章知识表示方法二、问题归约问题归约是另一种问题描述与求解方法。已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。采用问题归约表示可由下面三部分组成：一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述；问题归约的实质：从目标出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。第二章知识表示方法1.问题归约的描述三