共查询到20条相似文献，搜索用时 31 毫秒
1.
讨论网络中结点间路径的问题是图论中的基本问题之一，而求其中任两结点间的最短径已有一些方法，也可采用延长算法，即求出两点间的所有路径，算出其路径权值，从而求得最短路径。最短路径在实际中有着广泛的应用，在实际中有一些些求最优的问题，可化为网络中最短路径问题，从而得到最优的第一方案。本提出将任两结点间的不同路径按其权值分布不同阶短路径的概念，并基于Dijkstra算法和路径延长算法，给出根据给定的阶值λ，求相应的λ阶短路径Z算法，可同时获得最优的第一方案、第二方案、…、第λ方案。算法简单、便于手算，并易于计算机处理。 相似文献
2.
讨论网络中结点间路径的问题是图论中的基本问题之一 ,而求其中任两结点间的最短路径已有一些方法 ,也可采用延长算法 ,即求出两点间的所有路径 ,算出其路径权值 ,从而求得最短路径。最短路径在实际中有着广泛的应用。在实际中有一些求最优的问题 ,可化为网络中最短路径问题 ,从而得到最优的第一方案。本文提出将任两结点间的不同路径按其权值分成不同阶短路径的概念 ,并基于 Dijkstra算法和路径延长算法 ,给出根据给定的阶值 λ,求相应的 λ阶短路径 Z算法 ,可同时获得最优的第一方案、第二方案、…、第 λ方案。算法简单 ,便于手算 ,并易于计算机处理 相似文献
3.
为解决城市物流配送最优路径选取问题,从城市道路网络空间分布形态出发,综合考虑影响最短路径求解的多种因素,建立动态路网模型,并对经典最短路径算法进行改进。结合道路网络的几何性质,以实际路网为例,标记各路段交叉口作为结点,将实际路网部分转化为Manhattan型结构,同时分析相邻交叉口间距离和平均人口对路径选取的影响,通过重新定义考虑双重权重的最短路径权重与参考值[η],对算法进行改进。利用改进算法迭代计算获得最短路径解,并对多个解的情况进行分析,分别比较两条路径的[η]值,并选取其中[η]值较大的一条路径作为最优规划路径。实验结果表明,路网结构转化及算法改进不仅可简化计算,同时参考值[η]的引入还可有效解决最短路径不唯一时最优路径的选取问题。 相似文献
4.
求两点沿自由曲面最短路径的关键是正确选择两点间沿曲面的路径.粒子群优化算法(PSO)是一种全局性的概率搜索算法,它在整个问题空间实施搜索,可以得到问题的全局最优解.将粒子群优化算法的思想引入到路径寻优中,采用圆弧逼近法进行初始逼近,提出了解决自由曲面最短路径的随机搜索算法.最后给出了数值实例,结果表明该算法具有容易实现、运算量小等特点. 相似文献
5.
本文首先从轨道交通和常规交通的衔接规划的视角,阐述了求解K最短路径问题在公交线网优化中的意义。然后在Dijkstra最短路算法的基础上,创造性地引入了多个P标和多个T标来记录起点到该节点的K短路径及其上界,使改进后的算法成功求解K最短路径。最后用C语言对算法进行实现,并随机产生测试数据进行算法测试,测试结果表明了该算法的计算效率和应用前景。 相似文献
6.
张岩 《西安文理学院学报》2014,(4):32-35
首先引出图论模型这一基本概念,然后简单介绍了最短路问题的分类,在此基础上具体阐述并且分析了求最短路径的常用算法——Dijkstra算法、Floyd算法和Ford算法.最后主要对Dijkstra算法在公交网络中的应用进行了研究和分析,并且列举了最短路算法在其他领域中的一些应用. 相似文献
7.
对于单源点最短路径问题可用Dijkstra算法进行实现,对两点间(单源点、单目的点)最短路径问题则用A~*算法实现。重点对A~*算法的实现作了细致的讨论,并用A~*算法解决了八数码问题。 相似文献
8.
基于最短路径优化问题Dijkstra算法程序的设计和实现 总被引：1，自引：0，他引：1
在九十年代公认的求最短路径的最好的算法是由E.W.Dijkstra于1959年提出的标号算法,此算法可以很好地解决求最短路径问题,但是该算法采用手工求解,计算量大且很繁琐.本文在此算法的基础上采用矩阵运算的方法,从而实现了完全应用程序求解,在很大程度上解决了上述问题所遇到的难点,使求最短路径和最短距离这两个较复杂的问题变得非常容易求解. 相似文献
9.
10.
连顺金 《黎明职业大学学报》2001,(2):36-38
提出了求关键路径的另一方法，即利用我们所熟悉的求每对顶 间最短路径的Floyd算法来实现求AOE－网中的关键路径，使得求关键路径的算法在形式上简单些，更易让读理解、掌握。 相似文献
11.
为解决暑假旅行人员以成本最小化为目标的最佳旅行路线选择难题,基于路径优化理论（VRP）及粒子群算法,设计了以暑假旅游路线最短为优化目标的数学模型,采用计算机编程技术,设计了求解该优化模型的粒子群算法,并选择案例对模型及算法进行了验证。案例应用结果表明,该模型和算法能够有效解决最佳旅游路线选择难题,正确率达98%。基于VRP理论及粒子群算法的最短路选择模型不仅能够快速求解出最优路径方案,还能够有效降低人工经验选择最短路径中存在的误差。 相似文献
12.
13.
李兴芳 《四川职业技术学院学报》2011,21(6):101-103
将动态时间弯曲距离（DTW）的差异矩阵一一对应于点阵,按DTW定义的行走规则对该点阵连线定向,使所对应点阵成为一个有向图,然后使用一个加权技巧对该有向图的边加权后得到一个加权有向图,于是把求DTW的精确计算问题等价地转化为求一个有向图起点到终点的最短路长,从而使图论中求两点间最短路径的方法如目前公认的经典Dijkstra算法均可用于求DTW,因此间接地找到了精确计算DTW的一个新方法. 相似文献
14.
解决几何最值问题的理论依据一般是几何中的一些公理和定理,如两点间线段最短公理、垂线段最短定理等.求解时要先画出最值位置的状态图,转化为求线段长度问题,也可以通过建模转化为方程、函数、不等式等问题,如转化为二次函数模型,利用顶点式来求最值,转化一次函数问题,通过不等式限定自变量的取值范 相似文献
15.
探索使用不确定理论中的期望值模型处理最短路径问题,将网络中有向边的权值描述为不确定变量,提出了利用99表表示的期望值简化最短路径通用模型,从而把模型直接转化为确定的最短路径问题模型,用传统方法如Dijkstra算法等即可求解.最后通过算例证明了模型的可行性与有效性. 相似文献
16.
17.
为解决经典Dijkstra算法存在搜索效率低，并可能发生组合爆炸问题，提出了利用动态规划技术改进的Dijkstra算法。运用由后向前分段逐步求解的方法，降低每一段的运算法，从而达到提高效率的目的。理论分析及计算机模拟结果表明，改进的Dijkstra算法在提高搜索效率、减少组合爆炸的可能性以及降低运算法等方面，明显优于经典的Dijkstra算法。在求单源最短路径问题上有实用价值。 相似文献
18.
提出了平面散乱数据点集曲线重构的最短路逼近算法,它创造性地把散乱数据点集的曲线重构问题转化为图论中带权连通图的最短路求解问题。新方法根据散乱数据点的分布情况构造平面上的势函数,并对散乱数据点集进行Delaunay三角化。根据势函数对Delaunay三角网格的每条边赋一个权值,生成带权连通图。在带权连通图上生成重构曲线两端点间的逼近路径,简化逼近路径,找出该路径上的关键点。以关键点为控制点,势函数值为权值,生成有理B样条曲线。最短路逼近算法在实验中取得很好的效果,成功解决了移动最小二乘法难以解决的具有尖点特征的数据点集的曲线重构问题。 相似文献
19.
20.
受顶点数限制的最短路径计数问题在复杂性网络的社区识别、介数计算等方面有重要应用,但目前对其研究较少。Bellman算法能有效解决边带有负权且无负圈的最短路径问题,但对结点数受限定的最短路径的计数问题,直接用Bellman公式进行求解,则存在重复计数的问题。对Bellman递推关系式进行改进,建立新的求结点数受限制的最短路径的递推关系式和求结点数受限制的最短路径数目的递推关系式,从而给出了结点数受限定的最短路径计数问题的一种求解算法,并验证了其正确性。 相似文献