高中信息技术人工智能教学案例（05年）ppt课件选修.ppt

《高中信息技术人工智能教学案例（05年）ppt课件选修.ppt》由会员分享，可在线阅读，更多相关《高中信息技术人工智能教学案例（05年）ppt课件选修.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能初步人工智能初步 教学案例教学案例状态空间表示法状态空间表示法案例案例1 11/7/20232目标目标 学会用状态空间法表示重排九宫问题了解状态空间法的相关概念、基本思想1/7/20233程序程序算法算法问题问题使用计算求解问题的思路使用计算求解问题的思路分析建模分析建模程序设计程序设计1/7/20234要求：用尽可能少棋步能由初始状态到达目标状态。要求：用尽可能少棋步能由初始状态到达目标状态。例例1 重排九宫问题重排九宫问题28 3 16 427 5初始状态初始状态1 2 3 8 47 6 5目标状态目标状态1/7/202352 8 31 6 47 52 8 31 47 6 52 8

2、 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目标状态目标状态初始状态初始状态1/7/20236状态状态 表示问题求解过程中每一步问题状况的数据结构。表示问题求解过程中每一步问题状况的数据结构。例如，例如，在棋弈中的格局即为问题的状态。在棋弈中的格局即为问题的状态。操作操作 把问题从一种状态变换为另外一种状态的手段。把问题从一种状态变换为另外一种状态的手段。

4、例如，棋弈中一步例如，棋弈中一步“走子走子”可将一个格局变为另一种格可将一个格局变为另一种格局。局。状态空间表示法状态空间表示法1/7/20237状态空间状态空间 用来描述一个问题的全部状态以及这些状态之间的相互用来描述一个问题的全部状态以及这些状态之间的相互关系。包含三个部分：关系。包含三个部分：S问题的初始状态集合问题的初始状态集合 F操作集合操作集合 G目标状态的集合目标状态的集合状态空间树（图）状态空间树（图）可用一个图（树）来直观地表示出状态空间。可用一个图（树）来直观地表示出状态空间。1/7/20238状态空间表示法的基本思想状态空间表示法的基本思想 用用“状态状态”和和“操作操作

5、”来表示问题及其变化，形成状态来表示问题及其变化，形成状态空间，求解问题的过程就是在状态空间树中搜索表示解的状空间，求解问题的过程就是在状态空间树中搜索表示解的状态的过程。态的过程。搜索时，从某个初始状态出发，每次使用一个操作使得搜索时，从某个初始状态出发，每次使用一个操作使得问题能够从一种状态变为另外一种状态，直到到达目标状态问题能够从一种状态变为另外一种状态，直到到达目标状态为止。为止。1/7/20239 假设有假设有7个钱币，任一选手只能将已分个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一两位选手轮流

6、进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。不能分的情况，则就为输。假设对方先走，我方是否有必胜策略？假设对方先走，我方是否有必胜策略？例例2 分钱币问题分钱币问题1/7/202310（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）对方先走对方先走我方胜我方胜对方胜对方胜对方胜对方胜分钱币问题的搏弈图分钱币问题的搏弈图1/7/202311结论结论评价评价

7、1/7/2023121.还有哪些类似的问题可以使用状态空间来还有哪些类似的问题可以使用状态空间来描述？描述？比如，井字棋、五子棋、拾火柴等比如，井字棋、五子棋、拾火柴等游戏。画出井字棋问题的状态空间树。游戏。画出井字棋问题的状态空间树。2.过河问题如何使用状态空间法表示？过河问题如何使用状态空间法表示？3.画出过河问题的状态空间图。画出过河问题的状态空间图。思考与练习思考与练习1/7/202313井字棋井字棋游戏井字棋游戏1/7/202314五子棋游戏五子棋游戏1/7/202315 假假定定盘盘中中放放有有n根根火火柴柴，由由弈弈者者A和和B两两人人参参加加比比赛赛。比比赛赛的的规规则则是是：

8、两两名名弈弈者者轮轮流流从从盘盘中中取取走走火火柴柴，每每次次从从盘盘中中取取走走1，2或或3根根火火柴柴均均为为合合法法着着，否否则则为为非非法法着着。拿拿走走盘盘中中最最后后一一根根火火柴柴的的弈弈者者为为输输。假假定定A方方先先走走，A有有必必胜胜策策略略吗？若有就找出吗？若有就找出A的必胜策略。的必胜策略。拾火柴游戏拾火柴游戏1/7/202316搜索技术搜索技术案例案例21/7/202317目标目标 学会用几种搜索技术求解重排九宫问题 体验几种搜索技术的基本思想1/7/202318盲目搜索盲目搜索状态空间树（图）上的搜索策略状态空间树（图）上的搜索策略启发式搜索启发式搜索宽度优先搜索宽

9、度优先搜索深度优先搜索深度优先搜索1/7/202319求解思路：求解思路：1.先将问题的求解过程用状态空间树表示出来先将问题的求解过程用状态空间树表示出来2.在状态空间树上搜索问题的解答在状态空间树上搜索问题的解答要求：用尽可能少棋步能由初始状态到达目标状态。要求：用尽可能少棋步能由初始状态到达目标状态。例例1 重排九宫问题重排九宫问题28 3 16 427 5初始状态初始状态1 2 3 8 47 6 5目标状态目标状态1/7/2023202 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

10、 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 41 8 7 6 52 8 3 1 47 6 52 81 4 37 6 52 8 3 1 67 5

11、 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目标状态目标状态初始状态初始状态深度优先搜索深度优先搜索1/7/2023212 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

12、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 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

13、67 4目标状态目标状态初始状态初始状态宽度优先搜索宽度优先搜索1/7/202322启发式函数启发式函数:f(X)=g(X)+h(X)Xg(X)h(X)启发式搜索启发式搜索1/7/2023232 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+4

14、3+2 3+44+1启发函数：启发函数：f(X)=g(X)+h(X)目标目标1/7/2023242 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)1/7/202325 假设有假设有7个钱币，任一选手只能将已分个钱币，任一选手只能将已分好的一堆钱币分成两堆

15、个数不等的钱币，好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。不能分的情况，则就为输。假设对方先走，我方是否有必胜策略假设对方先走，我方是否有必胜策略？例例2 分钱币问题分钱币问题1/7/202326分钱币问题的搏弈图分钱币问题的搏弈图（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

16、,1,1）对方先走对方先走我方必胜我方必胜00011010011111MinMaxMinMaxMin1/7/202327机器搏弈机器搏弈存在问题：存在问题：一盘棋平均走一盘棋平均走50步，总状态数约为步，总状态数约为10的的161次方。假设次方。假设1毫微秒走一步，约需毫微秒走一步，约需10的的145次方年。因此，不可能将所有情次方年。因此，不可能将所有情况列尽，即不能穷举走象棋的整个状态况列尽，即不能穷举走象棋的整个状态空间树（搏弈树）。空间树（搏弈树）。1/7/202328机器搏弈机器搏弈解决办法：解决办法：模拟人模拟人“向前看几步向前看几步”，然后作出决，然后作出决策，决定自己走哪一步最

17、有利。也就是策，决定自己走哪一步最有利。也就是说，只能考虑状态空间树的几层（即向说，只能考虑状态空间树的几层（即向前看几步），然后按照一定的估算方法，前看几步），然后按照一定的估算方法，决定走哪一步棋。这就是决定走哪一步棋。这就是极大极小化方极大极小化方法法。所得到的搜索方法是一种启发式搜。所得到的搜索方法是一种启发式搜索方法。索方法。1/7/202329结论结论评价评价1/7/2023301.启发式知识从何而来？启发式知识从何而来？2.求解重排九宫问题还可挖掘什么启发式知识求解重排九宫问题还可挖掘什么启发式知识？3.在井字棋、五子棋等游戏中如何挖掘启发式在井字棋、五子棋等游戏中如何挖掘启发式知识？知识？思考与练习思考与练习井字棋应该放在哪应该放在哪？1/7/202331