人工智能及其应用2(蔡自兴).ppt

《人工智能及其应用2(蔡自兴).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第二章知识表示方法2.1状态空间法2.2问题归约法2.3谓词逻辑法2.4语义网络法2.5其他方法2.6小结22.1状态空间法（StateSpaceRepresentation）问题求解技术主要是两个方面：问题的表示求解的方法状态空间法状态（state）:表示问题解法中每一步问题状况的数据结构算符（operator):把问题从一种状态变换为另一种状态的手段状态空间方法:基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的32.1.1问题状态描述定义状态(State)：描述某类

2、不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合。算符(Operate)：使问题从一种状态变化为另一种状态的手段称为操作符或算符。问题的状态空间(StateSpace)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即三元状态（S，F，G）。2.1状态空间法4状态空间表示概念详释状态空间法：从某个初始状态开始，每次加一个操作符，递增的建立起操作符的实验序列，直到达到目标状态止。例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalSt

3、ate2.1状态空间法……5例:三数码难题（3puzzleproblem）123123123312312312初始棋局目标棋局2.1状态空间法6有向图一对节点用弧线连接起来，从一个节点指向另一个节点这种图叫做有向图。路径某个节点序列（ni1，ni2，…，nik）当j=2，3，…，k时，如果对于每一个ni，j-1都有一个后继节点ni，j存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径代价用c（ni，nj）来表示从节点ni指向节点nj的那段弧线的代价。两点间路径的代价等于连接该

4、路径上各节点的所有弧线代价之和.2.1.2状态图示法2.1状态空间法AB7图的显示说明对于显式说明，各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价(举例：邻接表，邻接矩阵)图的隐示说明说明节点的无限集合｛si｝作为起始节点是已知的。后继节点算符Γ（gamma）也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。（举例：棋局）表示方法的多样性如十五数码难题中规则1：移动数码（15X4条规则）规则2：移动空格（4条规则）8

5、产生式系统搜索过程描述产生式系统（productionsystem）一个总数据库：它含有与具体任务有关的信息随着应用情况的不同，这些数据库可能简单，或许复杂。一套规则：它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略：它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。2.1状态空间法9状态空间表示实例（1）例：猴子和香蕉问题2.1状态空间法10解题过程用一个四元表列（W，x，Y，z）来表示这个问题状态.W猴子的水

6、平位置x当猴子在箱子顶上时取x=1；否则取x=0Y箱子的水平位置z当猴子摘到香蕉时取z=1；否则取z=0这个问题的操作（算符）如下：goto（U）表示猴子走到水平位置U或者用产生式规则表示为（W，0，Y，z）goto（U）（U，0，Y，z）2.1状态空间法11pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）pushbox（V）（V，0，V，z）应当注意的是，要应用算符pushbox（V），就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是箱子顶上。这种强加于操作

7、的适用性条件，叫做产生式规则的先决条件climbbox猴子爬上箱顶，即有（W，0，W，z）climbbox（W，1，W，z）提问：应用算符climbbox的先决条件是什么？2.1状态空间法12grasp猴子摘到香蕉，即有（c，1，c，0）grasp（c，1，c，1）令初始状态为(a，0，b，0)。这时，goto(U)是唯一适用的操作，并导致下一状态(U，0，b,0)。现在有3个适用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有适用的操作继续应用于每个状态，我们

8、就能够得到状态空间图，如下图所示。从图不难看出，把该初始状态变换为目标状态的操作序列为{goto(b),pushbox(c),climbbox,grasp}2.1状态空间法13(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）目标状态goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉问题的状态空间图goto（U）U=V2.1状态空间法14猴子和香蕉问题自动