1. 研究目的与意义
算法究竟给使用者带去了怎么样的便利或者好处？对于机械，重复，毫无智能的机器语言如何组织，编译发展出智能性语言？对于普通的，非专业人员是否也能对算法带来的便利有所了解？我的毕业设计课题题目是：改进算法在迷宫游戏中的研究与实现。面对堵得水泄不通车流还有10分钟就要上班打卡，或者外出旅游走在不熟悉的城市道路上，这时一张地图就显得尤为重要，现实中需要用到地图的地方实在是太多，但是拿到地图你是否能够真正找到最优的路线，这时规划路线这种算法就显示出了它的价值，考虑到算法实现的难度和难以理解性，而我的课题就将用最简单最直观的方式向使用者展示出算法的便利性:使用游戏迷宫实现算法代码。因此我们就非常有必要对算法的实现进行更深层次的研究和探索。
2. 课题关键问题和重难点
课题主要研究算法代码和非算法代码之间的优劣势。为了比较有无算法的代码的优劣性，首先就需要两个模块，一个代码自动生成迷宫地图，一个算法生成迷宫地图，迷宫地图生成需要考虑的问题不多，最基本的只需产生一条从起点到终点的路线，以及最重要的难点就是理解算法生成迷宫地图中的算法代码，通过debug查看各变量的值和进行迷宫实现动画比较以解决代码理解问题，但是为了游戏美观以及可操作性，必须设置更多通路提高难度，以达到游戏效果。除了地图生成模块，课题还有寻路模块，加入了DFS遍历和最优路径显示，其中的重难点也是对算法代码的理解，也是通过debug查看各变量的值进行理解。
3. 国内外研究现状（文献综述）
最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。他们在空间复杂度、时间复杂度、易实现性及应用范畴等方面各具特色。解决此最短路径问题最典型的算法是Dijkstra算法，该算法采用贪心策略，即每-步都选择与源节点构成局部路径距离最短的节点作为当前扩展节点来形成当前局部最短路径，进而得到全局的最短路径。Dijkstra算法是已经证明的能得出单源路径的最优解，主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。迪杰斯特拉算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构、运筹学等等。国内外大量专家对此问题进行过深入的研究。最短路径问题可分为单源最短路径问题及全源最短路径问题两种，其中单源最短路径问题更具有普遍意义，且可为全源最短路径问题提供良好的借鉴方案。除了Dijkstra算法本课题使用了A*算法下面就对这两种算法的特点进行一下比较：Dijkstra算法计算源点到其他所有点的最短路径长度，A*关注点到点的最短路径(包括具体路径)Dijkstra算法建立在较为抽象的图论层面，A*算法可以更轻松地用在诸如游戏地图寻路中。Dijkstra算法的实质是广度优先搜索，是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。对路径上的当前点，A*算法不但记录其到源点的代价，还计算当前点到目标点的期望代价，是一种启发式算法，也可以认为是一种深度优先的算法。由第一点，当目标点很多时，A*算法会带入大量重复数据和复杂的估价函数，所以如果不要求获得具体路径而只比较路径长度时，Dijkstra算法会成为更好的选择。所以本课题选择了A*算法。
本课题主要在在探究算法在简单迷宫生成中起到了什么作用。课题使用了比较的方式，对地图生成给出了三种方式：手动输入，自动生成（无算法），算法生成。分别展示了不同情况下的地图生成的不同情况。除了地图的生成，对于地图的路径寻找本课题也进行了一些算法的使用，例如最短路径生成，深度遍历路径等一些简单算法的应用。本课题使用java作为编程语言，前端编写和展示使用了Java的BookstripFX和css表单样式。
本课题主要在在探究算法在简单迷宫生成中起到了什么作用。课题使用了比较对比的方式，对地图生成给出了三种方式：手动输入，自动生成（无算法），算法生成。分别展示了不同情况下的地图生成的不同情况。除了地图的生成，对于地图的路径寻找本课题也进行了一些算法的使用，例如最短路径生成，深度遍历路径等一些简单算法的应用。本课题使用java作为编程语言，前端编写和展示使用了Java的BookstripFX和css表单样式。
4. 研究方案
|
1.课题分成两个大模块包括地图生成模块和路径生成模块。地图生成模块包括手动输入迷宫地图子模块，自动生成迷宫地图子模块，算法生成迷宫地图子模块通过对比实现展现有无算法代码的地图生成的优劣性。路径生成模块包括寻路子模块和寻优子模块通过对比展现有无算法代码的路径寻找的优劣性。 2.完成课题的总体方案最主要完成两个工作：迷宫地图的生成和起点到终点的路径生成，也就是地图生成模块和路径规划模块。地图生成模块下分成了手动输入，自动生成和算法生成，路径生成模块下分成了寻路模块和寻优模块。手动输入模块进行手动书写地图（0表示墙壁，1表示路径），并且用户自己设置起点和终点。自动生成模块地图随机自动生成（无算法），算法生成模块地图由算法（Prime）生成。路径生成模块下寻路模块有一个基础功能三个寻路功能，基础功能还原地图也就是刷新地图，三个寻路功能包括：遍历，寻路（随机），寻优（最小路径）。遍历功能:深度遍历（DFS）动态生成所有从起点到终点的路径。寻路功能:随机寻找一条到起点到终点的路。寻优功能:找出起点到终点的最短路径。 3.生活，工作中许多东西都能看到与本课题相关的联系，比如开车导航的最佳路径规划,外卖骑手取餐送餐最优路线，飞机航线规划等。 4.客观条件:课题选择使用游戏的方式展现首先是为了更直观，也是为了更高效简单的部署算法代码。 前端展示使用了Java的BootstrapFx,GUI等，相较于其他前端也更简单。代码方面:虽然算法代码难以理解，但是整体代码量并不多。 主观因素:相较于其他开发软件java在以前的学习中经过大量联系，对于java的操作变得得心应手，没有太大压力。代码方面:虽然算法代码难以理解，但是整体代码量并不多，有很多时间进行算法代码的理解，也没有太大的负担。 5.在代码编写的过程中最难的就是算法的代码实现，简单的算法代码可以轻松的打出来，如何将里面的变量和迷宫代码逻辑连接起来，包括对算法复杂度等的一些计算。代码的编写出现过太多错误，通过大量文献，资料的参考借鉴，解决了其中大部分的问题。
|
5. 工作计划
22-23-1第15-16周 完成选题，查阅相关中英文资料，进行相关技术的学习；22-23-1第17周 与导师沟通进行课题总体规划；22-23-1第18周 导师下发毕业设计（论文）任务书，学生根据导师的要求进行外文翻译，列出开题报告大纲；22-23-1第19周 搭建开发环境，撰写开题报告，假期中需提交开题报告。22-23-2第1周 进行课题的需求分析；22-23-2第2-3周 根据需求分析设计地图生产算法；22-23-2第4-6周 完成几种地图生成方式的算法的编码与测试，地图的路径寻算法的研究与设计；22-23-2第7周 提交毕业设计论文提纲给指导老师审阅；22-23-2第8-10周 地图的路径寻算法中寻路和寻优两个模块的编码与测试；完成毕业论文初稿；22-23-2第11周 在教师的指导下对撰写的论文进行修改，提交论文终稿及合格的论文检测报告、毕业设计（论文）资料装袋；22-23-2第12-13周 筹备毕业答辩相关事宜，制作参加毕业答辩的演示课件。参加毕业答辩，并提交全部文档和成果材料。
以上是毕业论文开题报告，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
