使用visual studio c# 2008编程实现八数码游戏

《使用visual studio c# 2008编程实现八数码游戏》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于VisualStudioC#2008的八数码游戏的设计与实现龙之梦1引言搜索是人工智能中的一个基本问题，也是模拟仿真中研究的一般性问题，是推理不可分割的一部分。现实世界中的大多数问题都是结构不良或非结构化的问题，一般不存在现成的求解方法，而只能利用已有的知识一步步地摸索着前进，如梵塔问题、MC问题、猴子摘香蕉、八数码难题等。八数码难题一般描述：在3×3的方格棋盘上，分别放置标有数字1、2、3、4、5、6、7、8的八张牌，第九张牌不标数字，记为空格，给定一种初始状态和目标状态，通过移动空格，使得棋盘从初始状态向目标状态转换（其中操作空格可用的操

2、作有：左移、上移、右移、下移，但不能移出棋盘之外），通过搜索策略寻找从初始状态到目标状态的解路径。解决八数码问题的搜索策略有很多，归纳起来主要有三种：深度优先搜索（DepthFirstSearch，DFS）、宽度优先搜索（BreadthFirstSearch，BFS）、A*算法。前两种是经典的盲目搜索算法，后一种是经典的启发式搜索算法。对于八数码问题，深度优先搜索一般不能保证得到最优解，A*算法又与其启发式函数息息相关，也无法保证得到最优解。而宽度优先搜索算法可以得到从初始状态到目标状态的最短解路径。虽然宽度搜索算法效率相对较低，搜索点数较多，但

3、考虑到计算机技术的飞速发展，运算速度已经不是影响搜索效率的重要瓶颈了。因此，展开宽度优先搜索算法的研究，不但对解决八数码难题有着实际的意义，而且对解决人工智能中的其它问题，也可以起到积极的参考作用。2宽度优先搜索算法2.1算法一般描述宽度优先搜索是—种先生成的节点先扩展的搜索策略，其一般过程是：从初始状态节点开始逐层向下扩展，在第N层节点还没有全部搜索结束之前，不进人第N+1层节点的搜索。设TreeNodes表中的节点是根据生成的先后进行排序的，先进人TreeNodes表中的节点排在前面，后进入TreeNodes表的节点排后面，则算法可以进行一般

4、描述：(1)把初始节点StartState放入TreeNodes表中，作为当前节点；(2)如果TreeNodes表中当前节点指向为空，则问题无解，失败退出；(3)把TreeNodes表的当前节点取出，并记该节点为CurrentState；(4)检查当前节点CurrentState是否为目标节点。若是，则得到问题的解，成功退出；否则进行第（5）步；(5)若节点CurrentState无法扩展，设定TreeNodes的下一个节点为当前节点，转第(2)步；(6)对当前节点CurrentState进行扩展，将其子节点存放入TreeNodes表的尾部，并为

5、每一个子节点设置指向父节点CurrentState的指针，然后设定TreeNodes的下一个节点为当前节点，转第(2)步。2.2针对八数码问题的宽度优先搜索算法分析对于求解八数码问题，首先要给出一个起始状态和结束状态，如图1所示。那么，宽度优先搜索算法的目标就是寻找一条从起始状态到结束状态的解路径。图1八数码问题的起始状态和结束状态根据算法的一般描述，首先把起始状态加入到TreeNodes表中，作为根节点0。然后，把0节点取出，和结束状态比较，如图1来看，明显不是目标节点。所以对节点0进行扩展，根据空格上下左右移动，得到四个子节点，即节点1、2、

6、3、4，并加入到TreeNodes表的尾部。再取出节点1作为当前节点，也不是目标节点，对其进行子节点扩展，得到2个节点，即节点5、6，并加入到TreeNodes表的尾部。然后，取出节点2作为当前节点，以此类推，进行下去，整个搜索节点过程，如图2所示。图2八数码问题宽度优先搜索过程图2给出了搜索到节点12时，整个TreeNodes表的节点情况。然后继续搜索节点13，根据算法过程，直到发现目标节点结束。这样的搜索过程，就是宽度优先搜索算法。最坏情况下，该算法将搜索整个状态空间，即搜索9!/2=181440个节点。但从图2可以看出，只要从根节点到目标节

7、点构建一个路径，则该路径一定是最短的一条解路径。3八数码问题的VS2008实现3.1编程环境简介我们的软件实验开发软件选用了VisualStudio2008，它是基于.NET框架的软件开发平台，.NET开发环境是流行的基于Windows平台的编程平台。VisualStudio2008可以为项目指定.NETFramework的版本：.NETFramework2.0、3.0或3.5。应用程序的.NETFramework目标是指为使该应用程序能够在计算机上运行而需要在该计算机上安装的.NETFramework版本。VisualStudio2008中的C

8、#代码编辑器提供了语句结束和快速信息功能，以支持C#3.0中的下列新语言构造：n隐式类型的局部变量n查询表达式n扩展方法n对象/集合初始