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

人工智能初步

教学案例2023/12/102状态空间表示法案例12023/12/103目标

学会用状态空间法表示重排九宫问题

了解状态空间法的相关概念、基本思想2023/12/104程序算法问题使用计算求解问题的思路分析建模程序设计2023/12/105要求：用尽可能少棋步能由初始状态到达目标状态。例1[重排九宫问题]83647■5初始状态123■84765目标状态2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态2023/12/107状态

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

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

用来描述一个问题的全部状态以及这些状态之间的相互关系。包含三个部分：

S—问题的初始状态集合

F—操作集合

G—目标状态的集合状态空间树（图）

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

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

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

假定盘中放有n根火柴，由弈者A和B两人参加比赛。比赛的规则是：两名弈者轮流从盘中取走火柴，每次从盘中取走1，2或3根火柴均为合法着，否则为非法着。拿走盘中最后一根火柴的弈者为输。假定A方先走，A有必胜策略吗？若有就找出A的必胜策略。拾火柴游戏2023/12/1017搜索技术案例22023/12/1018目标

学会用几种搜索技术求解重排九宫问题

体验几种搜索技术的基本思想2023/12/1019盲目搜索状态空间树（图）上的搜索策略启发式搜索宽度优先搜索深度优先搜索2023/12/1020求解思路：1.先将问题的求解过程用状态空间树表示出来2.在状态空间树上搜索问题的解答要求：用尽可能少棋步能由初始状态到达目标状态。例1[重排九宫问题]83647■5初始状态123■84765目标状态2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态深度优先搜索2831647528314765283164752831647528364175283147652318476528314765283167548326417528364175832147652837146523184765231847652831476528143765283167542816375483264175236841758321476528371465123847652341876528314765281437652831675428163754283641752836741523184765283164752318675428315674目标状态初始状态宽度优先搜索2023/12/1023启发式函数:f(X)=g(X)+h(X)Xg(X)h(X)启发式搜索2831647■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)

目标2831647■5283164■752831■476528316475■283■147652■318476528314■765■83214765283714■6545353343

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

启发函数：

f(X)=h(X)

2023/12/1026

假设有7个钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱