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

人工智能初步

教学案例11/27/20221人工智能初步

教学案例11/27/20221状态空间表示法案例111/27/20222状态空间表示法案例111/27/20222目标学会用状态空间法表示重排九宫问题了解状态空间法的相关概念、基本思想11/27/20223目标11/27/20223程序算法问题使用计算求解问题的思路分析建模程序设计11/27/20224程序算法问题使用计算求解问题的思路分析建模程序设计11/27要求：用尽可能少棋步能由初始状态到达目标状态。例1[重排九宫问题]83647■5初始状态123■84765目标状态11/27/20225要求：用尽可能少棋步能由初始状态到达目标状态。例1[重排2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态11/27/202262832832832状态

表示问题求解过程中每一步问题状况的数据结构。例如，在棋弈中的格局即为问题的状态。操作

把问题从一种状态变换为另外一种状态的手段。例如，棋弈中一步“走子”可将一个格局变为另一种格局。状态空间表示法11/27/20227状态状态空间表示法11/27/20227状态空间

用来描述一个问题的全部状态以及这些状态之间的相互关系。包含三个部分：S—问题的初始状态集合F—操作集合G—目标状态的集合状态空间树（图）

可用一个图（树）来直观地表示出状态空间。11/27/20228状态空间11/27/20228状态空间表示法的基本思想

用“状态”和“操作”来表示问题及其变化，形成状态空间，求解问题的过程就是在状态空间树中搜索表示解的状态的过程。搜索时，从某个初始状态出发，每次使用一个操作使得问题能够从一种状态变为另外一种状态，直到到达目标状态为止。11/27/20229状态空间表示法的基本思想11/27/20229

假设有7个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。假设对方先走，我方是否有必胜策略？[例2]分钱币问题11/27/202210假设有7个钱币，任一选手只能将已分好的一堆钱（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）对方先走我方胜对方胜对方胜分钱币问题的搏弈图11/27/202211（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,◆结论◆评价11/27/202212◆结论11/27/2022121.还有哪些类似的问题可以使用状态空间来描述？比如，井字棋、五子棋、拾火柴等游戏。画出井字棋问题的状态空间树。过河问题如何使用状态空间法表示？画出过河问题的状态空间图。思考与练习11/27/2022131.还有哪些类似的问题可以使用状态空间来描述？比如，井字棋井字棋游戏11/27/202214井字棋井字棋游戏11/27/202214五子棋游戏……11/27/202215五子棋游戏……11/27/202215

假定盘中放有n根火柴，由弈者A和B两人参加比赛。比赛的规则是：两名弈者轮流从盘中取走火柴，每次从盘中取走1，2或3根火柴均为合法着，否则为非法着。拿走盘中最后一根火柴的弈者为输。假定A方先走，A有必胜策略吗？若有就找出A的必胜策略。拾火柴游戏11/27/202216假定盘中放有n根火柴，由弈者A和B两人参加搜索技术案例211/27/202217搜索技术案例211/27/202217目标学会用几种搜索技术求解重排九宫问题体验几种搜索技术的基本思想11/27/202218目标11/27/202218盲目搜索状态空间树（图）上的搜索策略启发式搜索宽度优先搜索深度优先搜索11/27/202219盲目搜索状态空间树（图）上的搜索策略启发式搜索宽度优先搜索深求解思路：1.先将问题的求解过程用状态空间树表示出来2.在状态空间树上搜索问题的解答要求：用尽可能少棋步能由初始状态到达目标状态。例1[重排九宫问题]83647■5初始状态123■84765目标状态11/27/202220求解思路：要求：用尽可能少棋步能由初始状态到达目标状态。例12831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态深度优先搜索11/27/20222128328328322831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态宽度优先搜索11/27/2022222832832832启发式函数:f(X)=g(X)+h(X)Xg(X)h(X)启发式搜索11/27/202223启发式函数:Xg(X)h(X)启发式搜索11/27/20222831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■65■2318476523■184765123■847650+41+51+31+52+32+32+43+33+43+23+44+1启发函数：

f(X)=g(X)+h(X)

目标11/27/20222428328322831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■6545353343

4到目标到无结果的漫游8■32147653

启发函数：

f(X)=h(X)

11/27/2022252832832

假设有7个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。假设对方先走，我方是否有必胜策略？[例2]分钱币问题11/27/202226假设有7个钱币，任一选手只能将已分好的一堆钱分钱币问题的搏弈图（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）对方先走我方必胜00011010011111MinMaxMinMaxMin11/27/202227分钱币问题的搏弈图（7）（6,1）（5,2）（4,3）（5,机器搏弈存在问题：一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。因此，不可能将所有情况列尽，即不能穷举走象棋的整个状态空间树（搏弈树）。11/27/202228机器搏弈存在问题：11/27/202228机器搏弈解决办法：模拟人“向前看几步”，然后作出决策，决定自己走哪一步最有利。也就是说，只能考虑状态空间树的几层（即向前看几步），然后按照一定的估算方法，决定走哪一步棋。这就是极大极小化方法。所得到的搜索方法是一种启发式搜索方法。11/27/202229机器搏弈解决办法：11/27/202229◆结论◆评价11/27/202230◆结论11/27/2022301.启发式知识从何而来？2.求解重排九宫问题还可挖掘什么启发式知识？3.在井字棋、五子棋等游戏中如何挖掘启发式知识？思考与练习井字棋应该放在哪？11/27/2022311.启发式知识从何而来？思考与练习井字棋应该放在哪？11/2人工智能初步

教学案例11/27/202232人工智能初步

教学案例11/27/20221状态空间表示法案例111/27/202233状态空间表示法案例111/27/20222目标学会用状态空间法表示重排九宫问题了解状态空间法的相关概念、基本思想11/27/202234目标11/27/20223程序算法问题使用计算求解问题的思路分析建模程序设计11/27/202235程序算法问题使用计算求解问题的思路分析建模程序设计11/27要求：用尽可能少棋步能由初始状态到达目标状态。例1[重排九宫问题]83647■5初始状态123■84765目标状态11/27/202236要求：用尽可能少棋步能由初始状态到达目标状态。例1[重排2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态11/27/2022372832832832状态

表示问题求解过程中每一步问题状况的数据结构。例如，在棋弈中的格局即为问题的状态。操作

把问题从一种状态变换为另外一种状态的手段。例如，棋弈中一步“走子”可将一个格局变为另一种格局。状态空间表示法11/27/202238状态状态空间表示法11/27/20227状态空间

用来描述一个问题的全部状态以及这些状态之间的相互关系。包含三个部分：S—问题的初始状态集合F—操作集合G—目标状态的集合状态空间树（图）

可用一个图（树）来直观地表示出状态空间。11/27/202239状态空间11/27/20228状态空间表示法的基本思想

用“状态”和“操作”来表示问题及其变化，形成状态空间，求解问题的过程就是在状态空间树中搜索表示解的状态的过程。搜索时，从某个初始状态出发，每次使用一个操作使得问题能够从一种状态变为另外一种状态，直到到达目标状态为止。11/27/202240状态空间表示法的基本思想11/27/20229

假设有7个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个遇到不能分的情况，则就为输。假设对方先走，我方是否有必胜策略？[例2]分钱币问题11/27/202241假设有7个钱币，任一选手只能将已分好的一堆钱（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）对方先走我方胜对方胜对方胜分钱币问题的搏弈图11/27/202242（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,◆结论◆评价11/27/202243◆结论11/27/2022121.还有哪些类似的问题可以使用状态空间来描述？比如，井字棋、五子棋、拾火柴等游戏。画出井字棋问题的状态空间树。过河问题如何使用状态空间法表示？画出过河问题的状态空间图。思考与练习11/27/2022441.还有哪些类似的问题可以使用状态空间来描述？比如，井字棋井字棋游戏11/27/202245井字棋井字棋游戏11/27/202214五子棋游戏……11/27/202246五子棋游戏……11/27/202215

假定盘中放有n根火柴，由弈者A和B两人参加比赛。比赛的规则是：两名弈者轮流从盘中取走火柴，每次从盘中取走1，2或3根火柴均为合法着，否则为非法着。拿走盘中最后一根火柴的弈者为输。假定A方先走，A有必胜策略吗？若有就找出A的必胜策略。拾火柴游戏11/27/202247假定盘中放有n根火柴，由弈者A和B两人参加搜索技术案例211/27/202248搜索技术案例211/27/202217目标学会用几种搜索技术求解重排九宫问题体验几种搜索技术的基本思想11/27/202249目标11/27/202218盲目搜索状态空间树（图）上的搜索策略启发式搜索宽度优先搜索深度优先搜索11/27/202250盲目搜索状态空间树（图）上的搜索策略启发式搜索宽度优先搜索深求解思路：1.先将问题的求解过程用状态空间树表示出来2.在状态空间树上搜索问题的解答要求：用尽可能少棋步能由初始状态到达目标状态。例1[重排九宫问题]83647■5初始状态123■84765目标状态11/27/202251求解思路：要求：用尽可能少棋步能由初始状态到达目标状态。例12831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态深度优先搜索11/27/20225228328328322831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态宽度优先搜索11/27/2022532832832832启发式函数:f(X)=g(X)+h(X)Xg(X)h(X)启发式搜索11/27/202254启发式函数:Xg(X)h(X)启发式搜索11/27/20222831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■65■2318476523■184765123■