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