人工智能 课件 第二讲 知识表示法----状态空间法.ppt

第二讲 知识表示法----状态空间法 一 问题状态描述 状态（state):描述某类不同事物之间的差别 而引入的一组最少变量的有限集合。 Q=[q0,q1,…,qn]T 其中：qi （i=0,1,2,…,n)称为状态变量，给定每个分量的一组值就得到一个具体的状态。 第二讲 知识表示法----状态空间法 一 问题状态描述 操作符：使问题从一个状态变化为另一个状态的手段。 例如；走步，过程，规则，数学算子，运算符号，逻辑符号等。 问题的状态空间；一个表示该问题全部可能状态及其关系的图。 记为三元状态（S，F，G）。 第二讲 知识表示法----状态空间法 一 问题状态描述 S：问题的初始状态集 F：操作符集 G：目标状态集 第二讲 知识表示法----状态空间法 二 八数码难题 2 8 3 初始状态： S= 1 4 7 6 5 1 2 3 目标状态：G= 8 4 7 6 5 操作符：空格的上，下，左，右移动 第二讲 知识表示法----状态空间法 三 猴子与香蕉问题 状态表示（W，X，Y，Z） W：猴子的水平位置； X：X=1表示猴子在箱子上， X=0表示猴子不在箱子上； Y：箱子的水平位置； Z：Z=1表示猴子摘到香蕉， Z=0表示猴子没有摘到香蕉 第二讲 知识表示法----状态空间法 三 猴子与香蕉问题 初始状态 S=（a,0,b,0) 目标状态 G=（c,1,c,1) 操作符： F =（goto,pushbox,climbbox,grasp) 第二讲 知识表示法----状态空间法 第二讲 知识表示法----状态空间法 (a,0,b,0) goto(U) goto(U) (U,0,b,0) pushbox(v) U=b,climbbox (V,0,V,0) (b,1,b,0) goto(U) V=c,climbbox (c,1,c,0) (U,0,V,0) U=V grasp goto(U) (c,1,c,1) 猴子与香蕉的状态空间图 第二讲 知识表示法----状态空间法 应用实例传教士和野人问题(Missionaries and Cannibals) 三个传教士与三个野人来到河边, 有一条船可供一人或两人乘渡, 问题是如何用这条船渡河才能使得河的任一岸上野人的数目总不超过传教士的数目 我们用一个三元组(m c b)来表示河岸上的状态, 其中m、c分别代表某一岸上传教士与野人的数目, b=1表示船在这一岸, b=0则表示船不在。 ???约束条件是: 两岸上M≥C, 船上M+C≤2。  我们采用产生式系统来解决这一问题。由于传教士与野人的总数目是一常数, 所以只要表示出河的某一岸上的情况就可以了, 为方便起见, 我们选择传教士与野人开始所在的岸为所要表示的岸, 并称其为左岸, 另一岸称为右岸。但显然仅用描述左岸的三元组描述就足以表示出整个情况, 因此必须十分重视选择较好的问题表示法。高效率的问题求解过程与控制策略有关, 合适的控制策略可缩小状态空间的有哪些信誉好的足球投注网站范围, 提高求解的效率。因而问题的初始状态是(3 3 1), 目标状态是(0 0 0)。 (1) 综合数据库: 用三元组表示, 即 (ML, CL, BL), 其中0≤ML, CL≤3, BL∈{0, 1} 此时问题述简化为 (3, 3, 1) (0, 0, 0) (2) N=3的M-C问题, 分析状态空间的总合法状态数，列出分析的结果。 (3) 初始和目标状态: 即(3