共查询到19条相似文献,搜索用时 125 毫秒
1.
ZHANG Hong-ke 《数字社区&智能家居》2008,(26)
迪杰斯特拉算法是图论中计算最短路径的经典算法,但在实际使用中该算法耗费大量的计算时间和存储空间。通过对传统迪杰斯特拉算法的深入分析,在计算时间和存储空间上对该算法提出了一种新的优化方案,并给出了优化后的详细算法。改进算法从消除冗余计算和冗余存储入手,采用链表数组作为存储结构。经算法复杂度分析,优化后的迪杰斯特拉算法在求解最短路径问题时在时间和空间复杂度上都有明显的提高。该优化算法操作性强,具有一定的实用价值。 相似文献
2.
扇形优化Dijkstra算法 总被引:2,自引:0,他引:2
Dijkstra算法无数次遍历所有的临时标记结点,无疑成为该算法的一个瓶颈。在分析Dijkstra算法的基础上,结合平面网络的特点,从限制搜索范围和限定搜索方向两方面着手,在扇形区域内寻找最短路径,从而完成对Dijkstra算法的优化。优化算法基于有损算法,抛弃寻找最短路径时概率较小的顶点,直接寻求在方向和位置上趋向终点的顶点。它根据用户给出的起始顶点与目标顶点以及搜索的扇形角度查找最短路径。因此,在优化算法中,频繁遍历的顶点数量大幅度减少,提高了算法的速度和运行效率。 相似文献
3.
Dijkstra的一种改进算法 总被引:20,自引:3,他引:20
在Dijkstra算法的基础上,该算法使用了一些独特的数据结构(如:前趋表和最短路径表);使用该算法能高效率地求出图中一个顶点到其它各顶点的所有最短路径。用C语言设计了相应程序验证了此算法。 相似文献
4.
Dijkstra算法在GIS中的优化实现 总被引:7,自引:0,他引:7
地理信息系统(GIS)的应用经常涉及最短路径搜索问题。1959年迪杰斯特拉(Dijkstra)提出的Dijkstra算法是最适合网络拓扑中两结点间最短路径搜索的算法之一。本文讨论一般公路交通网络中两结点间的最短路径搜索问题,从核心算法方面对Dijkstra算法进行改进。 相似文献
5.
Dijkstra算法是计算最短路径的经典算法,在对该算法分析的基础上,对其进行了优化和改进。其一是对数据存储方式进行了改进,其二是对辅助向量采用堆排序改进。通过优化降低了内存消耗,搜索效率明显提高。 相似文献
6.
7.
8.
一种改进的Dijkstra算法的分析及程序实现 总被引:1,自引:0,他引:1
Dijkstra算法是求有向图中从某一源点到其余各点最短路径的算法。本文通过对传统的Dijkstra算法进行分析,提出一种改进算法,经理论分析,对于顶点数较多而边数较少的有向稀疏图来说,在求最短路径时能够大大提高算法的运行效率。 相似文献
9.
10.
在深入分析传统Dijkstra算法的基础上,提出了利用基于k叉堆的优先级队列对算法进行改进的思想,并对3种可合并替进行了比较,从理论上证明了四叉堆在k叉堆中的最优性,设计了基于四叉堆优先级队列及逆领接表,顾及路段方向阻抗的改进型Dijkstra最短径算法,将Dijstra算法复杂度降为O(nlogn)。 相似文献
11.
插入排序算法的双链表模拟 总被引:4,自引:2,他引:2
主要讨论了插入排序算法,并用双链表模拟实现了该算法。在WIN-TC下面调试通过程序并得到正确的执行结果,从而直观地反映出插入排序算法的排序过程。 相似文献
12.
在人工智能传统的搜索方法中,一直是将OPEN表和CLOSED表分开的。这不仅增加了搜索算法的复杂性,久而久之,也许禁锢了人们的思想。文章试图改变这种状况,提出了一种与众不同的新思路,巧妙地将OPEN表和CLOSED表合二为一,减少了一些工作量,在一定程度上降低了算法的复杂性。 相似文献
13.
14.
15.
本文研究了我国电子商务环境下物流配送存在的问题,提出了改进对策.关于物流路径的选择有很多方法,本文将Dijkstra算法引入到物流配送,达到了费用最小的目的,提高了工作效率,因此该方法合理有效. 相似文献
16.
基于Dijkstra算法的网络最短路径分析 总被引:17,自引:1,他引:17
最短路径分析是网络分析最基本的功能之一。Dijkstra算法是目前公认的较好的最短路径算法。文章通过对Dijkstra算法运行速度分析,在该算法的基础上采用二叉树结构来改进Dijkstra算法,在一定程度上优化了最短路径的计算过程,并提高了算法的分析效率,实际数据测试也表明了该算法的可行性。 相似文献
17.
灾害决策系统中,核心安置点的选择对救灾工作效率影响重大;分析常用的最短路径搜索方法,选用Dijkstra算法并对其进行改进,计算选取到达最远安置点最近的安置点作为核心安置点。实验结果表明,该方法具有良好的实用性。 相似文献
18.
罗霄 《数字社区&智能家居》2006,(36)
在游戏开发过程中常常面临多条通路存在却不知道应该选择哪条路径到达终点效率最高的问题。本文应用人工智能中的路径搜索算法将这一问题的求解过程转化为在状态空间中从初始状态到目标状态寻找路径的过程。在寻找最佳路径的过程中,应用启发式搜索和估价函数,对每一个搜索的位置先进行评估,从而得到最好的起始点,再从这个位置依次搜索直到目标,最终发现到达终点的最便捷途径。同时结合实际应用中遇到的问题,给出了该算法的进一步优化解决方案。 相似文献