空间网络数据库中移动对象的最短路线算法

在空间网络数据库中,基于位置的服务（location-based services,LBS）变得越来越重要,最短路线查询是最广泛的服务请求之一.假设在网络上有一个原始对象（例如：在道路上行驶的汽车）、有一个目标对象（例如：旅店、加油站、救护车等等）,那么最短路线查询就是要找到原始对象到目标对象的最短路线.最短路线算法的研究主要分为两个方面,实时计算和预计算.在预计算方面,当前的研究对网络空间中的最短路线查询提出了多种解决方式,但是这些方法中都假设目标对象是静止的.文中在原始对象和目标对象都处于移动状态时,给出了一种最短路线查询的算法.该算法创建了一组索引结构,将计算两个动态点之间最短路线的问题转换为计算静态边之间最短路线的问题.主要关注交通网络.但是该算法不会使用任何领域相关的信息,所以能够被应用到其他的网络环境中.从计算复杂性而言,传统的Dijkstra算法时间复杂性估计是O((i+k)²),而该算法的相应估计是O(klbi).     

基于最小生成树的R~*-树结点分裂算法

针对R*-树应用到逆向工程领域时遇到的适用性差等问题,提出了一种新的R*-树结点分裂算法.该算法将R*-树索引结点表示为轴向包围盒,依据轴向包围盒外接球间的重叠度计算结点相似度,并将其作为权值构建结点无向连通图,用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树,并基于结点外接球体积对R*-树结构进行优化,从而实现了R*-树结点分裂.实例表明,R*-树结点分裂算法可处理各种复杂数据的结点分裂问题,能够有效地提高R*-树的构建效率及空间数据的查询效率.     

结点度数组表示下的二叉树上两个算法的优化

先从理论上证明结点度数组表示下的二叉树上结点之间存在的某种关系 ,然后运用该关系 ,优化求二叉树上任意一个结点的左儿子结点和父亲结点的两个算法 .     

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

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

对改变线索二叉树结点结构中左右标志域涵义的探讨

给出了线索二叉树结点结构中ltag和rtag域新的涵义,讨论了新涵义对求先序后继结点算法、后序前趋结点算法以及求先序遍历算法带来的效果.     

维修资源运力需求中的“最短路线选择问题”新算法

提出了一种在维修资源运力需求中解决最短路线选择问题的新算法,这一算法在项目的实施中收到了较好的效果。     

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

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

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

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

无向无权图同构判别算法简

首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.     

无向无权图同构判别算法

首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.     

Ad Hoc中一种新的路由维护机制

在MANet中,由于节点的移动,在路由创建的过程中找到的最短路径经过一段时间后可能变得不是最短的。这就会导致更大的端到端的延迟,要多的节点碰撞和更快的能量消耗。为了解决这个问题,提出了一种适用于所有的距离向量路由协议的机制,使用该机制可以在活性路由上定期查找路由捷径。不仅如此,该机制还可以用来在双向路由上进行路由的恢复。     

最短路径子图

在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.     

函数迭代法的推广与应用

本文拓广了函数迭代法的内容及应用范围，并提出算法检验准则新形式，提高了计算速度．用此法可圆满解决一般形式的最短路问题，计算结果优于其他常用方法，具有实际应用价值．     

公共交通路网描述方法及诱导模型设计

在采用传统的公共交通路网描述方法的公交网络中,会出现大量两节点间有多条同向边的情况,这使得无法求解公交网络中的最短路径问题.有鉴于此,文中提出了一种新的公交路网描述方法,该方法克服了以上问题,使得所有经典的最短路径算法都能够用于公交诱导系统.在此基础上设计了3个单目标和一个多目标公交诱导模型来满足不同乘客的需求,同时对文中提出的描述方法和模型的有效性进行了证明.最后,以广州市的公交线路网络为例,对所提出的公交诱导模型进行了试验,结果表明所提出的方法和模型是十分有效的.     

多约束最短路径模型与求解

提供满足驾驶员多个心理期望的路径是导航系统该解决的关键问题,其本质是资源约束最短路径问题,属于NP难问题,无法使用传统的最短路径算法解决.提供了多约束路径规划的数学模型,并使用了蚁群算法对其求解,在算法中针对问题重新设计了信息素更新规则和启发因子.实验证明算法具备良好的寻优能力,能准确找出路网中满足多种属性约束的路径.     

局部扭曲立方体单播容错路由算法

局部扭曲立方体是一种新型的网络拓扑结构．基于此网络拓扑结构,利用安全级概念以及此种网络拓扑结构自身特有的性质设计了一种单播容错路由算法．通过模拟仿真实验对该算法进行了性能评价与分析．当故障节点的数目达到或超过一半时,仍能保持在一个相当高的容错路由成功率上．另外,该算法所选线路在多数情况下是最短距离．     

Ad Hoc网络中多点对点视频传输系统设计与仿真

针对传统C/S(client/server)结构的流媒体模式存在服务器负载较大问题,设计了Ad Hoc网络中多点对点视频传输系统.发送端依据路由应答分组(RREP)选择优先权高且路径最短的路由来传输视频.与协议扩展前相比较,可用路由的节点不再集中在接收端附近,故当发送端附近的某个链路断开时,视频信号仍可以由其他链路来传输.从仿真结果可以看出:使用扩展动态源路由协议时,系统的归一化路由开销增加了0.02～0.08,但是从平均峰值信噪比和视频中断发生时间长短与次数等方面来看,视频的传输品质有显著提高,其中以3个传输点的效果最佳.     

一种维持动态网络中最短路径的方法

本论文提出解决动态网络中多源-目的点对最短路径路动态问题的有效方案。针对动态网络中的边权被改变后,需要扫描所有的边重新计算所有点对之间最短路径,我们提出采用相应的数据结构,使每次边权改变后,只需重新计算含该边的源-目的点对间最短路径,即最低限度的扫描动态图中的边,提高维持所有点对之间最短路径算法的时间性能。     

限制搜索区域的距离最短路径规划算法

提出一种时间复杂度为O(n)的限制搜索区域距离最短路径规划算法(n为路网节点数).算法设计的基础是,经典Dijkstra算法搜索时的无方向性及实际城市道路网络特有的空间分布特性.算法实现采用邻接表数据结构和限制搜索区域的搜索机制,即利用实际城市道路网络的空间分布特性,合理限制算法的搜索区域.结合路径规划算法在实时车辆导航系统中的实际应用,给出了该算法的应用实例,实验结果表明,该算法能将路网中任意两点间的最短路径解算时间控制在3 s以内.     

确定最短航程的投影坐标转换模型

在描述计算“最短航程”距离及方位角方法的基础上，提出利用“球心投影”法建立的球面与平面间的坐标转换模型，并且给出了在平面上描述最短航程的轨迹方程。对问题的研究基于球面三角，同时借助了能将空间几何问题确切地表示在平面上的多面正投影方法。