搜索
1安徽工程大学信息10课程设计马踏棋盘的求解及演示设计摘要数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。《数据结构》课程设计是计算机科学技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。开设本课程设计实践的主要目的就是要达到理论与实际应用相结合，提高学生的动手能力，完成计算机应用能力的培养；本课程设计主要解决马踏棋盘的问题，找出踏遍棋盘的多种路径，并实现动态要是过程。马踏棋盘问题，实际上是图论中的哈密顿通路问题，是典型的NP问题,求解的问题与算法设计有很大关系，如果采取穷举搜索的话，很容易陷入海量搜索的状态，耗费巨大的时间，使问题几乎不可解，因此马在棋盘上遍历采用算法当中的深度优先算法和启发式贪心算法，用栈来存储遍历过程，通过对栈的使用实现对所有路径的搜索。在调试过程发现，启发式贪心算法，针对于马踏棋盘问题有着极大的好处，就是无论从棋盘上哪个点开始，找到一条遍历完棋盘的通路是不需要回溯的，也就节省了大量的时间，而试探性的操作对于每个点都也只有168步，所以求出所有路径在不到一秒的时间内完成。关键词：马踏棋盘；骑士周游；哈密顿通路;NP-完全问题；贪心算法；回溯法；2目录马踏棋盘的求解及演示设计..........................................1目录............................................................2第一章引言..................................................3第二章需求分析..................................................42.1问题描述........................................................42.2基本要求........................................................42.3具体需求........................................................42.4开发环境........................................................4第三章概要设计..................................................53.1系统概述........................................................53.2系统描述........................................................63.3逻辑设计........................................................6第四章详细设计..................................................74.1功能模块设计...................................................74.2数据结构设计...................................................74.3算法设计........................................................9第五章调试与分析...............................................135.1调试分析.......................................................13第六章系统试用说明.............................................146.1系统试用说明...................................................14第七章总结与体会...............................................14参考文献.........................................................153第一章引言本课程设计主要研究马踏棋盘的问题，即骑士周游问题，是将马随机放在国际象棋的8×8棋盘的某个方格中,“马”按照走棋规则进行移动，要求每个方格只进入一次,走遍棋盘上全部64个方格。许多知名的数学家，如德莫弗(DeMoivre)、欧拉(Euler)与范德蒙德(Vandermonde)等人，在过去的200年中都研究过这个问题，今天从数据结构的角度，解决这一问题。力求以最快的速度，即最高的效率来解决问题。已知穷举法是几乎不可能完成的，而与解决迷宫问题的回溯法，也要占用大量的时间，这里采用贪心算法来解决这一问题，并找出多有的遍历路径。4第二章需求分析2.1问题描述马随机放在国际象棋的8×8棋盘的某个方格中,“马”按照走棋规则进行移动，要求每个方格只进入一次,走遍棋盘上全部64个方格。设计一个国际象棋的马踏遍棋盘的演示程序。2.2基本要求设计合适的数据结构，编制递归以及非递归程序,求出马的行走路线,并按求出的马的行走路线,将路线1,2,…,64依次填入一个8×8的方阵,输出之，若有多种走法，则能将全部的输出。必须要能够将踏遍棋盘的过程显示在计算机屏幕上。要求：（1）描述设计所涉及的数据模型，设计高效的数据结构完成总体设计，搭好框架，确定人机对话的界面（要求界面上能动态体现出演示的过程），实现功能；（2）界面友好，函数功能要划分好（3）要有算法设计的流程图（4）程序要加必要的注释（5）要提供程序测试方案2.3具体需求1、首先要找到马踏棋盘棋盘的多条路径。2、实现马踏棋盘的动态演示过程。3、优化算法，提高算法效率，以递归与非递归的方式实现2.4开发环境开发环境：Windows8辅助工具：VisualStudio2012,MyEclipse10.55运行环境：WindowsXP/Vista/7/8第三章概要设计3.1系统概述3.11系统流程图3.12主函数main()的执行流程求解多条路径子系统：自动演示路径子系统NY马踏棋盘演示系统求解多条路径自动演示路径开始输入起始点判断合法性6NY3.2系统描述通过VS2012完成的寻找多条路径的子系统，通过java来实现马踏棋盘的动态演示子系统。在寻找多条路径的子系统中，通过启发式贪心算法，将某点的下一步最少通往其它落脚点，将该点确定为最佳落点。每次只走下一步通向其他点最少的点。用栈记录探寻的过程，将走过的点标记为1，试探而没有走的点标记为0.最后通过寻找出栈标志为0的点来寻找其他路径。在动态显示模块式通过java的线程机制是先的自动动画演示。3.3逻辑设计抽象数据类型棋盘上某点的位置坐标结构体Postion把个方向试探的增量位置数组direct[8]棋盘某点通向其他点的可到达数的二位数组access[8][8]链栈用来记录可到达下一位置坐标的数组：nextPath[8];用来记录整个遍历过程的数组：tourpos[64];遍历(找出一条路径)tour(Postion)打印找到的路径fprint()寻找其他路径other_Path（Postion）打印全部路径结束开始寻找下一步next_Path(Postion)//开始移动domoving(Postion);//尝试下一步的移动extAccessible();While(hasMorePath())递归调用tour(nextPath[arrayPos]);结束7第四章详细设计4.1功能模块设计4.1.2创建模块本模块创建棋盘，以及棋盘上每一点的可到达数，一个向8个方向试探的增量数组。以及记录整个遍历流程的链栈。选择或设计数据结构的存储结构，实现存储结构的基本运算、设计的模块构成、各模块的简要说明、流程图、调用关系表等。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4.1.3操作模块实现对棋盘的周游，并找到多条路径4.1.4显示模块将找到的所有路径显示在屏幕上，并统计找到的路径数。4.1.5自动演示模块通过Java的Applet和线程机制，实现对找到的路径进行动态演示。4.2数据结构设计4.2.1数据设计定义棋盘上某点的位置坐标结构体Postiontypedefstruct{intx;inty;}Postion;定义把个方向试探的增量位置数组8Postiondirect[8]={{1,2},{2,1},{2,-1},{1,-2}，{-1,-2},{-2,-1},{-1,2},{-2,1}};定义棋盘某点通向其他点的可到达数的二位数组intaccess[8][8]={{2,3,4,4,4,4,3,2},{3,4,6,6,6,6,4,3},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2}};定义一个以某一棋盘上的点和标志的类型，作为栈的存储数据typedefstruct{Postionp;intflag;}DataType;定义一个链栈：typedefstructnode//定义结点结构{DataTypedata;structnode*next;}StackNode,*PStackNode;////////////////////////////////////////typedefstruct//定义一个栈{PStackNodetop;}LinkStack,*PLinkStack;用来记录可到达下一位置坐标的数组：PostionnextPath[8];876543219用来记录整个遍历过程的数组：Postiontourpos[64];4.3算法设计寻找下一条路径：流程图：略：算法描述：应考察每一方格的可到达性。使用数组accessibility[]表示可达到数,并当马踏棋盘时，程序动态修正剩余格子的可达到数。accessibility[arrayPos]=0表明格子已经被占据。算法：voidnext_Path(PostionP){PostiontestPos;for(inti=0;i8;i++){//有八种到达的情况testPos.x=P.x+direct[i].x;//得出X,Y坐标的测试位置testPos.y=P.y+direct[i].y;if(checkPath(testPos)){//判断测试位置是否在棋盘内nextPath[arrayPos]=testPos;//由测试位置给出正确X,Y坐标accessibility[arrayPos]=access[testPos.x][testPos.y];//利用对应的X,Y坐标得出相应的可到达的路径总数if(accessibility[arrayPos]0)//accessibility[arrayPos]=0表明格子已经被占据arrayPos++;}//寻找空格子结束}//结束for循环,寻找结束countAccessibility=arrayPos;//统计可达到数if(countAccessibilit