共查询到20条相似文献，搜索用时 46 毫秒
1.
2.
3.
本文从城市道路网络的实际特点出发，对城市电子地图的道路网进行网络分析，将最佳路径搜索问题转化为图论中的最短路径搜索问题，通过对最短路径搜索算法的分析，实现了一种求解城市道路网两点间最短路径的算法，将求城市道路网两点间最短路径目标约束转化为求最短路问题，随之建立最短路模型，并描述了用Matlab程序进行求解的过程。最后用实例验证了模型和算法的可用性。 相似文献
4.
基于最短路径优化问题Dijkstra算法程序的设计和实现 总被引：1，自引：0，他引：1
在九十年代公认的求最短路径的最好的算法是由E.W.Dijkstra于1959年提出的标号算法,此算法可以很好地解决求最短路径问题,但是该算法采用手工求解,计算量大且很繁琐.本文在此算法的基础上采用矩阵运算的方法,从而实现了完全应用程序求解,在很大程度上解决了上述问题所遇到的难点,使求最短路径和最短距离这两个较复杂的问题变得非常容易求解. 相似文献
5.
讨论网络中结点间路径的问题是图论中的基本问题之一 ,而求其中任两结点间的最短路径已有一些方法 ,也可采用延长算法 ,即求出两点间的所有路径 ,算出其路径权值 ,从而求得最短路径。最短路径在实际中有着广泛的应用。在实际中有一些求最优的问题 ,可化为网络中最短路径问题 ,从而得到最优的第一方案。本文提出将任两结点间的不同路径按其权值分成不同阶短路径的概念 ,并基于 Dijkstra算法和路径延长算法 ,给出根据给定的阶值 λ,求相应的 λ阶短路径 Z算法 ,可同时获得最优的第一方案、第二方案、…、第 λ方案。算法简单 ,便于手算 ,并易于计算机处理 相似文献
6.
随着当前城市规模的不断扩大,交通网络变得越来越复杂,最短路径问题的求解会花费更多的时间资源。为了提高最短路径求解的实时性,分别在MPI和OpenMP环境下设计了并行的最短路径求解算法,在结点数众多的大规模路网中能够明显地提高运行效率,减少路径查询计算时间。 相似文献
7.
讨论网络中结点间路径的问题是图论中的基本问题之一，而求其中任两结点间的最短径已有一些方法，也可采用延长算法，即求出两点间的所有路径，算出其路径权值，从而求得最短路径。最短路径在实际中有着广泛的应用，在实际中有一些些求最优的问题，可化为网络中最短路径问题，从而得到最优的第一方案。本提出将任两结点间的不同路径按其权值分布不同阶短路径的概念，并基于Dijkstra算法和路径延长算法，给出根据给定的阶值λ，求相应的λ阶短路径Z算法，可同时获得最优的第一方案、第二方案、…、第λ方案。算法简单、便于手算，并易于计算机处理。 相似文献
8.
黄颖 《河南广播电视大学学报》2006,19(4):61-62,65
提出一种基于K-均值聚类的TSP演化算法。该算法利用K-均值聚类技术,将TSP分为一些简单的TSP问题。在寻求最短路径时,首先所有结点用其聚类中心去代替,以聚类中心为结点构造TSP演化算法;其次,对于每一聚类,可寻求其距前面的聚类和后面的聚类最近的两结点之间的最短距离,若其中的结点较多,则再次演化得到其最短路径,若结点较少,则可用warshall算法可得到最短路径;最后对获得的最短路径进行剪接操作,可得到其更优解。 相似文献
9.
为解决城市物流配送最优路径选取问题,从城市道路网络空间分布形态出发,综合考虑影响最短路径求解的多种因素,建立动态路网模型,并对经典最短路径算法进行改进。结合道路网络的几何性质,以实际路网为例,标记各路段交叉口作为结点,将实际路网部分转化为Manhattan型结构,同时分析相邻交叉口间距离和平均人口对路径选取的影响,通过重新定义考虑双重权重的最短路径权重与参考值[η],对算法进行改进。利用改进算法迭代计算获得最短路径解,并对多个解的情况进行分析,分别比较两条路径的[η]值,并选取其中[η]值较大的一条路径作为最优规划路径。实验结果表明,路网结构转化及算法改进不仅可简化计算,同时参考值[η]的引入还可有效解决最短路径不唯一时最优路径的选取问题。 相似文献
10.
排列计数问题是组合数学中主要而又基本的问题,一般的排列计数问题采用映射、分类、分步、捆绑、插空等方法即可解决,但有些问题（特别是数学竞赛中涉及到的问题）用构建递推关系的方法会更为简洁．本文将通过几个经典问题,讲解用递推方法求排列计数问题的基本策略． 相似文献
11.
在导航过程中,当最短路径道路上有拥挤、堵塞或中断的情况发生时,利用Dijkstra最短路径算法中的最短路径长度和前驱结点两个辅助向量数据,可迅速在其邻接结点中选择一条新的最短路径。实现了最短路径的动态调整,从而可以尽快地到达目的地。 相似文献
12.
"定弦定角"类试题在近几年来各地中考试题中屡屡出现,进而发展到现在九年级上学期的期末试题中也屡见其身影,笔者对近几年的定弦定角问题作了一些研究,按题目求解将它分成定弦定角求半径、定弦定角求路径长、定弦定角求线段最值、定弦定角求面积最值等四类问题加以研究,通过四种问题的求解分析帮助学生理解定弦定角问题,提高学生分析解决此类问题的能力. 相似文献
13.
14.
叙述使用网络技术中的最短路径法求解教育装备全寿命周期最低费用的方法,为使实用性和可操作性更强,专门介绍求最短路径的Dijkstra算法。 相似文献
15.
钢管订购和运输优化模型 总被引：3，自引：0，他引：3
建立一个钢管订购和运输模型，从钢厂到主管道结点的运费是影响总费用的重要因素．为使总费用最小，须使从钢厂到主管道结点的运费──钢管运输费最小．对求网络中最短路径的Ｄｉｊｋｓｔｒａ算法进行改进，得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径）．在此基础上，建立起描述总费用的函数，把钢管的订购和运输问题归结为在一定约束条件下求最小总费用的二次规划问题．用Ｍａｔｌａｂ软件中的ＱＰ（）函数求得问题的最优解． 对于问题（１），最小总费用为１２９．１７亿元；对于问题（２），钢厂Ｓ１的产量上限的变化和钢厂Ｓ５的钢管销价的变化对订购和运输计划及其总费用的影响最大；对于问题（３），最小总费用为１４１．８３亿元． 相似文献
16.
谢治州 《黔南民族师范学院学报》2012,32(3):118-124
对2011年全国大学生数学建模竞赛B题的问题建模和解决进行研究。依据赛题提供的"附件2"建立描述市区交通网络图的权矩阵,采用求最短路的Dijstra算法求出市区任意两节点的最短路径及路长,构作最佳路径阵和距离矩阵,并以此为基点分别建立描述各问题的数学模型,给出模型求解的方案、算法和计算的结果。 相似文献
17.
递推关系是给出数列的一种常用的方法,由递推关系式求数列的通项公式,方法多样,求解过程灵活多变,近年来在全国和各省市高考中时有出现,是各类数学竞赛必考的热点问题.因而教学中应注意对学生进行这方面的训练,下面就对由数列递推关系求通项问题作一归类解析. 相似文献
18.
19.
本文首先从轨道交通和常规交通的衔接规划的视角,阐述了求解K最短路径问题在公交线网优化中的意义。然后在Dijkstra最短路算法的基础上,创造性地引入了多个P标和多个T标来记录起点到该节点的K短路径及其上界,使改进后的算法成功求解K最短路径。最后用C语言对算法进行实现,并随机产生测试数据进行算法测试,测试结果表明了该算法的计算效率和应用前景。 相似文献