共查询到18条相似文献,搜索用时 140 毫秒
1.
2.
岑文杰 《大众科学.科学研究与实践》2007,(2)
近年来,随着交通系统的建设和我国物流事业迅速发展。一个信息化、自动化、一体化的物理信息系统已是势在必行。它带给企业的不单单是便捷,还有巨大的经济利益。为了解决运输货物中最佳路径及方式的选择。 相似文献
3.
本文介绍了求最短路径的迪杰斯特拉算法和弗洛伊德算法,并以地理信息数据为基础,以网络模型图为背景,利用弗洛伊德算法建立邻接矩阵D和路径矩阵P,最终求出任意两个位置的最短路径以及中间所经过的中转点。 相似文献
4.
交通问路系统中最短路径的新算法 总被引:7,自引:2,他引:5
傅冬绵 《华侨大学学报(自然科学版)》2001,22(2):139-142
研究交通线路中的最短路径算法,应用图论中的广度优先搜索思想,给出优先队列的进出队方式,提供一种有效的最短路径的新处,该算法简洁,运算速度快,效果好,并在实际应用中取得了证明。 相似文献
5.
道路网络中最短路径的算法与实现 总被引:5,自引:0,他引:5
最短路径算法是地理信息科学与计算机科学等领域的研究热点。本文从网络分析的理论基础及拓扑性质出发,提出了一种适于最短路径算法的空间数据组织方式。结合道路网络的特点,在构造邻接结点矩阵来表达网络结构的基础上,运用优化的迪杰斯特拉(Dijkstra)最短路径算法,在电子地图环境下实现了道路网络中任意两结点间最短路径的快速解算与刷新。 相似文献
6.
针对单源最短路径Dijkstra 算法效率低的问题, 基于地理信息系统(GIS: Geographic Information System),提出距离均衡的社区分析网络分割方法。将GIS 中道路网络分割降解为距离均衡的社区网络, 再利用限制分层算法, 通过淘汰不太可能出现在最短路径上的节点, 限制GIS 中最短路径的搜索区域, 以降低算法的复杂度。实验结果表明, 优化后的算法可有效减少搜索节点数, 与经典算法相比, 其运行效率有所提高。 相似文献
7.
针对多工种交叉作业频繁、环境时常变化、场地狭窄、明火作业多的建筑工程施工现场,本研究以疏散时间为目标函数建立其人员疏散时间模型,基于疏散时间模型以疏散时间最短为目的提出疏散路径优化模型,并利用修正的 迪杰斯特拉(Dijkstra)算法求解模型,同时结合BIM(building information model)4D模型和Anylogic软件以及某在建楼房案例对模型进行仿真模拟验证分析。由仿真模拟结果可知,疏散时间模型计算出的疏散时长与模拟疏散时长吻合度较高,使用经优化后的疏散路径疏散,能够在一定程度上较大幅度节约紧急情况下建筑工程施工现场劳务人员的疏散时间,提高施工阶段的安全管理效率,且在一定疏散人数范围内,优化程度随疏散人数增加而增长。 相似文献
8.
余金山 《华侨大学学报(自然科学版)》1984,(2):99-103
本文给出最短路径问题的一种算法——解答图算法。它是一种十分有效的算法。对于边的数目为n×(n-1)的图(n为图的顶点数),本算法具有与Dijkstra算法同样的性能。而对于边稀疏的图,本算法在时间和空间两方面都优于Dijkstra算法,与Dijkstra算法阳比较,图的边数越少,本算法所需的存贮空间也越少,而其执行速度却越高。文中分析了时间和空间的复杂件,并给出几个实际结果。 相似文献
9.
在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高. 相似文献
10.
关于最短路径算法 总被引:2,自引:0,他引:2
肖金声 《中山大学学报(自然科学版)》1987,(3)
本文先为两个经典的最短路径算法补充具体路径的保留办法。然后,提供一个便于实现的求有向图两点间所有路径的算法. 相似文献
11.
最短路径算法是计算机科学与地理信息科学领域的研究热点。本文对常用的最短路径标号算法进行了分析,并讨论了优化算法的方法。 相似文献
12.
大规模网络最短路径算法的优化及实现 总被引:1,自引:0,他引:1
求解大规模复杂网络的最短路径问题由于其计算速度慢、需耗费的存储空间大,是与地理信息相关的应用系统经常遇到的瓶颈问题.在深入分析各种常用最短路径算法基础上,基于经典Dijkstra算法,从时间和空间优化角度,实现一种计算任意2点间最短路径的优化算法.初步实验表明,优化后的算法在处理大规模复杂网络的最短路径问题时比经典Dijkstra算法在计算时间上缩短了80%,在耗费的存储空间上减少了将近一倍. 相似文献
13.
针对STEP-NC(standard for the exchange of product data, STEP ; STEP-compliant numerical control,STEP-NC)复杂型腔的刀具路径生成问题,本文提出了一种基于图论和改进Dijkstra算法的STEP-NC复杂型腔最短刀具路径生成方法.在该方法中,首先根据走刀行距和基本元素的等距偏置,生成STEP-NC复杂型腔封闭等距环.然后,基于图论得到封闭等距环的赋权有向图.最后,利用改进的Dijkstra算法生成STEP-NC复杂型腔最短刀具路径.通过实例验证了所提出方法的可行性和有效性. 相似文献
14.
一种基于城市应急系统的最短路径算法 总被引:1,自引:0,他引:1
城市应急系统(如119火警、110报警以及120急救等)要求在事故发生时,救援者能以最快的速度到达事故现场,而"最短路径"问题是满足该系统需求的关键技术之一。正是针对城市应急系统的这种特点,以消防信息系统为例,在对现有最短路径算法分析研究的基础上,结合G IS技术的应用,提出了一种实时、高效的最短路径生成算法。 相似文献
15.
通过对问题的分析和假设,建立了线性规划的数学模型,运用Dijkstra算法提供了一个最优的方案,采用Lingo软件得到了全局最优解。 相似文献
16.
白青海 《内蒙古民族大学学报(自然科学版)》2007,22(2):127-130
利用图论中Dijkstra算法,提出了一种求解交通图最短路径的方案.该方案可以实现全国范围内任意两个主要城市之间的最短路径的求解。 相似文献
17.
一种限制搜索区域的最短路径改进算法 总被引:3,自引:0,他引:3
最短路径算法效率是许多应用领域普遍关注和迫切需要解决的问题。该文在深入分析经典Dijkstra最短路径算法优化途径的基础上,从控制路网规模入手,提出了矩形限制搜索区域的最短路径算法。根据路网分布的特点,采取比值系数分段取值的方法,进一步提高了算法效率。原型系统实验显示了改进算法的高效性和可行性。 相似文献
18.
杜领 《西南师范大学学报(自然科学版)》2013,38(9):094-100
通过对交通调度系统信息分调需求分析,构建交互型Floyd算法模型.基于Floyd算法设计出交通调度系统最短路径,并通过仿真设计和测试运行该程序,程序运行良好. 相似文献