1、人工智能初步人工智能初步 教学案例教学案例2022-12-82状态空间表示法状态空间表示法案例案例1 12022-12-83目标目标 学会用状态空间法表示重排九宫问题了解状态空间法的相关概念、基本思想2022-12-84程序程序算法算法问题问题使用计算求解问题的思路使用计算求解问题的思路分析建模分析建模程序设计程序设计2022-12-85要求：用尽可能少棋步能由初始状态到达目标状态。要求：用尽可能少棋步能由初始状态到达目标状态。例例1 重排九宫问题重排九宫问题28 3 16 47 5初始状态初始状态1 2 3 8 47 6 5目标状态目标状态2 8 31 6 47 52 8 31 47 6 5
2、2 8 31 6 47 5 2 8 31 6 4 7 52 8 3 6 41 7 52 8 3 1 47 6 52 31 8 47 6 52 8 31 4 7 6 52 8 31 6 7 5 4 8 32 6 41 7 52 8 36 41 7 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 3 1 8 47 6 52 8 31 47 6 52 8 1 4 37 6 52 8 31 67 5 42 81 6 37 5 48 32 6 41 7 52 36 8 41 7 58 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52
3、 3 41 8 7 6 52 8 3 1 47 6 52 81 4 37 6 52 8 3 1 67 5 42 81 6 37 5 42 8 36 4 1 7 52 8 36 7 41 52 31 8 47 6 52 8 31 6 47 52 31 8 67 5 42 8 31 5 67 4目标状态目标状态初始状态初始状态2022-12-87状态状态 表示问题求解过程中每一步问题状况的数据结构。表示问题求解过程中每一步问题状况的数据结构。例如，例如，在棋弈中的格局即为问题的状态。在棋弈中的格局即为问题的状态。操作操作 把问题从一种状态变换为另外一种状态的手段。把问题从一种状态变换为另外一种状态
4、的手段。例如，棋弈中一步例如，棋弈中一步“走子走子”可将一个格局变为另一种格可将一个格局变为另一种格局。局。状态空间表示法状态空间表示法2022-12-88状态空间状态空间 用来描述一个问题的全部状态以及这些状态之间的相互用来描述一个问题的全部状态以及这些状态之间的相互关系。包含三个部分：关系。包含三个部分：S问题的初始状态集合问题的初始状态集合 F操作集合操作集合 G目标状态的集合目标状态的集合状态空间树（图）状态空间树（图）可用一个图（树）来直观地表示出状态空间。可用一个图（树）来直观地表示出状态空间。2022-12-89状态空间表示法的基本思想状态空间表示法的基本思想 用用“状态状态”和
5、和“操作操作”来表示问题及其变化，形成状态来表示问题及其变化，形成状态空间，求解问题的过程就是在状态空间树中搜索表示解的状空间，求解问题的过程就是在状态空间树中搜索表示解的状态的过程。态的过程。搜索时，从某个初始状态出发，每次使用一个操作使得搜索时，从某个初始状态出发，每次使用一个操作使得问题能够从一种状态变为另外一种状态，直到到达目标状态问题能够从一种状态变为另外一种状态，直到到达目标状态为止。为止。2022-12-810 假设有假设有7个钱币，任一选手只能将已分个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只
6、有一两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。不能分的情况，则就为输。假设对方先走，我方是否有必胜策略？假设对方先走，我方是否有必胜策略？例例2 分钱币问题分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走对方先走我方胜我方胜对方胜对方胜对方胜对方胜分钱币问题的搏弈图分钱币问题的搏弈图2022-12-812结论结论评价评价2
7、022-12-8131.还有哪些类似的问题可以使用状态空间来还有哪些类似的问题可以使用状态空间来描述？描述？比如，井字棋、五子棋、拾火柴等比如，井字棋、五子棋、拾火柴等游戏。画出井字棋问题的状态空间树。游戏。画出井字棋问题的状态空间树。2.过河问题如何使用状态空间法表示？过河问题如何使用状态空间法表示？画出过河问题的状态空间图。画出过河问题的状态空间图。思考与练习思考与练习井字棋井字棋游戏井字棋游戏五子棋游戏五子棋游戏2022-12-816 假定盘中放有假定盘中放有n根火柴，由弈者根火柴，由弈者A和和B两人两人参加比赛。比赛的规则是：两名弈者轮流从盘参加比赛。比赛的规则是：两名弈者轮流从盘中取
8、走火柴，每次从盘中取走中取走火柴，每次从盘中取走1，2或或3根火柴均根火柴均为合法着，否则为非法着。拿走盘中最后一根为合法着，否则为非法着。拿走盘中最后一根火柴的弈者为输。假定火柴的弈者为输。假定A方先走，方先走，A有必胜策略有必胜策略吗？若有就找出吗？若有就找出A的必胜策略。的必胜策略。拾火柴游戏拾火柴游戏2022-12-817搜索技术搜索技术案例案例22022-12-818目标目标 学会用几种搜索技术求解重排九宫问题 体验几种搜索技术的基本思想2022-12-819盲目搜索盲目搜索状态空间树（图）上的搜索策略状态空间树（图）上的搜索策略启发式搜索启发式搜索宽度优先搜索宽度优先搜索深度优先搜
9、索深度优先搜索2022-12-820求解思路：求解思路：1.先将问题的求解过程用状态空间树表示出来先将问题的求解过程用状态空间树表示出来2.在状态空间树上搜索问题的解答在状态空间树上搜索问题的解答要求：用尽可能少棋步能由初始状态到达目标状态。要求：用尽可能少棋步能由初始状态到达目标状态。例例1 重排九宫问题重排九宫问题28 3 16 47 5初始状态初始状态1 2 3 8 47 6 5目标状态目标状态2 8 31 6 47 52 8 31 47 6 52 8 31 6 47 5 2 8 31 6 4 7 52 8 3 6 41 7 52 8 3 1 47 6 52 31 8 47 6 52 8
10、 31 4 7 6 52 8 31 6 7 5 4 8 32 6 41 7 52 8 36 41 7 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 3 1 8 47 6 52 8 31 47 6 52 8 1 4 37 6 52 8 31 67 5 42 81 6 37 5 48 32 6 41 7 52 36 8 41 7 58 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 8 7 6 52 8 3 1 47 6 52 81 4 37 6 52 8 3 1 67 5 42 81 6 37 5 42 8 3
11、6 4 1 7 52 8 36 7 41 52 31 8 47 6 52 8 31 6 47 52 31 8 67 5 42 8 31 5 67 4目标状态目标状态初始状态初始状态深度优先搜索深度优先搜索2 8 31 6 47 52 8 31 47 6 52 8 31 6 47 5 2 8 31 6 4 7 52 8 3 6 41 7 52 8 3 1 47 6 52 31 8 47 6 52 8 31 4 7 6 52 8 31 6 7 5 4 8 32 6 41 7 52 8 36 41 7 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 3 1
12、8 47 6 52 8 31 47 6 52 8 1 4 37 6 52 8 31 67 5 42 81 6 37 5 48 32 6 41 7 52 36 8 41 7 58 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 8 7 6 52 8 3 1 47 6 52 81 4 37 6 52 8 3 1 67 5 42 81 6 37 5 42 8 36 4 1 7 52 8 36 7 41 52 31 8 47 6 52 8 31 6 47 52 31 8 67 5 42 8 31 5 67 4目标状态目标状态初始状态初始状态宽度优先搜索宽度优先
13、搜索2022-12-823启发式函数启发式函数:f(X)=g(X)+h(X)Xg(X)h(X)启发式搜索启发式搜索2 8 3 1 6 47 52 8 3 1 6 4 7 52 8 3 1 47 6 52 8 3 1 6 4 7 5 2 8 3 1 47 6 52 3 1 8 47 6 52 8 3 1 4 7 6 5 8 3 2 1 47 6 52 8 3 7 1 4 6 5 2 3 1 8 47 6 5 2 3 1 8 47 6 51 2 3 8 47 6 50+41+51+31+52+32+32+43+3 3+43+2 3+44+1启发函数：启发函数：f(X)=g(X)+h(X)目标目标2
14、 8 3 1 6 47 52 8 3 1 6 4 7 52 8 3 1 47 6 52 8 3 1 6 4 7 5 2 8 3 1 47 6 52 3 1 8 47 6 52 8 3 1 4 7 6 5 8 3 2 1 47 6 52 8 3 7 1 4 6 545353343 4到目标到目标到无结果的漫游到无结果的漫游 8 3 2 1 47 6 53 启发函数：启发函数：f(X)=h(X)2022-12-826 假设有假设有7个钱币，任一选手只能将已分个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一两位选手
15、轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。不能分的情况，则就为输。假设对方先走，我方是否有必胜策略？假设对方先走，我方是否有必胜策略？例例2 分钱币问题分钱币问题分钱币问题的搏弈图分钱币问题的搏弈图（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走对方先走我方必胜我方必胜00011010011111MinMaxMinMaxMin2022-12
16、-828机器搏弈机器搏弈 存在问题：存在问题：一盘棋平均走一盘棋平均走50步，总状态数约为步，总状态数约为10的的161次方。假设次方。假设1毫微秒走一步，约需毫微秒走一步，约需10的的145次方年。因此，不可能将所有情次方年。因此，不可能将所有情况列尽，即不能穷举走象棋的整个状态况列尽，即不能穷举走象棋的整个状态空间树（搏弈树）。空间树（搏弈树）。2022-12-829机器搏弈机器搏弈 解决办法：解决办法：模拟人模拟人“向前看几步向前看几步”，然后作出决，然后作出决策，决定自己走哪一步最有利。也就是策，决定自己走哪一步最有利。也就是说，只能考虑状态空间树的几层（即向说，只能考虑状态空间树的几层（即向前看几步），然后按照一定的估算方法，前看几步），然后按照一定的估算方法，决定走哪一步棋。这就是决定走哪一步棋。这就是极大极小化方极大极小化方法法。所得到的搜索方法是一种启发式搜。所得到的搜索方法是一种启发式搜索方法。索方法。2022-12-830结论结论评价评价2022-12-8311.启发式知识从何而来？启发式知识从何而来？2.求解重排九宫问题还可挖掘什么启发式知识？求解重排九宫问题还可挖掘什么启发式知识？3.在井字棋、五子棋等游戏中如何挖掘启发式在井字棋、五子棋等游戏中如何挖掘启发式知识？知识？思考与练习思考与练习井字棋应该放在哪？应该放在哪？
