1引言
1.1研究背景与意义
最短路径问题是图论中的一个经典算法问题，旨在寻找图中两点之间的最短路径。最短路径问题是组合优化领域的经典问题之一，它广泛应用于计算机科学、交通工程、通信工程、系统工程、运筹学、信息论、控制理论等众多领域，与人类社会的发展进程息息相关。
早在20世纪60年代，人们对最短路的讨论已经初有成效。如今科技快速发展，人们生活质量不断的提升，人类对空间认知能立的增加体现出导航工具的重要性。近代互联网技术的飞速发展和社会的需求带动了各类地图应用的发展，诸如高德地图，百度地图，其核心算法就是最短路径算法。借由导航卫星提供的地理位置信息，软件需在秒级时间内计算出用户所需要的最短路径。
导航只是最短路径问题的一种应用，大多数情况下，人们可以把现实生活中的问题抽象成数学模型通过最短路径来解决。例如抗震救灾，病毒疫情的传播，网络通信系统，城市交通规划系统[1]等等。随着人类社会的飞速发展，城市之间的密切联系，道路网呈现出复杂性，动态性和随机性。研究人员通过对复杂道路网的研究发现其存在小世界特征和无标度[2]的性质。节点之间并非毫无规律，而是有着相近的平均距离，相邻节点具有连边的概率较高。
就目前的社会需求和社会发展速度来看，最短路径算法在我国仍有巨大的市场规模和开发潜力。人们对外的交流需求在不断提升，位置应用的需求量也是只增不减。大规模复杂网络的最短路径计算仍没有较好的解决方案，动态变化的节点对整个道路网对短路径的影响仍然较大，这会降低对最短路径的求解效率和准确度。
1.2国内外研究现状
随着科技文化发展，最短路问题早已不再是最初的两点间求最短路线的问题，各行各业中的问题都可以通过构建数学模型，从而将问题转化成最短路问题进行求解，而计算机和算法的发展使得最短路问题有了更加多样的解决方法。如道路导航、信息传播、信息延时、电力网络、疾病传播、购物推荐[3]等，最短路问题已经广泛覆盖于计算机、交通、通信、运筹学等众多领域。其中比较经典的算法是Dijkstra算法，Floyd算法[4]。
荷兰人迪杰斯特拉设计出的Dijkstra算法利用广度遍历的思想，存储了所有已经遍历的网格节点，从而保证搜索到的路线是全局最优路线，然而因其高计算复杂度而无法适用于各类场合，硬件的限制使传统的寻路算法无法在动态复杂网路中提供高效快速的最短路线，人们提出了一系列近似最短路求解方法，如限制区域搜索方法、目标引导方法、层次划分方法、基于局部区域中心点等最短路径的近似计算方法，同样由于对网络动态性的处理能力较低，也不适用于动态复杂网络的最短路径近似求解。因此，一些针对动态复杂网络的近似最短路径算法被相继提出，主要包括构建动态最短路径树方法，改进的A*算法[5]、分布式计算方法、基于图结构索引方法、基于数据库更新算法、基于社区的动态更新算法等。
A*算法作为一种启发式算法，通过Dijkstra算法改进而来，加入了估价函数[6]，在寻路过程中不断对距离目标点的距离进行估算，从而计算最短路径，逐渐成为了主流寻路算法之一。经过国内外研究者的改进和优化，其性能已经大大提高，适用于各个领域，例如起点和目标点同时进行的双向A*启发式算法[7]在目标点和起点处同时使用A*算法，当二者的搜寻路线相遇时即产生最终最短路径，此方法速度要胜于A*算法但无法保证准确度，引入限制区域的A*算法[8]对A*算法的搜索区域进行了限制，防止其对障碍物周围进行过多的搜索，某些情况下可以更快速的通过障碍物，提升运行效率，但在障碍物足够大且距离目标点较远时算法的运算效率较差，添加了迭代思想的IDA*算法避免了广度优先搜索占用搜索空间太大的缺点，也减少了深度优先搜索的盲目性，然而其不易找到合适的估价函数且容易产生重复的搜索。
还有很多求解最短路径的算法被提出和改进，例如蚁群算法，模拟退火算法，遗传算法等等。最短路径算法在生产实践中被广泛应用，因此对最短路径相关问题的研究具有不可替代的意义和价值，在未来应用前景十分广阔。
1.3本文主要研究内容
本文第一章介绍课题的研究背景和国内外的研究现状，介绍了本文的主要研究的内容。第二章中以Dijkstra算法作为切入点，对最短路径算法进行概述性介绍，指出其优缺点，引出A*算法，概述了A*算法的原理和存储结构，并对A*算法进行分析和探索。第三章中用生活实例对A*算法进行具体演示，使用Java代码进行仿真演示，对比结果数据测试算法的准确性和运行效率并且阐述自己的观点，对某些地方提出改进方案。第四章提出三种不同的改进的方案并加以演算，分析数据，得出结论。最后总结全文，对成果进行归纳，对不足做出总结，对接下来的研究提出展望。
2最短路径算法分析
2.1常见的几种寻路算法
2.1.1 Dijkstra算法
早在1959年，荷兰计算机科学家狄克斯特拉就提出了著名的Dijkstra算法[9]，这是比较经典的由广度搜索算法思想设计出的算法。计算时由起点开始，层层向外扩展，直到搜索到目标节点，可以搜索到路网中某点到其余任意一点的最优路线，但缺点是需要消耗大量时间和计算资源，Dijkstra算法示例见图1。
图1广度优先搜索（BFS）
Dijkstra算法可以求解单一目标点到周围各点的最短路径，其时间复杂度为O(n^2)。本质上Dijkstra算法是一种标号算法[10]，对已知节点的周围节点进行标号，每进行一次标号就要迭代一次运算以确保所有的标号都是最优的，通过这种不断的迭代运算，算法对周围每个节点进行标号，某一时刻目标节点被标记时搜索即结束。
在规划城市道路网时，Dijkstra算法无法做到对地图上任意两点的最短路径进行求解，这时就需要Floyd算法。作为Dijkstra算法的改进版本，Floyd算法作为一个经典的动态规划算法实现了求解任意两点之间的最短路径，其主要思路为从任意一条单边路径开始。所有两点之间的距离是边的长度即权值，如果两点之间没有边相连，则视为权值无穷大。对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是则更新它，从最初的一条边逐渐遍历整个地图，最终实现任意两点最短路径的求解。
2.1.2深度优先搜索算法
与BFS相比，深度优先搜索（DFS）更注重缩短与目标点之间的距离，每一步都是为了更快的接近目标点，但也造成了算法的局限性，每一步只是局部最优，而对于整体却不做考虑。导致最终的路线不一定是最优路线。深度优先搜索算法示例见图2。
图2深度优先搜索（DFS）
深度优先搜索算法是回溯法的一种，区别Dijkstra算法，深度优先搜索会沿着一条路线一直搜寻下去直到路线无法正常行进后回溯至上一节点再寻找路线接近目标点。
便于理解我们可以将起点当作一个树的根部，我们从根部出发进行深度优先搜索。每当我们遇到岔路时便分出对应数目的分支，然后估算每个分支到达目标点所需要的代价，进入代价最低的那个分支，当某一分支无法继续行走下去时，立刻回溯至该分支的根节点，并且不再搜索该分支，然后重复上述步骤，当搜索到目标点时立即停止搜索，顺着终点的根节点一直回到起点，这条路线就是深度优先搜索得到的最短路径。
与Dijkstra算法的广度遍历模式相比，深度优先搜索遍历的节点少，耗时短，效率高，但算法的解并不是最优解，只能说找到了一条可以到达目标点的路，因其深度搜索的特性，若在遍历到最优解之前就搜索到了一条路线，那么算法就会认为该路线就是最优解而停止搜索，从而忽视掉真正的最优解。综上深度优先搜索只是一种高效的寻路算法，可以用于快速生成连接两点的一条通路，但并不能用来求解最短路问题。
2.2 A*算法的基本运作原理
2.2.1存储结构
A*算法是综合了BFS中对已知路线的存储的方法，和DFS中对待行进距离的估算权重而产生的一个高精度，高效率的寻路算法。其启发式搜索思想使得在搜索时可以省略大量无用的路径，既结合了深度优先搜索的遍历和广度优先搜索的启发思路，又避免了二者的不足之处。在搜索时每个节点状态包含待遍历、已遍历两种状态。与传统遍历搜索方法相比较，A*算法为典型启发式搜索算法，可以用于实现静态路网中最短路径的有效求解。
图3 A*算法openlist/closelist列表存储结构示意图
算法中的核心数据存储方式是两个列表，用于存储已检索和未检索的道路网节点。如图3所示，开放列表（open list）：记录所有在寻找最短路径中正被考虑到的节点；闭合列表（close list）：记录那些不需要再次考虑的节点，这些节点无论是在开放列表还是闭合列表，均有五种属性：G（通过估价函数计算到达目标点预计距离）、H（距离终点的哈夫曼距离）、F（对当前整条路线的预计距离，数值为H和G的和）、坐标（当前节点在坐标系中的位置）、父节点（该节点在上一层搜索中所处位置的节点）。本文中使用Java代码进行仿真模拟，用ArrayList动态数组表示开放列表和闭合列表，使用类为每个节点定义好五种属性，使用时只需实例化即可生成一个节点，非常方便。
搜索时由起始结点出发，将行走到的节点加入闭合列表，周围的节点加入开放列表，由启发函数选取开放列表中较短的那个，循环此步骤直至终点。
2.2.2曼哈顿距离
曼哈顿距离即坐标系上各个坐标轴差值的绝对值之和[11]，例如坐标和之间的曼哈顿距离可表示为。如图4所示的左下到右上角的曼哈顿距离为红色线路的长度，蓝色和黄色为等价曼哈顿距离，绿色则为欧式距离，在本文中不做应用。
图4曼哈顿距离示意图
在本文中指横向和纵向行走所经过的方格数目总和。启发函数对地图上任意栅格节点距目标节点的距离进行有效估价，其中G(n)代表起点到该方格已经移动的节点的总距离，这个距离随着算法的进行会不断更新，H(n)代表该方格和终点之间由估价函数计算出的预计距离，在本文中为方便计算和观察规定节点之间只能进行上下左右的移动，无法进行斜方向的移动，因此估价函数采用当前节点到终点的曼哈顿距离，即横纵格子长度之和，用于估计后续移动的代价。
2.2.3 A*算法的简单介绍
下面举一个简单的例子对A*算法[12]进行一个简单的概述和分析。
图5 A*算法初始位置图
如图5所示，一个方格长度为10，红色为起始位置，蓝色为终点，褐色为不可通过的障碍物，规定只能上下左右四个方向移动，禁止斜对角移动，现用A*算法进行最短路径计算。
使用A*算法进行计算，具体操作步骤如下：
①先将起点移入closelist列表，父节点为空，周围四个点移入openlist列表，父节点为起点，记录下各点到终点的曼哈顿距离H，已经行走的距离G，曼哈顿距离和已行走距离之和F，结果如图4所示。
图6 A*算法openlist节点的添加
因为方格的长度为10所以周围格子的已行走距离G均为10，距离终点的曼哈顿距离也很容易通过纵横方向的方格数计算出，F的值可由计算。每个子节点和父节点之间用紫色线条连接方便观测，在图6中绿色方格均为红色方格的子节点。
②寻找F最小值的格子，将其移入closelist，然后判断其周围格子，若为障碍物、closelist、则直接跳过，否则执行下列操作：
若不为openlist则将其移入openlist,前方格设置为父节点。
若为openlist则比较旧F值和新F值大小，更新成F值较小的数据。
该步骤运行结果见图7。
图7 A*算法closelist节点的添加
③一直重复步骤②，将openlist列表中F值最小的节点置入closelist列表，然后将该节点周围未加入openlist列表的节点加入openlist列表。直至终点加入openlist列表或者openlist列表为空，该步骤计算结果如图8所示。
图8 A*算法节点搜索完成图
④从终点沿着closelist中的父节点回到起点，该路径就是最短路径，将方格颜色改为黄色展示，具体效果见图9。
图9 A*算法生成最短路径图
从图7中看到A*算法成功寻找到一条到达目标点的最短路径。A*算法综合了广度和深度的算法，在保证路线精确度的基本要求上，大大缩减了搜索的方格，减少了搜索的时间。
3 A*算法的具体应用
3.1地图的栅格化处理
在导入地图前，需要将地图转换成黑白色的栅格化数据，便于计算机处理分析[13]。本章节以宿迁学院的平面图为例，后面章节中不做说明，也采用该简化地图进行示范。首先在百度地图上搜索后获取到宿迁学院的简略平面地图见图10，为便于分析，需先将地图转换成只有黑白色块的地图。
使用Java代码导入图像并设置像素阈值，将地图划分成黑白两色，白色的像素点视为道路，其余像素点视作障碍物，用黑色表示，将其栅格化成图11。
在图11中白色代表道路，桥梁等可行走区域，黑色则代表湖泊，小山以及各类建筑障碍物等无法行穿行的区域。
图10宿迁学院地图图11栅格化宿迁学院地图
从结果来看，栅格化后的宿迁学院地图比较完整的体现了原地图的道路网，道路之间基本通畅，比例大小，障碍物的位置均原地图一致，适合作为A*算法的地图数据。
3.2计算最短路线
将栅格化处理后的地图文件用java代码编写的A*算法进行计算，分析出最短路线，展示在软件上，运行结果见图12，并将数据汇总至表1：
图12 Java代码A*算法运行结果图
A*算法运行结果如图12所示，观察发现算法搜寻时间很短，运行效率高，寻找的路线与最短路线基本吻合，软件可以正常展示A*算法的特点和运行结果。
表1 Java代码A*算法运行数据
实验次数1 2 3 4 5
起点2，91 2，91 2，91 20，179 156，122
终点19，65 156，151 215，93 281，26 4，33
花费时间(ms)1 4 2 36 157
是否找到路线是是是是否
行走步数84 223 264 499 0
openList节点数279 1466 1114 4889 9107
一共执行的
搜索次数1301 44657 14535 133470 189575
由表1中数据不难发现，1、2、3、4次均成功找到路线，且花费时间随着移动的距离变短而变短，说明若搜寻的两个点初始距离越近，花费时间越短，这也是符合理论的。第5次实验终点选在了无法抵达的区域(左上角)，因此未能找到结果，花费的时间最长且相近，说明算法遍历了整个地图，openList中所有方格都被遍历也未搜寻到路线。
表格中可以看出最终行走的距离并不是影响搜索效率的关键因素，维护的openList列表以及执行的搜索次数才是影响算法效率的关键所在。而路径越是复杂往往需要越多的搜索资源去搜索。后续改进应该着重从减少搜索次数和改进算法搜索效率入手。
4 A*算法的改进
一般来说，作为普遍应用的导航算法，A*算法在实际应用中应该考虑更多的因素，例如路况(路况好与坏影响行进的速度)，客户需求(由于路况不同导致速度不通，最短路往往不是最快路线，若客户赶时间，此时最基本的A*算法便不适用)，另外还有红路灯数量，限号限行，是否优先考虑高速公路等等。随着人们对生活质量的追求，越来越多的需求也促使人们对A*算法的不断改进。
对于算法本身来说，A*算法随着地图的扩大，运算量呈指数级增加，如何在不减少算法精度的情况下减少运算量，提升算法效率成为最需要解决的问题。
就目前的情况来看，一个既精准又快速还不怎么占存储空间的算法是不存在的，某些情况下牺牲了精准度从而提升了速度，又或许花费额外的时间提升精准度，还有一些通过对地图预处理，加快搜索速度，用空间代价交换时间代价的一种策略。
本章将选取其中部分问题进行改进并得出结论。
4.1减少转向
从A到B本可以只转向一次就可到达的最短路径，有时算法给出了另一条阶梯状的最短路径，虽然从路程上来说而这并没有区别，但在实际生活中，如图13所示，在不考虑其他因素的情况下，同样的路程如果多次转向对车辆、燃料都会造成不必要的损耗。
图13 A*算法寻路图
在算法中，G值代表代价，为了使算法在相同F值的情况下转向和直行中选择直行，需要对转弯适度的增加一定代价，每转一次弯，G值除了路程上的代价增加，还应该在每次转向时增加一个转向代价g即，运行结果见图14，可以看出明显减少了转向次数。
图14改进权值后A*算法寻路图
需要注意的是g的大小不应该大于单元格长度/期望行走的最大路线，否则随着路线的不断搜寻，有可能导致最后寻找的路线并不是最短路线，使算法不够准确。
4.2栅格化精度的选取
4.2.1栅格精度对算法计算效率和准确性的影响
地图在栅格化处理的时候如果追求精度，将地图的像素划分的非常细小，无疑会指数级的增加算法的运算时间，而划分的过大又会导致路线不精确，甚至提供错误的路线。如何设定一个在满足精度的基础上，提升运行速度的栅格化方法是提升效率的关键。
本文使用的方法是以最窄的可通过道路的宽度为1个栅格基准，这样可以尽可能地压缩地图，增加运算效率。但这会导致地图精度不够，有可能会造成这样一种结局：导航提示你到了目标点，然而实际上目标点还在你的右边十米处。显然这种结局不是所有人都能接受的，因此在接近目的地时应细化栅格，使导航更加精确。
4.2.2针对栅格精度的改进方案
在初期使用精度比较低的搜索方案，设定一个范围，当closeList中的点进入目标点周围的范围的时候说明你距离目标已经“足够近”了,这时重新划分精度，从当前点进行比较细致的A*搜索，这种方法也许找到的路线不是全局最优路线而是局部最优，但在长距离搜索时可以大大节约时间。
在游戏领域这种方案应该更为广泛的应用——鼠标点击后游戏人物必须迅速响应，如果直接进行长距离的高精度A*搜索可能会出现人物“卡住”一下再移动的情况，降低玩家的游戏体验，而先进行低精度的A*搜索，让人物先动起来，在移动的时候再进行高精度的A*搜索，玩家不会有卡顿的感觉而且最终路线和最优路线不会有太大偏差。
如图15起点为红色方格，终点为蓝色小方格，对其直接进行A*算法搜索，注意此时选取的栅格化精度较高。
图15高精度A*算法初始图
算法运算结果如图16所示，绿色方格是被搜索的方格，蓝色方格是被确定的最短路线。
图16高精度A*算法运行结果图
现在降低栅格化的精度，转化成大方格A*算法寻路(3*3的小方格转换成1个大方格)，再次使用A*算法进行计算，运行结果如图17所示。
图17低精度A*算法运行结果图
在搜索到目标地3×3的黄色区域后转化回小方格，采用高精度A*搜索，效果如图18和图19。
图18低精度A*算法的接近目标点区域
图19近目标点区域的高精度A*算法运算结果
拼接后得到的最终行进路线见图20：
图20先低精度后高精度A*算法总路径
算法具体运算数据汇总见表2。
表2不同栅格精度的A*算法运行结果
算法高精度先低精度后高精度
花费时间(ms)3 1
是否找到路线是是
行走步数49 51
openList节点数88 311
搜索次数197 2861
分析：先通过低精度A*算法向前行进，接近目标点后再使用高精度A*算法，通过牺牲小部分最终路线的精度，大大提升了算法搜索的效率，且最终路线不会与最短路偏差太大，极大的节约了运算资源。
如果运算资源较为充裕，可以缩短低精度A*算法的行走距离，在行走一段距离后即采用高精度A*算法，可以最大限度的提升路线的精度，又减少了等待的时间。
例如在网络实时对战的游戏中，可以先进行低精度的A*算法，然后只行进一小段例如5%的路程，使玩家操作的角色迅速动起来，在移动5%路程后，利用这段时间计算机能够计算好后续的高精度A*算法的路线，从而使得后面95%的路线都是极为精确的最短路线。而随着计算机性能的不断完善，这5%的路程会被不断缩小，所产生的误差对玩家的游戏体验来说已经可以忽略不计了。
这种注重目的地而不怎么考虑路程的思想也可以在估价函数H中加入一个权值实现——越接近目标点，这个函数就会计算的越精确，反之可以降低函数的精度，使一开始的路线不怎么耗费运算资源。
4.3对地图进行节点化处理
对于长距离移动来说，我们不应该也不可能对每一步都进行A*算法计算，即使采取降低栅格精度的策略有时也难以有效的降低算法复杂度，这时就要果断放弃栅格化，采用节点化的地图。在进行导航时，人们往往对细节精确到每一条道路，每一个路口，如果划分的再细致些也没有过多的意义，因为没有人会在意自己怎么通过一条没有岔路的直行道，反而会消耗硬件大量的算力，卫星的定位也难以精确到人的每一步上，因此不如只在路口处设置节点，最后导航的结果以道路名展示，用户只需沿着道路走即可到达目标点。
对图10宿迁学院地图进行黑白二值化处理，然后对每个路口标记节点，效果如图21所示：
图21以A*算法计算节点化地图初始图
原本数万像素的地图，在每个分叉路口设置一个节点，变成了仅有68个主节点的节点图。现在我们想从A点向B点进发，寻路时：
①分别找到起点和终点周围哈夫曼距离最近的主节点保存下来。用经典A*算法进行计算起始点到各自最近主节点的最短路线，因为距离通常较短，计算量很低。
②对两个已存储的主节点进行A*搜索，因为主节点的数量很少，计算量也很少。
③将三段路线进行拼接，最后得到的路线就是节点化处理的最短路线。
运行后得到路线见图22。
图22 A*算法计算节点化地图运算结果
算法几乎是瞬间完成了计算，两条绿色路线是起始点到主节点的最短路线，红色路线是两个主节点中的最短路线。不难看出最终行进的路线非常接近最短路线。
优点：极大的提升了搜索效率，在长距离导航中优势明显。
缺点：最终的路线不一定是最短路线，且在短距离寻路时可能会因节点过少而绕路，因此短距离时不应采用此方法。
5结论与展望
5.1结论
A*算法结合了Dijkstra和BFS启发式思想，保证最短路的同时提升了效率，在实际应用中表现出色，寻路效率高，用时短。是现在被广泛使用的最短路算法。
本文在经典A*算法的基础上加以改进，增加了转向时的权值，使得算法在多条相同预期的道路时，总会优先选择不怎么转向的道路。
针对栅格化地图的A*算法，考虑到地图尺寸以及精度的需求，可能会造成的算法效率缓慢，用时过长的结果。采用先低精度后高精度的A*算法，减少了算法在初期的运算量，使用者不会体验到算法运行所产生的卡顿感，在软件性能有限的情况下非常实用。
对于大地图道路网的导航，不需要对全图都进行栅格化，转换成在每个有道路连接的路口处设置节点，节点与节点之间的距离就是道路的长度。算法运算时只需要先将人导航到距离最近的节点，然后在节点中使用A*算法，可以大大提升算法效率。
5.2展望
本文为方便计算将路径导航抽象成二维空间中正方形节点的寻路问题，且仅有4邻域移动方向，与现实生活中有较大差异，后续研究应该以更复杂的情况例如6邻域8邻域为研究对象，移动方向应有更多选择，对应的估价函数H也应由原本的曼哈顿距离改为欧氏距离或者其他更加准确的估价函数。
在计算一段路线的移动代价时，只采用路径长度作为代价是不准确的，相同长度的道路在不同的路况影响下，通过时有较大的时间差异，后续研究应该加上路况的影响，以路线长度和路况好坏的综合评价结果作为移动的代价。
文中演示的道路节点大多道路连接分布均匀，而实际生活中的道路网存在大量无标度网络，应当进一步研究和调整，使算法适应更多不同网络。
参考文献：
[1]郭阳.动态复杂网络的最短路径研究[D].辽宁大学,2019.
[2]梁娟.网络最短路径问题的研究与应用[D].南京邮电大学,2015.
[3]刘宏魁.基于A-star算法的地图查询系统的设计与实现[J].电子技术与软件工程,2018(22):44.
[4]李坤,蒋莉莉.分布式计算中基于A-star的工作流调度改进算法研究[J].计算机工程与科学,2013,35(03):38-42.
[5]宋岩.基于A-Star算法的进路搜索研究[D].西南交通大学,2014.
[6]刘熙明,魏旭,窦立刚,覃洪波,杨露溪.基于A-Star算法的Ad Hoc无线网络最优路由模型研究[J].佛山科学技术学院学报(自然科学版),2019,37(04):38-42.
[7]刘微,肖华勇.复杂网络中近似最短路径问题[J].计算机系统应用,2016,25(05):107-112.
[8]时也.基于A-Star算法与模糊控制融合的移动机器人路径规划[D].武汉科技大学,2012.
[9]王恒青,宋如敏.最短路径算法Dijkstra算法在路由选择中的应用[J].科技信息(学术研究),2008(32):569-570.
[10]向志华,赖小平.基于BFS算法的有阻断路径的最短路径算法研究[J].信息通信,2019(11):41-42.
[11]谢晖,张达奇,冯李.结合曼哈顿距离的A-star算法在光缆寻址中的应用[J].信息通信,2019(01):34-36.
[12]吴健.基于A-star改进路径规划算法研究[D].安徽工业大学,2019.
[13]万平.基于A-star算法的航路规划算法设计与仿真研究[J].中国水运.航道科技,2018(04):58-65.
致谢
时光荏苒，4年的大学生活如白驹过隙般转瞬即逝，宿迁学院大校园生活给了我许多快乐和惊喜。大学的学习生活让我学到了为人处世的原则和专业的知识理论，而我已不再是从前那个无知的少年，衷心祝愿母校未来发展得更好！
首先我要感谢导师在对我的指导和讲解，从论文材料的收集、题目的确认和理解、创新点的研究、论文的反复修改一直到最终的论文定稿，老师都给了我非常多的帮助，让我对选题有了一个深刻的理解和认识，期间对我的提问也是热心解答。中期检查时指出我论文的不足，并协助我完善内容。疫情期间无法见面讨论，导师督促我们抓紧完成论文后网上对我们进行了指导。可以看出导师为了协助我完成论文顺利毕业付出了很多，态度也是一丝不苟，不容有一点错误，这种严谨踏实的风格令我十分尊敬。尤其是在我的论文进展出现问题时，老师即使提醒和指导，使论文进度得以正常进行。
其次还要感谢在宿迁学院的各科的任课老师在校期间对我的栽培，正是有了他们的督促，我没有虚度四年的大学时光，用在校时间学习很多理论知识。还要感谢辅导员，在日常生活中和学习工作上对我的大力支持，辅导员的认真负责让我的学习生活很少遇到阻碍，很多事情在辅导员的帮助下迎刃而解，感谢宿迁学院的老师们，使我顺利完成这篇论文！
还要感谢各位对我论文做出帮助的同学，很多小问题例如格式，一些零散的知识点，在学校没有完善的部分，是多亏了同学们的帮助，在小问题上节约了我大量的精力，让我可以腾出时间去钻研论文，感谢你们的一路陪伴！
最后对本次论文的评阅专家致以最诚挚的敬意！
附录
package读取;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import javax.swing.JFrame;
import javax.swing.JPanel;
public class AStar{
static int[][]NODES=new int[292][260];
static int[][]DRAW=new int[292][260];
static int[][]point=new int[2][2];
static int pointNumber=0;
static ArrayList<Node>arrayList=new ArrayList<Node>();
public static final int STEP=10;
private ArrayList<Node>openList=new ArrayList<Node>();
private ArrayList<Node>closeList=new ArrayList<Node>();
public Node findMinFNodeInOpneList(){
Node tempNode=openList.get(0);
for(Node node:openList){
if(node.F<tempNode.F){
tempNode=node;
}
}
return tempNode;
}
public ArrayList<Node>findNeighborNodes(Node currentNode){
ArrayList<Node>arrayList=new ArrayList<Node>();
int topX=currentNode.x;
int topY=currentNode.y-1;
if(canReach(topX,topY)&&!exists(closeList,topX,topY)){
arrayList.add(new Node(topX,topY));
}
int bottomX=currentNode.x;
int bottomY=currentNode.y+1;
if(canReach(bottomX,bottomY)&&!exists(closeList,bottomX,bottomY)){
arrayList.add(new Node(bottomX,bottomY));
}
int leftX=currentNode.x-1;
int leftY=currentNode.y;
if(canReach(leftX,leftY)&&!exists(closeList,leftX,leftY)){
arrayList.add(new Node(leftX,leftY));
}
int rightX=currentNode.x+1;
int rightY=currentNode.y;
if(canReach(rightX,rightY)&&!exists(closeList,rightX,rightY)){
arrayList.add(new Node(rightX,rightY));
}
return arrayList;
}
public boolean canReach(int x,int y){
if(x>=0&&x<NODES.length&&y>=0&&y<NODES[0].length){
return NODES[x][y]==0;
}
return false;
}
public Node findPath(Node startNode,Node endNode){
openList.add(startNode);
while(openList.size()>0){
Node currentNode=findMinFNodeInOpneList();
openList.remove(currentNode);
closeList.add(currentNode);
ArrayList<Node>neighborNodes=findNeighborNodes(currentNode);
for(Node node:neighborNodes){
if(exists(openList,node)){
foundPoint(currentNode,node);
}else{
notFoundPoint(currentNode,endNode,node);
}
}
if(find(openList,endNode)!=null){
return find(openList,endNode);
}
}
return find(openList,endNode);
}
private void foundPoint(Node tempStart,Node node){
int G=calcG(tempStart,node);
if(G<node.G){
node.parent=tempStart;
node.G=G;
node.calcF();
}
}
private void notFoundPoint(Node tempStart,Node end,Node node){
node.parent=tempStart;
node.G=calcG(tempStart,node);
node.H=calcH(end,node);
node.calcF();
openList.add(node);
}
private int calcG(Node start,Node node){
int G=STEP;
int parentG=node.parent!=null?node.parent.G:0;
return G+parentG;
}
private int calcH(Node end,Node node){
int step=Math.abs(node.x-end.x)+Math.abs(node.y-end.y);
return step*STEP;
}
private static void flash(){
Node startNode=new Node(point[0][0],point[0][1]);
Node endNode=new Node(point[1][0],point[1][1]);
Node parent=new AStar().findPath(startNode,endNode);
while(parent!=null){
arrayList.add(new Node(parent.x,parent.y));
parent=parent.parent;
}
System.out.println("n");
for(int i=0;i<NODES.length;i++){
for(int j=0;j<NODES[0].length;j++){
if(exists(arrayList,i,j)){
System.out.print(",");
}else{
System.out.print(NODES<i>[j]+",");
}
}
System.out.println();
}
}
public static void main(String[]args)throws IOException{
File f=new File("D://QAP.txt");
BufferedReader buf=new BufferedReader(new FileReader(f));
int[][]city=new int[292][260];
int line=0;
String str=null;
while((buf.read())!=-1){
str=buf.readLine();
String[]date=str.split("");
String s=date[0];
int[]a=new int[s.length()];
for(int i=0;i<s.length();i++){a<i>=Integer.parseInt(String.valueOf(s.charAt(i)));}
for(int i=0;i<a.length;i++){NODES[line]<i>=a<i>;DRAW[line]<i>=a<i>;}
line++;
}
Node startNode=new Node(point[0][0],point[0][1]);
Node endNode=new Node(point[1][0],point[1][1]);
Node parent=new AStar().findPath(startNode,endNode);
while(parent!=null){
arrayList.add(new Node(parent.x,parent.y));
parent=parent.parent;
}
System.out.println("n");
JFrame jFrame=new JFrame();
JPanel jpanel=new JPanel(){
public void paint(Graphics graphics){
super.paint(graphics);
for(int i=0;i<NODES.length;i++){
for(int j=0;j<NODES[0].length;j++){
if(exists(arrayList,i,j)){
graphics.setColor(Color.BLUE);
graphics.fillRect(3*j,3*i,3,3);
}else if(NODES<i>[j]==1){
graphics.setColor(Color.BLACK);
graphics.fillRect(3*j,3*i,3,3);
}else if(DRAW<i>[j]==2){
graphics.setColor(Color.RED);
graphics.fillRect(3*j,3*i,3,3);
}
}
System.out.println();
}
}
};
jFrame.add(jpanel);
jFrame.setSize(680,900);
jFrame.setVisible(true);
jpanel.addMouseListener(new MouseListener(){
Override
public void mouseClicked(MouseEvent e){
DRAW[(int)(e.getY()/3)][(int)(e.getX()/3)]=2;
System.out.println(e.getX());
System.out.println(e.getY());
pointNumber++;
point[pointNumber-1][0]=(int)(e.getY()/3);
point[pointNumber-1][1]=(int)(e.getX()/3);
flash();
jpanel.repaint();
}
Override
public void mouseEntered(MouseEvent arg0){
}
Override
public void mouseExited(MouseEvent arg0){
}
Override
public void mousePressed(MouseEvent arg0){
}
Override
public void mouseReleased(MouseEvent arg0){
}
});
}
public static Node find(List<Node>nodes,Node point){
for(Node n:nodes)
if((n.x==point.x)&&(n.y==point.y)){
return n;
}
return null;
}
public static boolean exists(List<Node>nodes,Node node){
for(Node n:nodes){
if((n.x==node.x)&&(n.y==node.y)){
下载提示：
1、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“文章版权申述”（推荐），也可以打举报电话：18735597641(电话支持时间：9:00-18:30)。
2、网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友投稿，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务。
原创文章，作者：写文章小能手，如若转载，请注明出处：https://www.447766.cn/chachong/14749.html,
