第二章知识表示方法

《第二章知识表示方法》由会员分享，可在线阅读，更多相关《第二章知识表示方法（64页珍藏版）》请在文档大全上搜索。

1、第二章 知识表示方法2.1 状态空间法2.2 问题归约法2.3 谓词逻辑法2.4 语义网络法2.5 其他方法2.6 小结CSUCSUCSUCSUCSUCSUCSUCSUCSU22.1状态空间法（State Space Representation）v问题求解技术主要是两个方面：v问题的表示v求解的方法v状态空间法v状态（state）v算符（operator）v状态空间方法CSUCSUCSUCSUCSUCSUCSUCSUCSU32.1.1 问题状态描述v定义v状态：描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合。v算符：使问题从一种状态变化为另一种状态的手段称为操作符或算

2、符。v问题的状态空间：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。其中所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU42. 状态空间表示概念详释v例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU5例:三数码难题123123123312312312初始棋局目标棋局2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU6CSUCSUC

3、SUCSUCSUCSUCSUCSUCSU7CSUCSUCSUCSUCSUCSUCSUCSUCSU8例：例：十五数码难题v（15 puzzle problem）119415131275861321014123456789101112131415初始状态初始状态目标状态目标状态CSUCSUCSUCSUCSUCSUCSUCSUCSU9CSUCSUCSUCSUCSUCSUCSUCSUCSU10CSUCSUCSUCSUCSUCSUCSUCSUCSU11CSUCSUCSUCSUCSUCSUCSUCSUCSU12v有向图v路径v代价v图的显示说明v图的隐示说明2.1.2 状态图示法AB2.1 状态空间法CS

4、UCSUCSUCSUCSUCSUCSUCSUCSU132.1.3 状态空间表示举例v产生式系统（production system）v一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。v一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。v一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU14 状态空间表示举例状态空间表示举例v例：猴子和香蕉问题2.1 状态空间法CSUCSUCSUCSUCS

5、UCSUCSUCSUCSU15解题过程1v用四元 表列（W,x,Y,z）来表示这个问题的状态v其中，vW猴子的水平位置vx当猴子在箱子顶上时取x=1；否则取x=0vY箱子的水平位置vz当猴子摘到香蕉时取z=1；否则取z=0CSUCSUCSUCSUCSUCSUCSUCSUCSU16解题过程2v这个问题的操作（算符）如下：v2 goto（U）表示猴子走到水平位置Uv或者用产生式规则表示为（W，0，Y，z） goto（U） （U，0，Y，z）2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU17vpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbo

6、x（V） （V，0，V，z）vclimbbox猴子爬上箱顶，即有（W，0，W，z） climbbox （W，1，W，z）2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU18vgrasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1） v该初始状态变换为目标状态的操作序列为goto(b),pushbox(c),climbbox,grasp2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU19(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目标状态目标状态

7、goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图猴子和香蕉问题的状态空间图goto（U）U=V2.1 状态空间法CSUCSUCSUCSUCSUCSUCSUCSUCSU202.2 问题归约法（Problem Reduction Representation）子问题子问题1子问题子问题n原始问题原始问题子问题集本本原原问问题题CSUCSUCSUCSUCSUCSUCSUCSUCSU21v 问题归约表示的组成部分：v一个初始问题描述；v一套把问题变换为子问题的操作符；v一套本原问题描述。v问题归约的实质：v从目标(要解决的问题)出发

8、逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU222.2.1 问题归约描述 （Problem Reduction Description）v梵塔难题123CBA2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU23v梵塔难题2.2.1 问题归约描述(a) 初始状态(b) 目标状态CSUCSUCSUCSUCSUCSUCSUCSUCSU24问题规约v原始问题归约（简化）为三个子问题1、移动A，B盘至柱子2的双圆盘难题2、移动圆盘C至柱子3的单圆盘问题3、移动A，B

9、盘至柱子3的双圆盘难题CSUCSUCSUCSUCSUCSUCSUCSUCSU25v归约过程CSUCSUCSUCSUCSUCSUCSUCSUCSU26解题过程（3个圆盘问题）1231231231231231231231232.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU27梵塔问题归约图（113） （123） （111） （113） （123） （122） （111） （333） （122） （322） （111） （122） （322） （333） （321） （331） （322） （321） （331） （333） 2.2 问题规约法CSUCSUCSUCSUCSUC

10、SUCSUCSUCSU28多圆盘梵塔难题演示2.2 问题规约法CSUCSUCSUCSUCSUCSUCSUCSUCSU292.2.2与或图表示v1.与图、或图、与或图2.2 问题规约法ABCD与图ABC或图CSUCSUCSUCSUCSUCSUCSUCSUCSU302.2 问题规约法BCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSU312.一些关于与或图的术语2.2 问题规约法HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点 终叶节点：对应于原问题的本原节点。终叶节点：对应于原问题的本原节点。或节点：只要解决某个问题就可解决其父辈问题的节点集合，如（或

11、节点：只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。）。与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（与节点：只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C)和和 （D,E,F）各个结点之间用一端小圆弧连接标记）各个结点之间用一端小圆弧连接标记 CSUCSUCSUCSUCSUCSUCSUCSUCSU323.定义2.2 问题规约法与或图例子与或图例子ttttttttt（a）（b）有解节点无解节点终叶节点CSUCSUCSUCSUCSUCSUCSUCSUCSU33v不可解节点的一般定义v没有后裔的非终叶节点为不可解节点。v全部后裔为不可解的非终叶节点且