电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

信息与计算科学-最短路径图形结构算法及应用论文

信息与计算科学-最短路径图形结构算法及应用论文_第1页
1/29
信息与计算科学-最短路径图形结构算法及应用论文_第2页
2/29
信息与计算科学-最短路径图形结构算法及应用论文_第3页
3/29
最短路径图形结构算法及应用摘要 日常出行人们依靠地图和导航来查询路线,计算两地最短的距离,选择最适合的路径,这时最短路径算法的需求就体现了出来。最短路径算法,比较经典是 Dijkstra 算法,采用广度搜索(BFS)的思想,深度优先搜索(DFS)仅考虑与目标点的剩余代价而导致往往搜索不到最短的路径。A*算法作为 Dijkstra 算法的扩展,因其高效性而被广泛应用于寻路及图的遍历,且结果往往是最优解。本文中主要探讨 A*算法的运作方式,使用 java 代码编写对应程序,对生活中实例进行演示操作,发现影响算法搜索的效率的主要原因是 openlist 节点的遍历次数和一共执行的搜索次数,遍历次数和搜索次数的增多均会导致搜索时间的增加在对算法进行分析改进后,提出了增加转向时的权值从而减少转向、以低精度的栅格替代高精度的栅格、用节点网图替代栅格网图等算法改进方案。经过实验均可在部分情况下提升算法效率同时精度损失可以忽略不计。关键词 路径规划 最短路径 A*算法 运行效率IAlgorithm and application of shortest path graph structureAbstract Daily travelers rely on maps and navigation to query routes, calculate the shortest distance between the two places, and choose the most suitable path. At this time, the demand of the shortest path algorithm is reflected.Dijkstra algorithm is the classic shortest path algorithm. It adopts the idea of breadth search (BFS), and depth first search (DFS) only considers the residual cost with the target point, so it often fails to find the shortest path. As an extension of Dijkstra algorithm, A * algorithm is widely used in path finding and graph traversal due to its high efficiency, and the final path is often the optimal solution.This paper mainly discusses the operation mode of A * algorithm, uses Java code to write corresponding programs, and demonstrates the operation of real life examples. It is found that the main reasons that affect the efficiency of algorithm search are the number of traversal of openlist node and the...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

信息与计算科学-最短路径图形结构算法及应用论文

您可能关注的文档

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部