共查询到18条相似文献,搜索用时 62 毫秒
1.
一种建立公交网络的最短路径改进算法 总被引:3,自引:0,他引:3
目前,对最短路径问题的研究很多,基本都是关注算法的计算效率问题,而其应用到具体领域时会遇到一些算法本身无法解决的细节问题。如将邻接结点算法用于公交网络的最短路径计算时,会遇到诸如缺少网络拓扑信息、属性数据复杂等问题。本文针对这些问题给出了解决方法:在计算最短路径之前,利用算法将站点和线路数据进行自动匹配,建立公交网络的拓扑关系。同时在数据存储方式上进行了改进,运用数据库存储复杂的公交属性数据和中间过程中产生的公交网络数据,节约了运算时的内存占用率,提高了数据的利用率,使算法更具实际意义。 相似文献
2.
传统编辑距离算法采用动态规划方法用一个维度大小分别为源字符串长度和目标字符串长度的二维数组保存计算过程中求得编辑距离值。这种传统求解方式在时间效率和空间效率上开销较大,限制了编辑距离算法在长字符串中地应用。针对传统方法存在的问题,经深入研究编辑距离的求解过程,发现在某个关键区域内存在一条最优路径,通过确定最优路径所在关键区域可以快速地求解两字符串之间的编辑距离值。实验表明,方法在计算两字符串之间的编辑距离与传统方法相比可以降低问题的求解规模,提高算法的时间效率和空间效率。所描述的方法同样适用于图论中使用动态规划方法求解一般问题地应用,比如最优分配问题和背包问题等。 相似文献
3.
现代物流业需要快速高效并智能化制定物流运输方案。传统路径优化方法适合处理中小规模的车辆路径问题,计算时间较长,方案质量较低,故需发展短时间内能提供高质量路径方案的启发式算法。针对大规模物流车辆路径优化,本文提出了一种Voronoi邻近的快速优化方法。该方法先创建初始解,而后进行迭代优化。初始解创建利用Voronoi邻近关系,顾及车辆容量约束,自底向上进行客户点空间聚类,将问题降维;采用最廉价插入算法安排聚类内部路径,生成性质良好的初始解。迭代优化在客户点Voronoi邻近内进行有效的局部搜索,利用模拟退火机制接受较差解,从而跳出局部最优,不断提高解的质量。本文利用模拟生成的北京市大规模车辆路径问题进行实验,结果表明:本文算法能够在4500s内优化客户点高达12 000个物流车辆路径问题,计算时间较短,解的质量优良,算法性能稳定。本文与其他算法比较,能在较短时间内提供高质量车辆路径方案,适用于大规模物流车辆路径的优化。 相似文献
4.
紧急情况下人员快速、安全疏散是室内空间智能化导航和路径规划服务的研究热点.本文采用房产空间管理数据为数据源,以“路径”和“节点”为关键要素,设计了楼宇空间路径模型,用以表达楼宇内部的空间关系及拓扑结构.基于此模型进一步研究了用于紧急疏散的楼宇路径构建算法,论述了构建“单楼层”和“多楼层”路径过程中走廊(过道)路径提取、... 相似文献
5.
6.
历史名人的行为轨迹反映了当时的历史文化背景,通过历史名人行为轨迹的空间化和可视化,可以对历史社会状态进行探索和分析。对历史名人的社交关系网络进行可视化研究,有利于剖析当时的政治背景与人物关系。目前,基于GIS的空间人文社会科学深层次分析方法和工具还很少,根据地理位置对历史人物的社交网络进行分时段的研究也很少。本文以玄奘和欧阳修为例,探索了基于WebGIS的历史人物轨迹空间可视化分析方法,基于核密度估计与标准差椭圆的空间分析方法,分析历史名人轨迹点的空间分布特征,统计迁徙指数、首都距、家乡距、成长地距以分析基于距离的轨迹点移动特点;分时段构建了历史名人的空间社交网络,并结合历史背景、名人事迹、名人作品和空间化结果进行了综合分析。分析结果表明: ① 历史名人的迁移轨迹与当时的历史人口迁移趋势基本是一致的,受社会变动影响较大;② 历史名人在事业上升期有更大的社交网络圈,而在人生没落阶段社交网络圈减小。本文对历史名人轨迹的空间可视化与分析方法进行了探索,可以为空间人文社会科学相关领域的分析研究提供参考。 相似文献
7.
8.
针对大区域路径规划问题,论述了道路层次划分模型和多尺度道路网数据库的建立,提出了构建多级道路网拓扑结构的方法,利用层次空间推理和改进的启发式A*算法进行最优路径的选取。 相似文献
9.
10.
蚁群算法是近年来出现的一种新的仿生优化算法.针对基本蚁群算法在求解过程中容易出现收敛时间过长以及易陷入局部最优解的不足,对算法中的状态转移、搜索方式以及信息素更新进行改进,提出了一种新的改进蚁群算法.一类典型旅行商问题的仿真实验表明改进的蚁群算法具有收敛速度快、全局搜索能力强和计算时间短的特点,证明了方法的可行性和有效性. 相似文献
11.
目前三维建筑模型已广泛应用于城市规划,导航和虚拟地理环境等领域.不同细节的模型是LOD( Level of detail )技术的基础,由于三维模型的生产成本高昂,模型自动化简逐渐引起了学者的关注.三维模型化简包括单模型化简和多模型综合2方面,目前单个模型的化简研究比较多,而模型群组综合的研究仍然处于起步阶段.本文主要研究模型群组的聚类综合,提出一种基于房屋轮廓与纹理的分层次聚类算法:首先,基于房屋的底面轮廓构建约束Delaunay三角网,以道路为基准对三角网进行划分,通过可视分析构建初始的邻接图,使建筑群组分类符合城市形态学;其次,将房屋纹理引入三维模型群聚类的过程,使用SOM( Self-organizing Map )智能分类算法对纹理进行分析,然后分割邻接图;最后,以最邻近距离对邻接图构造最小生成树,并进行线性检测,将离散的建筑合并到已聚类的群组中,最终完成模型的合并.本文利用纹理辅助轮廓特征,实现三维建筑模型的聚类,符合人类的视觉习惯,实验结果证明了本文方法的有效性. 相似文献
12.
13.
径向基函数(Radial Basis Function,RBF)是一种不需对数据做任何假设,能准确逼近任意维度数据的空间插值方法。其特别适合于复杂地形的数字高程模型(Digital Elevation Model,DEM)插值重建,但随着已知点数量的增加会导致插值模型求解困难或缓慢。针对这个问题,本文基于二叉树自适应递归分块原理,采用局部最优形态参数的RBF分块插值方法进行DEM插值重建。首先,设定子区域最小点数阈值和相邻子区域的重叠率,自顶向下,对研究区域进行递归分块,构建区域分块二叉树,对二叉树叶子节点区域,采用逐点交叉验证(Leave One Out Cross Validation,LOOCV)方法求解其最优形态参数,建立局部RBF最优插值模型;然后,根据单元分解原理,采用加权平均方法对相应叶子节点区域内的待插值点高程进行加权求和,自底向上递归求解,得到待插值点最终高程值。以云南某地区DEM进行插值实验表明,采用本文方法进行DEM插值重建,稳定性较好,插值精度高。 相似文献
14.
路径搜索问题作为地理信息科学等学科的一个研究热点,由此出现的许多路径搜索算法,在交通道路网和导航系统中已得到广泛应用。纵观这些成果,往往需要以构造矢量道路为前提,道路网缺乏地区(如野外、室内)等情况不太适用。由此,本文提出了基于地球剖分网格的以方向主导的路径搜索算法,文中描述了具体的原理和方法,且针对算法设计相应实验验证了该算法的可行性和效率,为路径搜索提出了一种新思路。 相似文献
15.
岩溶裂隙网络的识别与重构,一直是岩溶地下水资源和岩溶区地质环境保护研究的热点与难点。基于地表原始裂隙数据、经过克里格插值后的地表裂隙数据、以及通过蒙特卡洛预测得到的地下裂隙数据,本文针对三维裂隙构造中的水流通路识别模块,提出了一种基于圆盘模型的渗流路径构建方法,采用有向图的数据结构来模拟圆盘模型概化后水流沿裂隙的渗流路径,并以邻接矩阵的形式存储其渗流路径数据。同时,为满足大规模裂隙数据快速求交的需要,本文给出了三维R树索引算法缩减遍历各个采样点所用的时间,提高了整套算法运行的效率。最后,以北京市房山区张坊地区地表采样裂隙数据为基础,借助遥感地质调查、重点岩溶区精细地质测量及取样分析等手段,开展三维裂隙空间网络分布模型研究,对岩溶裂隙渗流路径构建算法进行计算机仿真实现,为张坊地区岩溶发育机理的研究及岩溶水裂隙数值模拟提供可视化的分析手段。 相似文献
16.
建立了关于时间(路程)的瓶颈运输问题的动态规划模型,并利用熵作为工具.解决了物品运输过程中所用时间长短的界问题,进而给出易于处理的瓶颈运输问题的动态规划模型。最后给出一个实例说明该方法的实用性和有效性。 相似文献
17.
建立了关于时间(路程)的瓶颈运输问题的动态规划模型,并利用熵作为工具,解决了物品运输过程中所用时间长短的界问题,进而给出易于处理的瓶颈运输问题的动态规划模型。最后给出一个实例说明该方法的实用性和有效性。 相似文献
18.
景区游览线路是游客游览不同景点的有效选择路径。在导航系统中通常结合各景点POI(Point of Interest)和景区路网的路径规划而生成,但是,针对具有一定范围与多出入口的景点(如建筑物类景点),单一的POI坐标描述机制规划产生的游览路径,往往与智能导游应用中实际可行的最优游览路径存在明显差异。本文分析了景点大小、多出入口等特征对景区游览路径规划的影响,提出了顶点和边的权重均可动态选择的景区双加权图模型,突破了单一POI描述机制的限制。同时,讨论了景区双加权图模型的化简、构建方法,并以Dijkstra算法和Prim算法为基础,给出了其最优路径规划求解算法。实验表明,本文模型及其最优路径规划算法所得结果更为优化与合理,具有较少的游览规划距离和更为紧凑的游览过程安排。 相似文献