共查询到10条相似文献,搜索用时 15 毫秒
1.
王一剑 《数字社区&智能家居》2009,5(1):182-183
最短路径是GIS应用中的主要问题之一。该文简单介绍了GIS的基本概念.对传统的Dijkstra算法和启发式搜索算法A^*算法进行了详细的探讨,并且说明了各自的特点。 相似文献
2.
改进的Dijkstra算法在GIS路径规划中的应用 总被引:9,自引:0,他引:9
最短路径算法是计算机科学与地理信息科学等领域研究的热点。文章讨论了一种改进的Dijkstra算法,利用本算法根据用户给出的起始结点、必经点序列和目标结点在GIS的交通层网络图基础上进行路径规划,生成满足一定约束条件的最短路径。实际应用分析表明,改进的Dijkstra算法在提高网络系统空间分析效率方面是可行的。 相似文献
3.
Dijkstra算法在GIS中的优化实现 总被引:7,自引:0,他引:7
地理信息系统(GIS)的应用经常涉及最短路径搜索问题。1959年迪杰斯特拉(Dijkstra)提出的Dijkstra算法是最适合网络拓扑中两结点间最短路径搜索的算法之一。本文讨论一般公路交通网络中两结点间的最短路径搜索问题,从核心算法方面对Dijkstra算法进行改进。 相似文献
4.
路径诱导是停车诱导系统中需要解决的关键问题,而路径诱导的本质就是求最短路径,Dijkstra算法可以很好地求解最短路径.传统Dijkstra算法采用邻接矩阵作为存储结构,算法的时间复杂度为O(n2),存在搜索速度慢和浪费空间的缺点.为此,对传统Dijkstra算法进行了改进,采用邻接多重表作为存储结构,采用堆排序法的思想来寻找权值最小的顶点,算法的时间复杂度为O(nlog2n).用改进后的算法在实际地图中进行仿真实验,结果表明,改进后的算法能更快、更有效率地找到两点间的最短路径. 相似文献
5.
6.
改进Dijkstra算法在GIS导航应用中最短路径搜索研究 总被引:3,自引:2,他引:1
研究GIS在电子导航系统应用中的最短路径搜索效率问题。在电子导航系统中对最短路径的搜索效率要求很高。随着城市发展交通线路剧增,传统的基于Dijkstra算法的GIS导航系统不能适应日益复杂的交通线路,存在最短路径搜索效率过低的问题。考虑到GIS空间分布的特性,提出了改进的Dijkstra算法用以解决GIS导航中的最短路径搜索问题。改进算法不仅避免了传统Dijkstra算法逐个节点遍历搜索,而且根据方向优先特性缩小搜索范围,大大减少了搜索工作量,并通过改变搜索节点存储的数据结构提高了最短路径的搜索效率。实验表明,这种改进算法较之传统算法能够有效提高最短路径的搜索效率,满足了电子导航系统对最短路径搜索效率的要求,取得了满意的结果。 相似文献
7.
GIS最短路径分析中Dijkstra算法的优化 总被引:4,自引:0,他引:4
古凌岚 《计算机与数字工程》2006,34(12):53-56
最短路径分析是GIS地理网络分析功能中的一个关键问题。Dijkstra算法是计算最短路径的经典算法,在对该算法分析的基础上,提出了基于面向对象的改进算法,大大降低了内存消耗,搜索效率明显提高。讨论了地理网络的数据存储结构和最短路径算法的具体实现,并通过实例验证表明,该算法是有效可行的。 相似文献
8.
为了有效提高市民出行效率。减小城市资源消耗,优化城市环境,在改进型Dijkstra算法的基础上设计并实现城市公交线路查询系统。Dijkstra算法是图论中求解最短路径问题的一种优秀算法。在Dijkstra算法的基础上.进行对存储结构进行优化、对结点进行分类、对权值进行排序这三大改进.并将改进型Dijkstra算法作为最优公交线路查询算法的核心。以时间最小、费用最小、综合最优这三种需求作为评价标准分别建立数学模型,通过数学模型将搜索两点间的最优路线问题转化成求解两点间的最短路径问题.最后以南昌市的公交路网为例对算法和数学模型进行仿真测试。仿真结果验证算法和数据模型的有效性。 相似文献
9.
10.
游戏开发中智能路径搜索算法的研究 总被引:8,自引:3,他引:8
路径搜索是许多游戏特别是即时战略游戏的核心组成部分,首先介绍了游戏中路径搜索的相关概念。路径搜索的算法有很多,不同的搜索算法有其不同的搜索策略、时间效率、空间消耗与应用场合。分析对比了多种路径搜索算法的运行数据之后,详细讨论了A^*算法。由于游戏中的路径搜索有其自身的特点,针对游戏中路径搜索的具体要求从搜索效率、路径的真实平滑性和动态变化状态空间的适应性等方面对A^*算法进行了优化和改进。 相似文献