基于子路径可用带宽测量的紧链路定位方法

针对现有紧链路定位方法存在测量负载较大、测量精度不高等问题,提出一种性能优秀的端到端主动测量方法——PathLoche。该方法通过设计一种新颖的包列Loche,逐步迭代测量子路径的可用带宽,进而得到整条网络路径的可用带宽并确定紧链路的位置。仿真实验表明,PathLoche测量精度高、入侵度低。

基于BSO-GA算法的机器人子区域覆盖路径规划

为解决传统子区域覆盖路径规划方法的环境普适性不足等问题,课题组设计了专门的头脑风暴-遗传算法BSO-GA。对原始头脑风暴算法个体更新方式进行了改进,单个个体更新采用遗传算法移位、倒位和换位算子的思想,混合个体更新采用贪心交叉算子。实验结果表明:BSO-GA在距离、运行时间上均优于头脑风暴算法、遗传算法、模拟退火算法和遗传-模拟退火算法;无论在普通作业环境还是特殊作业环境,该算法覆盖率均能达到100%,且没有路径交叉及重复现象,能够较好地完成覆盖任务。

最短路径子图

在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n+e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.

基于量子路径积分理论的大分子单缝衍射实验

以C_(60)分子的单缝衍射为例,通过求解薛定谔方程及费曼的路径积分方法,给出了C_(60)单缝衍射强度的解析式,利用该式分析了C_(60)单缝衍射实验,其理论计算结果与实验数据一致.

一种带匹配路径约束的最长公共子序列长度算法

在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度。

基于子路径扩展的不可达路径检测方法

不可达路径是造成软件测试资源消耗的一个重要方面.在路径测试之前,检测程序中的不可达路径可以有效节约软件测试资源.提出了一种基于子路径扩展的不可达路径静态检测方法.该方法首先生成程序的子路径集,将路径的可达性问题转换为不等式组的求解问题.使用约束求解器判断子路径的可达性,可以分为:可达子路径,不可达子路径和无法判定三个部分,并对后面两部分的子路径扩展出的路径做二次可达性检测,最终获得程序中所有路径的可达性信息.可达性检测工作主要在子路径集上进行,因此有效地解决了路径爆炸问题.实验结果表明本文方法可以准确有效地检测出程序中的不可达路径.

控制子区内协调路径集的构成及优选方法

为了实现城市交通信号协调控制的精细化,协调对象的选取不应停留在子区层面,而需要进一步细化到有向路径连线上。文中通过定义协调路径、协调路径链与协调路径集,以及构成路径链的父路径与子路径,建立了一套可以反映协调控制方向性需求的概念体系,并分析了路径链的计数方法。针对路网中车辆的轨迹分布,从路径链经过的交叉口数量(路径链长度)和所承载的交通流量的角度出发,分别制定了相应的协调路径集优选法则与流程。算例分析结果表明,文中方法能够根据拟协调的交叉口数量和行驶路径流量,选出控制区域内流量较大的主要路径链,从而进一步丰富控制子区与交叉口群的划分理论。

基于成对可替代子路径的交通分配改进算法

以Bar-Gera设计的基于成对可替代子路径(PAS)的交通分配算法(TAPAS)为研究对象,注意到TAPAS算法为了追求最大熵用户均衡交通分配,存储了大量PAS并从中选择PAS集合进行流量转移。由于很多交通分配问题更加专注于提高算法的收敛速度和其简易性,将算法的核心操作仅限于当前新构建的有效PAS(不再存储PAS集合),在新构建的PAS上转移流量以均衡子路径费用,在相关起点之间均衡路径流量比例。设计包括有效PAS构建子算法、基于PAS的流量转移子算法和基于PAS在相关起点之间均衡路径流量等比例分配子算法。通过数值试验算例分析,结果表明:相比原算法,仅基于当前新构建PAS上进行流量转移的交通分配改进算法的收敛效率不会降低,同时,改进后的算法结构更简单,编程工作量更小,对部分案例来说更适于应用。

带时间窗限制的车辆调度子路径平衡性研究

带时间窗限制的车辆路径规划问题(VRPTW)是物流领域中一个很重要的问题。路径平衡性作为该问题域新兴的需求,迫切需要得到更深入的研究。本文基于其国际标准测试用例,设计了一个三阶段启发式算法,与已公布的最佳结果比较,该算法以较小的代价获得了更佳质量的近似解。

对弱密钥AES算法新的子空间路径攻击

自2001年Rijndael算法被确定为美国新数据加密标准(Advanced Encryption Standard,AES)以来,对AES的分析一直是密码学的研究重点。子空间路径分析方法由LorenzoGrassi等于2016年提出,研究具有特定结构的子空间在AES轮函数作用下的变化规律。子空间路径分析不依赖密钥与秘密S盒,并且可以与不可能差分、截断差分等分析方法相结合。我们以带有秘密S盒的AES算法作为研究对象,将子空间路径分析与不变子空间、不可能差分分析结合,研究得到了3条新的AES的子空间路径,构造出弱密钥下的2个5轮AES区分器,需要的选择明文量为233.3,弱密钥量为232。

采用局部子图嵌入的MOOCs知识概念推荐模型

大规模开放在线课程(MOOCs)在减少用户学习盲区和改善用户体验方面已经有大量的研究,尤其是基于图神经网络的个性化课程资源推荐,但现有工作主要集中在固定或同质图上,容易受到数据稀疏问题的影响且难以扩展。在局部子图上使用图卷积,并结合扩展的矩阵分解(MF)模型来解决这一问题。首先,将异构图分解为多个基于元路径的子图,结合随机游走采样方法实现在采样节点富有影响力邻域的同时捕获实体之间复杂的语义关系,并在局部邻域上进行图卷积平滑各节点表示,实现高可扩展性;然后,使用注意力机制适应性地融合不同子图的上下文信息,更全面地构建用户偏好;最后,通过扩展矩阵分解优化模型参数,获得推荐列表。为了验证提出模型的性能,在公开的MOOCs数据集上进行对比实验,相较于最优基线,性能提升了2%,内存计算需求降低了近500%,缓解数据稀疏问题的同时仍具有较强的可扩展性。

求解车辆路径问题的混合遗传算法

针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2-OPT子路径优化的混合遗传算法。在该算法中,提出了一种新的双层染色体编码方案。该染色体编码方案能确保子路径为满足车辆容量约束的可行路径,并且该编码方案只需根据客户编号生成染色体,无需预先知道有容量限制的车辆路径问题所需的最小车辆数,更适于求解实际中的车辆路径优化问题。采用2-OPT算法作为遗传算法的变异算子以优化子路径,从而提高算法的收敛速度。基于典型基准测试实例的计算结果表明,该算法是求解有容量限制的车辆路径问题的有效方法。

多策略蚁群算法求解越野路径规划

针对车辆的越野路径规划问题,设计了以最少行驶时间为目标的多策略蚁群算法。首先,分析了地形坡度和地表属性对于车辆路径规划的综合影响,通过叠加坡度与粗糙度约束建立了禁忌表;其次,一方面引入了自适应调整策略以提高路径搜索的有效性,另一方面设计了双向搜索策略以增加蚂蚁之间的协作能力和成功路径的搜索机率;另外,还提出了子路径多段交叉策略以提高算法的全局搜索能力和收敛速度,在详细叙述改进算法的步骤之后,优化了算法的部分参数取值;最后,就基本算法和改进算法的性能指标、收敛代数和仿真结果进行了比较与分析。实验结果表明,改进算法能够快速有效地实现越野路径规划,较之基本算法有一定的优越性。

XML结构完整性约束下的路径表达式的最小化

引入了一个XML结构完整性约束体系.这个体系描述了XML文档中节点或路径之间的5种结构关系,包括路径蕴涵、路径同现、路径互斥、必需性包含和排他性包含.给出了这些结构完整性约束的语法和语义定义,并研究了它们在XML查询优化中的作用.基于子路径的概念,提出了有结构完整性约束的路径表达式的最小化算法.该算法以路径蕴涵闭包为工具,不仅可以删除路径表达式的冗余,还可以识别无效路径表达式.实验结果表明了该算法的正确性和有效性.

基于访问路径树的Web频繁访问路径挖掘算法研究

频繁访问路径发现是Web数据挖掘的重要研究内容。提出了一种挖掘连续频繁访问路径的高效算法:PS2算法,该算法利用访问路径树挖掘频繁扩展子路径,只需一次数据库扫描,试验表明该算法在效率上优于类Apriori的算法。

一种复杂场景下的路径规划问题解决方法

路径规划在诸多领域都有重要的应用价值,研究者们提出了多种解决路径规划问题的算法。但复杂场景下的路径规划问题并未得到很好的解决,特别是窄通道和Z字形场景下的路径规划问题。为了解决这一问题,提出了一种关键点路径规划方法。该方法通过关键点的引入,将整个路径规划切分成多个较短的子路径规划,从而降低问题的规模,提高规划效率;同时,这些关键点将随机路径搜索转化为启发式搜索,从而大幅提高了在窄通道和Z字形下的路径规划效率。算法首先确定绕过障碍物的关键点,然后使用这些关键点引导规划过程,初步规划出一条路径。最后通过路径压缩来优化路径,降低路径长度。实验结果表明,该方法不仅能够高效地完成窄通道场和Z字形场景中的路径规划,在其他常见场景的应用中也有不俗的表现。

时间演化矩阵乘积算符方法及其在量子开放系统中的应用

量子开放系统在量子科学的发展中占据着举足轻重的地位,因此对其数值计算方法进行研究具有重要的意义.对于量子开放系统,在20世纪90年代发明的准绝热传播子路径积分方法是为数不多的精确的数值计算方法,但其计算复杂度随着系统的大小和关联时间长度呈指数增长,因此在实际计算中它所能计算的物理模型比较受限.近年来,张量网络的研究和应用有了长足的进展.使用张量网络来表达该方法可以使其计算复杂度变成多项式增长,极大地提高了计算效率.由此发展出的新方法则被称为时间演化矩阵乘积算符方法,是一种高效的、数值精确的、并且非马尔可夫的计算方法,在量子开放系统的研究中有着广泛的应用前景.本文首先综述了准绝热传播子路径积分方法,接着介绍了矩阵乘积态的基本思路,然后利用矩阵乘积态来表述准绝热传播子路径积分方法,从而对时间演化矩阵乘积算符方法进行介绍;最后综述了该方法在量子开放系统中的应用,并以自旋-玻色子系统中的关联函数和热流计算为例对该方法进行了展示.

基于PathSim的MOOCs知识概念推荐模型

大规模开放在线课程提供大规模开放式在线学习平台,为推进现代教育发挥关键作用。然而,减少用户学习盲区和改善用户体验方面的研究仍具有挑战性:交互数据稀疏;难以扩展到大型推荐任务上;用户需求不单由用户喜好决定,还受到不同教师、课程影响;以统一的方式对课程学习事件中不同类型实体及关系进行建模并不妥靠。基于此,引入相关性度量,依据全图结构信息计算各边权重,提出采用相关性度量算法PathSim进行邻域采样的知识概念推荐模型PathSimSage。各实体间相关性得分可在本地离线计算,将神经网络与传播过程分离,保证神经网络的堆叠层数和传播过程的独立性,大幅减少模型所需训练时间。在公开的MoocCube数据集上进行了综合实验,PathSimSage降低了不相关的信息甚至噪声的影响,解决随机游走采样所引发的高度节点偏差问题,并在一定程度上缓解了过平滑效应。

煤矿环形综合业务网中路由算法的研究

在分析研究煤矿井下综合业务传输网络的基础上 ,提出了一种适合于环形结构互连网使用的路由简化算法——“1 /2路径和”算法 .该算法根据环形网的特点将复杂的路由算法简化成累加、简单比较和数据的存取操作 ,适用于开发以 DSP,ASIC或单片机为核心的路由器 ,满足了煤矿井下综合业务传输网络的需要 .

一种任意子路径的带宽测量方法

随着Internet用户数和网络复杂度的激增,人们对网络性能提出了更高的要求,而带宽测量已经成为一种网络性能研究的重要手段。这里提出的任意子路径的瓶颈带宽测量方法,采用包列作为探测报文,基于单端测量,可以在一条超路径的两端测量任意子路径的带宽,并且能定位出此链路,解决了在测量路径两端难以部署测量设施问题。最后用NS2仿真工具作了实验验证,在多种不同的背景流量情况下的实验结果表明此方法准确有效。