图划分对Arc-flags算法的影响

最短路径计算作为导航的常用算法在移动互联网中扮演了重要角色,由于路网规模的增大和终端的不停移动,传统的串行最短路径算法已经无法满足实时性要求,因此预处理技术得到了广泛使用。Arc-flags是一个经典的基于预处理技术的最短路径算法,可以提供高效的在线最短路径查询服务。现有Arc-flags算法的研究主要集中在提升预处理时空效率和比较不同路网划分方式的优劣上,尚未见图划分对Arc-flags算法影响的深入研究。本文在真实路网上测试了不同的图划分数量和边界点数量等因素对Arc-flags算法的影响,主要包括预处理时间和空间的消耗、在线查询时间和搜索范围等方面,并根据实验结果和分析提出了合理的图划分建议（如选用好的图划分方法减少边界点数量等）,为改进和使用Arc-flags算法提供指导。     

城市商业区智能泊车系统的设计与开发

针对石家庄市商业区停车压力和停车管理系统现状,基于运动车辆的当前位置、车库中的车位数量、道路状况、路口限制等动态约束因子,进行了智能泊车系统的技术设计与软件开发。通过建立复杂约束条件下的模糊预测模型,并使用扩展和改进后相邻节点低值传递的最短路径引导算法,实现了城市商业区泊车过程中动态最短路径与最佳路径的分析与可视查询,并介绍了模拟应用情况。     

SA*：一种多线程路径规划算法

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

一种基于路网等级启发式策略的路径搜索算法

本文提出了一种基于路网等级启发式策略的路径搜索算法。通过引入考虑路网等级因素的代价评估函数,有目的地引导搜索过程考虑路网道路等级特征,限制路径搜索规模,在精度可控的前提下,大幅度提高时间最短路径算法的效率,并使得搜索路径结果更符合心理认知过程。其与经典的层次空间推理算法相比,本文提出的算法实现过程简单,效率和精度相似。理论分析和实验过程验证了本文所提出算法的有效性。     

一种基于接收信号强度的源节点定位算法

提出一种基于接收信号强度的源节点定位算法,无需事先已知源节点的发射功率以及环境中的路径损耗指数。该算法首先对接收信号强度的路径损耗模型进行两次差分,消去与源节点发射功率相关的模型参数和路径损耗指数,然后利用最小二乘准则来估计源节点的位置。通过仿真数据评估该算法的定位精度,并与其他源节点定位算法进行比较。     

分布式空间拓扑连接查询优化处理算法

针对传统分布式数据库查询应用于分布式空间数据库查询带来的传输和处理代价高的问题,本文结合已有分布式跨边界片段连接优化方法,深入研究了分布式空间拓扑连接查询处理,提出跨边界连接优化的空间查询优化算法,丰富了传统的分布式查询的关系代数等价变换规则。同时,针对不同片段连接类型的分布式空间查询全局优化策略,实现了分布式空间查询分解与数据本地化,从而优化分布式查询中的数据传输所付出的高昂代价。最后,提出了结点归并、连接归并树、执行结点、执行计划树等分布式查询优化方法,利用相应归并和优化算法将全局空间查询转化为各个场地局部空间数据库的具体执行计划,消除分布式查询中的冗余计算,优化查询计算策略,从而解决分布式空间查询中的处理代价高的问题。通过分布式空间查询实验表明,本文的算法能够较好地提高分布式空间查询的性能。     

基于中轴变换算法的室内外一体化导航路网自动生成方法

室内外一体化导航路网的快速生成与更新对面向行人的跨场景导航具有重要意义。当前研究主要关注单一场景下的导航路网构建,对于跨室内外场景的导航路网自动生成研究较少。本文基于对偶图思想与二维平面多边形中轴变换（Medial Axis Transform）算法,提出一种室内外一体化导航路网自动生成方法,并以某建筑CAD平面图及周边路网环境为基础数据进行了实例研究。结果表明：该方法能够根据原始数据的几何、拓扑、语义信息自动构建导航路网,并支持室内外跨场景的最短路径查询,在最短路径查询效率上较传统分场景寻路模型整体提升10.18%;相较单一场景下的导航路网,一体化导航路网可结合语义信息将室内及室外导航路网有机统一起来,解决跨场景寻求最优路径的问题,为最优路径规划的相关研究提供了新的思路。     

基于弧段标记的交通网络时间最短路径算法

标号算法是经典的最短路径算法之一,在交通领域中具有广泛的应用。在交通领域中,时间最短路径比距离最短路径更有意义,而时间最短路径不仅与道路的时间权值有关,还与道路之间的转弯阻抗有关。在传统的交通路网抽象方式下,道路抽象为平面图中的弧段,道路间的交叉口抽象为节点。本文介绍了一种适用于传统交通路网模型的弧段标记时间最短路径算法,详细阐述了该算法的原理、数据基础与运行结构。通过分析和实例测试表明,该算法可以顾及城市路网在路口的交通限行与转弯延迟的影响,并且时间复杂度低,具有一定的实际应用价值。     

洪灾应急疏散路径规划算法优化

应急疏散是救灾工作的重要环节,合理的路径规划能有效缩短疏散时间,减少人员伤亡.本文以疏散总时间最短为目标,考虑需求控制,容量限制,交通延误,公平分配和资源节约等约束条件,对经典Dijkstra算法进行改进;并采用混合拆分疏散方法,构建洪灾避难应急疏散路径规划模型.运用C#语言编写算法,求解最佳路径,基于自主开发的应急疏散分析工具MiniGIS,对规划路径进行动态模拟,依据反馈逐次优化算法.结果表明:理想算法,延时-改进算法,逆行-改进算法均能为县域尺度的洪灾避难疏散路径选择提供参考,但理想算法适用于组织简单,高度有序的疏散情景,延时-改进算法考虑了除交通拥堵之外的延误,与真实情况更为接近,逆行-改进算法避免了因中途路径调整而出现的"回头路",在时间最短次优的条件下,更有利于疏散过程管理与资源节约,其结果被认为是此次应急疏散路径规划的最优解.     

基于最短折减路径法的边坡安全系数研究

使用双参数折减方法分析边坡稳定性的研究较多, 如何把两个折减系数定义为单一的综合安全系数是目前研究的一项重要内容。Isakov提出的最短折减路径法能够保证在不同工况下得到最小安全系数, 但是该方法的缺点在于计算复杂, 不适合工程应用。通过有限元数值模拟, 利用最短折减路径方法计算不同强度黏土构成的不同坡度均质土坡的最小安全系数和对应的折减系数, 探索了最小安全系数与土的初始黏聚力、内摩擦角以及边坡坡度的关系, 分析了初始强度对折减系数的影响。结果表明, 相同坡度下不同强度的黏土边坡在失稳时, 最小安全系数对应的临界破坏强度相同。临界破坏强度与坡度近似成线性正相关关系。由此基于最短折减路径法提出了一种新的计算最小安全系数的方法, 该方法得到的安全系数与目前常用的极限平衡方法所得结果相近, 并且计算简单, 因此可以用于边坡稳定性分析。      

顾及单木三维形态的无人机立体影像单木识别算法

单木参数对当前的森林资源管理、生态研究以及生物多样性保护等具有重要意义。无人机立体影像数据与单木识别算法为单木参数的低成本、自动化获取提供了基础。现有研究表明,常用的基于局部最大值搜索的单木识别算法面对密集林分时存在严重的漏识别问题,影响了参数提取的精度,因此本文提出了顾及单木三维形态的无人机立体影像单木识别新算法。算法首先综合利用无人机立体影像的高程与RGB光谱信息,通过随机森林分类进行林冠区的提取;然后利用形态学的多层腐蚀、膨胀与连通区标记进行树冠相连单木的分离与树冠中心点的提取,从而实现单木自动化识别。本文选取内蒙古大兴安岭林区和四川王朗林区的4块样地进行验证,以目视解译数据为参考,分别与基于高程值的局部最大值搜索算法（算法A）、基于RGB光谱亮度值的局部最大值搜索算法（算法B）进行比较。结果显示：本文提出的算法在4个样地的平均F1-score为94.17%,与算法A和算法B相比分别提高了15.85%和9.37%;而对于密集样地,本文提出的算法在查全率上相比算法A和算法B分别提高51.79%和35.64%。结果表明本文提出的算法在不同林区均能够实现较好的单木识别效果,特别是能够有效避免密集林分下的漏识别问题,为基于无人机立体影像的单木识别研究提供了一种新的思路。     

���ģ��������������뾫�������ĸĽ��㷨

????????????????????????????????????飬???????????????????????????Ч??????????t???Cholesky???????OpenMP???п?????????и?????????????????????????????????????????????????????￡???????Ч??????????????????OpenMP???п??????????????????????????     

基于标记控制分水岭分割方法的高分辨率遥感影像单木树冠提取

树冠是树木的重要组成,可以直接反映树木健康状况。高空间分辨率遥感影像和遥感技术为快速获取详细的树冠信息和实时监测林冠变化提供了有效的途径。因此,基于高空间分辨率遥感影像的单木树冠提取方法研究对现代森林管理具有重要意义。本文以黄河三角洲地区孤岛林场人工刺槐林和旱柳为研究对象,以QuickBird影像为数据源,首先利用面向对象方法实现研究区林地和非林地分类;然后以林地为掩膜,提取出树冠分布范围;在此基础上,分别选取疏林区和密林区为试验区域,通过形态学开闭重建滤波,平滑图像,去除噪声;最后,利用标记控制分水岭分割方法分别对疏林区和密林区进行树冠提取。本文以人工勾绘结果为参考进行精度验证,结果显示疏林区F测度达到87.8%,密林区F测度达到65.5%,表明该提取方法简单易行,精度可靠。     

多边形叠加Vatti算法的VCS优化方法与GPU并行化

Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著。本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS（Vertex Coordinate Pre-Sorting）方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化。VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升。在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题。实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了4.9倍。     

基于计算网格的DEM空间分析系统

计算网格技术可以解决DEM空间分析中大数据量和高密度计算对计算资源的需求。计算网格平台Alche-mi给出了模型系统的架构设计和层次设计,将系统划分为DEM分析服务器、计算网格节点和空间数据库服务器;通过集中式空间数据库服务器和基于数据分解的方法设计了系统的并行算法。实例结果表明,应用网格技术可以显著提高大计算量DEM模型分析的运算效率,具有重要理论和现实意义。     

Blondel和k-核分解混合算法相结合的网络空间点群要素多尺度模型构建

随着人们对网络空间的依赖性不断增强,互联网技术与网络基础设施规模迅速发展。很难直接用数字或表格的形式对网络空间进行全局的规划与管理,并且不容易发现隐藏在网络空间中的一些关键信息。网络空间点群要素的多尺度模型构建对网络空间数据的多尺度分析和可视化具有非常重要的意义。本文以网络空间的特征为依据,在借鉴基于社团划分的网络空间分层算法和基于节点重要性的网络空间分层算法特点的基础上,提出了Blondel算法和k-核分解的混合算法相结合的网络空间点群要素多尺度模型构建算法。本算法通过自动社团划分,用同一社团内的节点合并构建新的网络,有效解决了基于节点重要性的网络空间分层算法自动化程度低的弊端。利用核心节点来代替整个社团结构,显著保留了网络空间中节点的属性。实验表明使用该算法可以使各个层次网络空间点群要素的综合比例降至30%以下,较好的实现了网络空间点群要素的聚类与分层,若将网络空间点群要素的多尺度模型应用于地理空间中,则可实现网络空间地图的多尺度绘制。     

一种基于小波分析的卫星钟差数据粗差处理方法

针对传统MAD方法在探测钟差粗差方面存在的不足,提出一种基于小波分析的钟差数据粗差探测与处理方法。该方法利用小波变换的多尺度分析能力,将含有粗差的数据分解为低频小波系数和各层的高频小波系数,并在不同时间尺度下进行粗差探测和消除。使用CODE提供的BDS精密钟差数据进行实验,分析不同小波函数及不同分解尺度对预处理效果的影响,并与传统MAD方法比较,发现利用小波分解预处理后的数据在钟差预报方面有明显优势,预报精度平均提高10%。     

林木多样性模型及生长模拟

林木生存环境复杂多变,导致林木形态千差万别,为了准确描述林木的形态多样性特征,提出了一种基于模型分解的林木生长模拟方法。首先构建多样性林木三维模型,使用林木形态的实际测量数据,基于B样条函数约束树干、树冠形态,依据削度方程模拟树干直径的变化趋势,利用Direct3D实现林木形态的三维建模;其次,按林木形态特征进行林木模型分解,将林木模型分为9个子模型;最后,使用场景节点按照拓扑结构关系对子模型进行动态组织,基于胸径、树高、枝下高、冠高和冠幅生长模型,使用多核CPU多线程并行的计算方式,获得各年龄阶段林木东、南、西、北方向形态参数,从而对子模型生长状态进行控制,实现林木不同方向生长变化的可视化模拟。结果表明：该方法可将林木三维模型与生长模型紧密结合起来,林木各方向的枝下高、冠高和冠幅严格按照生长模型进行生长,可有效模拟出林木各方向生长状态的多样性;三维场景渲染帧率（FPS）保持在25以上,平均FPS可以达到50,实现林木生长的方向异质性模拟。     

确定深基坑隆起破坏面的优化方法

采用有限元程序求得深基坑支护结构和土体开挖前后的应力状态以及土体任一点处的极限状态函数值;运用人工参与的优化方法选择坑底最大可能隆起破坏的起点与终点以及潜在隆起破裂面的形状和位置,并计算相应的安全系数。计算表明,潜在破裂面终点的位置对围护桩插入比不敏感．而潜在破裂面起点位置随围护桩入土深度的增加而逐渐靠近围护桩。工程实例证实了组合优化算法对潜在破裂面确定的有效性和实用性。     

C4.5算法与粗糙集在数据挖掘中的研究

分类在数据挖掘中是一项非常重要的任务,而决策树方法和粗糙集方法则是分类的主要方法.在详细介绍决策树方法的经典算法C4.5算法和粗糙集方法的基础上,针对C4.5算法的不足,引人粗糙集方法,提出新算法IC4.5来弥补C4.5算法的缺陷.并设计出一个基于C4.5算法和粗糙集算法的分类器,最后通过实验来证明基于IC4.5算法的分类器在抗噪声方面要优于C4.5算法.