基于树分解的时序最短路径计数查询算法

最短路径计数是图计算中的一个重要研究问题,旨在查询顶点间的最短路径数,在路径规划与推荐、社交网络分析、介数中心性计算等领域中具有广泛应用。目前越来越多的网络可以建模为时序图,但少有针对时序图最短路径计数查询问题的研究工作。与静态图相比,时序图增加了时间信息,结构更复杂,在查询顶点间的路径数时必须考虑边的激活时间,因此静态图中最短路径计数方法不再适用于时序图,并且在大规模时序图上查询更具有挑战性。针对时序图最短路径计数问题,提出一种基于树分解构建TG-TL(Temporal Graph-Tree Label)索引的方法。该方法包含构建索引和在线查询两个阶段,构建索引阶段根据时序图的属性设计时序树分解算法,将时序图转化为树结构;然后根据树分解的结构信息以及凸路径定义提出高效构建索引算法;在线查询阶段基于TG-TL索引提出了高效的时序最短路径计数查询算法。在4个真实数据集上的实验结果表明,与基于TG-base(Temporal Graph-base)索引的查询算法相比,所提算法在查询效率上至少提升了61%,因此所提算法在时序图最短路径计数问题上具有高效性和有效性。

正确性可验证的密文图数据最短路径外包计算方案

地理位置、社交网络等海量图数据应用广泛且包含大量隐私,通常需要安全的外包计算来提供多样化的查询服务。然而,如何设计正确性可验证的图数据外包计算协议仍是公开的难题。为此,提出了加密图数据上正确性可验证的精确最短路径外包计算方案。该方案利用加法同态加密构造密态图数据上的广度优先最短路径计算算法,支持加密图数据的精确最短距离查询外包计算;其次,基于双线性映射累加器构造最短路径外包计算结果的概率正确性验证机制。分析和证明表明,该方案能以概率可靠性实现正确性可验证的精确最短路径的外包计算,具备随机预言模型下的IND-CCA2安全。对比实验结果表明,所提方案相比其他相关方案在安全性、功能性方面有显著优势,性能上较已有可验证图数据外包计算方案在初始化及加密环节、查询环节、验证及解密环节的时间开销分别降低了0.15%~23.19%,12.91%~30.89%和1.13%~18.62%。

考虑鲁棒成本与绝对后悔的最短路径问题研究

为克服鲁棒偏差方法在处理区间路网时所求鲁棒最短路径的保守性问题,通过分析鲁棒成本的定义以及鲁棒最短路径过于保守的原因,结合算例分析提出了绝对后悔值的概念,并以鲁棒成本和绝对后悔值为目标函数建立了区间路网的多目标最短路径模型;根据最短路径模型的特点设计了分离路径决策变量与连续变量的Benders分解算法,同时基于传统有效路径的判断依据重新定义了符合该最短路径模型的有效路径,并在分解后的主问题模型中引入了有效路径约束以加快算法收敛速度;利用MATLAB生成了一个包含29个节点、70条双向通行路段的区间路网对模型与算法进行仿真测试。结果表明:考虑鲁棒成本和绝对后悔值的最短路径模型能在区间路网中找到不保守,且同时兼具鲁棒性的最短路径,能够有效克服鲁棒偏差方法的缺陷。

考虑偏好的空间文本对象多目标最短路径查询

为了解决路网中考虑偏好的空间文本对象多目标最短路径查询问题,设计了包含属性的IR树索引结构;然后利用类别约束,排序约束构建限定的有向无环图.提出了支持属性的局部贪婪算法SALG_SPG,以对最短路径查询进行处理;为进一步提高查询处理效率,提出了支持属性的全局优化算法SAGO_SPG,该算法利用阈值和缓存机制减少了大量无效、重复的计算;最后,通过与现有的FEBF算法的对比实验,分析并验证了所提算法的高效性.

最短路径算法案例的设计

数据结构是计算机专业的核心课程之一,最短路径算法是数据结构课程中的一个核心章节,与社会实践紧密融合,在路径优化中具有非常重要的作用,也蕴含丰富的思政元素。迪杰斯特拉算法是最经典的求解最短路径算法,算法的教学实施对学生实践能力和科学素养的培养,具有深远的意义。本文从实际应用和课程思政教学两个角度,给出求解最短路径算法的案例设计,并取得良好的教学效果。

尾矿库稳定性最短路径强度折减极限分析

尾矿库堆积边坡稳定性研究手段常以有限元强度折减的方式实现,尾矿砂抗剪强度参数(c,φ)对于坝体稳定性的影响存在差异。为此,引入最短路径强度折减理论,开展东北某大型尾矿库稳定性实例分析。主要结论:1)以逼近尾矿砂实际容重的方式,利用Optum G2进行渗流条件下尾矿库最短路径强度折减稳定性极限分析,获得尾矿堆积边坡最小综合安全系数及潜在破坏面。2)非等比例强度折减过程中,随着折减比例增大,折减路径长度先减小后增大,说明最短折减路径求得的最小综合安全系数,对应于尾矿堆积边坡最不利极限状态;3)利用最短路径强度折减极限分析得到的尾矿库最小综合安全系数,稍小于瑞典条分法和简化Bishop法结果,但整体上吻合较好;4)随尾矿库堆积边坡的增高,最小综合安全系数持续降低,潜在尾矿坝滑动体范围增大,对应的滑动面向库内扩展。

求最短路径的Dijkstra形式模型与算法

计算模型(概念模型、形式模型)是计算学科最基础的概念,针对传统算法类教学存在的忽视计算模型的问题,以最短路径求解的Dijkstra算法为例,探讨如何构造其形式模型,给出基于模型的算法,以及算法的正确性证明、复杂性分析和算法实现,介绍用抽象、理论和设计3个学科形态拆分该算法求解问题的整个过程,以达到控制和降低问题求解复杂性,提高学生求解复杂问题能力的目的。

结构化加密图的最短路径查询

随着云计算的快速发展,数据用户将大量图数据外包给云以节约存储和管理成本。然而,外包数据的安全隐私问题是云计算面临的一大挑战。由于云是半诚实的,为保护敏感信息的隐私安全,数据拥有者希望在将图数据外包给云服务器之前对其加密,同时保留对加密的图数据进行查询和处理的能力。最短路径查询查找图中给定两节点之间的最短路径,是图应用中最基础的查询类型之一。目前已有许多研究者提出一系列高效的方案,以支持加密图上近似或精确最短距离查询、约束最短距离查询和top-k最近关键字查询,但支持最短路径查询的方案较少,且已有方案的存储与时间开销较大。本文提出一种支持在加密图上进行两节点间最短路径查询的结构化加密图方案。在本方案中,我们基于2-Hop标签技术构造支持有向图上最短路径查询的标签索引并加密,然后将加密的标签外包给云服务器。利用改进的保序编码算法编码距离值,实现加法运算和值的比较,提高最短路径查询的效率。在查询阶段,通过递归式地计算两节点间最短路径上的第一条边和最后一条边,最终输出完整的最短路径。安全性和性能分析证明本文方案是安全有效的,能以较小的存储和较高的查询效率实现两节点间的最短路径查询并保护图数据的隐私。

面向最短路径的汇聚层光缆网规划建设策略研究

随着传送网汇聚机房规模增长,汇聚层光缆网逐渐从单平面环网向网状网结构演进。提出一种基于最短路径理论的光缆规划建设策略,通过深入分析汇聚设备组网特性和汇聚机房布局,寻找最优的汇聚层光缆网结构,可以有效缩短光缆长度,提高光缆资源利用率。经对比分析,该策略对城域传送网的汇聚层光缆布局优化具有实际应用价值。

考虑行程时间相关性的可靠最短路径算法

可靠最短路径(RSP)问题反映了出行时间的可变性,比只考虑平均出行时间的标准最短路径问题更加实际可行。本文提出了一种考虑路段行程时间相关性的均值-标准偏差RSP问题的求解思路。该算法采用拉格朗日代入和协方差矩阵分解技术,解决了混合整数非线性规划(MINLP)的非线性和不可加性带来的困难。将该问题分解为标准最短路径问题和凸优化问题,证明了凸优化问题的最优解,并将拉格朗日乘子范围与协方差矩阵的特征值联系起来,提出采用次梯度法进行拉格朗日乘子更新。该算法能降低了原问题的复杂性,可扩展到大型网络。

通讯网络连接的最短路径问题探究

本文研究了旅行商模型(TSP)的蚁群法算法和树模型的最小生成树法,构建了139个节点的通讯网络线路,结果表明采用TSP模型的蚁群法得到单连通网络线路总长度在320附近,低于平均值;而树模型的最小生成树法得到了更佳优化的具有唯一性的网络连接线路,其总路径最小值为254。从网络连接图中明显的看出后者在连通性和抗摧毁性上明显的优于前者。

基于灰色关联分析与最短路径算法的供应商选择研究

随着企业间竞争与协作关系的深化,需要基于整个供应链网络结构来考虑供应商的评价选择问题。运用灰色关联分析与最短路径算法结合的评价模式选择供应商,有利于使供应链节点企业间更好地合作,有效提高供应链运作的效率。营造信息共享环境,加强供应链节点企业间的协同合作,建立企业间的数据联盟能有效地应用该评价模式。

基于图分割的求解最短路径加速方法探讨

最短路径问题是大数据、人工智能、基础科学等领域的基础问题,其算法的应用范围涵盖了自动驾驶、关系网络以及其他现实生活领域。目前,最短路径问题在单机图处理方面取得了一定进步,但针对于海量图数据进行计算最短路径时,仍面临计算机资源要求过高、计算执行时间长等问题。为了解决以上问题,本文提出了图缩减的方法,该方法利用割点将原图进行拆分,建立覆盖图、原图、子图间的映射关系;求解最短路径时不在覆盖图路径的子图不参与计算,从而降低参与计算的图数据规模,以实现最短路径求解过程中的加速效果。

Floyd多源最短路径算法的并行化研究

首先对现有的Floyd多源最短路径算法进行分析,指出了该算法执行效率低下,无法在数据量大的稠密图上高效运行这一问题。为解决这一问题,从并行计算的角度着手研究,将算法中插入点给定时进行一次矩阵迭代并逐条刷新所有当前最短路径的顺序过程优化为基于并行计算的同步刷新过程。该优化使得Floyd算法的时间复杂度由原来的立方阶降低为线性阶,从理论上提高了算法的执行效率,使该算法对数据量大的稠密图顺利进行计算和求解成为了可能。

有序开展数学实验,发展几何直观能力——以“最短路径之造桥选址问题”的教学为例

数学实验教学可以有效改变学生学习数学的方式,与几何直观这一关键能力的发展紧密相关.在“最短路径之造桥选址问题”的教学中,通过几何画板软件、折纸操作、动手作图开展不同形式的数学实验教学,发现实验教学对提高学生基于几何直观的感性认识、理性思考和表达应用具有积极的促进作用.由此受到启示,依据学生的认知发展规律,有序开展数学实验教学能有效促进学生几何直观能力的发展.

基于SDN的卫星网络最短路径优化算法研究

天地一体化网络正在成为下一代网络的发展新趋势,SDN和NFV正在成为集成卫星网络和地面网络的主要渠道。SDN具有转控分离的特性,可以从整个网络配置资源,实现卫星网络的优化。本文在基于SDN的天地一体化网络背景之下,针对卫星网络流量不均、拥塞等问题,将扩展最短路径优化算法进行改进,并应用于天地卫星网络中,在多层卫星架构中使用LEO卫星作为支持OpenFlow的SDN转发交换机,GEO同步卫星作为控制器控制全局网络,并对相关网络指标进行了性能分析和仿真。与现有卫星路由算法的研究相比,本算法降低卫星网络端到端时延与丢包率。

基于改进人工鱼群算法的最短路径问题研究

为提高智能机器人的路径寻优能力,文章提出一种基于检测算子和经验学习的鱼群算法(Detection Operator and Experiecnce Learning Artificial Fish Swarm Algorithm,DOEL-AFSA)。仿真实验结果表明,DOEL-AFSA得到的最短路径比鱼群算法(AFSA)、动态分级蚁群算法(WAS)等算法更好,其求解效率更高。

生鲜肉品冷链配送最短路径算法研究

近年来,大数据云计算技术、人工智能算法被引入生鲜冷链物流配送管理中,可针对冷链物流的制冷成本、运输成本、时间窗惩罚成本使用蚁群优化算法(Ant Colony Optimization,ACO)、人工鱼群算法(Whale Optimization Algorithm,WOA),全面分析多点配送的带模糊工作时间窗的冷链物流最优配送方案。为保证生鲜肉品冷链配送低碳保鲜效益、运输成本效益的最优化,引入改进传统蚁群算法的种群初始化、转移状态规则、信息素调整因子PAF、信息素更新策略等方式,进行生鲜肉品冷链配送行进路线的粒子群寻优、迭代任务分配及迭代结果优化分析,得出更适合生鲜肉品企业冷链配送的最短路径。仿真实验结果显示,基于改进蚁群算法的冷链配送路径优化,相比蚁群优化算法等算法的寻优路线更优、保鲜及运输成本更低,能够产生更优良的冷链物流配送经济效益。

基于Dijkstra算法的移动机器人最短路径规划设计研究

本研究针对移动机器人的路径规划问题,结合Dijkstra算法进行了深入探讨。设计了一套针对移动机器人的最短路径规划系统,该系统全面考虑了机器人的运动约束、环境信息以及目标位置等关键因素。在此基础上,提出了一种基于Dijkstra算法的路径规划方案,旨在实现高效且精准的路径规划,为移动机器人的自主导航提供有力支持。

基于最短路径问题的初中数学创新案例研究

本文通过对最短路径问题的系统分析与归纳,结合图论的基础知识,设计适合初中学生理解与实践的教学案例.旨在帮助学生深入理解最短路径问题背后的数学原理,提升学生的数学逻辑思维能力和问题解决能力.