文档介绍：人工智能初步 教学案例
2017/11/11
2
状态空间表示法
案例1
2017/11/11
3
目标
学会用状态空间法表示重排九宫问题
了解状态空间法的相关概念、基本思想
2017/11/11
4
程序
算法
问题
使用计算求解问题的思路
分析建模
程序设计
2017/11/11
5
要求:用尽可能少棋步能由初始状态到达目标状态。
例1 [重排九宫问题]
8 3
6 4
7 ■ 5
初始状态
1 2 3
■ 8 4
7 6 5
目标状态
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
6 4
1 7 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
1 6
7 5 4
8 3
2 6 4
1 7 5
2 8 3
6 4
1 7 5
8 3
2 1 4
7 6 5
2 8 3
7 1 4
6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 8
1 4 3
7 6 5
2 8 3
1 6
7 5 4
2 8
1 6 3
7 5 4
8 3
2 6 4
1 7 5
2 3
6 8 4
1 7 5
8 3
2 1 4
7 6 5
2 8 3
7 1 4
6 5
1 2 3
8 4
7 6 5
2 3 4
1 8
7 6 5
2 8 3
1 4
7 6 5
2 8
1 4 3
7 6 5
2 8 3
1 6
7 5 4
2 8
1 6 3
7 5 4
2 8 3
6 4
1 7 5
2 8 3
6 7 4
1 5
2 3
1 8 4
7 6 5
2 8 3
1 6 4
7 5
2 3
1 8 6
7 5 4
2 8 3
1 5 6
7 4
目标状态
初始状态
2017/11/11
7
状态
表示问题求解过程中每一步问题状况的数据结构。
例如, 在棋弈中的格局即为问题的状态。
操作
把问题从一种状态变换为另外一种状态的手段。
例如,棋弈中一步“走子”可将一个格局变为另一种格局。
状态空间表示法
2017/11/11
8
状态空间
用来描述一个问题的全部状态以及这些状态之间的相互关系。包含三个部分:
S—问题的初始状态集合
F—操作集合
G—目标状态的集合
状态空间树(图)
可用一个图(树)来直观地表示出状态空间。
2017/11/11
9
状态空间表示法的基本思想
用“状态”和“操作”来表示问题及其变化,形成状态空间,求解问题的过程就是在状态空间树中搜索表示解的状态的过程。
搜索时,从某个初始状态出发,每次使用一个操作使得问题能够从一种状态变为另外一种状态,直到到达目标状态为止。
2017/11/11
10
假设有7个钱币,任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币,两位选手轮流进行,直到每一堆都只有一个或两个钱币,不能再分为止,哪个遇到不能分的情况,则就为输。
假设对方先走,我方是否有必胜策略?
[例2] 分钱币问题