网络最大流问题求解的符号ADD增广路径算法

本文通过对网络及网络最大流问题的符号代数判定图(ADD)描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法。与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善。实验结果表明,本文算法是切实有效的,且可处理更大规模的问题。

InSAR相位解缠最大流/最小割权值改进算法

InSAR已经在高精度DEM反演中得到了广泛应用,相位解缠技术是影响DEM获取精度的关键步骤之一,然而大梯度变化区域一直是影响解缠结果精度的核心问题。针对该问题,本文提出一种基于势函数改进权值的最大流/最小割相位解缠算法。首先,针对PUMA模型权值设置不合理的问题进行研究,利用外部已有DEM获取相位梯度变化的先验信息,将窗口最大绝对相位梯度值代入相应的势函数公式中获取权值;然后,通过对势函数权值的设置进行阈值调节,解决由于势函数权值设置不合理导致PUMA势函数无法发挥作用引起的解缠错误问题,进而提高大梯度变化区域相位解缠精度;最后,通过仿真数据和真实TanDEM-X InSAR数据对本文算法进行验证,并与已有方法进行对比。结果表明,仿真数据中本文算法可以提高至少44.93%的解缠精度,真实数据中在大梯度变化区域,本文算法较已有算法可以获得更大范围的有效解缠结果。

带有模糊流量限制的最大流问题

定义构造区间中智数的基本运算,提出中智逻辑并给出数学定义,通过概率论期望的概念提出中智数学期望的定义.结合图论,提出用区间中智数表示网络流中每条弧上的模糊信息,通过改进区间中智数运算并运用增广链算法调整流网络流量,给出中智最大流问题的中智线性规划模型.最后通过算例给出算法具体实现步骤,得到中智环境下的最大流以及流量的波动率,结果说明运算可行,算法合理有效.

基于规划模型的运输网络最大流问题的分析研究

当今,世界经济形成命运共同体,各国各地的贸易往来非常频繁。物流产业作为供应链的重要组成部分,也迎来快速发展。研究运输网络最大流问题成为许多学者关注的焦点。现实生产生活中,某地区有一公司需将货物从配送中心运送至仓库储存,在运输过程中,物流车会遇到若干个路口,因为每段路程的车辆承载量和目前平均通过量各有不同,因此,文章通过建立规划建模求解,得出货物运输效率最大的研究结果,以期在实际物流运输环节中节约大量的成本。

基于最大流算法的电力负荷坏数据辨识系统

用电负荷坏数据会对电力供电产生很大的破坏性,为了提高对电力负荷坏数据的检测能力,设计基于最大流算法的电力负荷坏数据辨识系统。硬件主要包括采集器、处理器、信号识别器三部分,采集器在高压电池侧边需要放置微控制单元,处理器将波形数据转换为数字信息实现控制。信息识别器的连接结构为阅读芯片与单片机的输入端口互相连接,单片机的输出端口与通信状态显示屏相互连接,载波发生器与调制器相互连接。利用最大流算法建立拓扑模型,在电力系统网络流中,采用中心性指标完成对点到边、边到点、点到点、边到边之间的电力数据划分,利用最大流算法对坏数据完成辨识。实验结果表明,所设计系统可以确保电网受到攻击后剩余流量高于95%,辨识准确率高于90%。

动态网络上最大流概念及其性质的研究

本文在动态商空间模型的基础上,研究动态网络环境下最大流、最小割的定义及最小割定理成立的条件.首先分析动态网络最大流量的特点,发现直接将静态环境下的最大流量概念移植到动态的情况,所得的最大流不具有可加性和总流量最大性.为此引入t-截网络的概念,将动态网络化成静态网络的组合,为动态网络的分析提供一个有效的方法;在此基础上提出(最速)最大流量的定义,并证明新定义的最大流具有可加性和总量最大性.接着给出相应的最小割概念,证明新定义下的最大流、最小割对应的最小割定理成立.最后给出求动态(最速)最大流量的算法.

网络最大流求解算法的研究

近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展。文章简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法。此算法使得计算网络最大流变得简便,且具有很强的实用性。

求网络最大流的新方法

对Ｆｏｒｄ－Ｆｕｌｋｅｒｓｏｎ标号法进行改进，使得通过一次标号便可找到全部增广链，并同时增流即得最大流．还给出了求最小费用最大流的一种新的、更简单的方法．

基于标号法求解网络最大流算法的研究

近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展.本文简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法.此算法使得计算网络最大流变得简便,且具有很强的实用性.

最小费用最大流算法（C＋＋）实现

最小费用最大流是一类网络优化问题，它与最大流的区别在于，它不仅要考虑流量问题，还要考虑费用因素，其优化的目标是流量最大且费用最小。本文综合求最大流原理和求最短路原理，在直接输入初始状态下就求出任何一个网络图的最小费用值。最大流值以及其他一些相关数据。该算法程序可以为我们减少大量计算，提高工作效率，因而它在信息学竞赛，国际信息学竞赛，大学生数学建模比赛等方面都能得到应用。

消耗性网络最大流问题研究

本文在网络最大流问题的基础上，提出了消耗性网络最大流问题，分析了问题存在可行解的充分必要条件以及求解问题的优化方法。

AMR:一个基于网络最大流的Ad-Hoc多路径路由算法

移动Ad Hoc网路研究中 ,路由是一个关键问题 .现有的Ad Hoc路由算法大多为单路径算法 .但是多路径方法可以更好地支持QoS ,最近也受到较大关注 .在没有精确的网络拓扑结构情况下 ,找出多条不相交路径是比较困难的 .本文提出了一个基于网络最大流的Ad Hoc多路径路由算法AMR(Aggregatedmultipathrouting) .该算法可以有效地找出多条节点不相交的路径 ,较大幅度地提高网络传输性能、减少网络拥塞 .经过性能测试 ,表明AMR算法比DSR算法在数据传输率方面提高 2 0 %— 6 0 % ,端对端平均延迟降低 4 0 %— 6 0 % .

网络最大流问题研究进展

网络最大流问题和它的对偶问题———最小截问题 ,是一对经典组合优化问题 ,它们在许多工程领域和科学领域有重要的应用 ,是计算机科学和运筹学重要的内容 最大流问题已经有 4 0多年的研究历史 ,近年来 ,随着各种网络的飞速发展 ,最大流问题的研究也取得了很大的进展 对最大流问题研究做了详细的总结 。

基于最小费用最大流的大规模资源调度方法

并行作业是大规模资源调度的研究热点.已有的研究工作通常采用队列进行资源调度建模,仅能满足局部最优解且只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优先级和放置约束这3种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构,使其具备适应性调整能力;其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法;最后,实验对比公平性、优先级和放置约束这3种资源调度典型系统,验证了该方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真,验证了万级规模下,基于图的资源调度延迟比基于未优化图算法的资源调度延迟最多降低90%.

节点和边都有容量的有向平面网络中的最小截和最大流

在一般网络中,节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题.但传统转化方法用在平面网络中破坏了网络的平面性,使平面网络中节点和边都有容量的问题比仅边有容量的问题难.使用传统转化方法得到的两个问题的算法复杂度均为O(n2logn)(n表示网络中的节点数).对此,作者曾给出了无向平面网络中最小截问题的保持平面性的转化方法.在此基础上,这里进一步讨论有向平面网络中的最小截、最大流问题,给出有向网络中保持平面性的转化方法,并利用此转化得到了复杂度均为O(nlogn)的最小截和最大流算法.从并行计算复杂性角度来看,传统方法转化后的问题是P-完全的.而使用新方法可以得到NC算法,且可以证明节点和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC的.

网络最大流问题的一种新的符号ADD求解算法

通过对网络及网络最大流问题的符号代数判定图描述,在Trff算法的基础上,给出了网络最大流问题的一种新的符号ADD求解算法。与Dinic、Karzanov算法相比,本文算法的空间复杂度较低。实验结果表明,该算法可处理更大规模的问题。

基于最大流传输贡献度的电力网关键线路和节点辨识

从结构性视角提出一种准确辨识电力网关键线路和节点的方法。该方法基于网络最大流和复杂网络理论,定义传输贡献度作为电力网关键线路和节点辨识依据,表征它们对实现电力网电能传输功能体现出的承载和贡献能力。该方法克服了现有研究中假设潮流沿着母线间最短路径传输的缺陷,依据网络整体结构考虑不同电源—负荷节点对间所有参与功率传输的路径;同时将电力网作为有向加权网络考虑,计及了线路最大有功传输容量约束,物理背景更符合电力工程实际。对IEEE 39节点系统进行仿真计算并将结果与现有方法对比,验证了所述方法的合理性和有效性。

最大流问题的DNA计算两阶段法

给出了最大流问题的DNA计算两阶段法:第一阶段采用路序问题DNA算法得到包括所有增广路的路集,算法有两点改进,即采用等码长编码和不进行排序,这减少了生化实验时间.第二阶段算法思路是:设置一个逐步减小的增量Δ,对每个确定的Δ值从第一阶段得到的路集中寻找并增广容量不小于Δ值的增广路,对整数容量网络,当Δ<1时获得最大流.证明了算法的正确性和复杂性,并指出在以增广路为基础的最大流算法中,本算法复杂度最低,这说明DNA计算和电子计算相结合的巨大优势.

最小费用最大流模型在航班衔接问题中的应用

针对单枢纽航线网络的特点 ,以所需飞机数最少 ,航班在枢纽机场的过站衔接最紧凑为目标 ,提出了描述航班衔接问题的最小费用最大流网络模型 :首先将航班衔接问题转化为航班节的衔接问题并以各航班节在枢纽机场的到港、离港时刻为结点 ,建立了一个描述航班节衔接问题的单源汇网络 ,从而将航班衔接问题转化为该单源汇网络的最小费用最大流问题。利用 dijkstra算法求该网络的最小费用最大流进而得到了一个需用飞机数最少 ,且过站衔接最紧凑的航班节衔接方案 。

基于最大流的网络编码组播路由算法

网络编码是一种能显著提升组播传输性能的通信机制。在组播网络中部署和实施网络编码,必须建立传输路由和确定编码模式。对于后者,许多学者提出了有效的解决方法,而对于路由问题的研究则相对较少。由于网络编码自身固有的特点,基于网络编码的组播传输与传统的IP组播在建立传输路由的方式上有所不同。鉴于此,本文提出了一种基于最大流的网络编码组播路由算法,该算法与有的编码模式一起,能够构成完整的网络编码组播传输方案。仿真实验表明,与传统的IP组播相比,基于该算法的网络编码组播能够提升组播传输的性能。