导读:本文包含了最小割最大流论文开题报告文献综述及选题提纲参考文献，主要关键词:最小费用最大流,最短路算法,负权值
最小割最大流论文文献综述
唐四云,罗操,张倩[1]（2019）在《最小费用最大流的改进算法》一文中研究指出目前出现的最小费用最大流算法都有自身的缺陷,一般情况下都能达到最大流,但费用和效率达不到理想状态.鉴于算法核心是在赋权图中搜索费用最短路,本文结合最短路算法和赋权图的特点,提出了对最小费用最大流算法的改进.改进算法易理解且便于计算,通过对实例的Lingo编程实现,进一步论证改进算法的可行性.(本文来源于《广东技术师范学院学报》期刊2019年03期）
赵璐阳,王丽娟,宋金凤[2]（2019）在《基于最小费用最大流改进算法的多种交通方式开行方案协同优化研究》一文中研究指出为降低日常非拥挤状态下城际间综合运输系统的客运总成本,对运输通道内多种交通方式的列车开行方案或车辆运行作业计划进行了协同优化。以广义运输成本最小为目标函数,以成本和客流为约束条件,将协同优化归纳为最小费用最大流问题。为提高计算效率,根据图论中最小费用最大流常用算法之一的最小费用路算法设计出协同优化改进算法。以示例路网为基础,构建协同优化合适算例进行改进算法应用。结果表明,协同优化可以有效降低非拥挤状态下综合运输系统客运总成本,其改进算法表现出良好的有效性和准确性。(本文来源于《铁道运输与经济》期刊2019年03期）
贾明涛,涂小腾,任助理,陈鑫,宋华强[3]（2018）在《基于改进最大流最小割算法的露天境界优化及应用》一文中研究指出最终境界对露天矿开采效益至关重要,而求解速度慢且结果不准确是最大流最小割算法在露天矿境界优化中的一个固有缺陷。对已有最大流最小割算法进行改进,以净现值(NPV)最大为目标,首先以最大几何境界内的价值块构造有向网络图,通过聚合网络图节点减少弧的复杂度,并在残留网络中对负价值节点增加开采约束,以保证得到的最小割集中正价值块受到负价值块的约束,最终通过C++编程实现该算法对露天矿进行境界优化。经实例验证,该方法科学可行,克服了原算法求解速度慢且结果不准确的弊端,且求解效率提高了近600 s,该算法具有理论上的优越性和实用性。(本文来源于《黄金科学技术》期刊2018年03期）
刘石坚,邹峥,乐晓波[4]（2018）在《基于Petri网的最大流-最小割问题建模与求解》一文中研究指出给出了任意流网络及其残留网络Petri网模型的构造流程;通过对模型中各元素的实际意义进行分析,指出如何得到最大流的各个分布;从理论上证明达到最大流的条件并给出通过活性分析可以得到一个最小割的结论;将残留网络和流网络Petri网模型结合起来给出最大流-最小割问题完整的解决方案。Petri网图形化的仿真过程为研究网络流从局部到整体的变化提供了直观的描述。仿真结果证实该方法准确、有效。(本文来源于《福建工程学院学报》期刊2018年01期）
纪亚宝[5]（2017）在《最大流最小截问题的算法研究与应用》一文中研究指出最大流最小截问题属于一个组合优化问题,经过多年的研究,获得了大量的的研究成果。同时最大流最小截问题在大量实际生活中的网络都取得了广泛的应用,并且很多的的工期优化、流程控制等管理学科的问题以及图像处理中图割问题都可以转化最大流最小截问题模型求解。本文主要研究两种最大流最小截问题的求解算法及其应用,做出了如下成果:1.提出了一种改进最短增广链算法。在改进算法中删除了原网络中在增广过程中达到饱和弧。从而优化了算法中的构建剩余分层网络的过程。实验结果显示:改进算法的效率优于传统算法。2.提出了最大流最小截问题的遗传算法解法。在算法中主要设计了算法中个体编码解码方法、初始群体生成方法、适应度计算方法和选择交叉变异算子。实验结果表明:该算法能够在稳定计算最大流最小截问题,并且算法效率优于传统算法。3.介绍了最大流最小截问题在图割技术中的应用。描述了图割问题与最大流最小截问题模型之间的转换。最后通过实验,对图像进行分割。(本文来源于《南京邮电大学》期刊2017-10-26）
魏华珍[6]（2017）在《基于商空间理论的最大流/最小割问题求解研究》一文中研究指出最大流问题是一种组合最优化的经典问题,紧连运筹学和网络流理论,常应用在现实场景中的复杂问题求解,为决策人员提供关于调度资源以及合理决策的数学依据,在科学与工程领域具有广泛的应用。大数据时代下的计算机以及网络规模都在飞速发展,虽然最大流问题有几十年的研究历史,但人们需要智能高效的方式去处理海量数据,在这个背景下使用经典算法计算大规模网络最大流变得困难。同时,随着计算机网络流量巨幅增加,网络拥塞的隐患尤为显着,最小割集是最终决定网络承载量的边集,也是影响网络通行能力上限的特殊位置,因此,最小割集的求解在具体应用下也有着重要意义。依据面对大量复杂信息人类智能能够把复杂的问题简单化、抽象化、在不同角度进行转换的特点,商空间理论能够模拟人类思考特点将复杂问题转化到不同空间上进行描述分析,有效地简小问题规模,提高求解效率。因此,本文提出将商空间理论应用到最大流以及最小割集的求解中,以简化问题规模,加快求解速度。本文的研究重点在于,如何结合商空间理论(Quotient Space理论)将粒度较细的大规模复杂网络依据其结构信息构建粒度较粗的小规模网络,并在粗粒度的小规模网络上近似求解大规模网络的最大流以及最小割集,在降低计算复杂性的同时保证准确率,以弥补经典算法时间复杂度过高的不足。本文提出基于商空间模型和标签传播的最大流求解算法,其次,基于该算法,基于商空间模型和增广标记的最小割求解算法,该算法通过构建的商网络信息来估计初始大规模网络最小割边集合。两种算法在保证求解精度的同时,能在不同程度上降低计算复杂性,提高求解速度,实验部分在不同规模的公用测试网络上进行,证明本文算法的有效性。本文的主要工作如下:一、介绍本文的研究背景和研究意义,以及在实际应用中有关求解最大流/最小割亟需解决的问题,介绍相关研究现状,同时概述与本文相关的主要算法以及商空间理论知识,并对其进行分析与讨论。二、提出基于商空间模型和标签传播的最大流求解算法MFLPA(Maximum Flow based on Label Propagation Algorithm)。首先,基于标签传播方法快速找到网络中具有模块化特性的子结构,依据商空间模型定义商网络的概念,进而新构建一个小规模的商网络,最后在商网络上使用Dinc([SAP)估计初始网络最大流,达到在较小误差范围内估计原始复杂网络的最大流的目的。叁、提出基于商空间模型和增广标记的最小割求解算法DSM(Double Sets Mapping)。在基于商空间模型和标签传播的最大流求解算法的基础上,为了在商网络中计算最大流的同时估计出初始网络的最小割集,在商网络中对节点进行划分,并通过一系列证明推理过程,在商网络中找到不同节点集合与初始网络关键节点的映射关系,根据映射得到初始网络关键节点集合,根据关键节点集合中是否存在边来求初始网络的最小割集的近似解,实验证明该算法在满足特定条件的网络中可以求得网络的全部最小割边。(本文来源于《安徽大学》期刊2017-02-01）
严子恒[7]（2016）在《最小割最大流算法的研究与应用》一文中研究指出最小割最大流问题是经典组合优化问题之一,遍及于形象及抽象领域,在形象领域中,通信网络两点间的最大流量,交通网络中两地之间的最大车流量都可以转化为最小割最大流模型,在抽象领域中,最小割最大流可以较单纯型等方法更快更方便地解决最优化问题,如在图像分割技术中,使用最小割最大流方法求解能量函数最小化问题并将最小割集映射到原始图像的生成网络中可以得到被分割物体的边缘,因此,研究更快的最小割最大流算法是提高图像处理速度的核心。本文提出了两种最小割最大流新算法并应用于图像分割技术中,做出了一些成果:1.指出增广链算法中增广链利用率低的问题,并基于贪心原则提出了增广链修复最小割最大流算法,在实验中,提出的新算法在NW小世界容量网络和BA无标度容量网络中效率高于Dinic算法及最高标号预流推进算法;2.发现预流推进算法中的回流现象,说明了回流现象会造成算法滞后并随着网络的层次增加产生的影响逐渐增大,为识别并终止回流过程,提出了回流检测最小标号预流推进算法,实验结果证明,新算法能够终止回流过程并得到精确解,在大多数网络中比最高标号预流推进算法更快;3.结合图像分割技术,构造图割网络,将上述两种算法用于基于能量函数最小化的图像分割,这两种新算法不但能够准确分离目标物体,并且较经典算法降低了运行时间,能做到实时处理;4.针对Ford-Fulkerson这类非多项式时间算法,提出了网络容量倍数压缩方法,通过对网络容量的近似调整实现Ford-Fulkerson算法提速。(本文来源于《南京邮电大学》期刊2016-11-18）
高洁,杨巨峰[8]（2016）在《一种求解最小费用最大流问题的新算法》一文中研究指出常见的两种最小费用最大流算法是在最小费用基础上通过增广链求得最大流量和在最大流量基础上通过可调圈求得最小费用。通过对两种算法进行综合比较,分析其优缺点及改进思路,提出新的算法:利用最小费用法寻找最小费用增广链,据此求得接近最小费用的最大流;再通过可调圈法检验并调整该结果。(本文来源于《运城学院学报》期刊2016年03期）
张瑞华,程合友,梁宇[9]（2016）在《基于最大流最小割算法的事件检测方案》一文中研究指出文中把最大流最小割算法应用于无线传感网络的事件检测中,针对边沿陡峭的事件,设计事件区域检测算法(G-Cut).该算法首先将相邻节点的传感数据转化为权值,形成流网络;利用最大流最小割算法切割流网络,获得事件边界;再根据上传信息隐含的方向,确定事件区域.以野外火灾为例进行仿真实验,结果表明:文中算法事件检测准确度高,节点计算量低;针对多事件区域,在不增加节点计算量和通信量的情况下,仍可保证其检测准确度.(本文来源于《华南理工大学学报(自然科学版)》期刊2016年01期）
赵礼峰,严子恒[10]（2015）在《基于预流推进的最小标号最大流算法》一文中研究指出针对原始最高标号预流推进算法中的回溯现象导致其在部分网络中执行效率低下的问题,提出了基于预流推进的最小标号算法。该算法仍以预流推进为基础,但在选取活跃节点时依据贪心原则寻找最小标号活跃节点作为调整点,同时还需构造回溯检验方法终止回溯现象以提升算法效率。在仿真实验中,该算法能够适应各类复杂网络,并在稀疏网络中具有最高标号预流推进算法5倍以上执行速度;在被应用于图像分割领域时,该算法也具有50%以上性能提升。提出的基于预流推进的最小标号最大流算法能够满足大规模网络流量分配、计算机视觉图像处理等需求。(本文来源于《计算机应用》期刊2015年12期）
最小割最大流论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
为降低日常非拥挤状态下城际间综合运输系统的客运总成本,对运输通道内多种交通方式的列车开行方案或车辆运行作业计划进行了协同优化。以广义运输成本最小为目标函数,以成本和客流为约束条件,将协同优化归纳为最小费用最大流问题。为提高计算效率,根据图论中最小费用最大流常用算法之一的最小费用路算法设计出协同优化改进算法。以示例路网为基础,构建协同优化合适算例进行改进算法应用。结果表明,协同优化可以有效降低非拥挤状态下综合运输系统客运总成本,其改进算法表现出良好的有效性和准确性。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最小割最大流论文参考文献
[1].唐四云,罗操,张倩.最小费用最大流的改进算法[J].广东技术师范学院学报.2019
[2].赵璐阳,王丽娟,宋金凤.基于最小费用最大流改进算法的多种交通方式开行方案协同优化研究[J].铁道运输与经济.2019
[3].贾明涛,涂小腾,任助理,陈鑫,宋华强.基于改进最大流最小割算法的露天境界优化及应用[J].黄金科学技术.2018
[4].刘石坚,邹峥,乐晓波.基于Petri网的最大流-最小割问题建模与求解[J].福建工程学院学报.2018
[5].纪亚宝.最大流最小截问题的算法研究与应用[D].南京邮电大学.2017
[6].魏华珍.基于商空间理论的最大流/最小割问题求解研究[D].安徽大学.2017
[7].严子恒.最小割最大流算法的研究与应用[D].南京邮电大学.2016
[8].高洁,杨巨峰.一种求解最小费用最大流问题的新算法[J].运城学院学报.2016
[9].张瑞华,程合友,梁宇.基于最大流最小割算法的事件检测方案[J].华南理工大学学报(自然科学版).2016
[10].赵礼峰,严子恒.基于预流推进的最小标号最大流算法[J].计算机应用.2015