Bellman-Ford算法性能可移植的GPU并行优化

提出了一种面向GPU的性能可移植的并行归约求极值优化算法和全局访存优化算法,对Bellman-Ford算法进行并行化改造,以解决不同类型GPU设备上都存在的并行粒度不足和全局内存访问不连续等问题。实验结果表明：本文的优化算法在NVIDIA和AMD的多款GPU设备上都取得了很好的效果,经本文算法优化后的程序性能较原始GPU并行版本提升3~6倍。

基于Bellman-Ford算法的无人机路径规划研究

通过预先侦察和经验评估,给出了一种敌情信息未知环境中的无人机路径规划方法。采用Bayes方法求取了给定规划区域内威胁存在的概率,构建了威胁概率分布图,并将其转化成权重为威胁概率的带权图,利用Bellman-Ford算法搜索该带权图,求取了一条从出发点到目标点的无人机最小威胁路径,根据无人机气动性能约束,对最小威胁路径进行了修正和优化,得到一条可飞的最优路径,最后给出了仿真结果,验证了方法的有效性。

基于时延限制的Bellman Ford算法

文中针对计算机通信中的QoS(QualityofService)要求 ,在Bellman Ford算法的基础上 ,提出了基于时延限制的Bellman Ford算法DCBF(Delay ConstrainedBellman Ford) .详细描述了DCBF算法 ,证明了DCBF算法的正确性 ,分析了DCBF算法的计算复杂度 ,并给出了一个实例 .

经典Bellman-Ford算法的改进及其实验评估

针对以高效求解有边数限制的最短路问题,对经典Bellman-Ford算法进行了改进.借鉴划分算法的思想,通过减少距离标号的数目,得到了两个改进算法.既然已有的改进算法均不能解决有边数限制的最短路问题,因而本算法是经典Bellman-Ford算法的全新改进.相对于经典Bellman-Ford算法,改进后的算法不仅可有效地节省存储空间,而且实验表明能显著地提高计算效率.

固定序Bellman-Ford算法的一个改进

通过对固定序Bellman-Ford算法进行修正,获得了一种求解边数不大于k的最短路问题的新算法.相对于原始算法,修正后的算法通过改变点的标号过程,使得在第k次迭代后每一条路径的边数均不超过k.新算法被证明是正确的,它的计算复杂性为O(km).实验表明,在大规模情形下,相对于修正的先进先出算法,该算法具有显著的竞争优势.

基于Bellman-Ford算法的空中编队协同对岸打击

为提高空中编队协同对岸打击作战能力,基于Bellman-Ford算法对空中编队协同对岸打击进行研究。为解决空中编队协同对岸打击作战中的时间协同问题,针对空中编队协同对岸打击作战的时间约束特点并结合简单时间约束网络理论,将其时间约束网络模型转化为简单时间约束网络模型;为克服传统简单时间约束网络一致性检测算法时间耗费大的缺点,提出借鉴Bellman-Ford算法检测一致性的新方法,并以实例进行检测、分析。结果表明:该方法能有效解决空中编队对岸打击作战中的时间协同问题,能减小时间复杂度,提高协同效率。

基于固定序的Bellman-Ford算法的改进

固定序算法是Bellman-Ford算法的一种基本改进算法。为了改变固定序算法在稀疏图上的劣势,本文通过预先订制参与迭代的点的计算顺序,对该算法进行了改进。实验表明,在稀疏图上,改进后的算法相对于原算法计算效率提高了近50%,并能够与国际流行的先进先出算法相媲美。本文的工作表明,固定序算法不仅在大规模稠密图上具有明显的优势,而且在稀疏图上也具有很强的竞争力。

基于AHP与Bellman-Ford算法的停车规划方法

为解决现代城市停车车位信息不透明、缺乏诱导信息等原因导致的停车难等问题,提出了一种车位引导算法。该算法根据各停车场、路段的静态信息和采集来的实时信息,建立相应的指标体系,采用层次分析法,计算各指标权值系数,得出区位排序,并给出基于改进Bellman-Ford算法的最短车位引导路径。

基于改进的Bellman-Ford算法优化中药配送路径

目的针对中药配送“小”“散”“多”现象,解决中药配送路径优化的问题,提高中药配送效率。方法围绕中药配送最佳路径问题,对传统的Bellman-Ford算法进行了改进,解决算法的存储空间等问题。结果通过亳州地区中药配送仿真实验,改进Bellman-Ford算法,对v-1条轮降距操作,找出所有路径,验证是否存在负环路,对Bellman-Ford算法结束后再增加一轮降距检查。结论改进的Bellman-Ford算法在计算最短路径优化过程中增加了算法的存储空间,优化了配送路径,节省了配送成本,提高了中药配送效率。

基于Bellman-Ford算法的配电网节能控制研究

为解决大量分布基于改进最小费用路算法的电源并网场景下的主动配电网节能控制优化问题,通过建立与配电网相应的图论模型,将潮流管理问题转化为寻求图论模型最小费用流的问题。鉴于传统最小费用路算法具有结构复杂、计算繁琐等缺点,论文提出了一种基于Bellman-Ford算法改进的最小费用流计算,该算法采用容量修改方式取代传统算法中的流量修改方式,大大简化了寻找图论模型中最小费用流的计算。应用Matlab建立仿真模型并进行仿真,仿真结果表明,改进的最小费用流Bellman-Ford算法应用于主动配电网潮流管理能够实现潮流优化,可以有效解决分布式电源(DG)并网造成的潮流阻塞问题,最终达到配电网节能控制的目的。

Dijkstra算法和Bellman-Ford算法生成印尼文本摘要的比较

是一种基于计算机的系统,它概括文本的同时保留文章的主题。在获取摘要过程中,用句子间的权重给每个段落建立句子的图谱;同时也考虑印尼文章段落结构的归纳演绎方法,用最短路径算法确定哪些句子部分将成为摘要的结果。实验结果表明,Dijkstra算法优于Bellman-Ford算法生成文本摘要压缩率的12%。

基于BLE Mesh的资产定位系统设计

针对当前资产定位系统定位精度、建设成本和部署灵活性难以有效平衡的问题,基于BLE Mesh采用多维标度分析(MultiDimensional Scaling-Map,MDS-MAP)定位算法设计了一种资产定位系统。系统首先对原始接收信号强度(Received Signal Strength Indicator,RSSI)进行高斯-卡尔曼融合滤波,提高了RSSI值的准确性;然后利用生存时间(Time To Live,TTL)对中继节点进行约束,提高了数据传输的有效性;最后利用半径弥补法与Bellman-Ford融合迭代方案对生成的距离矩阵进行修正,减小了测距误差。实验结果表明,所设计的系统可有效完成蓝牙标签信息更新以及位置展示,平均定位精度达到了0.94 m。本系统具有成本低、工程实施方便的优点,有一定的应用价值和发展前景。

SPFA算法的分析及改进

SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为Θ(|V||E|);在存在源点可达负圈的有向图中,算法将无限运行下去。对此,给出了改进的SPFA算法,对于任意的有向图,该算法能够在O(|V||E|)内运行完毕。最后,从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较。

负权最短路问题的新算法

Bellman-Ford算法自1958年以来一直是负权最短路问题的公认的最好算法之一．1970年,Yen对其进行了改进,理论上可以节省一半的计算量．本文得到了一种比Bellman-Ford算法更加优越的算法．尽管在理论上新算法无法保证完全超越于Yen的改进算法,但在许多情况下需要更少的计算量．

基于词共现有向图的中文合成词提取算法

分词系统由于未将合成词收录进词典,因此不能识别合成词。针对该问题,提出一种基于词共现有向图的中文合成词提取算法。采用词性探测方法从文本中获取词串,由所获词串生成词共现有向图,并借鉴Bellman-Ford算法思想,从词共现有向图中搜索多源点长度最长且权重值满足给定条件的路径,该路径所对应的词串即为合成词。实验结果显示,该算法的合成词提取正确率达到91.16%。

有限车辆调度问题的模型和改进遗传算法

考虑到对带时间窗的有限车辆调度问题研究不足的事实,在建立了数学模型的基础上对传统的遗传算法(GA)进行改进:提出采用Bellman-Ford求最短路算法找出染色体所表示路径的最优组合形式;变异操作应用禁忌搜索算法(TS),并采用TS的动态摆动策略,对邻域结构的可行及不可行解进行有效的搜索。最后用Solo-mon中的Rc1数据验证了算法的有效性,其结果比较理想。

宽带IP网络基于QoS的路由算法

文章简要介绍了网络服务质量路由问题,研究了一种在综合服务(IntServ)网络模型下保证服务质量的路由算法,并对该算法提出了一定的改进,从而提高了算法的性能。

无人机中继链路部署算法设计

在存在通信盲区以及无人机(UAV)使用数目受限等情况下,针对如何合理地部署UAV并构建通信中继链路,以及扩展UAV的数据传输距离的问题,提出改进Bellman-Ford(IBF)算法和改进Dijkstra算法(IDA)两个UAV中继链路部署算法。将通信中继链路中UAV部署问题形式化表示为全跳最优路径(AHOP)问题,其中IBF算法用来迭代生成一组可达记录集,通过逆向访问记录集可生成一组部署方案;IDA则在每轮迭代过程中改变连接边的权值,并查找能有效减少中继链路跳数的有效方案,得到UAV中继部署问题的可行解。仿真结果表明IBF和IDA能够提供中继链路部署的有效方案,同时它们的时间性能优于Bellman-Ford算法。

DMRMQ:基于多QoS的动态组播路由算法

提出了一种基于多QoS的动态组播路由算法-DMRMQ,该算法采用Bellman-Ford算法作为路径搜索算法,能在满足带宽、延迟、延迟抖动和丢包率的前提下确定具有最小跳数和开销的动态组播路由.针对音频和普通数据流的仿真实验表明,DMRMQ能在基于多QoS的前提下建立动态组播路由,算法在路由请求平均成功率、路由平均延迟和平均跳数等衡量指标上比不考虑QoS的动态组播路由算法具有更好的性能.

快速负环检测的负权最短路径算法

为优化存在负环的有向图[1]中的单源最短路径问题,针对有向图中的负环检测,提出一种基于快速检测负环的最短路径算法。采用最短路径树的数据结构,在时间复杂度O(n2)内,检测出负环,如果不存在负环,就将获得源节点到其它节点的最短路径距离。实验结果表明,与现有的方法相比,该算法在负环检测方面具有明显优势。