Floyd算法的改进与优化

介绍一个改进的Floyd算法。本文综合运用C＋＋语言编程技术,设计并实现了求带权有向图中各个顶点之间最短路径的算法,反映了最短路径序列上前后两个顶点之间的先后关系。本算法从顶点出发,每次在求各顶点间最短路径的时候,都进行路径优化。改进后的Floyd算法,迭代速度快,计算量一定程度减少。     

一种改进的Floyd算法

Floyd算法是解决最短路径问题的一种有效方法,算法简单,边权值可正可负,同时也被用于计算有向图的传递闭包。但存在着时间复杂度高等问题,不适合计算大量的数据。从搜索方向和数据存储的角度,对其进行了改进。理论分析和实验结果表明,改进的算法在运行时间和程序占用内存方面均优于传统的Floyd算法。     

最短路径算法在高速公路联网收费中的研究及应用

Floyd算法求任意2点间距离时间复杂度等同于Dijkstra算法,现行高速公路路网由环路和射线路段组成,当路网节点多时,两种算法单独操作计算速度慢。基于Floyd计算环路效率高,Dijkstra计算稀疏图的射线路段效率高的特性,本文结合Floyd和Dijkstra算法来计算高速公路路网任意2节点间最短路径。用VC＋＋设计模拟出路网中2点间（一对点）的最短路径,并对算法复杂度进行分析。     

实际配送中多个配送点闭回路最短路径的选取

将Dijkstra算法与Kruskal算法相结合求由配送中心到多个销售点然后返回配送中心最短的闭路径,比单一的用Dijkstra算法和Floyd算法简单,比单一的用Kruskal算法精确,从而给实际计算带来方便。     

Floyd算法的演示模型研究

路径分析是网络分析最基本的问题,其核心是对最短路径的求解．最短路径算法的优化直接关系到网络分析技术的提高,其求解算法的优劣决定相关软件的性能,通过对Floyd算法基本思想、算法实现步骤和时间复杂度分析,比较了各种算法的时间复杂度,并使用Java语言设计演示程序说明Floyd算法的实现机制,为Floyd算法的掌握和优化提供了参考模型．     

基于Dijkstra算法和Floyd算法的物流运输最短路径研究

对于物流公司或企业来说,往往会遇到配送物流时需要送至两个甚至更多的地方,在已有的这种客观条件下,如何使得系统的费用最低,服务效果最好,是配送的核心问题。本文通过利用Dijkstra的两种改进算法和Warshall－Floyd算法来对配送的最小路径进行寻优,比较了三种算法的优化效率和可靠性,结果发现改进的DDkstn算法和warshall－Floyd算法具有较好的搜索效率。     

基于Floyd算法的消防站选址确定

本文通过运用运筹学图论中的Floyd算法,针对消防站的选址问题进行了初步的讨论,并用一个实例通过MATLAB编程对算法进行了对Floyd算法求得最短路径进行了验证,对消防站的选址具有重要的指导意义。     

无线传感器网络分簇算法的研究

从节省无线传感器网络能量消耗的角度出发,在分析当前最具代表性的分簇算法LEACH的基础上,将图论知识和无线传感器网络拓扑结构相结合,引入Floyd算法来选择簇头.为测试Floyd算法的性能,通过仿真试验,主要从每个节点能量的消耗和LEACH算法进行了比较,证明了该算法能在一定程度上节省整个网络的能量消耗,说明了该算法的有效性.     

缺省分配问题的一种解法

主要考虑了在最少时间和资源消耗的前提下,n个人执行n项并行工作的最优分配问题.通过借助于Floyd算法规则,我们给出了一种有效的两阶段迭代算法.该算法可加以推广用于解决其他文献中所研究的类似问题.     

稀疏网络的Floyd动态优化算法

通过对Floyd算法进行研究,提出了一种新的求取任意两点间最短路径的算法:Floyd动态优化算法.该算法通过引入插入数组、可达数组以及可发数组,使得算法在求解最短路径前自动修改能够最小化路径的节点,剔除一些无用的节点,最小化语句执行的次数.算法分析表明,新算法在稀疏网络中比Floyd算法在性能上有较大的提高.     

一种新的自适应步长果蝇优化算法

针对基本果蝇优化算法(FOA)易陷入局部最优、寻优精度低和后期收敛速度慢的问题,提出了一种自适应步长果蝇优化算法(ASFOA).该算法在运行过程中根据上一代最优味道浓度判断值和当前迭代次数来自适应调整进化移动步长,使算法在初期的步长大而避免种群个体陷入局部最优,到后期果蝇移动的步长变小而获得更高的收敛精度解,并加快收敛速度.通过6个标准测试函数对改进算法进行仿真测试,结果表明ASFOA算法具有更好的全局搜索能力,其收敛精度、收敛速度均比FOA算法及参考文献中其他改进果蝇优化算法有较大的提高.     

一种改进的LDPC码BP译码算法

通过对LDPC码经典的BP译码算法进行研究,针对算法译码复杂度非常大、迭代次数多、不利于硬件实现的问题,提出了一种改进的BP译码算法.改进算法通过实时监控在连续3次迭代中译码是否稳定来减少在信噪比低于译码阈值时的迭代次数.同时,在变量消息更新过程中对传递的校验信息进行数据约束,防止由于数据溢出而导致的译码失败.仿真结果表明,改进的BP算法,在性能损失不大的情况下可以有效地降低译码的复杂度,从而更利于硬件的实现.     

变形FLOYD算法

给出了求有向网络中每对顶点间最短路径的变形Ｆｌｏｙｄ算法,其时间复杂度与Ｆｌｏｙｄ算法同量级,形象直观且易编写程序。     

基于信息熵改进的 K-means 动态聚类算法

初始聚类中心及聚类过程产生的冗余信息是影响K-means算法聚类性能的主要因素,也是阻碍该算法性能提升的主要问题.因此,提出一个改进的K-means算法.改进算法通过采用信息熵对聚类对象进行赋权来修正聚类对象间的距离函数,并利用初始聚类的赋权函数选出质量较高的初始聚类中心点;然后,为算法的终止条件设定标准阈值来减少算法迭代次数,从而减少学习时间;最后,通过删除由信息动态变化而产生的冗余信息来减少动态聚类过程中的干扰,以使算法达到更准确更高效的聚类效果.实验结果表明,当数据样本数量较多时,相比于传统的K-means算法和其他改进的K-means算法,提出的算法在准确率和执行效率上都有较大提升.     

适用于大规模网络的全源最短路径重优化算法——RASP算法

为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n~2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.