互联网络RCP（n）的最短路算法

RCP（n）是最近提出的一种新型互联网络拓扑结构,是由环、Petersen图和交叉立方体所组成的,具有短直径、良好的可扩展性和正则性以及较小的构造开销的性质,是一种具有良好拓扑性质的互联网络。针对RCP（n）上节点编码的特点,采用逐步分解编码,依次寻找路径的方法给出了寻找RCP（n）上任意两点间最短路的一个多项式算法,为RCP（n）上作进一步的路由算法、最优分组等通讯性能的研究提供了理论支持,因此具有一定的理论意义和应用价值。     

互联网络RCP（n）的路由算法

在对互联网络RCP（Ringed Crossed cube Petersen）拓扑结构研究的基础上,利用RCP（n）网络具有正则性,良好的可扩展性,以及具有比Q_n、HP（n）、RHP（n）网络更短的直径和更小的构造开销这些特性,给出了RCP（n）的单播路由算法和广播路由算法,并证明了RCP（n）比Q_n、HP（n）、RHP（n）网络具有更好的路由性能。     

一类层次双环网络的构造及其路由算法

高效互联网络的拓扑结构一直是人们关注的热点问题。提出了一类层次双环互联网络HDRN（k）,给出了HDRN（k）网络的构造方法,研究了它的性质,并且通过与相关网络的比较,证实了HDRN（k）具有好的连接性、短的直径以及简单的拓扑结构,是一种实用的互联网络。另外,讨论了HDRN（k）网络的路由性质,设计了点点路由和Broadcast路由算法,证明了这两种路由算法的通信效率与层次环网络上对应算法的通信效率相比均有明显的提高。综上所述,HDRN（k）是一种具有良好拓扑性质的新型互联网络。     

一种实用的互联网络RPn(k)及其路由算法

基于环的简单扩展性和Petersen图的短直径,提出了一类新型互联网络RPn(k),研究了该互联网络的性质,它不但具有正则性和良好的可扩展性,还具有比RP(k)互联网络更短的网络直径、更好的可分组性以及更小的网络构造开销。最后,讨论了RPn(k)网络的路由问题,给出了点点路由算法,其通信效率为[k/2]+2n个时间步。在节点个数相同时,RPn(k)比RP(k)网络上的路由算法的通信效率有明显提高。     

一种实用的互联网络拓扑结构RPC(k)及路由算法

Pertersen图由于具有短直径和正则性等特性,在并行计算与分布式计算中具有良好的性能.基于环结构,提出了一种Pertersen图的新扩展方法,构造了互联网络RPC(k).分析了该互联网络的性质,它具有连接度小、网络直径短、拓扑结构简单以及易于扩展等特点.同时给出了RPC(k)优于二维Torus以及RP(k)互联网络的直径和节点可分组性的条件.最后,分别设计了RPC(k)上的单播路由、置换路由、广播路由和多对多路由,它们的通信效率分别为「k/2」+5,k+9,「k/2」+5和k+9.特别是随着k的增大,RPC(k)网络路由算法的通信效率近似于RP(k)网络上的时应算法通信效率的1/3倍.     

Torus连接Petersen图互连网络及路由算法

可扩展性和短直径是设计大规模并行计算机系统互连网络的两个重要因素.基于Petersen图的短直径和正规性和Torus拓扑结构的可扩展性,提出了一种新的互连网络拓扑结构,称为Torus连接Petersen图互连网络.该互连网络拓扑结构具有短直径、正规性、对称性和良好的扩展性.网络节点采用混合编码方法,使得路由算法设计简单.分别设计了基于混合编码的单播、广播路由算法.分析表明提出的互连网络具有较好的拓扑性质.     

基于超立方体环连接的Petersen图互联网络研究

基于环的简单扩展性,Petersen图的短直径与超立方体互联网络中节点的高可连接性相结合,提出了一种新型互联网络RHP(n)(Ringed Hypercube Connected Petersen),并对其特性进行了研究．证明了RHP(n)网络不但具有正则性以及良好的可扩展性,同时还具有比Q、HP(n)网络更短的直径和更小的构造开销．另外,还基于RHP(n)网络分别给出了其上的单播和广播路由算法,证明了其通信效率分别为n-1和n-1．     

双环Petersen图互联网络及路由算法

Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.     

局部构造最小通信能耗路的拓扑控制算法

在分析了拓扑控制算法所基于的两种模型(UDG,MG)以及两种不同性质的网络(homogenous net,heterogeneous net)的基础上,考虑到无线通信的能量消耗与通信距离的n次方成正比(2＜n＜4),给出了一种选择邻居的标准,使邻居间的链接都是最小通信能耗链接.继而设计了一种局部构造最小通信能耗路的邻近图算法MCEC(MG).证明了算法具有连通性、稀疏性、1-spanner特性等.最后,实例仿真验证了算法的正确性和有效性.     

一种计算因特网AS拓扑的最短路径的快速算法

最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.     

基于ACS算法的移动机器人实时全局最优路径规划

以Ant Colony System（ACS）算法为基础提出了一种新的移动机器人实时全局最优路径规划方法.这种方法包括三个步骤:第一步是采用链接图理论建立移动机器人的自由空间模型，第二步是采用Dijkstra算法搜索出一条无碰撞次优路径，第三步是采用ACS算法对这条次优路径的位置进行优化，从而得到移动机器人的全局最优路径.计算机仿真实验的结果表明所提出的方法是有效的，可用于对移动机器人进行实时路径规划.仿真结果也证实了所提出的方法在收敛速度、解的波动性、动态收敛特征以及计算效率等方面都具有比采用精英保留遗传算法的移动机器人路径规划方法更好的性能.     

关键路径的稀疏矩阵求解算法

求解AOE网的关键路径算法一般基于拓扑排序，虽然具有较好的时间复杂度(O(n+e))，但由于必须进行拓扑排序，同时还要进行拓扑逆序扫描，使得算法本身比较复杂。针对这个问题提出了一个算法，算法采用了稀疏矩阵作为数据的存储结构，为防止关键路径丢失，采用队列方式进行操作。同经典算法相比，该算法简单，时间复杂度相近(O(n+e/n))。     

一种引入动量项的变步长LMS算法的研究

该文针对SVSLMS算法步长函数在误差e（n）接近零处不具有缓慢变化的缺点和MLMS算法由于采用固定步长使得在稳态阶段权值更新到期望值速度过慢的不足进行了讨论。通过更新SVSLMS算法步长函数和在权值调整式中增加动量项，该文提出了一种改进算法—SVS-MLMS算法。该算法具有步长函数在误差e（n）接近零处能够缓慢变化的优点，使得在白适应稳态阶段的步长稳定在最优值，进而使权值收敛到最佳。仿真结果证明该算法在学习曲线收敛速度加快和稳态误差减小方面取得了较好的效果。该文还讨论了算法中三个参数a，b，r的取值对算法收敛性能的影响，确定了它们的最优值。     

近邻场优化算法研究与应用综述

近邻场优化算法（neighborhood field optimization,NFO）是一种受生物个体向邻居学习行为启发的新型群体智能优化算法,该算法具有参数较少、结构简单和局部寻优性能强等优点,吸引了国内外众多学者的关注和研究。简单阐述NFO算法的寻优原理和搜索步骤,并分析了现有的算法的改进研究,包括混合算法、编码方式以及搜索步长等改进策略,同时对算法在能源效率、路径规划、经济调度等方面的应用进行概括总结。结合NFO算法的特点及现有研究成果,对算法的未来研究内容与方向做出展望。     

基于变步长A*与车身稳态转向模型的UGV路径规划

针对A*算法寻路时间长、生成的路径存在冗余折点的问题,本文提出一种基于车身稳态转向模型的变步长A*算法,首先通过设置子目标点的方式调节A*算法的搜索步长,减少寻路时间;其次在全局路径的折点处根据车身转向运动学约束进行局部重规划,从而得到一条易于跟踪的平滑路径;此外考虑到UGV (Unmanned Ground Vehicle,无人地面车辆)的实际宽度,改进后的算法还引入了障碍物延伸策略,使规划出的路径满足实际工程应用;最后通过仿真实验验证了本文改进算法的有效性,并与3种寻路算法进行对比,结果表明,本文改进的算法寻路时间更短、生成的路径更平滑,且与障碍物之间保持了安全距离.     

SHA-1差分路径搜索算法和连接策略研究

Hash函数SHA-1的攻击技术研究一直受到密码分析者的广泛关注,其中,差分路径构造是影响攻击复杂度大小的重要环节.提出了带比特条件的全轮差分路径构造方法,统一了第1轮差分路径构造和后3轮的差分路径构造.该方法既与原有第1轮路径构造相容,又能省去后3轮路径约简、消息约简等繁琐技术环节,具有良好的兼容性.此外,综合考虑状态差分、布尔函数差分与比特条件之间的制约关系,提出了带比特条件的前向扩展、后向扩展和中间连接这3个子算法,并提出3个指标——比特条件的更新次数、扩展结果的相容性和候选集合的正确率对中间连接的成功率进行评价,结合提前终止策略,提出了最优的中间连接算法.理论分析结果表明,该方法有助于提高SHA-1差分路径构造的成功率.最后,采用该算法进行路径搜索,可以得到正确的可用于碰撞搜索的差分路径.     

基于改进遗传算法的无人机路径规划

针对传统遗传算法收敛速度慢、容易陷入局部最优、规划路径不够平滑、代价高等问题,提出了一种基于改进遗传算法的无人机（UAV）路径规划方法,该算法对遗传算法的选择算子、交叉算子和变异算子进行改进,从而规划出平滑、可飞的路径。首先,建立适合UAV田间信息获取的环境模型,并考虑UAV的目标函数与约束条件以建立适合本场景的更为复杂、精确的数学模型;然后,提出了混合无重串选择算子、非对称映射交叉算子和启发式多次变异算子,寻找最优路径以及扩大种群搜索范围;最后,采用三次B样条曲线对规划出的路径进行平滑,得到平滑的飞行路径,并且减少了算法的计算时间。实验结果表明,与传统遗传算法相比,所提算法的代价值降低了68%,收敛迭代次数减少了67%;相较蚁群优化（ACO）算法,其代价值降低了55%,收敛迭代次数减少了58%。通过大量对比实验得出,当交叉率的值为（1/染色体长度）时,算法的收敛效果最好。在不同环境下进行算法性能测试,结果表明所提算法具有很好的环境适应性,适合于复杂环境下的路径规划。     

动态环境下多重A*算法的机器人路径规划方法

传统的A*算法仅适用于全局的静态环境,在求解路径规划问题时存在搜索效率低,路径不平滑等不足。针对这些问题,进行了以下改进：优化全局路径节点,引入删除冗余点准则与新增节点准则,使得全局路径更加平滑,更符合机器人运动学规律;结合滚动窗口法的思想,在每个滚动窗口内进行局部路径规划,首先根据前一步的节点信息确定局部子目标区域,然后在局部子目标区域内引入避障控制策略进行实时避障。最后通过Matlab软件建立多种栅格地图仿真,从路径轨迹的平滑度、搜索效率与局部规划能力方面将改进后的算法与原算法进行对比,并在动态环境下进行仿真分析,仿真结果表明改进后算法拥有良好局部规划能力,且路径轨迹更加平滑,在复杂环境下搜索效率更高。