最短路径

摘要： 本文采用数学几何思想建立地球表面两点最短路径验证模型,经过大量随机点选取和验证,证明了两点间最短路径是经过地球球心的大圆上劣弧段。同时,本模型采用简单的数学几何公式设计模型,能简单易懂地被学生接受,促使学生思考更多运用数学方法理解地理问题,提高自身的地理实践力。

摘要： 在无线传感器网络定位问题中,传感器节点间距离并不能全部直接测量,一般通过多跳距离进行最短路径估计。就经典多维尺度(Multidimensional Scaling,MDS)算法而言,其定位精度受距离估计精度的影响较大,少量误差较大的距离估计会极大影响定位结果。为了减少"错误"距离估计的影响,提出一种基于非对称广义中心化矩阵的多维尺度定位算法。该算法提出一类非对称广义中心化矩阵,并研究了中心化矩阵对定位误差的影响,从而选择有助于抑制"错误"距离的中心化矩阵提高定位精度。通过改变中心化矩阵中元素的权重,可以显著提升部分节点相对位置的定位精度。实验结果表明,与经典MDS算法相比,基于非对称广义中心化矩阵的MDS算法打破了原来中心化矩阵的局限性,可以有效减小距离估计误差对定位的影响,提高节点的定位精度。

摘要： 平衡态公理,又称最小势能原理,是物理弹性力学中的一个基本原理.该原理指出,在一个独立体系中,如果该体系处于势能最低状态,则必然处于平衡状态.研究旨在从物理学的视角出发,以平衡态公理为物理模型,重新思考和探究几何中一类最短路径问题,以使该类最短路径问题的结论更加明晰且自然.

摘要： 为降低城镇-森林交界域输油管道泄漏事件造成的灾害损失,基于灾害链理论和复杂网络理论,构建城镇-森林交界域输油管道泄漏事件演化模型,利用Python算法对节点和边进行分析,提取模型中的关键节点、关键边以及最短路径,结果表明:以相邻管线系统损坏、形成流淌火、管道爆炸、建筑物受损、人员伤亡为关键节点,以水土流失-山体塌方、改变土壤性质-水土流失、土壤中重金属元素超标-改变土壤性质、山体塌方-道路破坏、影响居民生活-不良社会舆论为关键边,通过对其采取断链措施,可实现城镇-森林交界域输油管道泄漏事件的灾害防治;城镇-森林交界域输油管道泄漏灾害事件与其他灾害事件之间具有较紧密的联系,一般只需要扩散3~4次就会造成灾害的蔓延。

摘要： 针对电力安全工器具便捷管理的需求,为了降低工器具管理所需的人力、物力资源,文中详细分析了电力安全工器具的管理流程,设计了一套智能化的工器具管理系统,基于无线传感网络(WSN)实现工器具信息的采集、入库、出库。为了降低WSN网络的能耗、提升传感器节点的生存周期,文中对传统的低能自适应聚类算法(LEACH)进行改进,得到A-LEACH算法。在A-LEACH算法的分簇阶段前增加了网络部署准备阶段并引入k-means算法;在信息传输阶段,引入基于多跳传输取代了LEACH算法的单跳传输方式。结合电力生产实际设计了WSN网络,并基于文中的ALEACH路由算法对网络的性能进行评估。实验结果表明,在平均生存周期上,LEACH算法中节点的平均生存时间为534轮,A-LEACH算法中节点的平均生存时间为762轮;在能源消耗上,在相同的轮次下,LEACH算法的能耗更大,A-LEACH性能曲线更平缓。

摘要： 传统交通路径规划方法忽略了对路径评估、选择的反复择优,导致路径的规划质量不高,路网通行效率无法有效提升。于是提出基于免疫遗传优化的实时交通路径诱导方法。根据出行者期望行驶速度,设定出行预期速率临界值,利用路网节点间的动态连通性优化路网架构,构建实时交通局部路网模型;计算局部路网中最短路径,在免疫遗传优化算法中加入单点交叉算子,设置群体模式、交叉概率、变异概率三个目标项,计算抗体、抗原的亲密度与浓度,建立抗体浓度概率选择解析式,反复执行评估、选择、交叉等流程,完成高质量实时交通路径诱导。实验结果证明,与传统方法相比,所提方法可以很好地缓解道路交通堵塞,增强路网通行速度,为出行者提供最优路径选择。

摘要： 在网络规模远超出最短路径经典算法适用范围的情况下,最短路径近似算法成为有效的替代解决方案。针对现有近似算法存在的预处理阶段计算效率低、算法性能受网络规模影响较大等问题,提出一种基于EIN覆盖网络的大规模复杂网络最短路径近似算法。算法基于边递归网络(The network created by edge iterations, EIN)的生成和标号方式在实际复杂网络上抽象出具有确定性拓扑结构的标号覆盖网络,结合覆盖网络标号节点间确定的位置信息快速推导出实际复杂网络中最短路径的近似解,在确定性网络层面高效解决非确定性复杂网络的最短路径问题。真实网络数据集上的实验结果表明,所提方法在大规模复杂网络上能保证较高精确度的同时,大幅度降低计算成本。

摘要： “最短路径问题”是各版本教材着力强调的重点,也是中考考查的热点,笔者以自编游戏情境的形式演绎“最短路径问题”,激发学生的内驱力,通过动手、动口、动脑培养学生的动手操作能力、合作互动能力与数学建模能力.

摘要： 单源最短路径问题是图算法理论中的经典问题,目的是在带权图上搜索一个源点到其他各个顶点的最短路径。Δ-stepping算法结合了经典Dijkstra算法和Bellman-Ford算法的优势,被广泛用于并行环境的单源最短路径计算。大规模网络的结构按照连接偏好机制演化,其顶点的度数分布呈显著的倾斜特征。基于大规模网络的倾斜性,提出了对Δ-stepping算法的两类改进策略。通过预处理计算任意两个顶点之间的距离上限,实现对边松弛操作的调度优化,提高单源最短路径计算的效率以及在并行环境中的伸缩性。首先,把权重超过所关联顶点之间距离上限值的边标记出来,在单源最短路径计算时,直接跳过这些边,从而减少计算过程中被松弛的边的数量。其次,利用顶点之间距离的上限值动态优化顶点的松弛顺序,只有一个顶点到源点的当前路径的长度不超过它们之间的距离上限值时,才松弛该顶点关联的边,从而减少这些边上的重复松弛操作。测试结果表明,与Graph500实现的Δ-stepping算法相比,改进后的算法在Graph500的基准测试图上有接近10倍的性能提升,在一些真实图上也有2.68~5.58倍的性能提升。

摘要： 随着旅行商问题规模的增长,完全图上最优解的搜索空间呈指数增长。为了减小最优解的搜索空间,提出一种针对旅行商问题的割边算法。推导出四边形最优圈内的最短路径包含一般边与最优哈密顿圈边的不同概率,采用一定数量的四边形最优圈内的最短路径计算边频率,根据所有边的平均边频率割边,基于建立的二项分布模型推导出最优哈密顿圈内边的保留概率。任给一个完全图,割边算法有4个步骤:1)随机选取包含每条边的若干个四边形;2)采用所选四边形最优圈内的最短路径计算各边的边频率;3)步删除5/6条最小边频率的边;4)对度数小于2的节点进行添边操作。计算实验表明:保留边数为完全图上边数量的1/6左右,采用精确算法求解割边后旅行商问题的计算时间也有所减少。

摘要： 由于公交网络的复杂性,与普通道路网相比,其最短路径计算涉及"点权"等难以处理的问题.单向交通管理措施等因素使得不少地区的公共线路出现上、下行不共线的情况,导致"点权"的处理变得更加复杂,从而对公交最短路分析提出了更高的要求.然而目前在最短路径的研究方面,很少有在设计算法之前,将上述现象考虑到模型之中,致使路径的准确性受到较大影响.针对这些问题,本文首先提出了"畸形站点"的概念,分析了"畸形站点"处乘客的换乘特性.然后提出一种能适应"畸形站点"的最短路径算法,并通过算例验证方法的可行性和有效性.

摘要： 笔者提出了一种进行油气勘探起伏地表最短路径射线追踪的新方法。首先，把笛卡尔坐标不规则区域变换到贴体坐标规则区域中，进行贴体坐标规则区域中最短路径射线追踪;然后借助坐标逆变换实现笛卡尔坐标系下起伏地表的射线追踪。数值实例表明，本文的方法准确高效，对地表地形剧烈起伏的模型具有良好的适应性和稳定性;此外，牛顿插值方法的应用使得插值精度和计算效率都有一定程度的提高。

摘要： 在轨道交通各专业日常维修、应急抢险、灾害救援等事件响应中,如何快速、准确地调度维修资源显得至关重要.利用公路交通网规划调度路径可以在维修资源调度方面发挥极大的正面作用.本文基于ArcGIS Engine平台,利用成渝区域轨道交通数据,开发了轨道交通维修资源调度的GIS路径分析模块,实现了地理位置选取及最短路径求解的功能,有利于轨道交通资源及时、准确地由维修工区调度至故障站点.通过对实验结果的总结,验证了该方法在实际资源调度中的可行性.

摘要： 道路交通信息(如旅行时间、旅行速率)为道路交通管理重要之参考指标.相较于传统车辆侦测器及GPS定位技术,行动通讯探侦车技术显然具有高覆盖率及低建置及营运成本之优势.基此,本研究旨在结合地图匹配算法及最短路径算法提出一套行动通讯算法.本研究以新北市市区道路及重要道路为分析对象,利用前述分析流程计算每五分钟之道路交通信息,并借助行动通讯资料探讨路段壅塞之原因.

摘要： 本文介绍寻路问题是路网交通应用中的一个基础问题.A*算法是一个求解点到点最短路径问题的高效算法.但随着路网数据规模的增长,A*难以保证求解的实时性.利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化.本文提出一种分段化搜索的改进A*算法(SA*).该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解.分段搜索本身可以减少寻路的搜索空间,借助多线程并行则可以进一步提高求解速度.实验结果表明,在真实路网数据上,利用16核的机器可以获得A*算法30倍的性能提高,而误差则在10％以内.

摘要： 图像分割是数字图像处理和计算机视觉的一项基本问题,图像本身所具有的的随机性与不确定性是该领域研究的最大挑战.基于图论的图像分割方法能够充分利用图像的整体和局部特征,具有很强的灵活性以及较高的计算效率和良好的分割特性,成为了图像分割领域的研究热点.该方法将图像映射为带权无向图,把像素视作节点,利用最小剪切准则得到图像的最佳分割.对图论方法用于图像分割的基本理论进行了简要介绍,根据图像分割方法，利用图的不同属性来完成图像分割，一般可将它归纳为以下5类:基于最小生成树的方法、基于Graph Cut的代价函数方法、基于Graph Cut的马尔科夫随机场方法、最短路径的方法以及其它基于图的方法。

摘要： 目的:提高一般SPFA算法(Shortest Path Faster Algorithm)的效率,缩短出警时间.方法:用离散化道路法优化辖区分配策略,在道路上设置虚拟路口,把每条道路离散成若干个点,然后把这些新增加的点作为新的路口,由此得到新的道路地图.结果:多次仿真实验数据显示离散化的优化策略可以缩短出警时间.结论:基于离散化的改进SPFA算法提高了一般SPFA算法的效率,优化了服务平台,具有一定的实用价值.

摘要： 广度优先搜索是图的一种常用遍历方法,本文通过利用图的广度优先遍历,在邻接矩阵的基础上,从已知的若干个城市的地图中,实现从一个城市到另一个城市的路径中经过的城市最少的算法,该算法能够根据输入查询任意两城市之间经过的城市最少,效率较高,较灵活.

摘要： 演化图理论可用于分析动态拓扑网络的路由问题,并给出了最早到达时间、最少跳数两种路由准则.本文利用演化图理论建立了带有相控阵指向性天线的导航卫星星座路由问题模型,并基于演化图理论中已有的路由算法准则,结合导航业务特点,提出了一种新的路由准则,即最少跳数最早到达时间路由准则,并证明了在导航卫星星座路由问题中最早到达时间路径的唯一性.本文给出了最少跳数最早到达时间和最早到达时间两种路由算法.其中,最少跳数最早到达时间算法与现有演化图理论中的最少跳数算法相比,具有复杂度低,路径到达目的卫星时间早的优势.最后给出了两种路由准则下路由算法的仿真结果,分析了两种算法的适用情况.

摘要： 演化图理论可用于分析动态拓扑网络的路由问题,并给出了最早到达时间、最少跳数两种路由准则.本文利用演化图理论建立了带有相控阵指向性天线的导航卫星星座路由问题模型,并基于演化图理论中已有的路由算法准则,结合导航业务特点,提出了一种新的路由准则,即最少跳数最早到达时间路由准则,并证明了在导航卫星星座路由问题中最早到达时间路径的唯一性.本文给出了最少跳数最早到达时间和最早到达时间两种路由算法.其中,最少跳数最早到达时间算法与现有演化图理论中的最少跳数算法相比,具有复杂度低,路径到达目的卫星时间早的优势.最后给出了两种路由准则下路由算法的仿真结果,分析了两种算法的适用情况.

摘要： 本发明公开的最优路径选择方法,在AGV路径网络布设若干路径点，路径点之间通过带有权值单向边连接建立路径地图模型；从路径点中选取起始点和目标点；搜索从起始点到相邻的路径点的最小权值路径，将该相邻路径点设为不再搜索的优选节点，在该最小权值路径中设定该优选节点上一个路径点为来源点；然后重复搜索从起始点到相邻的路径点和/或从起始点经优选节点到达该优选节点相邻的路径点的最小路径权值，将搜得最小路径权值的路径点设为不再搜索优选节点，并设定该优选节点的来源点；直至搜得相邻的路径点为目标点，重复迭代目标点的来源点直至来源点为起始点得出最优路径。应用本发明的优路径生成方法，可快速得出到达目标点行驶成本最低的路线。

摘要： 本发明公开了一种基于凸包特征的导航路径建模及最短路径求解方法，主要面向室外公共空间和室内场景，基于凸包特性，利用凸包任意两点可视的特点，将地图剖分为多个凸包的有限集合，形成多层次的地图表达，并在此基础上设计了一种层次最短路径算法。该方法可以有效降低图的节点和边的数目，进而提高最短路径算法的求解速度。

摘要： 本发明涉及一种用于多路径路由的多条部分不相交最短路径快速寻找方法，将有向网络表示为有向图模型；从所述有向图模型中获取一条最短路径，并令；根据中的所有路径，建立对应有向图的一个传统余图；基于传统余图，构造点分解余图；从点分解余图中获取一条最短路径，沿此路径对路径进行增广；分解获取螺旋最优路径。本发明提出的一种用于多路径路由的多条部分不相交最短路径快速寻找方法，提高了在网络中寻找不相交最短路径的效率和可行性，能够快速地找到部分不相交最短路径。

摘要： 本发明提供了一种虚拟最短路径树建立及处理的方法及路径计算单元，用以提高虚拟最短路径树建立和处理过程中资源的利用率。在虚拟最短路径树建立过程中，将已构建的根节点(目的节点)至叶节点的路径代价与代价阈值进行比较，在确定小于代价阈值时在VSPT中增加新的路径分支。在虚拟最短路径树处理过程中，在获取最优路径后，释放VSPT中不属于最优路径的路径分支。

摘要： 本发明旨在提供一种基于路径和权的最短路径搜索方法，包括以下步骤：1）每段路的路径长度为真实距离除以权值；2）将待分析区域内各条道路连接；3）连接起始点和终点得到连接线，得到多个初始路径多边形；4）将多个初始路径多边形合并，得到外包多边形；5）以连接线为界，取得外包多边形的起始左路径及起始右路径；6）用较短的连线代替起始路径对应两点的连接线，依次搜索得到新左路径和新右路径；7）若新左路径和新右路径有重叠，重叠部分必为最短路径部分，若新左路径和新右路径未重叠，得到最终左路径和最终右路径；8）合并最终左路径和最终右路径内的中间多边形，得到合并多边形；9)将新左右路径公共部分与求得的结果合并，得到最终最短路径。本发明搜索效率和精度高，可在当前各大空间数据处理软件平台实现。

摘要： 本发明公开了一种最短路径引导方法和最短路径引导系统，其包括以下步骤：S1、通过一GPS系统定位用户当前位置，并读入用户的目的地位置；S2、在一地图数据库中获取用户当前位置和目的地位置之间的所有路径信息，并生成用户当前位置和目的地位置之间路径的拓扑结构；S3、通过所述地图数据库获取所述拓扑结构中各个节点之间长度和拥塞信息；S4、分别设定节点之间长度和所述拥塞信息的权重值，并计算各个节点之间的有效长度；S5、基于所述拓扑结构和各个节点之间的有效长度并计算所述用户当前位置和目的地位置之间的最短路径。本发明还考虑了配送路线中各个路段的道路状况信息，从而能够得到时间上最短的配送路线。

摘要： 本发明公开了一种基于最短路径树技术实现数据血缘的批量检索和路径展示的方法及装置，其中方法包括：获取数据血缘更新信息，分析血缘变动情况后获取变动节点；获取所有与变动节点相关联的关联节点；基于最短路径树算法，分别计算从根节点到关联节点的最短路径；获取关联节点的子节点，处理并更新最短路径信息表中关联节点的子节点对应的最短路径；批量获取目标字段，在数据库中查询字段信息表，若目标字段存在，则基于目标字段进行检索，从最短路径信息表中输出对应的最短路径；将最短路径进行汇总，合并共同节点后形成数据，在最短路径树中高亮展示目标字段的位置和最短路径。本发明能降低数据更新后，血缘路径更新时重复无效的计算，以提高整体效率。

摘要： 本发明提出一种基于多出口选择A*算法求解最短路径的人群疏散动态路径规划方法，从起点和终点进行双向搜索，选择新扩展节点，结合人员疏散流体模型，对扩展节点进行评价，当扩展节点相同时视为规划完成，再对完成规划的路线进行优先级排序；进行排队或拥堵判定，对不拥堵且非最优的线路进行再次分配，完成路径规划；本发明针对现有的算法改良，遵守海事组织相关导则性要求并且考虑群体路径以及疏散环境的复杂性，将不同疏散路线分为不同优先级的分配策略，使得地图节点信息矩阵得以简化，极大程度提高了规划的效率。

摘要： 本发明公开了一种基于凸包特征的导航路径建模及最短路径求解方法，主要面向室外公共空间和室内场景，基于凸包特性，利用凸包任意两点可视的特点，将地图剖分为多个凸包的有限集合，形成多层次的地图表达，并在此基础上设计了一种层次最短路径算法。该方法可以有效降低图的节点和边的数目，进而提高最短路径算法的求解速度。

摘要： 本发明涉及一种用于多路径路由的多条部分不相交最短路径快速寻找方法，将有向网络表示为有向图模型；从所述有向图模型中获取一条最短路径，并令；根据中的所有路径，建立对应有向图的一个传统余图；基于传统余图，构造点分解余图；从点分解余图中获取一条最短路径，沿此路径对路径进行增广；分解获取螺旋最优路径。本发明提出的一种用于多路径路由的多条部分不相交最短路径快速寻找方法，提高了在网络中寻找不相交最短路径的效率和可行性，能够快速地找到部分不相交最短路径。