基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近邻查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络邻接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近邻查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。

增删边对最短路径影响的研究

在有向图中加入或删除一些边时，可能有多种可选的方案，通过对各种方案影响最短路径的大小进行研究；给出联通权重值的定义和对最短路径贡献大小的规定。

基于最短路径的求解与创新

笔者于2012年5月参加西北工业大学数模竞赛,试题详见问题充数部分。问题一:把矩形框架的四个顶点、八个入口点和花园内部四个交叉点总共是十六个点都看做是顶点,构造道路建设费用矩阵B,求得连接这十六个点的最小生成树,接下来,用迪杰斯特拉算法加以修改和完善(简述一下方法:按P1,P2……的先后顺序,用迪杰斯特拉算法,求得总述中11对入口之间最短路径,若该路径小于这两个入口直线距离的1.4倍,就保留这个路径,若某两个入口之间没有这样的路径,就通过已保留的路径,结合线性规划的方法,构建新的路径,使得该两入口之间存在小于其直线距离的1.4倍的路径,且使得新构建的路径之和尽量的小)使得总述中所说的11对入口之间存在路径总长不大于直线距离的1.4倍的道路,即为最佳路径设计。最终得到符合题意的最短路径为394.56m。问题二:在问题1得到方案的基础上进行优化,用Floyd算法求解出任意两个路口仅通过矩形图边的最短路径矩阵Df=(dfij)n*n,用求出的最短路径dfij与vi,vj,两点的直接连接的距离dfij的1.4倍做比较得出不可周向矩阵T=(tij)n*n,并用matlab程序计算出矩阵T,最终得到符合题意的最短路径为358.62m。针对问题三:在问题2中,道路有经过湖面的,这不符合第三问的要求,因此,在假设第二问的解是最优的情况下,绕过湖面所在地,求出其长度最小的道路设计,模型仍沿用第二问的原理,在第二问的基础上求解出满足题意的解,最终得到符合题意的最短路径为360.7149m。

解一般TSP问题的并行算法

任何连通的带权图均有ＴＳＰ的解．本文用图的最短路径矩阵代替加权邻接矩阵，使所有带权图，ＨＰ模型都能够接受．由于采用并行算法，可以较快获得问题的最优解．

一种城市动态交通网络紧急疏散路线确定的方法

研究城市动态交通网络紧急疏散路线确定问题。针对城市交通网络的不确定性并考虑到智能交通系统的发展,在分析城市灾害应急管理对疏散路线确定要求的基础上,提出通过离线方式确定预案和根据实时信息调整预案的紧急疏散路线确定的方法,简介了实现该方法的系统结构。在离线模块中,利用已有路网统计先验信息建立基于时间依赖网络城市交通紧急疏散线路预案的确定模型,采用最小费用流与时间依赖非FIFO网络最短路的综合算法对模型进行优化求解;在在线调度模块中,采用非参数回归方法预测动态路阻,建立基于实时信息的紧急疏散线路模型,采用F loyd算法进行优化求解,对方案予以调整;仿真试验分析了该智能思想的效果,证明了该原理与方法的有效性。