1、第二章第二章 知识表示方法知识表示方法教材：教材：蔡自兴等蔡自兴等人工智能及其应用人工智能及其应用（第（第4版）版）清华大学出版社，清华大学出版社，2010.52第二章知识表示方法第二章知识表示方法v人类的智能活动主要是获得并运用知识。知识是人类的智能活动主要是获得并运用知识。知识是智能的基础。为了使计算机具有智能，能模拟人智能的基础。为了使计算机具有智能，能模拟人类的智能行为，就必须使它具有知识。但知识需类的智能行为，就必须使它具有知识。但知识需要用适当的模式表示出来才能存储到计算机中去，要用适当的模式表示出来才能存储到计算机中去，因此，知识的表示成为人工智能中一个十分重要因此，知识的表示成
2、为人工智能中一个十分重要的研究课题。的研究课题。v本章将首先介绍知识与知识表示的概念，然后介本章将首先介绍知识与知识表示的概念，然后介绍状态空间法、问题归约法、谓词逻辑法、语义绍状态空间法、问题归约法、谓词逻辑法、语义网络法、框架表示、本体技术、过程表示等当前网络法、框架表示、本体技术、过程表示等当前人工智能中应用比较广泛的知识表示方法，为后人工智能中应用比较广泛的知识表示方法，为后面介绍推理方法、专家系统等奠定基础。面介绍推理方法、专家系统等奠定基础。3第二章知识表示方法第二章知识表示方法2.1 知识与知识表示的概念知识与知识表示的概念 2.2 状态空间法状态空间法2.3 问题归约法问题归约
3、法2.4 谓词逻辑法谓词逻辑法2.5 语义网络法语义网络法2.6 框架表示框架表示2.7 本体技术本体技术2.8 过程表示过程表示2.9 小结小结42.1.1 2.1.1 知识的概念知识的概念v知识：在长期的生活及社会实践中、在科学研究知识：在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。及实验中积累起来的对客观世界的认识与经验。v知识：把有关知识：把有关信息关联信息关联*在一起所形成的信息结在一起所形成的信息结构。构。v知识反映了客观世界中事物之间的关系，不同事知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识物或者相同事物间的
4、不同关系形成了不同的知识*。信息关联形式：信息关联形式：“如果如果，则则”如果大雁向南飞，则冬天就要来临如果大雁向南飞，则冬天就要来临了。了。规则规则 事实事实例如：例如：“雪是白色的雪是白色的”。“如果头痛且流涕，则有可能患了感冒如果头痛且流涕，则有可能患了感冒”。2.1知识与知识表示的概念 52.1.1 2.1.1 知识的概念知识的概念Feigenbaum认为知识是经过加工的信息，它包括事实、信念和启发式规则。Bernstein说知识是由特定领域的描述、关系和过程组成的。Hayes-Roth认为知识是事实、信念和启发式规则。知识库观点看，知识是某论域中所涉及的各有关方面、状态的一种符号表示
5、。62.1.1 2.1.1 知识的概念知识的概念v人工智能系统所关心的知识人工智能系统所关心的知识l事实：事实：是关于对象和物体的知识。l规则：规则：是有关问题中与事物的行动、动作相联系的因果关系的知识。l元知识：元知识：是有关知识的知识，是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序包括怎样使用规则、解释规则、校验规则、解释程序结构等。结构等。l常识性知识：常识性知识：泛指普遍存在而且被普遍认识了的客观事实一类知识。2.1知识与知识表示的概念 72.1.2 2.1.2 知识的特性知识的特性 1.相对正确性相对正确性v任何知识都是在一定的条件及环境下产生任何知识都是在一定
6、的条件及环境下产生的的*，在这种条件及环境下才是正确的。，在这种条件及环境下才是正确的。1+1=2 （十进制）1+1=10 (二进制）2.1知识与知识表示的概念 82.1.2 知识的特性知识的特性2.不确定性不确定性*随机性引起的不确定性随机性引起的不确定性*模糊性引起的不确定性模糊性引起的不确定性*经验引起的不确定性经验引起的不确定性 不完全性引起的不确定性不完全性引起的不确定性(常识性？）常识性？）知识状态：知识状态：“真真”“假假”“真真”与与“假假”之间的中间之间的中间状态状态 “如果头痛且流涕，则如果头痛且流涕，则有可能有可能患了感冒患了感冒”小李小李很高很高2.1知识与知识表示的概
7、念 92.1.2 2.1.2 知识的特性知识的特性3.可表示性与可利用性可表示性与可利用性知识的可表示性知识的可表示性:知识可以用适当形式表示出来，如知识可以用适当形式表示出来，如用语言、文字、图形、神经网络等。用语言、文字、图形、神经网络等。知识的可利用性知识的可利用性:知识可以被利用。知识可以被利用。2.1知识与知识表示的概念 102.1.3 2.1.3 知识的表示知识的表示l知识表示就是研究用机器表示上述这些知识的可行性、有效性的一般方法，可以看作是将知识符号化并输入到计算机的过程和方法。l知识表示知识表示=数据结构数据结构+处理机制处理机制l知识表示的观点：陈述性过程性112.1.3
8、2.1.3 知识的表示知识的表示陈述性知识表示和过程性知识表示各有优缺点由于高级的智能行为似乎强烈地依赖于陈述性知识，因此AI的研究应注重陈述性的开发。过程性知识的陈述化表示。以适当方式将过程性知识和陈述性知识综合，可以提高智能系统的性能。122.1.3 2.1.3 知识的表示知识的表示v策略知识l关于如何解决问题的政策方略，包括在什么时间、什么地点、由什么主体采取什么行动、达到什么目标、注意什么事项等等一整套完整而具体的行动计划规划、行动步骤、工作方式和工作方法。132.1.3 2.1.3 知识的表示知识的表示v“智能”l在给定的问题问题环境主体目的的条件下，有针对性地获取问题环境的信息，恰
9、当地对这些信息进行处理以提炼知识达到认知，在此基础上，把已有的知识与主体的目的信息相结合，合理地产生解决问题的策略信息，并利用所得到的策略信息在给定的环境下成功地解决问题达到主体的目的。142.1.4智能中“信息-知识-策略”关系v4 4个要素包括个要素包括信息信息知识知识策略策略行为行为v4 4个能力包括个能力包括获取有用信息的能力获取有用信息的能力由信息生成知识由信息生成知识(认知认知)的能力的能力由知识和目的生成策略由知识和目的生成策略(决策决策)的能力的能力实施策略取得效果实施策略取得效果(施效施效)的能力的能力152.1.4智能中“信息-知识-策略”关系v信息、知识、智能之间的关系：
10、信息、知识、智能之间的关系：信息是基本资源；知识是对信息进行加工所得到的抽象化产物；策略是由客体信息和主体目标演绎出来的智慧化身，智能是把信息资源加工成知识、进而把知识激活成解决问题的策略并在策略信息引导下具体解决问题的全部能力。v信息、知识、智能关系，正好符合人类自身认识世界和优化世界活动过程中由信息生成知识、由知识激活智能的过程v总结：信息经加工提炼而成知识，知识被目的激活而成智能。162.1.42.1.4智能中智能中“信息信息-知识知识-策略策略”关系关系获取信息的功能由感觉器官完成，传递信息的功能由神经系统完成，处理信息和再生信息的功能由思维器官完成，施用信息的功能由效应器官完成。17
11、2.1.5 AIAI对知识表示方法的要求对知识表示方法的要求 表示能力，要求能够正确、有效地将问题求解所需要的各类知识都表示出来。可理解性，所表示的知识应易懂、易读。便于知识的获取，使得智能系统能够渐进地增加知识，逐步进化。便于搜索，表示知识的符号结构和推理机制应支持对知识库的高效搜索，使得智能系统能够迅速地感知事物之间的关系和变化；同时很快地从知识库中找到有关的知识。便于推理，要能够从己有的知识中推出需要的答案和结论。182.1.62.1.6 知识的分类知识的分类 形态性知识、内容性知识、效用性知识三者的综合，构成了知识的完整概念19第二章知识表示方法第二章知识表示方法2.1 知识与知识表示
12、的概念知识与知识表示的概念 2.2 状态空间法状态空间法2.3 问题归约法问题归约法2.4 谓词逻辑法谓词逻辑法2.5 语义网络法语义网络法2.6 框架表示框架表示2.7 本体技术本体技术2.8 过程表示过程表示2.9 小结小结202.2状态空间法状态空间法（State Space Representation）v问题求解技术主要是两个方面：l问题的表示问题的表示：同一问题有多种不同的表示l求解的方法求解的方法1：许多问题求解方法采用试探搜索方法v状态空间法状态空间法：基于解答空间的问题表示和求解方法l状态状态（statestate）l算符算符（operatoroperator）l状态空间方法
13、状态空间方法2.2状态空间法 212.2.1 问题状态描述问题状态描述l状态状态定义定义：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。其矢量形式如下：Q=q0,q1,qnT式中每个元素qi(i=0,1，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如：qk=qk,q1k,qnkT 2.1 状态空间法222.2.1 问题状态描述问题状态描述初始状态：由问题已知条件的原始描述所构成的状态目标状态：问题解决时应该到达的状态 l算符算符：使问题从一种状态变化为另一种状态的手段，操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。l状态空间
14、状态空间：一个表示该问题全部可能状态及其关系的图关系的图，包含三种说明的集合，即所有可能的问题初始状态集合初始状态集合S、操作符集操作符集合合F以及目标状态集合目标状态集合G。可把状态空间记为三元状态三元状态(S，F，G)。2.2 状态空间法23v状态空间表示概念详释状态空间表示概念详释OriginalStateMiddleStateGoalState2.2 状态空间法对一个问题的状态描述，必须确定对一个问题的状态描述，必须确定3 3件事：件事：该状态描述方式，特别是初始状态描述；该状态描述方式，特别是初始状态描述；操作符集合及其对状态描述的作用；操作符集合及其对状态描述的作用；目标状态的描述
15、。目标状态的描述。例如：例如：数码难题。数码难题。24例例1:三数码难题三数码难题（3 puzzle problem）123123123312312312初始棋局目标棋局2.2 状态空间法25v图论的基本概念图论的基本概念l有向图有向图l路径路径l代价代价l图的显示说明图的显示说明l图的隐示说明图的隐示说明2.2.2 状态图示法状态图示法AB2.2 状态空间法26v图论的基本概念图论的基本概念l有向图有向图(directed graph)(directed graph)：节点节点(node)(node)：图形上的汇合点，用来表示状态、事件和时间关系的汇合，也可用来指示通路的汇合；后继节点后继节
16、点(descendant node)(descendant node)与父辈节点与父辈节点(parent node)(parent node)：如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。弧线弧线(arc)(arc)：节点间的连接线；有向图有向图(directed graph)(directed graph)：图图由节点（不一定是有限的节点）的集合构。一对节点用弧线连接起来，从一个节点指向另一个节点。2.2状态空间法 27v图论的基本概念图论的基本概念l路径：路径：某个节点序列(n1,n2,nk)，当 j=2=2，3
17、3，k 时，如果对于每一个nj-1-1都有一个后继节点nj存在，那么就把这个节点序列叫做从节点n1至节点nk的长度为k的路径。如果从节点ni到节点nj存在有一条路经，则称nj是从ni可达到的节点。寻找从一种状态变换成另一种状态的某个算符序列问题等价于寻求图的某一路径问题。2.2状态空间法 28v图论的基本概念图论的基本概念l代价：代价：衡量状态之间转变所需的时间、精力等量化的值。用c(ni,nj)来表示从节点ni指向节点nj的弧线的代价。两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。对于最优化问题，就要找两节点间具有最小代价的路径。l显式表示：显式表示：各节点及其具有代价的弧线由
18、一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。问题：对于大型图和具有无限节点集合的图不适用。2.2状态空间法 29v图论的基本概念图论的基本概念l隐式表示隐式表示：起始节点的无限集合si和后继节点算符是已知的。算符能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。1 1节点扩展：节点扩展：将后继算符应用于节点的过程，就是扩展一个节点的过程。问题求解：问题求解：搜索某个状态空间以求得算符序列的一个解答的过程，就对应于使隐式图足够大一部分变为显示以便包含目标节点的过程。优化：优化：问题的表示对求解工作量有很大的影响。优化的问题表示使状态空间小而简单，从而
19、便于求解。许多似乎很难的问题，当表示适当时就可能具有小而简单的状态空间。2.2状态空间法 30尝试各种不同的走步，直到偶然得到目标棋局为止。1 2 38 47 6 5目标状态目标状态例例2 2：九宫排序：九宫排序（八数码问题）（八数码问题）2.2状态空间法 1 2 3 8 4 7 6 52 31 8 47 6 5初始状态2 31 8 47 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 3 41 87 6 531规则：规则：如果针对每个数码来规定规则(上下左右移动)，则需要8 8*4=324=32条规则，如果针对空格来规定规则
20、，则只需要4 4条规则。R1R1：IFIF 空格上方有棋 THENTHEN 空格上移R2R2：IFIF 空格右方有棋 THENTHEN 空格右移R3R3：IFIF 空格下方有棋 THENTHEN 空格下移R4R4：IFIF 空格左方有棋 THENTHEN 空格左移求解的方法求解的方法：首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止。2.2状态空间法 32九宫排序（宽度优先搜索）九宫排序（宽度优先搜索）2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31
21、47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 58433九宫排序（深度优先搜索）九宫排序（深度优先搜索）2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8
22、31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 3 8 47 6 523456789abcd1342.2.32.2.3状态空间表示举例状态空间表示举例v产生式系统产生式系统（production system）l一个总数据库：一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可
23、能简单，或许复杂。l一套规则：一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。l一个控制策略：一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法35用显式说明显式说明（列表）表示状态图，表中放有旅行商经过的城市，表中最后一个元素就是旅行商当前所在的城市。初始数据库初始数据库：（A A）目标数据库：（目标数据库：（A,A,.,A).,A)规则：规则：R1R1：IFIF 没有去过B B THENTHEN 下一步去B BR2R2：IFIF 没有去过C C THENTHEN 下一步去C
24、CR3R3：IFIF 没有去过D D THENTHEN 下一步去D DR4R4：IFIF 没有去过E E THENTHEN 下一步去E ER5R5：IFIF 都去过了 THENTHEN 下一步去A AA5722341431BEDC例例3 3：旅行商问题：旅行商问题2.2状态空间法 362.2.3状态空间表示举例状态空间表示举例v产生式系统产生式系统（production systemproduction system）数据库（事实库）：数据库（事实库）：含有与具体任务有关的信息,随着应用情况的不同，这些数据库可能简单，或许复杂。规则（知识库）：规则（知识库）：它对数据库进行操作运算。每条规则由
25、左部鉴别规则的适用性或前提条件以及右部描述规则应用时所完成的操作。控制策略控制策略1 1：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.2 状态空间法37例例4 4：猴子和香蕉问题：猴子和香蕉问题 在一个房间内有一只猴子（可把这只猴子看做一个机器人）、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么猴子怎样才能摘到香蕉呢？2.2 状态空间法1.1.综合数据库综合数据库：用一个四元表列(W,x,Y,z)(W,x,Y,z)来表示这个问题的状态：WW：猴子的水平位置；X X：当猴子在箱子顶上时 x=1x=1；否则x=0 x=0；Y Y：箱子的水平位
26、置，Z Z：当猴子摘到香蕉时z=1；否则z=0382.2 状态空间法pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）（2）climbbox猴子爬上箱顶，即有（W，0，W，z）climbbox （W，1，W，z）（3）grasp猴子摘到香蕉，即有（c，1，c，0）grasp （c，1，c，1）（4）goto（U）表示猴子走到水平位置（W，0，Y，z）goto（U）（U，0，Y，z）（1）2.规则库规则库这个问题的操作（算符）以及产生式规则表示如下：392.2 状态空间法3.3.控制策略控制策略 试探性方式4.4.初始条件初始条件 初始状态
27、为(a,0,b,0)5.5.结束条件结束条件 达到状态(c,1,c,1)abc(a,0,b,0)初始状态 猴子猴子香蕉香蕉箱子箱子goto(b)猴子猴子香蕉香蕉箱子箱子 (b,0,b,0)climbbox pushbox(c)(c,0,c,0)goto(U)goto(U)pushbox(V)climbbox(c,1,c,0)grasp(c,1,c,1)目标状态 Ha!Ha!求解结果：该初始状态变换为目标状态的操作序列求解结果：该初始状态变换为目标状态的操作序列goto(b),pushbox(c),climbbox,graspgoto(b),pushbox(c),climbbox,grasp状态
28、空间图状态空间图(求解过程求解过程1):40例例5 5：设字符转换规则ABC，ACD，BC G，BEF，DE。现在已知：A和B，求：F。1.综合数据库 3.控制策略 x，其中x为字符 顺序排队2.规则集(用产生式系统来描述）4.初始条件 IF AB THEN C A，B IF AC THEN D 5.结束条件 IF BC THEN G Fx IF BE THEN F IF D THEN E411、IF AB THEN C2、IF AC THEN D3、IF BC THEN G4、IF BE THEN F5、IF D THEN E 初始条件初始条件 A，B 结束条件结束条件Fx A,B,C,D（
29、3）（5）（2）（3）A,B A,B,C（1）A,B,C,D,G,E,F A,B,C,D,G,E（4）A,B,C,D,G（5）初始状态初始状态例例3 3问题的状态空间图问题的状态空间图42N个传教士，N个野人，一条船，可同时乘坐k个人乘渡。传教士为安全起见，应如何规定摆渡方案，使得任何时刻，当传教士与野人在同一地点(河两岸以及船上)时，野人数目总是不超过传教士的数目。传教士与野人均可摆渡。左左岸岸右右岸岸M30C30B10左左岸岸右右岸岸M03C03B01初始状态初始状态目标状态目标状态例例6 6：传教士与野人问题（：传教士与野人问题（M-CM-C问题）：问题）：以以N=3(N=3(传教士或野
30、人数传教士或野人数)，k=2(k=2(每条船的载人数每条船的载人数)为例求解。为例求解。43求解过程如下求解过程如下：1.1.综合数据库综合数据库用用(m,c,b)表示表示左岸左岸传教士人数、野人人数和船的状态（传教士人数、野人人数和船的状态（b=0无船，无船，b=1有船）：有船）：0m,c3,b 0,1。2.2.规则集规则集IF(m,c,1)THEN(m-1,c,0)IF(m,c,0)THEN(m+1,c,1)IF(m,c,1)THEN(m,c-1,0)IF(m,c,0)THEN(m,c+1,1)IF(m,c,1)THEN(m-1,c-1,0)IF(m,c,0)THEN(m+1,c+1,1)
31、IF(m,c,1)THEN(m-2,c,0)IF(m,c,0)THEN(m+2,c,1)IF(m,c,1)THEN(m,c-2,0)IF(m,c,0)THEN(m,c+2,1)太 繁 琐！44也可以定义为：也可以定义为：IF (m,c,1)(1 i+j2)(c-j m-i m-i=0)(3-c+j 3-m+i 3-m+i=0)THEN (m-i,c-j,0)IF (m,c,0)(1i+j2)(c+j m+im+i=0)(3-c-j 3-m-i 3-m-i=0)THEN (m+i,c+j,0)3.3.控制策略控制策略 试探性方式试探性方式4.4.初始条件初始条件 (3,3,13,3,1)5.5.
32、结束条件结束条件 （0,0,00,0,0）456.6.绘制状态空间图绘制状态空间图(3,3,1)(2,2,0)(3,1,0)(0,2,1)(1,1,1)(0,3,1)(2,2,1)(3,1,1)(3,2,1)(3,0,0)(3,2,0)(0,0,0)(0,1,0)(0,2,0)(1,1,0)(1)IF(m,c,1)THEN(m-1,c,0)(2)IF(m,c,0)THEN(m+1,c,1)(3)IF(m,c,1)THEN(m,c-1,0)(4)IF(m,c,0)THEN(m,c+1,1)(5)IF(m,c,1)THEN(m-1,c-1,0)(6)IF(m,c,0)THEN(m+1,c+1,1)
33、(7)IF(m,c,1)THEN(m-2,c,0)(8)IF(m,c,0)THEN(m+2,c,1)(9)IF(m,c,1)THEN(m,c-2,0)(10)IF(m,c,0)THEN(m,c+2,1)(3)(9)(9)(5)(7)(9)(7)(5)(9)(4)(2)(4)(6)(4)(6)(4)462.2.3 3问题归约法问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问原始问题题子问题集本本原原问问题题问题归约是另一种基于状态空间的问题描述与求解方法。问题归约是另一种基于状态空间的问题描述与求解方法。已知问题的描述，通过一系列变
34、换把此问题最终变为一已知问题的描述，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。决了初始问题。47 例例1 1：假定会求矩形的面积，现在要求如图所示的五边形的面假定会求矩形的面积，现在要求如图所示的五边形的面积。积。II2III 3I1求五边形面积 1面积 2面积 3面积面积面积面积I面积II面积III面积48v 问题归约表示的组成部分：l一个初始问题描述；l一套把问题变换为子问题的操作符；l一套本原问题描述。v问题归约的实质：l从目标(要解决的问题)出发逆向推理逆向推理，建立子问题以及子问题的子
35、问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.3 问题规约法492.3.12.3.1问题归约描述问题归约描述 （Problem Reduction DescriptionProblem Reduction Description）1.1.梵塔难题梵塔难题1 12.3 问题规约法最初，全部3个圆从大B到小堆放在第1个柱子上，要求把所有圆盘从大到小堆放在第3个柱子上。每次只许移动一个，并且只能先搬动柱子顶上的圆盘，还不能把大的圆盘堆放在较小的圆盘上。CCAB初始状态AB目标状态1 2 350v梵塔难题求解梵塔难题求解1 12.3 问题规约法把原始问题规约为一个较简单的问题集合：把原始问
36、题规约为一个较简单的问题集合：要把所有的圆盘移到柱子3，首先把圆盘C移至柱子3；而且在其之前，要求柱子3是空的。只有移开A、B之后，才能移动C；且A、B最好不要移至柱子3，否则C不能移至柱子3。因此首先把A、B移至柱子2上。然后，把C从柱子1移至柱子3，并继续解决难题的其他部分。CCAB初始配置初始配置AB目标配置目标配置1 2 351CABCAB（3,3,33,3,3）目标配置）目标配置CABCAB子问题(1,1,1)(1,1,1)初始配置初始配置CAB(1,2,2)(3,2,2)(3,3,3)上述分析允许把原始难题归约（简化）为上述分析允许把原始难题归约（简化）为3 3个子难题：个子难题：
37、移动圆盘A、B至柱子2的双圆盘难题。移动圆盘C至柱子3的单元盘难题。移到圆盘A、B至柱子3的双圆盘难题。52梵塔问题归约图梵塔问题归约图1（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321）（331）（322）（321）（331）（333）2.3 问题规约法将所有的子问题归约为本原问题，最后画出与或图(AND/OR graph)，来说明如何由问题归约法求得问题的解答。532.2.问题归约描述问题归约描述v问题归约方法应用算符来将问题描述变换为子为题描述。问题归约方法应用算符来将问题描述变换为子为题
38、描述。问题描述可以有各种数据结构形式：表列、树、字符串、问题描述可以有各种数据结构形式：表列、树、字符串、矢量、数组等。矢量、数组等。l对于梵塔难题，其子问题可以用一个包含两个数列的表列来描述：(1 1 3),(3 3 3)表示把初始配置(1,1,3)变换为目标配置(3,3,3)1 1。v可以用状态空间表示的三元组可以用状态空间表示的三元组(S,F,G)(S,F,G)来规定与描述问题。来规定与描述问题。可将有关子问题当作状态空间中两个一定的可将有关子问题当作状态空间中两个一定的“脚踏石脚踏石”之之间寻找路径的问题来处理。间寻找路径的问题来处理。l对于梵塔难题，子问题(1 1 1)(1 2 2)
39、(1 1 1)(1 2 2)，(1 2 2)(3 2 2),(1 2 2)(3 2 2),(3 2 2)(3 3 3)(3 2 2)(3 3 3)规定了最后解答路径要通过的脚踏石状态(1 2 2)(1 2 2)和和(3 2 2)(3 2 2)。54v问题归约法与状态空间法之间的不同点与关系：问题归约法与状态空间法之间的不同点与关系：l问题归约可以应用状态、算符和目标这些表示法来描述问问题归约可以应用状态、算符和目标这些表示法来描述问题，这并不意味问题归约和状态空间法是一样的。题，这并不意味问题归约和状态空间法是一样的。实际上，递增状态空间搜索应用某个问题归约的普通形式，而问题归约法是比状态空间
40、法更普通的一种问题求解方法。把问题描述变换为一个归约或后续问题描述的集合，这是由问题归约算符进行的。变换得到的所有后续问题的解就是父辈问题的一个解l所用问题归约的目的是最终产生具有明显解答的本原问题。所用问题归约的目的是最终产生具有明显解答的本原问题。这些问题可能是能够由状态空间搜索中走动一步来解决问这些问题可能是能够由状态空间搜索中走动一步来解决问题，或者可能是其他具有已知解答的更复杂的问题。题，或者可能是其他具有已知解答的更复杂的问题。本源问题除了对终止搜索过程起到明显的作用外，有时还被用来限制归约过程中产生后续问题的替代集合。1 1552.2.22.2.2与或图表示与或图表示1.1.与图
41、、或图、与或图与图、或图、与或图 与或图能够方便的用一个类似于图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图（与或图）1。2.3 问题规约法ABCD与图ABC或图562.3 问题规约法BCDEFGAHMBCDEFGAN图图2.6子问题替换集合结构图子问题替换集合结构图图图2.7 一个与或图一个与或图572.2.与或图的术语与或图的术语2.3 问题规约法l与或图：与或图：1 1由与节点及或节点组成的结构图由与节点及或节点组成的结构图模拟问题归约方法的相关结构是一个与或图模拟问题归约方法的相关结构是一个与或图在状态空间搜索中，根本不出现任何与节点。是否存在与在状态空间搜索中，根本不出
42、现任何与节点。是否存在与节点也就成为区别问题归约和状态空间两种问题求解方法节点也就成为区别问题归约和状态空间两种问题求解方法的主要依据。的主要依据。在描述与或图时，仍然采用如父辈节点、后继结点和连接在描述与或图时，仍然采用如父辈节点、后继结点和连接两节点的弧线等术语。两节点的弧线等术语。582.3 问题规约法HMBCDEFGAN父节点与节点与节点:只有解决所有只有解决所有子问题，才能解决其子问题，才能解决其父辈问题的节点父辈问题的节点 集合，集合，各个结点之间用一段各个结点之间用一段小圆弧连接标记小圆弧连接标记，如如(B,C)和和(D,E,F)。弧线或节点或节点:只要解决某个问题就只要解决某个
43、问题就可解决其父辈问题的节点集可解决其父辈问题的节点集 合，如合，如(M,N,H)。子节点终叶节点终叶节点:对应对应于本原问题的节于本原问题的节点点，它没有后裔，它没有后裔1。592.3 问题规约法l与或图与或图中一个中一个可解节点的可解节点的一般定义可归纳如下：一般定义可归纳如下：终叶节点必然是可解节点(因为它们是本原问题)。若某个非终叶节点含有或后继节点或后继节点，则只要当其后继节点有一个是可解时，此非终叶节点就是可解的。若某个非终叶节点含有与后继节点与后继节点，则只有当其后继节点全部为可解时，此非终叶节点才是可解的。l与或图与或图中不可解节点的一般定义可归纳如下：中不可解节点的一般定义可
44、归纳如下：没有后裔的非终叶节点为不可解节点。若某个非终叶节点含有或后继节点或后继节点，则只有当其全部后裔为不可解时，此非终叶节点才是不可解的。若某个非终叶节点含有与后继节点与后继节点，则只要当其后裔至少有一个为不可解时，此非终叶节点就是不可解的。60与或图的例子与或图的例子2.3 问题规约法图图2.8 与或图例子（与或图例子（显式图显式图）ttttttttt（a）（b）有解节点(用小圆点表示）无解节点(用小圆点表示)终叶节点(用字母t表示)61与或图的与或图的构成规则构成规则2.3 问题规约法 与或图中的每个节点代表一个要解决的单一问题或问题集合。与或图中的起始节点对应于原始问题。对应于本源问
45、题的节点，叫做终叶节点，它没有后裔。对于把算符应用于问题A A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继结点，表示所求得的子问题集合。对于与节点，需要用圆弧将有向弧线连接起来。而或节点不需要。代表子问题集合的中间或节点可以省略。备注：与状态空间问题求解一样，很少使用显式图来搜索，而是用由初始问题描述和消解算符所定义的隐式图来搜索。这样，一个问题求解时只要生成与或图的足够部分就可以问题求解时只要生成与或图的足够部分就可以了。了。62(S,F,Gf)(S,F,G)(g,F,G)问题归约机理问题归约机理关键算符：关键算符：当应用某个算符是问题求解的决定性步骤时，就称该算符为关
46、键算符。当确定下来某个关键算符时，可用它来确定问题归约的过程。例例2 2：假设一个状态空间搜索问题有三元状态(S,F,G)所规定。S为初始状态，F为规则集，G为目标状态。设f是该问题的关键算符关键算符，则(S,F,G)的第一个后裔问题是去寻找一条通向适用状态的路径问题。设Gf表示f适用的所有状态的集合，则得到原问题的子问题(S,F,Gf)。设状态gGf，则得到另一个子问题(g,F,f(g)。其中，f(g)表示把f应用于g而得到的状态，且f(g)G。因为这个问题仅仅由应用关键算符f来解决，所以它是本原的。63例例3.3.猴子和香蕉问题猴子和香蕉问题 在一个房间内有一只猴子（可把这只猴子看做一个机
47、器人）、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么猴子怎样才能摘到香蕉呢？2.2 状态空间法1.1.综合数据库综合数据库：用一个四元表列(W,x,Y,z)(W,x,Y,z)来表示这个问题的状态：WW：猴子的水平位置；X X：当猴子在箱子顶上时 x=1x=1；否则x=0 x=0；Y Y：箱子的水平位置，Z Z：当猴子摘到香蕉时z=1；否则z=0642.2 状态空间法pushbox（V）猴子把箱子推到水平位置V，即有 f2：（W，0，W，z）pushbox(V)（V，0，V，z）（2）climbbox猴子爬上箱顶，即有 f3：（W，0，W，z）climbbox （W，1
48、，W，z）（3）grasp猴子摘到香蕉，即有 f4：（c，1，c，0）grasp （c，1，c，1）（4）goto（U）表示猴子走到水平位置 f1：W，0，Y，z）goto（U）（U，0，Y，z）（1）这个问题的操作（算符）以及产生式规则表示如下：令F=f1,f2,f3,f4是4 4个算符的集合，G是满足目标条件的状态集合。则初始问题为：(a,0,b,0),F,G)。65 关键算符是关键算符是f4。假设Gf4是适用于算符f4的状态集合，则初始问题变为：(a,0,b,0),Gf4)和(S1,G)。这里S1=(c,1,c,0),S1必须是求解前一问题得到的状态。【第一步】找关键算符第一步】找关键算
49、符【第二步】求解问题第二步】求解问题(a,0,b,0),Gf4)由(a,0,b,0)所描述的状态不在Gf4中，因为：箱子不在c处；猴子不在c处；猴子不在箱子上。则下列算符为该问题的关键算符：f2:pushbox(c)，f1:goto(c)，f3:climbbox应用关键算符产生各归约问题的子问题集合。【第第三步三步】先解决问题，应用f2使问题(a,0,b,0),Gf4)变为问题(a,0,b,0),Gf2)和(S11,Gf4)，其中，其中 S11是应用f2得到的状态(c,0,c,0)。66计算(a,0,b,0),Gf2)问题的差别，此差别为猴子不在b处。则得到关键算符f1：goto(b)，应用f
50、1得到问题(a,0,b,0),Gf2)变为问题(a,0,b,0),Gf1)和(S111,Gf2)。S111是应用f1得到的状态(b,0,b,0)。因为状态(a,0,b,0)在规则f1的域内，因此问题(a,0,b,0),Gf1)已是本原问题。因为状态 S111=(b,0,b,0)在规则f2的域内，则问题(b,0,b,0),Gf2)也是本原问题，且问题 的目标状态S11为(c,0,c,0)。至此，所有问题得到解决。最后画出与或图。67(c,1,c,0)(c,1,c,1)(a,0,b,0)(c,0,c,0)(c,0,c,0)(c,1,c,0)(a,0,b,0)(c,1,c,1)f4(a,0,b,0)
