-
题名基于K-最短路径的大规模函数调用关系分析
- 1
-
-
作者
张晶晶
石剑君
高玉金
计卫星
-
机构
北京理工大学计算机学院
-
出处
《计算机应用与软件》
2017年第12期26-31,共6页
-
文摘
函数调用关系反映了软件系统中函数之间的依赖关系,在软件分析、软件测试与软件维护等众多软件工程领域都有着广泛的应用。但在大型复杂软件中搜索两个函数之间的调用关系时,由于函数数量众多、函数之间调用关系复杂,使得搜索所需时间较长。为了获得任意两个函数之间的调用路径,提出使用K-最短路径算法,并对K-最短路径算法进行并行化优化,减少搜索时间,为用户分析函数调用关系提供方便。通过对Linux内核3.19(包含40多万个函数结点和110多万调用关系)进行分析,实验结果表明通过并行化优化,并行加速比一般可达5~6倍。
-
关键词
函数调用关系
k-最短路径
路径搜索
LINUX内核
-
Keywords
Function call relationship
k-shortest
Path search
Linux kernel
-
分类号
TP3
[自动化与计算机技术—计算机科学与技术]
-
-
题名多目标最短路径模型及算法
被引量:18
- 2
-
-
作者
郝光
张殿业
冯勋省
-
机构
铁道部经济规划研究院
西南交通大学物流学院
西南交通大学交通运输学院
-
出处
《西南交通大学学报》
EI
CSCD
北大核心
2007年第5期641-646,共6页
-
基金
西南交通大学交通运输工程研究生创新实践基地资助项目
-
文摘
为获得满足决策者需要的多目标最短路径问题的有效路径,建立了多目标最短路径模型,并提出了综合k-最短路径算法和多目标格序决策方法的多项式算法.该算法根据决策者可以接受的各单目标的上限,用k-最短路径算法,分别确定各单目标的可行路径集及其交集.再用多目标格序决策方法,比较交集中的有效路径,最终获得决策者满意的路径.
-
关键词
多目标
有效路径
k-最短路径
格序决策
模型
算法
-
Keywords
multi-objective
efficient path
k-shortest path
lattice-order decision-making
model
algorithm
-
分类号
U116.2
[交通运输工程]
-
-
题名求解区间图K-连接最短路径问题的在线算法
- 3
-
-
作者
徐云峰
Rudolf Fleischer
-
机构
复旦大学计算机科学技术学院上海市智能信息处理重点实验室
-
出处
《计算机工程》
CAS
CSCD
2012年第11期51-52,55,共3页
-
基金
国家自然科学基金资助项目(60973026)
上海市重点学科建设基金资助项目(B114)
上海市科委科技基金资助项目(08DZ2271800)
-
文摘
针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。
-
关键词
区间图
最短路径问题
k-连接最短路径问题
贪心算法
在线算法
-
Keywords
interval graph
shortest path problem
k-link Shortest Path(k-SP) problem
greedy algorithm
on-line algorithm
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名一种基于光网络的搜索K最短路径的Yen改进算法
被引量:2
- 4
-
-
作者
王为亮
谭绍锋
肖雁鹏
-
机构
中国电子科技集团公司第三十四研究所
-
出处
《光通信技术》
2022年第4期101-106,共6页
-
文摘
为提高K最短路径(KSP)算法中路径计算的效率和规划路径的相异性,首先介绍了光网络的图论描述、路径相近性定义和平行边的理论,然后对KSP问题和传统Yen算法进行了简单描述,分析了KSP算法研究现状,最后提出一种Yen改进算法,重点阐述了相异路径计算策略和Yen改进算法实现步骤。通过构建与实际生产环境类似的拓扑图,对Yen改进算法进行验证,并与其它算法进行路径相近性和计算时间对比,证明了其有效性。
-
关键词
k-最短路径
Yen算法
光网络
相异路径
-
Keywords
k-short path
Yen algorithm
optical network
dissimilar paths
-
分类号
TN256
[电子电信—物理电子学]
-
-
题名时变条件下有害物品运输的路径选择与决策
被引量:2
- 5
-
-
作者
李飘
于影霞
-
机构
华东交通大学交通运输与物流学院
-
出处
《华东交通大学学报》
2021年第1期79-87,共9页
-
基金
国家自然科学基金项目(71861011)。
-
文摘
为解决传统的路径规划中,目标少、静态性,无法真实模拟现实情境的问题。研究了时变条件下,同时考虑成本、环境风险、人口风险的多目标路径优化及选择问题。建立了时变条件下多个不同出发时间且有到达时间限制的有害物品运输的多目标最短路径选择的数学模型;设计了该模型下的相关算法;考虑到实际决策环境的复杂度以及决策者理性的有限性,提出了综合k-最短路径算法和逼近理想解排序法(TOPSIS法)的算法,用k-最短路径算法分别确定各单目标的有效路径,再用TOPSIS法计算各有效路径到正负理想解的欧氏距离以及贴近度,比较优选决策者满意的路径。最后通过一个算例,证明所提出的模型是有效的。
-
关键词
时变网络
有害物品运输
多目标优化
扩展型Dijkstra法
k-最短路径
TOPSIS法
路径选择
-
Keywords
time-varying network
transportation of hazardous materials
multi-objective optimization
extended Dijkstra method
k-shortest path
TOPSIS method
path selection
-
分类号
U16
[交通运输工程]
X951
[环境科学与工程—安全科学]
-
-
题名突发事件条件下列车运行k-最短路模糊蚁群算法
被引量:5
- 6
-
-
作者
张兰霞
秦勇
孟学雷
张涛
-
机构
北京交通大学交通运输学院
北京交通大学轨道交通控制与安全国家重点实验室
兰州交通大学交通运输学院
中国铁道科学研究院通信信号研究所
-
出处
《模糊系统与数学》
CSCD
北大核心
2016年第4期159-168,共10页
-
基金
国家科技支撑计划项目(2009BAG12A10)
国家自然科学基金资助项目(61263027)
+1 种基金
甘肃省自然科学基金资助项目(213227)
高等学校博士学科点专项科研基金新教师类资助课题(20126204120002)
-
文摘
突发事件造成铁路线路区间的通过能力受损,在成网条件下,铁路行车调度指挥工作客观上需要搜索列车运行k-最短路。根据突发事件的影响程度设定区间距离的事故等级系数,针对突发事件的模糊性定义了模糊隶属度函数,得到了突发事件条件下模糊区间距离;考虑列车模糊停站时分对运行径路的影响,将列车的模糊停站时分转化为广义距离;将模糊区间距离与广义距离应用到突发事件条件下铁路路网构建中,很好地处理了突发事件条件下路网信息的不确定性问题。在应用蚁群算法求解最短路径的基础上,引入了C-enough概念,将其应用于搜索突发事件条件下k-最短路径问题中。以我国部分路网为例,与传统的Dijkstra算法对比验证了模糊蚁群算法的高效性和实用性,可为列车运行调度指挥提供一定的借鉴。
-
关键词
突发事件
模糊蚁群算法
模糊停站时分
C-enough
k-最短路径
-
Keywords
Emergencies
Fuzzy Ant Colony Algorithm
Fuzzy Dwell Time
C-enough
k-shortest Paths
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
U292
[交通运输工程—交通运输规划与管理]
-
-
题名基于KSP和重路由机制的WDM光网络路由优化
被引量:2
- 7
-
-
作者
李春贵
伍玉秀
-
机构
广西科技大学计算机科学与通信工程学院
柳州铁道职业技术学院信息技术学院
-
出处
《光通信技术》
北大核心
2017年第11期37-41,共5页
-
基金
国家自然科学基金(61302178)资助
广西自然科学基金(2013GXNSFAA019347)资助
-
文摘
针对波分复用(WDM)光网络中的传统路由和波长分配(RWA)算法不能有效降低阻塞率的问题,提出了一种基于K-最短路径(KSP)算法和顺序主动光路重路由(S-ALR)机制的路由优化方案。将WDM全光网络构建成一个由顶点、边和权重构成的图模型;当一个随机光路请求(RLD)到达时,先利用KSP算法寻找一条距离最短的路径和替代路径集合;当一个RLD离开时,相应的WDM通道被释放后启动重路由过程,调整现有RLD的路径以此充分利用空闲链路。仿真结果表明,提出的方案能够有效降低网络的阻塞率。
-
关键词
WDM光网络
路由和波长分配
k-最短路径
光路重路由
-
Keywords
WDM optical network
routing and wavelength assignment
K shortest paths
lightpath re-routing
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名设备参数变化的批量轧制调度问题模型与算法
- 8
-
-
作者
孙凯
杨根科
潘常春
-
机构
山东轻工业学院电气工程与自动化学院
上海交通大学自动化系
-
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2011年第7期1501-1508,共8页
-
基金
山东省自然科学基金资助项目(ZR2010FQ009)
国家自然科学基金资助项目(61074150)~~
-
文摘
针对冷轧平整机轧件与轧辊参数耦合的特点,建立了设备参数动态变化下批量轧制调度问题的数学模型。以轧辊磨损函数为切入点,通过分段线性简化轧辊磨损曲线,将复杂的调度问题分解为三个子问题。开发了基于分散搜索和动态规划相结合的混合策略,首先根据约束条件将轧件分配到不同的类中,然后通过分散搜索对每个轧件类求解K-最短路径问题,最后通过动态规划将这些子问题的解合成为一个原问题的可行解。通过某大型钢厂的实际生产数据验证了算法的有效性。
-
关键词
批量轧制调度问题
参数耦合
分散搜索
动态规划
k-最短路径问题
-
Keywords
batch rolling scheduling problem
parameter coupling
scatter search
dynamic programming
k-constrained shortest path problem
-
分类号
TP29
[自动化与计算机技术—检测技术与自动化装置]
-
-
题名一种改进FAR的WDM光网络路由和波长分配方案
- 9
-
-
作者
何健
韦玉科
-
机构
罗定职业技术学院电子信息系
广东工业大学计算机学院
-
出处
《光通信技术》
北大核心
2017年第12期13-15,共3页
-
基金
国家自然科学基金项目(61302178)资助
-
文摘
针对WDM光网络中的路由和波长分配(RWA)问题,提出一种基于改进型固定备用路由(FAR)机制的RWA方案。同时,利用现有的最大使用(MU)机制来分配波长。仿真实验表明,与传统的FAR技术相比,对于任何负载、波长数,所提RWA方案具有更低的请求阻塞率和较高的实用价值。
-
关键词
波分复用
光电混合网络
路由和波长分配
固定备用路由
k-最短路径
链路成本函数
-
Keywords
WDM
photoelectric hybrid network
routing and wavelength allocation
fixed alternate routing
k-shortest route
link cost function
-
分类号
TN929.11
[电子电信—通信与信息系统]
-
-
题名一种能耗优先的WSN强栅栏覆盖方法研究
- 10
-
-
作者
方凯
吴武豪
陈琼
-
机构
中电海康集团有限公司
-
出处
《智能物联技术》
2018年第2期7-12,共6页
-
文摘
无线传感器网络栅栏覆盖在入侵监测领域发挥着重要的作用,如何高效、低代价地构建栅栏以及栅栏出现间隙后如何修复是重点研究问题。针对该问题提出一种能耗优先的WSN栅栏覆盖方法,首先根据静态传感器节点构建全连接拓扑图,然后将全连接拓扑图转换为可移动节点需求拓扑图,接着采用K-最短路径算法和匈牙利算法选择可移动节点需求拓扑图中的最佳栅栏构建路径并派遣可移动节点完成栅栏的构建。该方法在充分利用静态传感器节点的基础上派遣少量可移动传感器节点即可完成栅栏的构建。实验结果表明在栅栏构建和修复方面与其他方法相比节约了能量,且栅栏修复率比Optimal方法提高了8%。
-
关键词
WSN
栅栏覆盖
低能耗
k-最短路径
匈牙利算法
-
Keywords
WSN
barrier coverage
low energy consumption
KSP
hungarian algorithm
-
分类号
TP212.6
[自动化与计算机技术—检测技术与自动化装置]
-