【摘 要】
:
全源最短路径是图计算的一个典型问题,它与描述复杂系统的最基本特征量——平均路径长度的求解密切相关,这为深入研究真实的复杂网络系统的基本构造与特征量奠定了基础。不仅如此,随着人类对生产与生活效率需求的增加,有关最短路径的问题越来越成为了不同专业的研究基础,为交通运输、旅行路径选取等问题提供了有效解决办法。因此,全源最短路径问题其具有重大的理论意义和很高的实用性。尽管求解最短路径的优化算法不断涌现,但
论文部分内容阅读
全源最短路径是图计算的一个典型问题,它与描述复杂系统的最基本特征量——平均路径长度的求解密切相关,这为深入研究真实的复杂网络系统的基本构造与特征量奠定了基础。不仅如此,随着人类对生产与生活效率需求的增加,有关最短路径的问题越来越成为了不同专业的研究基础,为交通运输、旅行路径选取等问题提供了有效解决办法。因此,全源最短路径问题其具有重大的理论意义和很高的实用性。尽管求解最短路径的优化算法不断涌现,但随着图的规模急剧扩大,求解全源最短路径的困难也愈来愈大。对于大规模的图数据,单机的计算资源无法一次性承载其全源最短路径的计算任务,所以人们研究了若干分布式图计算系统,以实现针对大规模图数据的分布式计算。然而,分布式集群又意味着较高的成本,往往为普通用户所不可得。综上所述,研究一种单机系统下求解大规模图的全源最短路径的方法具有十分重要的意义。本文提出了一种求解大规模图的全源最短路径的分治策略,该策略将一个大图划分规模较小的子图,分别计算各子图的全源最短路径,并对子图的路径进行合并,从而得到整个图的全源最短路径。在该过程中,本文通过一个有效的图划分算法得到一个最优的顶点序列,按照该序列中的顶点顺序依次将图中顶点进行分割,最终能够以较少的分割点和较快的速度将一个大规模图进行划分。接着,在每个子图上使用改进的Dijkstra算法求出各自的全源最短路径,然后利用子图间相同的分割点将路径拼接起来,计算出整个图的全源最短路径结果。另外,本文还借鉴LRU策略的思想,对内存中的grid进行置换。本文提出的算法在真实的图数据集上行之有效,对于有限资源下求解规模较大图的平均最短路径和中心介数性提供了有效的方法,为研究网络的拓扑结构和解决实际问题提供了支持。
其他文献
近年来,非线性偏微分方程得到了广泛的研究。非线性微分-差分方程(有时也称为晶格方程)作为非线性偏微分方程的空间离散对应形式,因其可用于描述不同领域的各种物理现象,同样引起了人们的广泛关注。离散Toda晶格方程是Lax可积的非线性微分-差分方程的第一个例子,它可以描述晶格中在指数形式相互作用力作用下的粒子运动。Toda晶格方程对研究晶格中格子动力学中的非线性波、遍历理论等都有很好的理论意义。本文以2
基于视觉的环境感知技术被应用于日常生活中的各个方面,具有重要的研究价值与现实意义。伴随着应用场景的复杂化,目标识别与跟踪等环境感知能力也要相应满足更高要求。但现存目标识别与跟踪技术在室内遮挡与室外开放等场景的精度及速度尚不能满足实际需求,无法出色地完成环境感知任务。本文利用深度卷积网络技术对武装人员及枪械等动态武装目标的识别与跟踪算法展开研究,提高视觉感知算法在实际场景应用中的有效性及鲁棒性,主要
随着城镇化和经济的快速发展,住宅建筑面积增长迅速,导致了住宅建筑的耗电量和二氧化碳(CO2)排放的急剧增长。因此住宅建筑的用电分析及其预测研究对建筑的节能和可持续发展具有重要意义。本文以住宅建筑的天气、温度和湿度以及用电量作为研究对象,通过研究基于数据包络分析(Data Envelopment Analysis,DEA)的Malmquist指数和基于贝叶斯优化算法(Bayesian Optimiz
近些年,随着微波集成电路的发展,对不同模块之间和不同层或同一层微波传输线之间的互连提出了越来越高的要求。选择一种合适的互连过渡方式有利于将不同优点的传输线集成于同一微波系统中以实现更好的性能,同时可以改变信号传播的方向以实现微波器件小型化。同时,第五代移动通信技术(The Fifth Generation,5G)的快速发展也要求滤波器具有适用于5G的性能指标。针对以上应用需求,本文的主要内容是微波
图像配准是指通过寻找最佳的空间变换关系,让两幅不同成像条件下获取的图像实现最佳对准的过程。近年来图像配准技术蓬勃发展,在医学、材料力学以及遥感等领域已经得到了广泛应用。其中遥感领域的配准是遥感图像解译的基础性工作,只有在对图像精确配准之后才可以进行后续的图像融合、变化检测等操作。光学遥感影像通常分辨率高,可以提供地面目标更丰富的细节信息,所以针对光学遥感影像的图像配准技术成为了遥感技术的探究重点之
滚动轴承的健康运行对机械设备的安全具有极其重要的作用,为防止滚动轴承失效而导致机械故障,通过对滚动轴承退化机理进行研究,实现对其剩余寿命的预测,已成为制造行业研究领域中的热点问题。本文通过分析滚动轴承的振动信号,研究了基于自编码器的特征融合方法,基于Bi LSTM-CRF的轴承剩余寿命预测方法。本文主要研究工作如下:1)基于轴承的失效形式、退化规律和主流的振动信号特征提取研究,通过分析并提取轴承的
学生在线编程评测系统(Online Judge System,OJ)被广泛应用于程序设计的教学之中。但现有OJ系统只返回程序是否正确。学生由于缺乏编程的实践经验,在独立定位程序发生错误位置的过程中经常遇到困难且难以自我解决。自动错误定位技术可以帮助程序开发人员定位错误,但现有错误定位技术的研究基于人工植入错误的开源项目或者工业程序,在包含真实错误的学生程序上定位错误精度不高。为了提升自动错误定位技
简缩极化(Compact Polarimetric,CP)是针对目前的合成孔径雷达(SAR)系统提出的一种新的SAR极化工作模式。简缩极化在一定程度上融合了全极化和双极化的优点,有效规避了二者的缺点。与双极化相比,可以通过调节发射信号之间的相对相位来获取更加丰富的地物信息,能更好的描述地物真实形貌;同样也可以视为全极化系统不同通道间信息的线性组合,它能有效避免全极化系统在成像幅宽、系统设计等方面的
相较于传统控制方法,模糊控制能够有效处理复杂系统中存在的不精确性问题,从而得到了广泛应用。随着其应用范围的不断扩大,基于模糊控制的被控系统安全性就显得尤为重要;而传统的测试方法由于无法覆盖所有输入空间,因此不能确保结论的完备性;为了将形式化验证方法引入基于模糊控制的应用验证中,保证其结论对于任意输入均成立,建立一个可复用的模糊控制器形式化模型是必不可少的工作。为此,本课题采用了形式化方法中的定理证
数字电路的功能可靠是集成电路行业发展的重要基础,基于模型的验证方法被广泛应用于数字电路功能验证中。但是,目前大多数建模方法复杂度较高,所建模型难以准确表示数字电路的功能行为和时序行为,进而难以确保基于模型进行的功能验证是有效和充分的。扩展有限状态机(Extended Finite State Machine,EFSM)作为一种形式化描述模型,能够准确表征系统的动态行为,常用于各类系统的建模与验证中