高中信息技术人工智能教学案例5年课件选修

1、高中信息技术人工智能教学案例5 年课件选修 人工智能初步人工智能初步 教学案例教学案例 2021-7-11高中信息技术人工智能教学案例5 年课件选修 2 状态空间表示法状态空间表示法 案例案例1 1 2021-7-11高中信息技术人工智能教学案例5 年课件选修 3 目标目标 学会用状态空间法表示重排九宫问题 了解状态空间法的相关概念、基本思想 2021-7-11高中信息技术人工智能教学案例5 年课件选修 4 程序程序算法算法问题问题 使用计算求解问题的思路使用计算求解问题的思路 分析建模分析建模 程序设计程序设计 2021-7-11高中信息技术人工智能教学案例5 年课件选修 5 要求：用尽可能

2、少棋步能由初始状态到达目标状态。要求：用尽可能少棋步能由初始状态到达目标状态。 例例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

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

4、 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 目标状态目标状态 初始状态初始状态 2021-7-11高中信息技术人工智能教学案例5 年课件选修 7 状态状态 表示问题求解过程中每一步问题状况的数据结构。表示问题求解过程中每一步问题状况的数据结构。 例如，例如， 在棋弈中的格局即为问题的状态。在棋弈中的格局即为问题的状态。 操作操作 把问题从一种状态变换为另外一种状态的手段。把问题从一种状态变换为另外一种状态的手段。 例如，棋弈中一步例如，棋弈中一步“走子走子”可将一个格局变为另一种格可将一个格局变为另一种格 局。局

5、。 状态空间表示法状态空间表示法 2021-7-11高中信息技术人工智能教学案例5 年课件选修 8 状态空间状态空间 用来描述一个问题的全部状态以及这些状态之间的相互用来描述一个问题的全部状态以及这些状态之间的相互 关系。包含三个部分：关系。包含三个部分： S问题的初始状态集合问题的初始状态集合 F操作集合操作集合 G目标状态的集合目标状态的集合 状态空间树（图）状态空间树（图） 可用一个图（树）来直观地表示出状态空间。可用一个图（树）来直观地表示出状态空间。 2021-7-11高中信息技术人工智能教学案例5 年课件选修 9 状态空间表示法的基本思想状态空间表示法的基本思想 用用“状态状态”和

6、和“操作操作”来表示问题及其变化，形成状态来表示问题及其变化，形成状态 空间，求解问题的过程就是在状态空间树中搜索表示解的状空间，求解问题的过程就是在状态空间树中搜索表示解的状 态的过程。态的过程。 搜索时，从某个初始状态出发，每次使用一个操作使得搜索时，从某个初始状态出发，每次使用一个操作使得 问题能够从一种状态变为另外一种状态，直到到达目标状态问题能够从一种状态变为另外一种状态，直到到达目标状态 为止。为止。 2021-7-11高中信息技术人工智能教学案例5 年课件选修 10 假设有假设有7个钱币，任一选手只能将已分个钱币，任一选手只能将已分 好的一堆钱币分成两堆个数不等的钱币，好的一堆钱

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

8、方胜 对方胜对方胜 分钱币问题的搏弈图分钱币问题的搏弈图 2021-7-11高中信息技术人工智能教学案例5 年课件选修 12 结论结论 评价评价 2021-7-11高中信息技术人工智能教学案例5 年课件选修 13 1. 还有哪些类似的问题可以使用状态空间来还有哪些类似的问题可以使用状态空间来 描述？描述？ 比如，井字棋、五子棋、拾火柴等比如，井字棋、五子棋、拾火柴等 游戏。画出井字棋问题的状态空间树。游戏。画出井字棋问题的状态空间树。 过河问题如何使用状态空间法表示？过河问题如何使用状态空间法表示？ 画出过河问题的状态空间图。画出过河问题的状态空间图。 思考与练习思考与练习 井字棋 井字棋游戏

9、井字棋游戏 五子棋游戏五子棋游戏 2021-7-11高中信息技术人工智能教学案例5 年课件选修 16 假定盘中放有假定盘中放有n根火柴，由弈者根火柴，由弈者A和和B两人两人 参加比赛。比赛的规则是：两名弈者轮流从盘参加比赛。比赛的规则是：两名弈者轮流从盘 中取走火柴，每次从盘中取走中取走火柴，每次从盘中取走1，2或或3根火柴均根火柴均 为合法着，否则为非法着。拿走盘中最后一根为合法着，否则为非法着。拿走盘中最后一根 火柴的弈者为输。假定火柴的弈者为输。假定A方先走，方先走，A有必胜策略有必胜策略 吗？若有就找出吗？若有就找出A的必胜策略。的必胜策略。 拾火柴游戏拾火柴游戏 2021-7-11高

10、中信息技术人工智能教学案例5 年课件选修 17 搜索技术搜索技术 案例案例2 2021-7-11高中信息技术人工智能教学案例5 年课件选修 18 目标目标 学会用几种搜索技术求解重排九宫问题 体验几种搜索技术的基本思想 2021-7-11高中信息技术人工智能教学案例5 年课件选修 19 盲目搜索盲目搜索 状态空间树（图）上的搜索策略状态空间树（图）上的搜索策略 启发式搜索启发式搜索 宽度优先搜索宽度优先搜索 深度优先搜索深度优先搜索 2021-7-11高中信息技术人工智能教学案例5 年课件选修 20 求解思路：求解思路： 1. 先将问题的求解过程用状态空间树表示出来先将问题的求解过程用状态空间

11、树表示出来 2. 在状态空间树上搜索问题的解答在状态空间树上搜索问题的解答 要求：用尽可能少棋步能由初始状态到达目标状态。要求：用尽可能少棋步能由初始状态到达目标状态。 例例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

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

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

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

15、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 目标状态目标状态 初始状态初始状态宽度优先搜索宽度优先搜索 2021-7-11高中信息技术人工智能教学案例5 年课件选修 23 启发式函数启发式函数: f(X)= g(X) + h(X) X g(X) h(X) 启发式搜索启发式搜索 2 8 3 1 6 4 7 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 4 7 6 5 2 3 1

16、 8 4 7 6 5 2 8 3 1 4 7 6 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 1 2 3 8 4 7 6 5 0+4 1+51+31+5 2+32+3 2+4 3+3 3+43+2 3+4 4+1 启发函数：启发函数： f(X) = g(X)+h(X) 目标目标 2 8 3 1 6 4 7 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 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 8 3

17、2 1 4 7 6 5 2 8 3 7 1 4 6 5 4 535 33 4 3 4 到目标到目标 到无结果的漫游到无结果的漫游 8 3 2 1 4 7 6 5 3 启发函数：启发函数： f(X) = h(X) 2021-7-11高中信息技术人工智能教学案例5 年课件选修 26 假设有假设有7个钱币，任一选手只能将已分个钱币，任一选手只能将已分 好的一堆钱币分成两堆个数不等的钱币，好的一堆钱币分成两堆个数不等的钱币， 两位选手轮流进行，直到每一堆都只有一两位选手轮流进行，直到每一堆都只有一 个或两个钱币，不能再分为止，哪个遇到个或两个钱币，不能再分为止，哪个遇到 不能分的情况，则就为输。不能分

18、的情况，则就为输。 假设对方先走，我方是否有必胜策略？假设对方先走，我方是否有必胜策略？ 例例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） 对方先走对方先走 我方必胜我方必胜 0 0 0 1 1 01 0 01 111 1 Min Max Min Max Min 2021-7-11高中信息技术人工智能教学案例5 年课件选修 28 机器搏弈机器搏弈 存在问题：存在问题： 一盘棋平均走一盘棋平均走50步，总状态数约为步，总状态数约为10 的的161次方。假设次方。假设1毫微秒走一步，约需毫微秒走一步，约需 10的的145次方年。因此，不可能将所有情次方年。因此，不可能将所有情 况列尽，即不能穷举走象棋的整个状态况列尽，即不能穷举走象棋的整个状态 空间树（搏弈树）。空间树（搏弈树）。 2021-7-11高中信息技术人工智能教学