共查询到19条相似文献,搜索用时 250 毫秒
1.
许正凯 《数字社区&智能家居》2008,(2):667-671
最短路径算法问题是计算机科学、运筹学、地理信息系统和交通导航系统等领域研究的一个热点。Dijkstra算法用于计算一个节点到其他所有节点的最短路径,得出最短路径的最优解,但它的效率是一个很大的问题。组合算法在Dijkstra算法的基础上.利用层次策略与准备算法,计算出最短路径,解决了常用最短路径算法中相关数据量大、耗用资源多、执行效率低等关键问题。 相似文献
2.
XU Zheng-kai 《数字社区&智能家居》2008,(4)
最短路径算法问题是计算机科学、运筹学、地理信息系统和交通导航系统等领域研究的一个热点。Dijkstra算法用于计算一个节点到其他所有节点的最短路径,得出最短路径的最优解,但它的效率是一个很大的问题。组合算法在Dijkstra算法的基础上,利用层次策略与准备算法,计算出最短路径,解决了常用最短路径算法中相关数据量大、耗用资源多、执行效率低等关键问题。 相似文献
3.
基于ITS的加速最短路径搜索算法研究 总被引:2,自引:0,他引:2
文章从路径搜索的基本原理入手,首先介绍了经典Dijkstra最短路径搜索算法,分析比较了基于堆结构和基数堆结构的Dijkstra算法的搜索效率,从而提出了采用多层地图和分级搜索技术来实现对最短路径搜索空间的控制策略和算法,结合湛江市区电子地图进行对比实验,该算法有效地解决了最短路径搜索效率的问题。 相似文献
4.
5.
并行问题和最短路径问题已成为一个热点研究课题,传统的最短路径算法已不能满足数据爆炸式增长的处理需求,尤其当网络规模很大时,所需的计算时间和存储空间也大大的增加;MapReduce模型的出现,带来了一种新的解决方法来解决最短路径;GPU具有强大的并行计算能力和存储带宽,与CPU相比具有明显的优势;通过研究MapReduce模型和GPU执行过程的分析,指出单独基于MapReduce模型的最短路径并行方法存在的问题,降低了系统的性能;论文的创新点是结合MapReduce和GPU形成双并行模型,并行预处理数据,针对最短路径中的数据传输和同步开销,增加数据动态处理器;最后实验从并行算法的性能评价指标平均加速比进行比较,结果表明,双重并行环境下的最短路径的计算,提高了加速比。 相似文献
6.
研究交通道路中的最短路径优化问题,由于城市道路拥塞严重,在导航过程中,为了尽快达到日的地,必须选择最短路径进行行驶.传统搜索算法计算复杂度高,寻优效率低,不利于实际优化.为解决最短路径优化问题,提出了一种蚁群算法的GIS中的最短路径优化方法.将路径的起点当成蚁群的巢,终点当成蚁群要寻找的食物,蚂蚁通过信息法指导搜索方向,并通过蚂蚁之间的相互协作达到终点.仿真结果表明,提出的优化方法降低了计算复杂度,更快地找到最短路径,提高了找到最短路径的平均正确率,为解决GIS中的最短路径优化问题提供了一种新的有效途径. 相似文献
7.
8.
9.
公路交通管理中,最短路径是进行车辆路径优化的基础.论文在简单分析了一些经典的最短路径算法和这些最短路径算法单独应用于车辆路径优化存在的局限性的基础上,提出了一种改进A*算法的方法[1~2],并用它来解决城市间道路网中实时最短路径问题,并以实例加以阐述. 相似文献
10.
Dijkstra算法中的多邻接点与多条最短路径问题 总被引:4,自引:0,他引:4
Dijkstra算法是图论中求取最短路径的经典算法。列举并分析了Dijkstra算法及其伪码,为了深刻理解Dijkstra算法,列举了几种错误观点并加以纠正。分析发现,根据Dijkstra算法,最短路径上的某个顶点的前面,可能有多个邻接点;从开始点到某个顶点之间,可能存在多条权重相同的最短路径。对于上述多邻接点问题与多条最短路径问题,Dijkstra算法并没有涉及。分析了多邻接点问题与多条最短路径问题的成因,提出解决方案,对Dijkstra算法进行了改进,给出了改进之后的算法与伪码,分析了算法的时间复杂度,并用c语言编码实现。实验结果表明,改进之后的Dijkstra算法可以有效解决多邻接点问题与多条最短路径问题。 相似文献
11.
王华 《计算机与数字工程》2012,40(4):22-23,129
通过实例对比分析Dijkstra算法和Floyd算法特点及适用性,选用Dijkstra算法计算物流配送的最短路径,给出Dijkstra算法求解最短路径问题的实现方法及步骤并集成了一个小型系统,使用随机生成的数据进行最短路径求解,将生成的最短路径在随机生成的图上进行演示,并计算出两种算法执行时间,以期对物流配送中点对点的最短路径有所帮助。 相似文献
12.
13.
路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。 相似文献
14.
求解最短路径问题的Lotka-Volterra回复式神经网络模型 总被引:1,自引:0,他引:1
有向图的最短路径(SP)问题是一个优化问题。通过构造有向图的最短路径问题的能量函数,提出了一种Lotka-Volterra (LV)回复式神经网络(RNN)模型,用于求解有向图的最短路径。当LV神经网络迭代收敛到稳定吸引子时,对应的能量函数也达到其能量最小点。因此,通过稳定吸引子可以获取最短路径。实验结果表明,利用LV神经网络模型可以有效地求解有向图中任意两个顶点之间的最短路径。 相似文献
15.
This paper studies a new kind of dynamic multi-stage facility layout problem under dynamic business environment, in which new machines may be added into, or old machines may be removed from the plant. We define this problem first on the basis of unequal area machines and continual presentation of layouts. Compared with nodes and arcs of the flow chart, we convert this problem into a shortest path problem by studying its cost function and machine adding/removing heuristic rules, and the corresponding mathematical model for this problem is established. An auction algorithm is proposed here to solve the shortest path problem. Finally, a shortest path based simulated annealing algorithm is presented to solve the optimization problem. Parameters of the SP based SA algorithm are discussed to improve the performance of the algorithm. Some cases are used to verify the proposed algorithm. 相似文献
16.
17.
This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log 2 (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log2 (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks 相似文献
18.
动态网络与传统的网络模型相比更具有现实意义,具有广泛的应用领域。本文对动态网络模型进行了描述,用实例证明了著名的Dijkstra算法在动态网络中不能有效地求解最短路径问题,提出了一种用带杂交算子的蚁群算法来求解动态网络最短路径问题的新算法。此算法不仅能够以较大的概率找到最优解而且对网络没有任何约束条件,即对离散
散和连续的动态网络模型都有效,而且用实例证明了算法的稳定性。 相似文献
散和连续的动态网络模型都有效,而且用实例证明了算法的稳定性。 相似文献
19.
最佳排序路径查询,是智能交通中的热点问题.在实际的应用中,由于最佳排序路径查询有许多限制条件,现有的算法不能有效地解决动态网络中受限制的路径查询问题.为了解决动态网络中最佳排序路径查询问题,用规则表示每个限制条件,提出了一种新的最佳排序路径查询形式,即多规则的最短路径查询.提供了统一的框架,该框架包含了路径集合查询和最短路径查询.在路径集合查询部分,为了高效地查询出满足多规则的路径集合,在广义规则树的基础上,提出一种新的树的遍历方式,即树的继承全遍历;并基于树的继承全遍历思想,提出一种剪枝技术,对路径集合进行删减,最后求得候选路径集合.在最短路径查询部分,提出一种基于动态阈值的最短路径搜索方法.通过两个真实的动态道路网络的实验验证,所提出的算法能够高效地解决多规则的最短路径查询问题. 相似文献