文档介绍：第二章知识表示方法
状态空间法
问题归约法
谓词逻辑法
语义网络法
其他方法
小结
中南大学智能系统与智能软件研究所
(State Space Representation)
问题求解技术主要是两个方面:
问题的表示
求解的方法
状态空间法
状态(state)
算符(operator)
状态空间方法
2
问题状态描述
定义
状态:描述某类不同事物间的差别而引入的一组最少变量q0,q1,…,qn的有序集合。
算符:使问题从一种状态变化为另一种状态的手段称为操作符或算符。
问题的状态空间:是一个表示该问题全部可能状态及其关系的图,它包含三种说明的集合,即三元状态(S,F,G)。
状态空间法
3
2. 状态空间表示概念详释
例如下棋、迷宫及各种游戏。
Original
State
Middle
State
Goal
State
状态空间法
4
例:三数码难题 (3 puzzle problem)
1
2
3
1
2
3
1
2
3
3
1
2
3
1
2
3
1
2
初始棋局
目标棋局
状态空间法
5
有向图
路径
代价
图的显示说明
图的隐示说明
状态图示法
A
B
状态空间法
6
状态空间表示举例
产生式系统(production system)
一个总数据库:它含有与具体任务有关的信息随着应用情况的不同,这些数据库可能简单,或许复杂。
一套规则:它对数据库进行操作运算。每条规则由左部鉴别规则的适用性或先决条件以及右部描述规则应用时所完成的动作。
一个控制策略:它确定应该采用哪一条适用规则,而且当数据库的终止条件满足时,就停止计算。
状态空间法
7
状态空间表示举例
例:猴子和香蕉问题
状态空间法
8
解题过程
用一个四元表列(W,x,Y,z)来表示这个问题状态.
这个问题的操作(算符)如下:
2 goto(U)表示猴子走到水平位置U
或者用产生式规则表示为
(W,0,Y,z) goto(U) (U,0,Y,z)
状态空间法
9
pushbox(V)猴子把箱子推到水平位置V,即有
(W,0,W,z) pushbox(V) (V,0,V,z)
climbbox猴子爬上箱顶,即有
(W,0,W,z) climbbox (W,1,W,z)
状态空间法
10