人工智能及其应用2.ppt

文档介绍：**(StateSpaceRepresentation)问题求解技术主要是两个方面:问题的表示求解的方法状态空间法状态(state):表示问题解法中每一步问题状况的数据结构算符(operator):把问题从一种状态变换为另一种状态的手段状态空间方法:基于解答空间的问题表示和求解方法,它是以状态和算符为基础来表示和求解问题的*(State):描述某类不同事物间的差别而引入的一组最少变量q0,q1,…,qn的有序集合。算符(Operate):使问题从一种状态变化为另一种状态的手段称为操作符或算符。问题的状态空间(StateSpace):是一个表示该问题全部可能状态及其关系的图,它包含三种说明的集合,即三元状态(S,F,G)。*状态空间表示概念详释状态空间法:从某个初始状态开始,每次加一个操作符,递增的建立起操作符的实验序列,直到达到目标状态止。例如下棋、迷宫及各种游戏。……*例:三数码难题(3puzzleproblem)*有向图一对节点用弧线连接起来,从一个节点指向另一个节点这种图叫做有向图。路径某个节点序列(ni1,ni2,…,nik)当j=2,3,…,k时,如果对于每一个ni,j-1都有一个后继节点ni,j存在,那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径代价用c(ni,nj)来表示从节点ni指向节点nj的那段弧线的代价。*图的显示说明对于显式说明,各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价 (举例:邻接表,邻接矩阵)图的隐示说明说明节点的无限集合{si}作为起始节点是已知的。后继节点算符Γ(gamma)也是已知的,它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。(举例:棋局)表示方法的多样性如十五数码难题中规则1:移动数码(15X4条规则)规则2:移动空格(4条规则)*产生式系统搜索过程描述产生式系统(productionsystem)一个总数据库:它含有与具体任务有关的信息随着应用情况的不同,这些数据库可能简单,或许复杂。一套规则:它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。一个控制策略:它确定应该采用哪一条适用规则,而且当数据库的终止条件满足时,就停止计算。*状态空间表示实例(1)例:*解题过程用一个四元表列(W,x,Y,z)=1;否则取x=0Y箱子的水平位置z 当猴子摘到香蕉时取z=1;否则取z=0这个问题的操作(算符)如下:goto(U)表示猴子走到水平位置U或者用产生式规则表示为 (W,0,Y,z)goto(U)(U,0,Y,z)