遗传算法在路径规划上的应用 被引量：13

1

作者 李敏 黄敏 +1 位作者 程智锋 周静 《计算机系统应用》 2020年第8期255-260,共6页

为了满足出行者能高效快捷地到达目的地,需要找到一条综合权值最优的出行路径,再在其上设置指路标志对目的地进行指引.基于此,本文首先根据路网的特点,对交通路网模型进行表述;接着阐述了遗传算法的基本概念和算法思想,并以行驶路程和... 为了满足出行者能高效快捷地到达目的地,需要找到一条综合权值最优的出行路径,再在其上设置指路标志对目的地进行指引.基于此,本文首先根据路网的特点,对交通路网模型进行表述;接着阐述了遗传算法的基本概念和算法思想,并以行驶路程和交叉口个数作为出行者路径选择的因素,定义了行驶路程和交叉口个数综合指标最小的路径为最优路径;最后,以广州大学城中山大学为例,在明确起终点的情况下,利用遗传算法的方法找到了去往中山大学的最优路径,验证了遗传算法在路径规划上的有效性. 展开更多

关键词 交通路网 遗传算法 路径规划 单源路径

下载PDF 职称材料

单源路径搜索算法的实现及比较 被引量：1

2

作者 冷劲夫 胡燮 胡颖 《地理空间信息》 2010年第3期154-156,共3页

单源路径搜索算法广泛应用于紧急出警、车载导航、物流配送和管线规划与设计等地理信息系统(GIS)相关领域。而在"连连看"游戏中,需要一种特殊的单源路径搜索方案,对此提出了一种算法,通过记录候选节点的转角数来筛选满足要求... 单源路径搜索算法广泛应用于紧急出警、车载导航、物流配送和管线规划与设计等地理信息系统(GIS)相关领域。而在"连连看"游戏中,需要一种特殊的单源路径搜索方案,对此提出了一种算法,通过记录候选节点的转角数来筛选满足要求的路径。依据这一算法的两种实现策略-宽度优先搜索(BFS)和深度优先搜索(DFS),采用标准模板库(STL)技术,编写了相应的代码,并对这两种策略进行了详细的测试,比较了它们的实际搜索性能。 展开更多

关键词 GIS 单源路径搜索 宽度优先搜索(BFS) 深度优先搜索(DFS)

下载PDF 职称材料

基于单源最优路径的NOMA中继选择与协作传输 被引量：3

3

作者 陆音 汪高瑜 +3 位作者 杨楚瀛 杨凌青 赵坤 朱洪波 《系统工程与电子技术》 EI CSCD 北大核心 2022年第1期292-298,共7页

目前,在非正交多址接入(non-orthogonal multiple access, NOMA)中继通信的研究中,中继用户的选择是随机的,并没有考虑中继节点之间信道条件的差异。为了得到信道条件较好的中继用户,提出一种基于单源最优路径的中继选择策略,从基站广... 目前,在非正交多址接入(non-orthogonal multiple access, NOMA)中继通信的研究中,中继用户的选择是随机的,并没有考虑中继节点之间信道条件的差异。为了得到信道条件较好的中继用户,提出一种基于单源最优路径的中继选择策略,从基站广播信号以用户为节点,设定信道参数,寻找最佳传输通路。当信号到达目标节点后,基站从目标节点处收集所有可达通路,通过对比各通路的信道参数,选出一条最好的传输通路。基于所提中继选择策略,在非机会式NOMA系统中,提出一种新的协作传输方法,该方法在中继传输过程中剔除了多余信号以降低信号间干扰。仿真结果表明,在相同条件下,采用所提策略的协作传输方法比随机中继选择用户中断概率更低,有效降低了系统复杂度。 展开更多

关键词 非正交多址接入 中继选择 单源最优路径 信道参数

下载PDF 职称材料

单源多路径配装-运输集成模型算法研究

4

作者 朱伟 徐克林 +1 位作者 周娜 李艳冰 《工业工程》 北大核心 2011年第2期66-69,共4页

货物配装和运输是物流配送系统的重要组成部分,是提高物流配送系统运作效率的关键。针对物流配送系统的复杂约束,建立了单源多路径配装-运输集成模型。为求解上述模型,采用基于客户点序号编码,最大保留交叉和自适应交叉变异等技术,设计... 货物配装和运输是物流配送系统的重要组成部分,是提高物流配送系统运作效率的关键。针对物流配送系统的复杂约束,建立了单源多路径配装-运输集成模型。为求解上述模型,采用基于客户点序号编码,最大保留交叉和自适应交叉变异等技术,设计了改进的遗传算法。实例计算表明,模型和算法可行有效,能较好地解算单源多路径配装-运输问题,为物流配送系统的优化提供了新的思路。 展开更多

关键词 改进遗传算法 单源多路径 集成的配装-运输

下载PDF 职称材料

SPFA算法的分析及改进 被引量：17

5

作者 夏正冬 卜天明 张居阳 《计算机科学》 CSCD 北大核心 2014年第6期180-184,213,共6页

SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在... SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为Θ(|V||E|);在存在源点可达负圈的有向图中,算法将无限运行下去。对此,给出了改进的SPFA算法,对于任意的有向图,该算法能够在O(|V||E|)内运行完毕。最后,从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较。 展开更多

关键词 组合算法 单源最短路径 SPFA算法 Bellman-Ford算法

下载PDF 职称材料

一种改进的Dijkstra算法应用于嵌入式GIS系统 被引量：6

6

作者 张雪燕 黄寅 杨晟刚 《计算机工程与设计》 CSCD 北大核心 2007年第2期412-414,共3页

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

关键词 DIJKSTRA算法 单源最短路径算法 多源最短路径算法 嵌入式GIS 前趋表

下载PDF 职称材料

基于单源最短路径算法的井下避灾路线 被引量：7

7

作者 李媛 高淑娟 洪玉玲 《煤矿安全》 CAS 北大核心 2013年第8期191-193,共3页

基于单源最短路径算法理论,针对井下网络节点的特点对巷道各类数据结构做以扇形优化,计算出各段巷道的长度当量,并开发了windows操作系统下的网络路线选择软件。

关键词 避灾路线 单源最短路径 扇形优化 最短路径

原文传递

单源最短路径算法的图示教学设计与实践 被引量：4

8

作者 沙宗尧 边馥苓 《测绘通报》 CSCD 北大核心 2010年第4期58-61,共4页

单源最短路径是GIS网络分析的一个重点内容,对GIS、空间信息技术等相关专业的学生来讲,由于经典的最短路径算法(Dijkstra)描述较抽象,让学生掌握单源最短路径算法的本质思想较难。提出用图示教学法来教授GIS中单源最短路径算法的基本原... 单源最短路径是GIS网络分析的一个重点内容,对GIS、空间信息技术等相关专业的学生来讲,由于经典的最短路径算法(Dijkstra)描述较抽象,让学生掌握单源最短路径算法的本质思想较难。提出用图示教学法来教授GIS中单源最短路径算法的基本原理和思路,详细介绍了图示表示的过程,可以为最短路径算法及其应用的教学过程提供参考。 展开更多

关键词 GIS 网络分析 图示教学法 单源最短路径

下载PDF 职称材料

基于有向图的流式文档逻辑结构重构方法 被引量：4

9

作者 赵林 李宁 彭欣 《计算机工程与设计》 北大核心 2016年第5期1239-1244,共6页

为解决以往流式文档中逻辑结构重构方法的不足,提出一种基于有向图的流式文档逻辑结构重构方法。从模板文档中提取逻辑结构,在此基础上,通过对待查文档中的逻辑标签进行筛选建立有向图,利用有向图的单源最短路径算法过滤多余的逻辑结构... 为解决以往流式文档中逻辑结构重构方法的不足,提出一种基于有向图的流式文档逻辑结构重构方法。从模板文档中提取逻辑结构,在此基础上,通过对待查文档中的逻辑标签进行筛选建立有向图,利用有向图的单源最短路径算法过滤多余的逻辑结构,得到最佳的文档逻辑结构。实验结果表明,该算法能够有效改善逻辑结构识别的准确性,对于文档内容理解和自动化排版与格式检查等应用具有重要意义。 展开更多

关键词 逻辑结构重构 逻辑标签 自动排版格式检查 流式文档 单源最短路径

下载PDF 职称材料

单源最短路径问题的改进算法 被引量：4

10

作者 周玉林 《上饶师范学院学报》 2001年第3期18-22,共5页

探讨了单源最短路径问题算法所能达到的时间复杂性的下界 ,提出了时间复杂性为O(tn+m)和O(nlogt+m)的改进算法 ,其中n =|V|,m =|E|,t为从优先队列中抽取最小结点的次数 ,我们主要用Fibonacci堆和拓扑排序的思想方法。

关键词 单源最短路径 拓扑排序 Fibonacci堆 算法 优先队列 时间复杂性

下载PDF 职称材料

基于GPU的单源最短路径算法设计与实现 被引量：4

11

作者 郭绍忠 王伟 +1 位作者 周刚 胡艳 《计算机工程》 CAS CSCD 2012年第2期42-44,共3页

针对目前图形处理器(GPU)上的动态数据处理问题,在分析现有并行单源最短路径(SSSP)算法的基础上,对GPU上的Moore SSSP算法进行并行化设计与实现。搜索时,综合应用层次化任务分配、层次化工作队列、层次化Kernel调用等策略。在不同类型... 针对目前图形处理器(GPU)上的动态数据处理问题,在分析现有并行单源最短路径(SSSP)算法的基础上,对GPU上的Moore SSSP算法进行并行化设计与实现。搜索时,综合应用层次化任务分配、层次化工作队列、层次化Kernel调用等策略。在不同类型图数据上进行实验测试,实验结果表明,该算法能有效减少空线程开销、访存开销以及同步时间。 展开更多

关键词 图形处理器 图论 动态数据 单源最短路径 计算统一设备架构

下载PDF 职称材料

一种基于桶结构的单源最短路径算法 被引量：4

12

作者 魏文红 李清霞 蔡昭权 《计算机工程与科学》 CSCD 北大核心 2012年第4期77-81,共5页

以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法,结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想,提出了一种基于桶结构的单源最短路径... 以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法,结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想,提出了一种基于桶结构的单源最短路径算法。实验结果表明,该算法与前两种算法相比,具有好的运行时间复杂度和可并行性。 展开更多

关键词 桶结构 单源最短路径 DIJKSTRA算法 BFM算法

下载PDF 职称材料

最短路径问题的若干算法的编程 被引量：3

13

作者 王强 《计算机科学》 CSCD 北大核心 2004年第B07期94-95,100,共3页

本文讨论了带权图的最短路径问题的三类不同情况，针对每种情况介绍了较好的算法，并在MATLAB软件环境下编制了这些算法的程序。通过一个实例，验证了算法的正确性。

关键词 最短路径问题 算法 带权图 MATLAB软件环境 正确性 单源最短路径 单汇最短路径

下载PDF 职称材料

两种GPU上改进的最短路径算法 被引量：3

14

作者 刘欣 王非 《计算机应用研究》 CSCD 北大核心 2014年第5期1407-1409,1413,共4页

针对图论中的最短路径问题，提出了两种在GPU上改进的最短路径搜索算法，即针对单源最短路径问题的基于迭代方式且采用原子锁优化的Advanced_Atomics-SSSP算法以及针对所有顶点间最短路径问题的采用二叉堆优化的Heap-APSP算法。将两种... 针对图论中的最短路径问题，提出了两种在GPU上改进的最短路径搜索算法，即针对单源最短路径问题的基于迭代方式且采用原子锁优化的Advanced_Atomics-SSSP算法以及针对所有顶点间最短路径问题的采用二叉堆优化的Heap-APSP算法。将两种算法应用到美国公路网图和节点的度均为6的普通图中，通过对算法的测试表明，Advanced-Atomics-SSSP算法的性能依赖于节点的度数，当节点的度数大于6时加速效果明显，当节点度数为1～3时加速效果不明显；而Heap-APSP可以达到46-56倍的加速比，且加速性能不受节点度的影响。 展开更多

关键词 DIJKSTRA算法 单源最短路径 所有顶点间最短路径 原子锁 二叉堆

下载PDF 职称材料

单源最短路径问题的Seidel迭代法 被引量：3

15

作者 伍建华 祁文清 晏伯武 《计算机应用》 CSCD 北大核心 2001年第z1期25-26,共2页

该文提出一种有别于Dijkstra法的Seidel迭代法。虽然在最坏情况下不优于Dijkstra法 。

关键词 单源最短路径 Dijkstra法 Seidel迭代法

下载PDF 职称材料

基于点云数据的树木骨架线提取研究 被引量：3

16

作者 李杨 李秀峰 《科技创新与生产力》 2017年第6期53-55,共3页

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

关键词 三维激光扫描 点云数据 骨架线 单源最短路径算法

下载PDF 职称材料

单汇最短路径问题的一种算法

17

作者 伍建华 祁文青 晏伯武 《黄石高等专科学校学报》 2001年第2期5-6,42,共3页

提出单源最短路径的逆问题———单汇最短路径问题 ,并给出相应的算法。

关键词 汇点 单汇最短路径问题 单源最短路径问题 迭代算法 迭代函数

下载PDF 职称材料

SiBNC多元陶瓷先驱体的最新发展与展望 被引量：2

18

作者 雷成乐 陈立新 +1 位作者 张建柯 何玮奇 《材料导报》 EI CAS CSCD 北大核心 2012年第17期44-48,共5页

综述了近年来聚硅硼氮碳烷陶瓷先驱体的分子设计、合成和陶瓷性能的研究新进展,详细介绍了聚合物路径和单源先驱体路径两种合成方法,对两种方法合成的先驱体进行分类详述,比较了先驱体合成产率、陶瓷转化率及热稳定性。亦提出将紫外光... 综述了近年来聚硅硼氮碳烷陶瓷先驱体的分子设计、合成和陶瓷性能的研究新进展,详细介绍了聚合物路径和单源先驱体路径两种合成方法,对两种方法合成的先驱体进行分类详述,比较了先驱体合成产率、陶瓷转化率及热稳定性。亦提出将紫外光固化陶瓷先驱体方法引入到SiBNC陶瓷的改性中来,将为先驱体转化法制备SiB-CN多元陶瓷材料提供一条新的技术途径。 展开更多

关键词 SiBNC 先驱体转化法 聚合物路径 单源先驱体路径

下载PDF 职称材料

基于OpenMP的Dijkstra算法并行优化研究 被引量：2

19

作者 侯竞夫 《中国科技信息》 2022年第11期110-111,共2页

1959年,计算机科学家E.W.Dijkstra提出了Dijkstra算法。Dijkstra算法是一种解决单源最短路径问题的贪心算法,其作用主要表现在解决有向图中的最短路径问题方面。但随着科学技术的发展,Dijkstra算法的应用领域得到了极大的扩展,“最短路... 1959年,计算机科学家E.W.Dijkstra提出了Dijkstra算法。Dijkstra算法是一种解决单源最短路径问题的贪心算法,其作用主要表现在解决有向图中的最短路径问题方面。但随着科学技术的发展,Dijkstra算法的应用领域得到了极大的扩展,“最短路径”也被赋予了全新的含义,不再单单指空间中的最短距离,同样也可以用来研究各种时间、经济、能量消耗问题。但是,随着研究问题的复杂化以及所研究数据规模的逐渐扩大,传统的串行Dijkstra算法计算量大、时间复杂度较高的问题也逐渐体现出来,影响着Dijkstra算法在诸多问题中的表现。而并行化计算不仅在计算大规模数据时表现优异,也非常契合Dijkstra算法的算法思想。 展开更多

关键词 DIJKSTRA算法 单源最短路径 贪心算法 大规模数据 数据规模 并行优化 最短距离 计算机科学家

下载PDF 职称材料

贪心算法的探讨及其在船舶领域的应用 被引量：2

20

作者 姚菊菊 《造船技术》 2015年第6期22-25,37,共5页

贪心算法是在求问题的最优解时,从最初的状态,通过一系列在当前环境下所能做出的最优的选择而得到整个问题的最优解,这便是贪心算法的基本思想。从中不难发现,贪心算法只能达到局部的最优解,它对于当前做出的选择只依赖于以往做出的选择... 贪心算法是在求问题的最优解时,从最初的状态,通过一系列在当前环境下所能做出的最优的选择而得到整个问题的最优解,这便是贪心算法的基本思想。从中不难发现,贪心算法只能达到局部的最优解,它对于当前做出的选择只依赖于以往做出的选择,而不与未来做出的选择相关,即不依赖子问题的解。这也就决定了贪心算法在解决问题时有一定的速度优势,由于此解决问题的优势使得它成为最优方案的备选方法之一。本文论述了贪心算法的实现思路和过程、核心思想、基本特性、特点以及存在的问题,并详细论述了其在船舶建设领域中的几点应用。 展开更多

关键词 贪心算法 哈弗曼算法 单源最短路径

下载PDF 职称材料