华容道算法设计课程设计

《华容道算法设计课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、华容道游戏课程设计1课程设计目的与要求现如今网络游戏日益繁荣，很多家长担心孩子会沉迷于网络中无法自拔，影响学业，而这款华容道游戏不仅可以使学生在玩的过程中体会到积极动脑的乐趣而且还会使他们热衷于思考，在游戏通关的成功中体会到满足感，提升学习的自信心。所以我选择开发一款华容道的小游戏来丰富学生的课外生活，同时也锻炼他们的智力水平。1.1游戏介绍。华容道，古老的中国游戏，以其变化多端、百玩不厌的特点与魔方、独立钻石棋一起被国外智力专家并称为“智力游戏界的三个不可思议”。游戏就是依照“曹瞒兵败走华容，正与关公狭路逢，只为当初恩义重，放开金

2、锁走蛟龙”这一故事情节设计，受到很多玩家的喜爱。1.2课程设计目的通过设计、编写、调试一个华容道游戏程序，在过程中，熟练掌握了对MicrosoftVisualC++6.0的应用，掌握用MFC设计界面，同时，加深对C++语言语法的理解，并实现对该语言中命令的灵活应用，掌握了C++中类的使用。此外，程序中用到了广度优先搜索算法，通过学习该算法，在搜索的过程中利用这些已有的结果，可以大大缩短解空间的个数和解题时间。1.3课程设计任务就华容道来说，需要解决一些问题。1）搜索的解空间比较巨大，如何存储和编码棋盘棋局2）使用MFC设计界面，该界

3、面的布局为华容道中“横刀立马”这一关。3）玩家71.4课程设计实验环境MicrosoftVisualC++6.02问题描述及讨论程序设计中，需要解决很多问题，除了编写程序过程中的问题，更重要的是算法设计过程中的问题。2.1问题描述在3x3的九宫格棋盘上，摆有8个将牌，每个将牌都刻有1—8中的某个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改编将牌的布局。这种游戏求解的问题是：给定一种初始的奖牌布局或结构和一个目标布局，问如何移动将牌，实现从初始状态到目标状态的转变。而且，并不是所有初始状态到

4、目标状态之间都存在解，如何判断解的存在与否。2.2解存在性的讨论首先，将8数码游戏的某一种状态按行合并，排成一行，共9个数，其中，空格用0表示。这样，8数码游戏的每一种状态都对应于一行数字。对任意一对数字，如果前面的数字比后面的数大，则为一对逆序。对于一个序列，如果其中有奇数对逆序，则称之为逆序奇；如果其中有偶数对逆序，则称之为逆序偶。这样，对于1—n这n个数，所有的排序可以分为两类，逆序奇和逆序偶。相应的，8数码问题中的每一种状态（出去空格）也有它的奇偶性，称之为奇九宫图和偶九宫图，并有如下结论：所有的奇九宫图之间是可达的，所有的

5、偶九宫图之间也是可达的，但是奇九宫图和偶九宫图之间互不可达。根据此结论即可判断初始状态和目标状态之间是否可达。2.3最优解的搜索由初始状态到达目标状态有多种走步方法，我们的目标是选择一条所走步数最少的路径，即最优解。根据所求得的最优解走步，尽快达到目标状态。本游戏中主要用启发式搜索算法中的A*算法来解决路径的搜索，而该算法的关键就是选取合适的启发函数。3.核心算法本程序的问题之一就是求最优路径，找最小的步数以尽快从初始状态到达目标状态，本设计中主要采用了A*算法来寻找最优解。73.1启发式搜索算法介绍启发式搜索是利用问题拥有的启发式

6、信息引导搜索，以达到减小搜索范围，降低问题复杂度的目的。这种利用启发信息的搜索过程称为启发式搜索。一般情况下，启发信息过弱，产生式系统在找到一条路径之前将扩展过多的节点，即求得解路径所需搜索的工作量较大；反之，引入强的启发信息，则有可能大大降低搜索工作量，但不能保证找到最佳路径。因此，实际应用中希望最好能引入降低搜索工作量的启发信息而不牺牲找到最佳路径的保证。在大多数实际问题中，人们感兴趣的是使路径的耗散值和求得路径所需搜索的耗散值两者的某种组合最小，更一般的情况是考虑搜索算法对求解所有可能遇见的问题，其平均的组合耗散值最小。实际上

7、，很难给出一个计算平均组合耗散值的方法，因此，启发能力的度量也只能根据实际经验判断，没有必要去追求严格的比较结果。启发式搜索过程中，要对OPEN表进行排序，这就需要有一种方法来计算得拓展节点有希望通过目标节点的不同程度，我们总是希望能找到最有可能同通向目标节点的待拓展节点优先拓展。一种最常用的方法是定义一个评价函数对各个节点进行计算，其目的就是用来估算出“有希望”的节点，如何定义一个评价函数呢？通常可以参考的原则有：一个节点处在最佳路径下的概率：求出任意一个节点与目标节点集之间的距离度量或差异度量：根据格局（博弈问题）或状态的特点来

8、打分，即根据问题的启发信息，从概率角度、差异角度或计分方法给出计算评价函数的方法。3.2A*算法在介绍A*算法之前，先介绍A算法。同宽度优先搜索和深度优先搜索，OPEN表用来存储待扩展的节点，CLOSED表登录已扩展节点。利用评价函数