检索结果-南通市图书馆

Improving Global Performance on GPU for Algorithms with Main Loop Containing a Reduction Operation: Case of dijkstra’s Algorithm

在线全文

学校读者我要写书评

暂无评论

Journal of Computer and Communications 2015年第8期3卷 41-54页

作者： Amadou Chaibou Oumarou Sie Laboratoire de Mathématiques et Informatique (LAMI) Université de Ouagadougou Ouagadougou Burkina Faso Département de Mathématiques et Informatique Université de Ouagadougou Ouagadougou Burkina Faso

In this paper, we study the impact of copying data in GPU computing. GPU computing allows implementing parallel computations at low cost: a GPU can be purchased at under USD 500. Many studies have shown that GPU can be used to speed up the calculations. But for algorithms requiring doing a part of the calculations on GPU and another part on CPU, alternately, latency due to the copy of the data is a performance degradation factor. To illustrate this, we consider the dijkstra’s algorithm on the shortest path used in solving optimization problems. This algorithm is very heavy to run on sequential machine. So, we are considering a parallel approach on GPU. Note that dijkstra’s algorithm has been subject of many implementations on GPU. In the present work, we use two platforms with external GPU. Graphs are represented in adjacency matrix. During the computation of this algorithm, intermediates results are copied from GPU to CPU or from CPU to GPU. The purpose of this work is to measure the impact of these copies in the overall performance of the algorithm. For that we calculate time due to the copying data’s implementation;then we compare results with implementation computing only on CPU memory (zero-copy). The real impact shown by experiments demonstrates the interest of this study. GP-GPU programmers have to think that they will use either memory zero-copy or GPU memory. The challenge for GPU’s manufacturers is how to reduce this impact.

关键词： GP-GPU Parallel Computing CUDA C dijkstra BGL Grid

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

对dijkstra量词研究的补充

南京大学学报（自然科学版） 2002年第1期38卷 110-118页

作者：梅卫锋张昱宋方敏南京大学软件新技术国家重点实验室南京210093

在dijkstra的研究工作的基础上 ,对量词作进一步的探讨 ,主要以存在量词的几个基本性质作为假定 ,并由此推出有关存在量词和全称量词的其他一系列的性质 .可视为dijkstra的补充。

关键词：量词存在量词谓词演算布尔结构 dijkstra 全称量词

改进dijkstra算法的城市道路最短路径仿真研究

在线全文

学校读者我要写书评

暂无评论

测绘科学 2013年第4期38卷 149-151页

作者：王华陕西交通职业技术学院西安710014

本文在分析dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度。仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15%～2... 详细信息

本文在分析dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度。仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15%～25%,当节点越多这种减少越明显,可提高搜索路径的实时性。

关键词： dijkstra 城市路网双向搜索改进算法搜索范围

Research on the Optimization and Simulation of the Shortest Path Based on Algorithm of dijkstra

在线全文

学校读者我要写书评

暂无评论

Journal of Measurement Science and Instrumentation 2010年第S1期1卷 199-201,37页

作者： Chuan-xiang REN,Xin-gang HAO,Ying-rui WANG, Guang-hui PAN (College of Information and Electrical Engineering,Shandong University of Science and Technology,Qingdao 266510,China)

dijkstra algorithm is a theoretical basis to solve transportation network problems of the shortest path, which has a wide range of application in path optimization. Through analyzing traditional dijkstra algorithm,on account of the insufficiency of this algorithm in path optimization,this paper uses adjacency list and circular linked list with combination to store date,and through the improved quick sorting algorithm for weight sorting, accomplish a quick search to the adjacent node,and so an improved dijkstra algorithm is got.Then apply it to the optimal path search,and make simulation analysis for this algorithm through the example,also verify the effectiveness of the proposed algorithm.

关键词： route optimization dijkstra algorithm fast sorting

基于dijkstra算法的巡航导弹航迹规划研究

在线全文

学校读者我要写书评

暂无评论

弹箭与制导学报 2003年第S5期23卷 123-125页

作者：胡晓磊鲁艺寇英信空军工程大学工程学院陕西西安710038

巡航导弹的航迹规划是依靠地形信息和敌情信息,在某些约束条件下,找出从发射点到目标点综合性能指标最优的飞行轨迹的过程。文中从易于工程实现的角度出发提出了一种威胁建模方法,把数字地图的大规模搜索空间转化为有向图网络,采用 Dijk... 详细信息

巡航导弹的航迹规划是依靠地形信息和敌情信息,在某些约束条件下,找出从发射点到目标点综合性能指标最优的飞行轨迹的过程。文中从易于工程实现的角度出发提出了一种威胁建模方法,把数字地图的大规模搜索空间转化为有向图网络,采用 dijkstra 算法来求解全局最优参考航线,仿真结果表明,优化的航迹能够很好的进行地形回避/威胁回避并满足巡航导弹的导航要求、突防要求以及飞行性能要求。

关键词：巡航导弹航迹规划 dijkstra 算法地形回避/威胁回避威胁模型

图结构与dijkstra算法在无人机航迹规划中的应用

在线全文

学校读者我要写书评

暂无评论

火力与指挥控制 2010年第4期35卷 155-157,160页

作者：阎昊樊兴夏学知武汉数字工程研究所武汉430074

对无人机任务区域内的航迹可以按照航迹节点和航迹段的方式建立拓扑关系。用图结构的形式对其进行描述,并用邻接矩阵和权值矩阵对该数据结构进行表达。根据dijkstra算法的原理计算出由出发点到各航迹节点间的最短航迹。

关键词：无人机航迹规划图 dijkstra

一种基于dijkstra的海量空间数据最短路径算法

在线全文

学校读者我要写书评

暂无评论

辽宁工程技术大学学报（自然科学版） 2009年第4期28卷 554-557页

作者：张福浩刘纪平辽宁工程技术大学测绘与地理科学学院辽宁阜新123000 中国测绘科学研究院北京100039

为了解决海量空间数据的快速网络分析,在分析dijkstra算法缺点的基础上,提出并详细介绍了一种基于dijkstra算法的优化算法—邻接结点算法,该算法充分利用了网络拓扑信息中的弧段的连接关系,避免了使用含有大量无穷值的关联矩阵,结果表明... 详细信息

为了解决海量空间数据的快速网络分析,在分析dijkstra算法缺点的基础上,提出并详细介绍了一种基于dijkstra算法的优化算法—邻接结点算法,该算法充分利用了网络拓扑信息中的弧段的连接关系,避免了使用含有大量无穷值的关联矩阵,结果表明:该优化算法可以节约大量的内存,适合海量数据的网络分析。实践证明,该算法对于结点数比较大的网络具有较好的适用性。

关键词：网络分析最短路径分析 dijkstra

在线全文

学校读者我要写书评

暂无评论

在ITS中dijkstra算法优化分析

武汉理工大学学报 2007年第4期29卷 122-124,143页

作者：尚前明严新平武汉理工大学仿真中心武汉430063 武汉理工大学ITS 武汉430063

网络搜索是一个经典的问题,在ITS(Intelligent Transportation System)中具有重要的意义。在ITS中,常常希望能在巨大的电子地图中搜寻一条最短路径。dijkstra算法是一种经典的路径算法,但是这种算法的效率不高,不足以满足在真实交通网... 详细信息

网络搜索是一个经典的问题,在ITS(Intelligent Transportation System)中具有重要的意义。在ITS中,常常希望能在巨大的电子地图中搜寻一条最短路径。dijkstra算法是一种经典的路径算法,但是这种算法的效率不高,不足以满足在真实交通网络图中搜索的实时响应的要求。于是,针对这种情况提出各种优化算法,提高经典dijkstra算法的效率。介绍了几种通过缩小搜索范围来提高搜索效率的算法,并通过在虚拟交通网络中做了大量的实验来分析这几种算法。

关键词：网络搜索 ITS dijkstra 算法

一种基于障碍物登陆点检测的全局路径规划算法

在线全文

学校读者我要写书评

暂无评论

中国惯性技术学报 2022年第3期30卷 388-394页

作者：王磊王毓孙力帆河南科技大学国际教育学院洛阳471023 河南科技大学信息工程学院洛阳471023

地图栅格化是机器人路径规划的常用方法,但地图规模的扩大会造成搜索栅格数量呈指数级增长,使得算法效率大幅下降。针对这一问题,提出了一种基于障碍物登陆点检测的全局路径规划算法。依据障碍物的分布特点,通过计算障碍物映射角寻找登... 详细信息

地图栅格化是机器人路径规划的常用方法,但地图规模的扩大会造成搜索栅格数量呈指数级增长,使得算法效率大幅下降。针对这一问题,提出了一种基于障碍物登陆点检测的全局路径规划算法。依据障碍物的分布特点,通过计算障碍物映射角寻找登陆点,并在障碍物边缘区域建立赋权图,缩小结点搜索范围,避免大规模搜索栅格结点;然后,依据赋权图特点对dijkstra算法进行改进,利用改进的dijkstra搜索全局最短路径。分别将所提的算法与传统A*算法及其变体JPS算法进行实验对比,结果表明,所提算法比传统A*算法以及JPS算法规划路径略短,搜索速度更快,尤其在走廊等障碍物块较少的大规模地图中,搜索时间仅为A*算法的1/8,JPS算法的1/3。

关键词：障碍物块登陆点碰撞检测 dijkstra 路径规划