状态空间法
教案
中职数学基础模块教案 下载北师大版¥1.2次方程的根与系数的关系的教案关于坚持的教案初中数学教案下载电子教案下载
一、问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
引入
结合一些典型问题(分油问题)提出问题:
我们是怎样解决这些问题的,在人工智能领域又可以通过怎样的方法去解决呢,(状态空间法) 2、引导学生思考问题，并得出结论。
二、讲授新课
(一)基础知识部分
1、什么是状态空间法,
许多问题求解方法是采用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。
2、状态空间法三要点
1) 状态(state):表示问题解法中每一步问题状况的数据结构;
2) 算符(operator):把问题从一种状态变换为另一种状态的手段;
3) 状态空间方法:基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。
由上可知，对一个问题的状态描述，必须确定3件事: 1) 该状态描述方式，特别是初始状态描述; 2) 操作符集合及其对状态描述的作用;
3) 目标状态描述的特性。
问题的状态空间可用一个三元序组来表示:
S:问题的全部初始状态的集合
F:操作的集合
G:目标状态的集合
4、用状态空间表示问题的步骤:
1)定义状态的描述形式
2)用所定义的状态描述形式把问题所有可能的状态都表示出来，并确定初始状态和目标状态的
集合描述
3)定义一组算符，使得利用这些算符可以把问题由一个状态转为另一个状态。
4)利用状态空间图表示求解过程。
(二)实践应用部分
【分油问题】 有A、B、C三个不带刻度的瓶子，分别能装8kg, 5kg和3kg油。如果A瓶装满油，
B和C是空瓶，怎样操作三个瓶，使A中的油平分两份,(假设分油过程中不耗油)
解:第一步: 定义问题状态的描述形式:
设Sk=(b,c)表示B瓶和C瓶中的油量的状态。 其中:
b表示B瓶中的油量。
c表示C瓶中的油量。
初始状态集:S={(0,0)}
目标状态集:G={(4,0)}
第二步: 定义操作符:
操作:把瓶子倒满油，或把瓶子的油倒空。
f1:从A瓶往B瓶倒油，把B瓶倒满。
f2:从C瓶往B瓶倒油，把B瓶倒满。
f3:从A瓶往C瓶倒油，把C瓶倒满。
f4:从B瓶往C瓶倒油，把C瓶倒满。
f5:从B瓶往A瓶倒油，把B瓶倒空。
f6:从B瓶往C瓶倒油，把B瓶倒空。
f7:从C瓶往A瓶倒油，把C瓶倒空。
f8:从C瓶往B瓶倒油，把C瓶倒空。
第三步: 求解过程:
由上述状态空间图，可见从初始状态(0,1)到目标状态(4,0)的任何一条通路都是问题的一个解。其中:{f1, f4, f7, f6, f1, f4, f7}是算符最少的解之一。
【传教士问题】设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去,
解:第一步: 定义问题状态的描述形式:
设Sk=(M,C,B)表示传教士和野人在河右岸的状态。
其中:
M表示传教士在右岸的人数。
C表示野人在右岸的人数。
B用来表示船是不是在右岸。(B=1表示在右岸，B=0表示在左岸)。 初始状态集:S={(3,3,1)}
目标状态集:G={(0,0,0)}
第二步:定义算符:
算符R(i, j)表示划船将i个传教士和j个野人送到左岸的操作。
算符L(i, j)表示划船从左岸将i个传教士和j个野人带回右岸的操作。
由于过河的船每次最多载两个人，所以i+j?2。这样定义的算符集F中只可能有如下10个算符。
F:R(1,0), R(2,0), R(1,1), R(0,1), R(0,2)
L(1,0), L(2,0), L(1,1), L(0,1), L(0,2) 第三步:求解过程:
由上述状态空间图，可见从初始状态(3,3,1)到目标状态(0,0,0)的任何一条通路都是问题的一个
:{R(1,1), L(1,0), R(0,2), L(0,1), R(2,0), L(1,1), R(2,0), L(0,1), R(0,2), L(1,0), R(1,1)}解。其中
是算符最少的解之一。
三、巩固
练习
飞向蓝天的恐龙练习非连续性文本练习把字句和被字句的转换练习呼风唤雨的世纪练习呼风唤雨的世纪课后练习
1、八数码问题(即九宫问题)
在一个,×,的九宫中有,,,这,个数及一个空格随机的摆放在其中的格子里，如左图所示。现在要求实现这个问题:将该九宫格调整为如中(或右)图所示的形式。调整的规则是:每次只能将与空格(上、下、或左、右)相邻的一个数字平移到空格中。
2、汉诺塔问题
古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求写出移动的步骤。
四、总结
本节课旨在帮助学生学习知识表示的方法——状态空间法，并通过两个具体案例，帮助学生将所学的
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
应用于实践，最后通过两个小练习帮助学生巩固练习。
浙公网安备 33021202002483