含负权有向图最短路问题的新解法

通过简要分析现有含负权有向图最短路问题求解方法,基于Dijkstra算法图表法的基本原理,提出了一种新的较为直观的图表求解方法。该方法根据问题抽象所得的含负权有向图,通过确定权数来求解最短路问题,并给出了计算实例。结果表明,该方法具有实用性,且所提算法具有简便直观,计算量较少,不易出错,效率较高的特点。

浮动车地图匹配算法研究

针对现有浮动车地图匹配算法应用于城市复杂路网时面临的关键技术难点,基于浮动车数据,在SuperMap GIS平台下实现城市交通路网构建,并研究一种浮动车地图匹配的新算法:基于网格的候选路段确定,基于距离、航向、可达性权重的定位点匹配及基于最短路径的行驶轨迹选择。算法能够满足浮动车地图匹配准确性与实时性的要求,为获取城市道路的交通拥堵状况信息提供可靠依据。

基于图论的快速FCM图像分割算法

研究基于图论的最短路径算法与加权直方图方法,结合快速模糊聚类思想,提出一种改进的快速模糊C-均值(FCM)图像分割算法。利用最短路径算法对图像进行初始化处理,使处理后的灰度值准确反映邻域像素对原像素的影响。通过加权直方图改变灰度变化剧烈区域像元在图像分割中的影响程度,并自适应寻找初始聚类中心。实验结果表明,该算法能快速准确地分割图像,具有较强的抗噪性。

基于稳定分支的变权网络最优路径算法

有向网络的最短路问题在交通、通讯系统的最优传输路径中有重要应用.在通常的模型中,每条弧的权是给定的.但在实际问题中,弧的权会发生变化,例如在交通拥堵时运行时间会变长.如果当权发生变化时,要重新调用最短路算法,则浪费计算时间.本文提出最短路稳定性的概念,给出了关于最短路长度稳定、最优解稳定与稳定分支的命题与理论证明,在此基础上给出一种新的变权网络最短路径算法,利用权发生变化前的信息,减少计算量,提高计算效率.通过模拟实验验证了该算法的有效性.

带限制条件的多权最短路径近似算法

带限制条件的多权最短路径问题具有广泛的用途。该文针对有向图，给出了一个带一个限制条件的多权最短路径的近似算法并且分析了它的时间复杂度。

基于理想点法的多目标最短路求解算法研究

为了简化多目标最短路算法并解决不同度量单位之间存在的换算问题,利用理想点法的优点,探索出一种多目标最短路问题的简便算法。该算法首先确定理想点,计算各目标的k-最短路路径,这些路径组成一个存在可能解的集合,然后对所有的最短路目标值进行归一化处理,并确定所有路径归一化之后的目标值与理想点之间的加权欧几里得距离,从路径集合中寻找与理想点距离最近的路径,该路径即为多目标最短路问题的满意解。最后,给出了算法分析和算法流程,并通过一个虚拟运输网络对算法进行了验证。结果表明:这种算法能够解决多目标最短路问题中不同目标度量单位之间换算或相互矛盾的问题,并能够把复杂的非线性函数转换为简单的线性函数,是一种简单、有效的算法。

基于自适应遗传算法的OSPF链路权重优化

在综合考虑链路利用率、链路流量与剩余带宽的基础上,提出了OSPF链路权重优化目标函数,建立了优化数学模型,并设计了自适应遗传算法对其进行求解。实验结果显示提出的优化目标函数在满足给定流量要求的前提下,可以减少链路上的总流量;在网络流量较大时,能够均衡网络内负载分布,提高网络总吞吐量。

求带单一限制条件的单源多权最短路径的一个算法

给出了带单一限制条件的单源多权最短路径问题的一个算法,并证明此算法是正确的;该算法中借用了语言的特点,设计了一些C独特的数据结构,这使得该算法设计和实现非常简单。

带权值的大规模社交网络数据隐私保护方法

各类移动社交网络应用的发展促使了海量网络用户的出现,从而形成了大规模的社交图结构数据.这些图结构数据中包含着大量的用户隐私信息,因此发布之前需要进行隐私保护处理以防数据遭到泄露.同时,用户间错综复杂的社交关系并非均等,个体间关系的强弱可能直接影响到隐私的分布和保护的效率.目前存在相当多的针对无权值的社交网络图数据的隐私保护方法,但这些方法不能直接应用于带权值(社交关系敏感程度不均等)的社交网络图数据中.为解决这一问题,提出一种基于非交互的差分隐私保护模型的带权值的社交网络图扰动方法dp-noisy,可实现对边权值以及图结构的强保护.该方法基于单源最短路径约束模型来添加扰动噪音,根据不同的权值划分出关键边和非关键边,有效减少了需要扰动的边关系.实验结果表明:在大规模数据集中(节点数为30000),dp-noisy在运行效率上比K-MPNP(K-shortest path privacy)提高了47.3%,比LWSPA(protection algorithm based on Laplace noise for weighted social networks)提高了41.8%,比DER(density-based exploration and reconstruc-tion)提高了52.6%.在相似的数据隐私保护程度下,dp-noisy的数据可用性比lp-noisy提高了10%,显著优于DER的数据可用性,略好于LWSPA.此外,dp-noisy的平均扰动质量比lp-noisy提高了14%,比DER提高了11.3%,比K-MPNP提高了27%;在达到最优数据效用时(ε=10),dp-noisy的平均扰动质量比LWSPA提高了6%.综上,dp-noisy具有较高的运行效率和数据效用,同时满足抵御图结构攻击的特性,可适用于大规模的社交网络数据分析.

带单一限制条件的单源多权最短路径算法及其实现

带限制条件的单源多权最短路径比一般网络中的最短路径有更加广泛的应用性 .给出了仅带单一限制条件的单源多权最短路径的算法及其实现 .

一种基于转向限制的城市交通网最短路径算法

针对城市交通网导航的实际需要,提出了有向加权图的模型,图中顶点不仅包括路口,还包括起点和终点,并对Dijkstra算法进行改进,提出了一种基于转向限制的城市交通网最短路径算法,通过加入虚拟顶点,从而适应转向限制的条件。实验表明了该算法的正确性。

考虑交叉口特性的疏散交通路线研究

疏散是应急管理中的重要措施,在应急计划中有必要制定合理的疏散路线以确保疏散车辆尽快到达终点。以往有关最佳疏散交通路线的研究没有考虑交叉口延误和通行能力等因素,若疏散路线经过城市内拥挤路段,忽略交叉口的这些特性会导致结果不尽合理。将交叉口分方向延误和通行能力作为节点权重,建立了点权交通网络,通过在点权网络中求解最小费用流来优化事故地点至安全地点的最佳疏散交通路线及相应的疏散流量,设计了一种最小费用路算法求解该点权网络中的最小费用流。最后以一个数值算例说明了方法的应用,并对考虑和忽略交叉口特性2种情况下得出的路线进行了对比。结果表明该方法能很好地兼顾路网特点和疏散路线优化的要求;若执行忽略交叉口特性的疏散路线方案,极易造成交叉口的拥堵,延长车辆的走行时间。

基于节点度和边权值比率的网络搜索算法

基于加权网络特性,以Internet网络为例,提出了一种基于节点度和边权值比率(Degree and Weighted Ratio,DWR)的搜索算法。通过理论分析与仿真实验得出:DWR搜索算法在搜索时间和搜索代价上均优于最大度搜索算法和最大局部介数搜索算法。通过数值仿真分析发现,DWR搜索算法的搜索时间随着设置参数的增大而逐渐增大。因此,在Internet网络中,DWR搜索算法既可以提高网络信息传输的速度,又可以增强网络的传输能力。

用Dijkstra算法求解最短路的矩阵方法

给出了利用权矩阵求解最短路的一种方法.该方法直接在权矩阵中进行简单计算及标记,在最终得到的矩阵中,且通过已标记元素的数值及其位置即可得到源点到其他各点的最短路长及路径.该方法操作简单,且便于在计算机上实现.

基于最短路算法和最小节点电压法的配电网络重构

提出了一种基于最短路算法和最小节点电压法的配电网络重构方法。首先将整个配电网当成一个赋权图,在潮流计算的基础上,利用最短路径法为每个负荷分别寻找供电路径,然后在形成的树状网络中利用最小节点电压法进行支路交换操作细致优化网络,从而得到满足目标函数的网络拓扑。实例表明该方法对所寻网络没有特殊要求,不依赖于网络初始结构,易于解决复杂结构网络的寻优问题,重构速度较快、结果理想。

遗传算法在动态权值路径寻优中的应用

为了克服传统算法在求解动态权值下最短路径问题时权值设定不合理,所得结果往往不是最优路径这一问题,提出了一种基于遗传算法的复杂路径寻优算法。遗传算法本身的随机性可以很好的避免权值设定这一步骤。为了使路径寻优算法更加可靠,该算法通过优化变异过程使得收敛速度更快,可靠性更高。将其应用在一个实际游戏模型中,实验结果表明其有效性。

基于Floyd算法的反恐防暴机器人腿部变形策略

反恐防暴机器人的腿部变形,能够改变机器人的运行姿态,适应不同的路况,完成跨越壕沟、翻越高墙等障碍物的任务;这就要求机器人能够准确、快速、平稳的变形到相应的姿态以适应不同的路况。通过Floyd算法实现了这一变形要求,Floyd算法是一种求解有向图中两个节点之间最短路径的算法。把机器人几种常用的姿态简化为有向图中的节点,用姿态变换过程中电机旋转角度和机器人重心偏移量来确定节点之间的连接权值。实验证明,Floyd算法能够快速找到两个姿态之间最短的变换路径,实现了机器人准确、快速、平稳的变形。

有向赋权网络中任意节点对的最短路径集求解方法

有向赋权网络任意节点对之间的最短路径可能多于一条,运用Floyd算法对已知加权交互网络的最短路径进行求解,对获得最短路径后的每一个节点对,向其中插入已知交互网络中的其余所有节点,并计算此时的节点对之间的路径,通过与前次Floyd算法计算出的最短路径进行比较,筛选出构成最短路径的所有中间节点,并构建路径支撑树,基于路径支撑树确定任意节点对的最短路径集。

权重社交网络隐私保护中的差分隐私算法

针对社交网络的边权重隐私泄露问题,提出一种权重社交网络隐私保护算法。利用无向有权图表示社交网络,把边权重序列作为一个无归属直方图处理,将包含敏感信息的权重加入拉普拉斯噪声以满足差分隐私保护要求。为减少噪音量,对直方图中具有相同计数的桶合并成组,根据组间k-不可区分性来保证差分隐私保护要求,通过对原始的权重序列进行一致性推理保持网络最短路径不变。理论分析和实验结果表明,该算法能够满足差分隐私保护要求,且提高了信息发布的准确性和实用性。

公交出行最优路径搜索的有向赋权图模型

当前的公交查询系统和模型在处理多目标和多模式查询时,存在着描述困难和缺乏灵活性的问题。为此,基于有向赋权图提出了一种新的公交出行最优路径搜索模型。该模型不仅可以让用户设定可接受的最大步行距离,而且通过灵活的赋权策略利用最短路径搜索算法可以满足个性化的查询要求,尤其是在多目标查询方面具有较强的表达能力。以真实的公交数据实验表明提出的模型有效、实用。