英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
基于DIJKSTRA算法的最优地图导航系统
阮创，罗建平，余武
广东电视信息技术服务有限公司，广东，中国
摘要：在智能交通系统中，最短路径的计算和最佳路径是车辆导航功能的重要环节。 由于参与计算的实时信息越来越多，对于算法要求计算效率高。 本文研究了基于车载终端导航系统，设计整体系统的框架，并给出了每个的功能模块。 系统可以提供最佳的服务路径
用户的选择和需求。 优化Dijkstra算法的设计与应用保存中间结果存储空间的过程系统运行，提高了精度导航路径，降低了Dijkstra的复杂性算法大大提高了效率系统。
关键词：最优路径; Dijkstra Alogorithm; 地图导航; 车辆导航
1介绍
在现代社会，智能交通系统是一种解决交通供求矛盾的有效的方式。车载导航系统作为智能交通系统的重要部分，有广泛的应用前景。技术和自主研发能力落后导致中国汽车导航产品“好”但是不便宜”。
目前市场上的车载导航系统使用面部信息传输，信息共享水平低，不能满足用户的个性化需求和综合要求。通过使用智能车辆导航，用户可以更方便地获得行程和周边的信息，享受方便快捷的旅游服务。机动车导航系统应用自动化定位技术，计算机技术和无线通信技术，有效地解决了使用各种高新技术的流量问题。主流车辆导航的路径规划通常使用Dijkstra算法。
学者们也对Dijkstra算法的优化进行了深入的研究，如武汉大学的张艳从基于GIS技术的道路网的研究特点提出了基于自己观点的最优路径搜索算法，最优路径的搜索过程显著增加。中国测绘学院张福豪根据映射科学提出了相邻点优化算法。
现有在算法研究中也有不可避免的问题。 如果算法是直接应用于计算城市道路网络的最优路径则需要大量的计算，而且不能满足动态搜索的要求。因此，本文解决了Dijkstra算法优化问题，着重改善处理复杂的动态变化的道路网络。 另外，本文研究和设计了智能车辆导航系统，改进了Dijkstra算法，满足了用户管理和更新旅游地图的需求，补充当前交通信息查询，查询目的地，最短路径规划和多媒体播放，给旅客真实方便的服务。
2车辆导航系统的设计与实施
目前交通繁忙问题成为世界主要城市迫切解决的问题。 为了解决交通繁忙的问题，改善运输效率，减少运输成本，智能交通系统在这历史性的时刻出现。 智能交通系统已经广泛应用，车载导航系统也是目前得紧急需求。
2.1车辆导航系统总体设计
车载导航系统是以电脑系统为主在数字地图上的地理网络中，使用预测定位，全球定位系统（GPS）技术找出最佳的路线，为旅客提供实时或动态导航信息，及时指导旅客驾驶的过程。本文提出的旅游智能车辆导航系统是根据用户的个性化选择，提供最佳、最实用的道路规划，同时改进了Dijkstra算法，通过系统给用户提供更友好的反馈。根据车辆的功能要求，导航系统按照分层结构分为人机界面模块和核心两部分，如图1所示。
图1 车辆导航系统的整体架构
2.2人机界面模块
在该模块中，系统提供功能如下：应用软件与用户交互的功能、目标搜索，多媒体播放，最短路径计算，交通信息查询，路径规划等，并集成系统所有应用软件，方便用户使用。 旅行者可以使用目标搜索功能搜索感兴趣的地方，系统会使用最短路径计算和路径规划、根据流量级别得到最优路径。
2.3车载导航系统模块
系统基于Eclipse开发工具和电子地图API。以下对实现路径规划过程的功能细节进行介绍。
车辆路径规划需要加载电子地图，为拓扑关系AL提供依据。该系统会自动加载每个电子地图数据集中的层，通过查找这些突然的对象数据集的发现和搜索方法。基于拓扑关系，原始对象与其他节点的距离将被初始化。路线只能在获取起始点和终点的信息后绘制。车载导航系统能够进行一些优化操作，比如确定路径是否已被规划。如果路径已被规划了，系统不需要重新计算它。如果这是一条新的路径，计算新路线的要求将提交给系统。系统将使用导航算法计算从起点到终点的最短路线。该系统中已改进了基于Dijstra的导航算法，可以满足用户的需求。按照最短路径节点顺序，流量路径对应最短路径显示在电子地图上。流量汽车导航图表如下图所示
图2 汽车导航流程图
3 Dijkstra改进算法
3.1传统Dijkstra算法
传统的Dijkstra算法将节点分割为永久节点（P）和临时节点（T）。 P节点是那些已经找到从起点到任意一点的最佳路线的那些节点，其余的节点是T。算法核心过程是将合格节点T转换为节点p。在N个节点的图中，二维阵列W [N][N]用于描述节点I到节点j的最佳路径。如果节点I至节点j之间存在边缘，则W（i，j）是边的权重，否则，W（i，j）是无限的，具体过程如下所示。
图3 传统Dijkstra算法流程图
3.2传统Dijkstra算法的缺点
传统的Dijkstra算法简单、容易实行。 这是一个成熟的求解最短路径问题的算法，但有以下几点实践缺陷：（1）传统算法使用邻接矩阵描述网络节点及其特点，导致数据冗余和浪费时间。
（2）算法复杂度过高，不适合计算大型网络的最短路径搜索。
（3）实际操作中，需要考虑实时交通状况，已提高算法准确性。
（4）传统算法采用贪心策略，保持每个步骤都是最佳状态，总体结果可能不是最佳的。
3.3改进算法
（1）使用邻接表存储道路网拓扑
因为在Dijkstra算法中，节点拓扑操作是根据相邻节来搜索道路网的拓扑结构，使用邻接表可以减少循环次数。和传统的邻接矩阵相比，提高了效率。在这种结构中，每个节点直接记录其相邻节点的权重，因此，在执行此循环时，循环数等于其相邻节点的数量（作为出局程度d）。对于整个算法，平均周期时间（以d为单位）
等于地图的向外程度。我们这样做可以将内循环1的时间从N减少到d。对于GIS系统而言，N远大于d，因此，将有效缩短和邻接列表间循环时间，减少了冗余空间。
（2）使用二进制堆作为优先级队列
算法Dijkstra的关键是找到每个循环中的最低成本代码。传统方法使用遍历。但遇到大量数据时效率会降低。最有效的方式是根据成本从低到高安排节点。我们会找到每个循环中的最优节点。使用二进制堆来存储优先队列。二进制堆可以看作是一种完整的二进制树，非叶节点值不大于左、右子节点的值，所以这个桩中的最小值是桩的顶部的元素，二进制堆在这里作为一个优先级队列和高效的数据结构，它包括三个主要步骤：
过滤器h：调整二进制堆的混沌序列h，将每个节点与其周围进行比较，将其放在右侧地点。
将元素x插入到h中：将元素x插入到堆栈h中，调用步骤1，调整h为二进制堆。首先把x放在堆得底部，然后遍历整个二进制数，把新元素放在在适当的地方。
调整h：查找h中最小的元素并将其删除，然后调用步骤1，调整h为二进制堆。主要的
操作时间花费在二进制堆的调整中。众所周知，算法Dijkstra的时间复杂性没有优化是O（V ^ 2）。这个算法使用的是每次添加具有最小成本的节点。deletemin操作的时间复杂度是O（logn）。然后根据其他顶点调整添加节点的树的距离，主要使用操作decresekey（log n）。操作降低成本O（mlogn），因为操作降解达到m倍。Deletemin操作执行时间为n，需要O（nlogn）时间。他们总共用时O（（m n）logn）。其初始部分的复杂性不会超过它，所以算法的复杂性是（（m n）logn）。
（3）交通阻抗分析
交通阻抗是运输电阻值。车辆没有交通阻挡时，时间和距离正比关系，但在实际交通道路上，车辆不能畅通无阻。所以不能简单的使用比例函数表示时间和距离间的运行关系。时间、距离和流量是一种负载函数。单位长度，时间和长度之间的关系函数交通流量如下：
t：单位道路所需的时间。
v：车辆在道路上的通行能力。
q：单位道路上的交通。
l：道路长度
对于道路交通阻抗函数的表达式，BPR功能是使用最广泛的功能，函数表达式称为：
T：无障碍驾驶车辆的平均时间。
e：道路交通能力。
alpha;，beta;：要校准的参数。
交叉路口交通阻抗：BPR
在道路交通观测数据中定义的功能，适合道路交通阻抗。 但在大城市交叉路口密集，车辆通过需要很长时间，显然不容忽视。 许多学者致力于此项研究，交通阻抗交叉路口的定位如下：
T表示道路阻抗值，Y表示时间交点处的阻抗值。 根据不同类型和不同应用的交点，Y的定义也不同，以下是韦伯斯特公式：
（4）交通阻抗分析
计算机中推导出的最短路径算法，它只考虑到网络拓扑结构特点，忽视实际道路网的空间分布特征，导致没有具体的研究方向。获得的最短路径树的初始节点在最低端，而目标节点处于树的顶端。进行一个路径树的创建，有很多冗余计算，这主要是由于算法的搜索范围被限制。路网节点坐标是指空间节点在地图中的实际位置。在路径搜索的过程中，如果起始节点和目的节点是已知的，空间分布可以测量最短路径。节点是否在搜索路径上需要考虑启动节点和目标节点在空间中的关系。根据概率观点，最短路径是最有可能包含由起始节点到目的节点的路线。因此，有必搜索区域是有必要的。
这里我们提出了一种最短路径算法，为了提高算法的性能动态限制搜索区域。 这个算法的原则是：每个阶段分析节点的分布空间关系。 节点分为几个阶段，基于搜索的实际空间分布过程中，这些节点已经生成但没有扩大。 在路径搜索过程中，节点决定是否加入该区域并屏蔽不可能节点的最短路径并删除它们。 限制搜索区域可以减少搜索空间，提高算法效率。 但是这种方法不完整，我们需要进一步适应所有节点的使用搜索区域。 如果找不到最佳路径，搜索范围应适当扩大。
3.4改进Dijkstra算法的实现
在改进的算法中，我们使用邻接表存储路网拓扑的网络数据，使用二进制堆存储生成的节点，使用二进制链表存储节点的生成和开发。假设s是起始节点，g是目标节点，A是限制搜索区域。 设置节点计数器C1，C2和C3表示区域P1，P2内的节点数和P3。 区域P1，P2和P3是三个非重叠限制搜索区域。 添加数据字段节点列表显示节点区和指针保护解。此外，在筛选中增加新的二进制堆的过程操作，找到X所属的区域，节点计数器的相应区域加1，实施流程图如下。
图4 改进的Dijkstra算法
调用改进的Dijkstra算法与调用传统Dijkstra算法相同。 它只需要输入起始节点和目的地，以及网络拓扑。
结构矩阵是得出从起点到目的地节点的最短路径距离。 主要的Matlab编写的最优算法程序
如下图所示。可以看出，算法只做一次圈，并且如果目的地节点不是最后标记的节点，算法减少循环小于n倍，改善操作时间复杂性，效率大大提高。 目的节点被设置为结束，所以算法的准确性得到保证。
3.5实验结果
（1）我们使用GoogleMap离线地图验证实验结果。 通过使用最低成本搜索路径模型，Mobile MapWidget表现良好，在最优路径生成过程在Eclipse仿真器测试成功，平均响应时间为0.56秒，而传统算法需要1.36秒。 该算法的时间复杂度优于Dijkstra算法。 使用邻接列表和二进制堆，改进Dijkstra算法可以快速找到相邻节点动态限制搜索区域，提高效率，缩短优先级队列的运行和操作时间。 如果起始节点和目标节点在地图区域的边界，搜索区域不能完全包含所有节点求解路径，需要增加节点数。 在大多数情况下，改进算法性能表现比传统算法更好。
（2）以运输网络为例说明改进算法比传统的Dijkstra算法好，图6是一个简化的本地城市交通网示意地图。
图5简化的流量网络图
图6网络子图（a）
图7网络子图（b）
假设源节点为n1，目的地为n10，如果使用Dijkstra算法直接可以获得n1-n2-n4-n6-n10的最短路径，显示传统的Dijkstra算法是可行的，但是路径搜索过程需要搜索108次。同改进的Dijkstra算法比较，按照行分子图法，我们连接直线在n1和n10之间，将n4和n5作为断点。将网络图分为两个子图，如如图6和7所示。然后用Dijstra算法分别计算两个子图，最后得到n1-n2-n4-n6-n10的最短路径，但整体过程只有40次。实验分析显示改进了的Dijkstra算法道路搜索数量降低显着，Dijkstra提高了系统运行的效率。
（3）性能测试
表1显示了不同显示负载和不同时间的实验结果
表I系统负载测试
|
每类培训样本数字 |
峰值请求比率( % ) |
峰值操作成功率( % ) |
|
15 |
100 |
100 |
|
60 |
98 |
98 |
|
150 |
lt;
剩余内容已隐藏，支付完成后下载完整资料 资料编号：[27570]，资料为PDF文档或Word文档，PDF文档可免费转换为Word |
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
