道路网络中最短路径的算法与实现

最短路径算法是地理信息科学与计算机科学等领域的研究热点。本文从网络分析的理论基础及拓扑性质出发，提出了一种适于最短路径算法的空间数据组织方式。结合道路网络的特点，在构造邻接结点矩阵来表达网络结构的基础上，运用优化的迪杰斯特拉(Dijkstra)最短路径算法，在电子地图环境下实现了道路网络中任意两结点间最短路径的快速解算与刷新。     

一种最短路径分析优化算法的实现

在对地理信息系统中最短路径分析的实现方案和现有各种最短路径分析算法进行分析、研究的基础上,提出了“优化Dijkstra算法”。该方法使Dijkstra算法的搜索方向明显趋向于目标结点,减少了算法中遍历的结点数,从而提高了搜索速度。总结出两个Dijkstra算法的优化途径：对搜索到的临时标记结点按照最短路径值排序;减小结点的搜索范围即减少永久标记结点的数量。     

最短路径的改进与实现

最短路径分析是GIS最基本的网络分析功能。Dijkstra算法是目前公认的较好的最短路径算法。文中从节约存储空间,提高运算速度出发,在Dijkstra算法基础上,提出邻接结点算法,并给出算法的面向对象的实现方法。     

Dijkstra优化算法及其在电子导游中的应用

导游电子化是旅游产业的发展趋势,最短路径搜索是电子导游系统的关键技术之一.经典的Dijkstra算法须花费大量时间用于计算最短路径以外的结点,从而影响了算法的速度.在分析景区结点分布特点和移动设备特性的基础上,对Dijkstra算法进行了优化,优化算法基于对景区结点进行区域划分,缩小了考虑结点的范围,在搜索时仅对相关区域内的结点进行处理,从而提高了算法的速度,最后对优化算法进行了正确性证明和性能分析.     

Dijkstra算法在室内移动导航最短路径寻址的改进

在室内复杂停车场的路径规划问题上,许多方法使用了单源最短路径的典型算法Dijkstra算法对最短路径进行规划,但该算法需要花费大量时间和空间来计算和存储与最终路径无关节点.为了提高算法效率,通过把地图中所有的结点进行顶点归一、区域集合划分以及区域编号排序等策略,大大提高了算法运行效率.实验显示,在随机对某结点目标进行最短路径搜索时,搜索时间可以缩短80.8%到98.9%,大大减少了时间复杂度和空间复杂度.     

基于佛洛依德算法的各院校间最短路径问题的求解

利用弗洛伊德算法通过邻接矩阵D和路径矩阵P,文中不仅计算出了最短路径,还找出了该最短路径下所经过的结点,从而为应用系统的开发与设计提供理论依据和实现技术。     

复杂网络的优化模型及最短路径求解

对大型复杂网络提出网络分级的思想，根据网络分级的情况定义网络结点的数据结构，然后使用改进的Dijkstra算法和最小生成树算法来计算网络中任意两结点之间的最短路径．     

大规模网络最大流对偶图算法模型及实现

在网络最大流算法的研究中,为了减少计算量,提出了许多改进的方法.基于图论中的最大流最小割定理,利用网络流图的对偶图的最短路径求网络最大流,对求最短路径的Dijkstra算法进行了研究,给出了一种改进的Dijkstra算法模型,该算法采用了堆排序中的小根堆来选择最短路径结点,使用集合运算对堆中的结点进行处理,使得参加运算的结点数减少,提高了算法的效率.     

Dijkstra算法的设计与实现

针对地理信息系统中网络分析的一个关键问题--最短路径分析,采用经典的Dijkstra算法,并在VC环境下实现自定义有向图,主要包括结点和边的绘制与修改,以及权重的更改等功能.能够实现几何网络中任意两结点间的最短路径查找.该程序在单项、双向,以及单双混合网络中都进行了验证,运算结果正确,并具有一定的可行性.     

适用于大规模网络的全源最短路径重优化算法——RASP算法

为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n~2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.     

一种无线传感器网络的传输路径规划算法

针对层次不多的树型拓扑结构无线传感器网络,介绍了一种根据ID格式选择传输路径的路径规划算法,该算法可使无线传感器网络中各节点到达sink节点的路径最优。经在温度传感器中应用,证明该算法切实可行。     

飞越北极数学建模方案Ⅰ

对“飞机从北京出发,飞越北极直达底特律所需时间可比原航线节省多少”的问题进行讨论,并将航线的选择归结为寻求曲面上的最短弧,应用“曲面上最短弧为测地线”的事实,分两种情况展开讨论：模型一：假设地球是球体,则测地线恰好是大圆,而球面上两点间的最短弧,就是其所在大圆对应的劣弧,我们可通过单位向量的点乘与夹角的关系加以解决;模型二：假设地球是旋转椭球体．我们利用微分几何学中测地线方程及曲线的弧长公式,并且把球面的纬度转化为旋转椭球面纬度,对于4组较特殊的点,纬度几乎相等或相近,或者两者之间的经度差过大,用测地线计算比较困难,我们用椭圆弧长代替测地线,结合数学软件Mathematica可求得测地线长．     

区域GPS空间基准网的建立

随着GPS的广泛应用，如何提高GPS的定位效率，实现实时定位，已经成为有待解决迫切的问题，目前RTK技术(实时动态全球定位系统)不需要数据的后处理即可快速定位，但在定位之前，需要在足够的已知点上进行观测，计算获得所需区域的坐标系统的转换参数，这在很大程度上影响了RTK的定位效率和点位的相关与一致性，此外，目前许多城市的地方坐标系统与国家坐标系统之间缺乏精确严格的换算关系，结合区域GPS空间基准网的建立项目，阐述了GPS空间基准网的布设与施测、投影与坐标系统转换等相关的数学模型和解算方法，探讨了多套参数的差异与应用，观测分量的误差对于拟合参数精度的影响等问题，并给出了相应的分析数据．基于上述方法可以获得区域统一的、精确的多套坐标系统之间的转换参数，将WGS84的大地坐标与现行实用的坐标系统如1954年北京坐标系统、80西安坐标系统以及地方坐标系统紧密联系起来，从而实现坐标系统之间实时精确的转换，为RTK实时定位奠定基础。     

城市道路最短路径的Dijkstra算法优化

在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用一种改进的Dijkstra算法对城市道路进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索.在计算某一段最短路径时,用Dijkstra算法时间为0.23 s,改进算法时间为0.20 s.仿真结果表明,该算法不仅在时间上有所改进,其时间复杂度由传统Dijkstra算法的O（n^2）减小为O（n）,而且其所选的最优路径更符合实际,是一种寻求最优路径的有效算法.     

考虑实时路况的出行路线选择模型

为了缓解交通拥堵问题,本文在现有的导航仪基础上,考虑到道路的实时情况,设计新的导航仪,帮助居民选择出用时最短且能尽量避免拥堵的路线。研究主要包括两方面：首先,在存在不拥堵路线的情况下,利用最大流模型计算出道路流量,结合实际流量,在尽量避免拥堵(实际流量不超过最大流量)的情况下,求出最短路程,给出建议。然后,考虑拥堵问题难以避免,加强了与实际道路状况的联系,对道路出行选择模型进行了优化,先将道路分为非常拥堵、存在拥堵、畅通三种情况,然后再根据道路实时流量,利用G-LN的模型计算出车道的速度,结合路程,找出用时最短的路线。     

最短路问题的灵敏度分析与最短路调整

本文讨论的是无负回路的有向网络,在己知网络各节点间最短路的前提下,当网络中的个别节点、权值、弧发生变化时,变化对最短路有无影响,若有,如何利用变化前的最短路得到改变后的最短路,即:利用网络的独特优势,建立最短路问题的灵敏度分析算法.     

神经网络PID控制

以工业ＰＩＤ控制中控制器参数调整困难为背景，在分析神经网络特性的基础上，提出神经网络控制方法，设计了具有自适应性的神经网络ＰＩＤ控制器，在描述了神经网络的学习机理的基础上，给出了控制器控制算法。通过２个实例验证了神经网络在线控制的可行性。     

一种新的近距离微波成像系统的建模与仿真

针对紧缩场成像系统造价昂贵,设计了一种新的近距离微波成像系统。采用合作目标建立数字建模,推导了严格的成像公式,应用球面波滤洪逆投影算法进行快速求解。仿真结果表明,该系统实现简单,能在球面波照射条件下获得雷达目标的高分辨率二维像,准确地诊断出目标的散射点分布,具有很高的推广应用价值。     

一种改进的通过查表实现的算术编解码方法

算术编解码是一种对非等概率的符号进行压缩和解压缩的有效方法,实现过程中需要很大的运算量和判断跳转操作.针对DSP流水线结构不适于判断跳转操作的特点,提出了一种改进的通过查表实现的算术编解码方法,该方法可以减少判断跳转次数,节省运算量,降低对硬件实现的要求.     

时变路网双目标动态路线优选有约束A*算法

为了解决现有交通时变网络(网络中的路权为时间的函数)模型中计算所得的最短路不稳定的问题,构建符合首进首出原则的时变网络,进而将时变网络扩展为一系列静态网络,并在扩展的静态路网上应用A*算法求解时变最短路;同时,为满足用户多重喜好,借助道路延误风险分析,设计有约束的时变A*算法,在路径寻优过程中对高延误风险路段进行启发式规避,从而实现在绕行许可范围内有效减少延误风险的可靠路径的快速搜索。数值试验结果表明:本算法由于利用了离线计算的信息,大大增加了有约束的动态A*算法的效率;考虑了阻塞发生的可能性,提高了导航的准确性,减少了出行延误风险;该方法具有路径搜索速度快、可有效避开延误高风险路段的优点。