一、问题引入
结合一些典型问题（分油问题）提出问题：
我们是怎样解决这些问题的？在人工智能领域又可以通过怎样的方法去解决呢？（状态空间法）
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座，要求写出移动的步骤。
四、总结
本节课旨在帮助学生学习知识表示的方法——状态空间法，并通过两个具体案例，帮助学生将所学的内容应用于实践，最后通过两个小练习帮助学生巩固练习。
