共查询到19条相似文献,搜索用时 546 毫秒
1.
网络最短路问题的改进算法 总被引:4,自引:0,他引:4
本文着重研究著名的Dijkstra网络最短路算法的实现效率,提出算法实现的若干技巧,大大提高了Dijkstra最短路算法的适用性和时间空间效率。 相似文献
2.
本文首先介绍最短路问题的数学模型及Dijkstra算法,紧接着采用Dijkstra算法的改进算法——Floyd算法,然后将求城市道路网两点间最短路径目标约束转化为求最短路问题.随之建立最短路模型,并描述了用MATLAB程序进行求解的过程。最后用实例验证了模型和算法的可用性。 相似文献
3.
4.
路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。 相似文献
5.
6.
经典模型及算法可解决固定弧权条件下的最短路问题,然而实际应用中孤权往往是动态的,即弧权依赖时间变化。本文提出一种特殊最短路径算法,即在有向无环网络中最小时间路径算法的一种实现。该算法是一种改进的扩散法,克服了扩散法的一些显著缺点。文中证明了该理论的正确性,最后列举了一个传统算法不能解决的实例,证明了该算算:法的正确性。 相似文献
7.
本文提出一种求解QoS路由问题的新启发式算法,该算法求解基于带宽、时延、丢失率的多约束优化路问题,通过构造评价函数调用最短路算法迭代求解,具有较小的时间复杂度。最后给出的仿真结果证明了算法的有效性。 相似文献
8.
9.
10.
一类问题的描述方式及其算法 总被引:3,自引:0,他引:3
本文给出了一类问题的一种描述方式,这类问题包括有向图的最短路问题、赫夫曼问题、矩阵链问题、汉密顿回路问题等等。在这种描述方式的基础上,给出了一个算法模式,并讨论了如何通过该算法模式得到回溯算法、动态规划算法、分枝限界算法、贪心算法以及启发式搜索算法等等,只要对这个算法模式中的变量给出不同的定义就可以得到求解这类问题中某一具体问题的算法,最后还给出了SIMD模型上的一个并行算法模式,通过该并行算法模 相似文献
11.
以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法,结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想,提出了一种基于桶结构的单源最短路径算法。实验结果表明,该算法与前两种算法相比,具有好的运行时间复杂度和可并行性。 相似文献
12.
基于层次空间推理的公交最优乘车方案 总被引:8,自引:0,他引:8
在比较传统的最短路径算法的基础上,提出了一种基于层次空间推理的、新的、实用的公交最优乘车方案算法。该方法采用快速的搜索策略,可实时搜索查询。并在此基础之上开发公交查询系统,取得了较好的效果。 相似文献
13.
14.
本文提出一种利用栅格法和改进的Dijkstra算法进行机器人路径规划的方法。该方法利用栅格法对机器人的工作环境进行表示,利用改进的Dijkstra算法进行最短路径的搜索。应用该方法在对环境细化到包含10000个栅格节点的情况下,在主频1.7GHZ的计算机上规划路径的时间最长不超过0.3秒。实践证明该方法具有实时性和路径最优性。 相似文献
15.
本文提出一种利用栅格法和改进的Dijkstra算法进行机器人路径规划的方法。该方法利用栅格法对机器人的工作环境进行表示,利用改进的Dijkstra算法进行最短路径的搜索。应用该方法在对环境细化到包含10000个栅格节点的情况下,在主频1.7GHZ的计算机上规划路径的时间最长不超过0.3秒。实践证明该方法具有实时性和路径最优性。 相似文献
16.
动态网络与传统的网络模型相比更具有现实意义,具有广泛的应用领域。本文对动态网络模型进行了描述,用实例证明了著名的Dijkstra算法在动态网络中不能有效地求解最短路径问题,提出了一种用带杂交算子的蚁群算法来求解动态网络最短路径问题的新算法。此算法不仅能够以较大的概率找到最优解而且对网络没有任何约束条件,即对离散
散和连续的动态网络模型都有效,而且用实例证明了算法的稳定性。 相似文献
散和连续的动态网络模型都有效,而且用实例证明了算法的稳定性。 相似文献
17.
考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论:在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。 相似文献
18.
19.
目前研究最短路径的算法,多数只是针对从起点出发到达终点的情况。如果限制这条最短路径必须要经过某些指定的中间节点,则现有的一些算法就不再适用了。基于Dijkstra算法和贪心理论,给出了解决此类问题的方法。将相关节点集拆分成三个子集,分别求连通三个子集的局部最短路径,进而形成全局待选最短路径,通过筛选得到目标路径。通过理论分析算法的时间复杂度和实际编程实验确认了该算法的有效性。 相似文献