一种改进的Dijkstra算法应用于嵌入式GIS系统

在实践中,Dijkstra算法是处理道路网络的最有效的算法之一。但Dijkstra算法每次都需要扫描节点集合中的所有节点,降低了算法效率。通过对前人的成果和嵌入式系统的性能进行研究和分析后,分两步来提高算法效率:第1步通过数据的预处理缩小算法的搜索范围;第2步为每个节点添加属性值、增加前趋表,以辅助算法快速找到一条最短路径。然后将此算法应用于嵌入式GIS系统中,并使用大量的数据进行测试,结果表明改进的算法明显提高了GIS系统的效率。

基于点云数据的树木骨架线提取研究

为了构建树木骨架线,利用三维激光扫描仪对树木扫描得到点云数据,以此为数据源,利用Geomagic软件去噪配准后构建树木三维模型,对树木主干、枝干分割后,利用Excel对点云数据进行微分后计算出每一小段的重心即骨架点,最后基于单源最短路径算法来构建出树木的骨架线,实验证明该方法简单可行,对树木三维建模以及林业研究有重要的意义。

图计算中遍历类图框架的特性

利用Skylake架构处理器上的性能分析工具perf分析Ligra、Gemini和GraphBIG等3种图计算框架中的单源最短路径(Single Source Shortest Path,SSSP)及介数中心性(Betweenness Centrality,BC)算法的特性,评估了在3种框架下实现两种算法的性能指标,并使用皮尔逊相关系数方法分析了各指标与性能/能耗之间的关系。实验结果表明,当缓存每千条指令的平均未命中数较大且每一时钟周期内执行的指令数较小时,图计算的执行时间较长。若数据移动量较小,则图计算的执行时间和功耗均较小。随着系统处理任务的线程数增加,图数据边的执行时间明显减少,通过增加处理单元个数的方式可以提高硬件加速器的性能。当处理器内核数小于4时,应优先选择Gemini框架实现算法,而当内核数大于4时,选择图框架Ligra能够有效减少执行时间。数据移动量和功耗与性能/能耗表现出极强的相关性。将图数据全部加载到内存中计算能够有效减少数据移动的次数。在处理较稀疏的图数据时,选择Ligra框架实现算法计算量较小。

无人机与无人车协作导航系统设计

为解决无人车在复杂环境或灾后环境下难以获知道路通阻情况而导致作业效率低的问题,利用无人机能垂直升降、多方位飞行的便捷性,设计了一种无人机引导无人车航行的系统,利用无人机、地面站处理器与无人车的相互协作,实现地图的建立与无人车的最优路径规划,使得无人车在无人机的导航下,能快速规避不畅通的道路,从而以最快效率行进到目的地。