导读:本文包含了最大割问题论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:算法,组合,近似,启发式,复杂度,大流,计策。
最大割问题论文文献综述
许莹莹[1]（2018）在《面向最大割问题的启发式算法及其应用》一文中研究指出最大割问题是一个着名的NP-Hard问题,在过去几十年,众多学者提出了大量算法。由于启发式算法在求解组合优化问题上优势突出,遗传算法、神经网络算法等被大量用于求解最大割问题。本文设计了叁种求解该问题的启发式算法,并将其应用于图像分割问题,论文主要工作包括:(1)本文以一种增益调整策略为基础,设计了叁种求解最大割问题的启发式算法:融合变异的启发式算法、基于分配贡献值的启发式算法、融合交叉操作的启发式算法。为了验证算法性能,论文采用51组典型的Benchmak进行对比,结果表明融合交叉操作的启发式算法的性能最优。此外,在与其它四种算法进行的对比实验,也表明该算法的平均性能最优。(2)本文将图划分问题转化成最大割问题,首先利用区域生长法对图像预处理,然后将得到的区域作为顶点,区域间基于颜色特征的相异性作为顶点间的权值来构建图模型,采用基于分配贡献值的启发式算法寻找相异性最大的相邻区域,将其标黑,其余区域按照一定的规则合并,合并后重新构造图模型,依次循环。为了验证算法性能,论文与其它四种算法进行对比,结果表明本文算法的平均性能最优。(3)交互式图像分割通过用户标记指导图像分割,可以获得更准确的分割结果,首先利用超像素SLIC算法预处理图像,然后将得到的区域作为顶点构造图模型,采用欧氏距离与巴氏系数的加权方式来构建权值,采用基于分配贡献值的启发式算法寻找距离最远的相邻区域,将其标黑,其余区域按照一定的规则合并,合并后重新构造图模型,依次循环。为了验证算法性能,论文与MSRM算法进行对比,结果表明本文算法的平均性能最优。(本文来源于《太原科技大学》期刊2018-05-02）
刘石坚,邹峥,乐晓波[2]（2018）在《基于Petri网的最大流-最小割问题建模与求解》一文中研究指出给出了任意流网络及其残留网络Petri网模型的构造流程;通过对模型中各元素的实际意义进行分析,指出如何得到最大流的各个分布;从理论上证明达到最大流的条件并给出通过活性分析可以得到一个最小割的结论;将残留网络和流网络Petri网模型结合起来给出最大流-最小割问题完整的解决方案。Petri网图形化的仿真过程为研究网络流从局部到整体的变化提供了直观的描述。仿真结果证实该方法准确、有效。(本文来源于《福建工程学院学报》期刊2018年01期）
魏华珍[3]（2017）在《基于商空间理论的最大流/最小割问题求解研究》一文中研究指出最大流问题是一种组合最优化的经典问题,紧连运筹学和网络流理论,常应用在现实场景中的复杂问题求解,为决策人员提供关于调度资源以及合理决策的数学依据,在科学与工程领域具有广泛的应用。大数据时代下的计算机以及网络规模都在飞速发展,虽然最大流问题有几十年的研究历史,但人们需要智能高效的方式去处理海量数据,在这个背景下使用经典算法计算大规模网络最大流变得困难。同时,随着计算机网络流量巨幅增加,网络拥塞的隐患尤为显着,最小割集是最终决定网络承载量的边集,也是影响网络通行能力上限的特殊位置,因此,最小割集的求解在具体应用下也有着重要意义。依据面对大量复杂信息人类智能能够把复杂的问题简单化、抽象化、在不同角度进行转换的特点,商空间理论能够模拟人类思考特点将复杂问题转化到不同空间上进行描述分析,有效地简小问题规模,提高求解效率。因此,本文提出将商空间理论应用到最大流以及最小割集的求解中,以简化问题规模,加快求解速度。本文的研究重点在于,如何结合商空间理论(Quotient Space理论)将粒度较细的大规模复杂网络依据其结构信息构建粒度较粗的小规模网络,并在粗粒度的小规模网络上近似求解大规模网络的最大流以及最小割集,在降低计算复杂性的同时保证准确率,以弥补经典算法时间复杂度过高的不足。本文提出基于商空间模型和标签传播的最大流求解算法,其次,基于该算法,基于商空间模型和增广标记的最小割求解算法,该算法通过构建的商网络信息来估计初始大规模网络最小割边集合。两种算法在保证求解精度的同时,能在不同程度上降低计算复杂性,提高求解速度,实验部分在不同规模的公用测试网络上进行,证明本文算法的有效性。本文的主要工作如下:一、介绍本文的研究背景和研究意义,以及在实际应用中有关求解最大流/最小割亟需解决的问题,介绍相关研究现状,同时概述与本文相关的主要算法以及商空间理论知识,并对其进行分析与讨论。二、提出基于商空间模型和标签传播的最大流求解算法MFLPA(Maximum Flow based on Label Propagation Algorithm)。首先,基于标签传播方法快速找到网络中具有模块化特性的子结构,依据商空间模型定义商网络的概念,进而新构建一个小规模的商网络,最后在商网络上使用Dinc([SAP)估计初始网络最大流,达到在较小误差范围内估计原始复杂网络的最大流的目的。叁、提出基于商空间模型和增广标记的最小割求解算法DSM(Double Sets Mapping)。在基于商空间模型和标签传播的最大流求解算法的基础上,为了在商网络中计算最大流的同时估计出初始网络的最小割集,在商网络中对节点进行划分,并通过一系列证明推理过程,在商网络中找到不同节点集合与初始网络关键节点的映射关系,根据映射得到初始网络关键节点集合,根据关键节点集合中是否存在边来求初始网络的最小割集的近似解,实验证明该算法在满足特定条件的网络中可以求得网络的全部最小割边。(本文来源于《安徽大学》期刊2017-02-01）
孙婷,李改弟,徐文青[4]（2016）在《最大割问题和最大平分割问题基于半定规划松弛的近似算法》一文中研究指出考虑每条边具有非负权重的无向图,最大割问题要求将顶点集划分为两个集合使得它们之间的边的权重之和最大.当最大割问题半定规划松弛的最优解落到二维空间时,Goemans将近似比从0.87856…改进为0.88456.依赖于半定规划松弛的目标值与总权和的比值的曲线,此曲线的最低点为0.884 56,当半定规划松弛的目标值与总权和的比值在0.5到0.9044之间时,利用Gegenbauer多项式舍入技巧,改进了Zwick的近似比曲线.进一步,考虑最大割问题的重要变形——最大平分割问题,在此问题中增加了划分的两部分的点数相等的要求.同样考虑了最大平分割问题半定规划松弛的最优解落到二维空间的情形,并利用前述的Gegenbauer多项式舍入技巧得到0.709 1-近似算法.(本文来源于《运筹学学报》期刊2016年03期）
邓瑾[5]（2016）在《图与定向图的最大割问题的研究》一文中研究指出图的划分问题是图论研究的热点问题之一,在计算机科学、生物科学、大规模集成电路设计和图像分割等方面都有广泛的应用.图划分问题起源于最大割问题:给定一个图G,寻求图G的顶点集的一个二部划分V(G)= 1 ∪V2,使得e(V1,V2)尽可能大,其中e(V1,V2)表示一个端点在V1中,另一个端点在V2中的边的条数.最大割问题是计算机理论研究的基本问题之一,受到众多研究者的广泛关注.对于有向图D,以及两个不相交的顶点子集X,Y(?)V(D),用e(X,Y)表示由X指向Y的弧的条数.显然,在研究有向图D的一个划分V(D)= V1 ∪V2所对的割边时,我们需要考虑两个量:e(V1,V2),e(V2,V1).因此,有向图最大割问题是比图的最大割问题更复杂的问题,目前已有的研究成果较少.在本文,我们主要讨论图与定向图的最大割问题,论文结构如下:第一章,我们先介绍图论中的一些基本概念和符号.然后,介绍本文所研究的图划分问题的基本定义、最大割问题的历史背景与发展,最后给出论文的主要结果.第二章,我们主要讨论一类特殊图的最大割问题.构造图H:用一个点连接任意多个完全二部图K2,s(s ≥ 2).在本章,我们对不含H作为子图的图的最大割问题进行研究,证明了:若图G有m条边且不含H作为子图,则存在c = c(H)>0,以及G的一个二部划分V(G)= V1 ∪ V2,使得e(V1,V2)≥ m/2+ + cm4/5,并且这个下界是紧的.第叁章,我们运用概率方法,主要研究了定向图的最大平衡割问题.对有向图D的一个划分V(D)= V1 ∪ V2,如果||V1|-|V2|| ≤ 1,则称这个划分为二部平衡划分.在本章,我们证明了:设d ≥ 4是正整数,D是有m条边的定向图,如果对任意∈ V(D),满足min{d+(v),d-(v)} ≥ d,则D存在二部平衡划分V(D)= 1 ∪V2,使得min{e(V1,V2),e(V2,V1)} ≥((d-1)/(2(2d-1)))+ o(1))m.最后,我们给出了两个值得进一步研究的问题。(本文来源于《福州大学》期刊2016-06-01）
孔树锋[6]（2014）在《启发式算法求解最大割问题的性能分析与优化》一文中研究指出最大割问题(MAXCUT Problem)是着名的NP难问题，即使形式最简单的2-最大割问题(2-MAXCUT Problem)也属于NP难问题。这意味着，不存在任何算法能在多项式时间内为其找到最优解，除非NP=P。启发式算法是为了快速求解时间复杂度极高的组合优化问题(如NP难问题)而提出的一类近似算法。启发式算法与确定性算法的主要区别在于：启发式算法利用某些特殊的信息在多项式时间内寻找问题的近似解，而并非最优解。在过去的几十年，最大割问题作为一个研究热点一直被众多专家学者关注着。为了求解最大割问题，大量启发式算法被提出，如演化算法、蚁群算法等，但多数研究只从实验的角度估算算法的时间复杂度，而基于严格理论推导的研究成果却十分稀少。本文的主要工作包括：(1)本文从理论的角度分析和比较了叁种着名的启发式算法在2-最大割问题上的近似性能，它们分别是：随机局部搜索算法(Random Local Search, RLS)，(1+1)-演化算法((1+1)-Evolutionary Algorithm，(1+1)-EA)和随机游走算法(RandomWalk Algorithm)。分析结果表明：(1+1)-EA寻找一个0.5-近似解的时间上界是O (n3)；随机游走算法寻找一个(12α)-近似解(α≥0)的时间上界是O (n (1+1/(3+2α)) n)。此外，为了深入了解不同启发式算法求解最大割问题的效率差异，本文分析了这叁种算法求解完全二分图的时间复杂度。分析结果表明，这叁种启发式算法都能够在多项式时间内找到完全二分图的最优解，且(1+1)-演化算法与随机局部搜索算法算法的性能均优于随机游走算法。(2)除了关注启发式算法在最大割问题上的性能分析，本文还关注启发式算法在最大割问题上的性能优化。在求解最大割问题时，朴素演化算法的稳定性较差、且容易出现过早收敛的现象。为了克服这些缺点，本文对朴素演化算法进行了改进。首先，本文在朴素演化算法中混合了一种局部优化策略来提高算法求解的质量；同时，本文为算法设计了自适应变异算子和交叉算子，它们可以克服算法的过早收敛。此外，本文通过降低“种群的浓度”来改进“比例选择算子”的性能。为了验证改进算法的有效性，本文研究了当前求解最大割问题的几种近似算法，并进行了实验对比。实验结果表明，本文提出的改进演化算法比朴素演化算法的性能好20%，且算法在求解最大割问题上的效率和质量上均优于大多数近似算法。(本文来源于《华南理工大学》期刊2014-06-09）
张爱君,秦新强,龚春琼[7]（2014）在《求解最大割问题的多启动禁忌搜索算法》一文中研究指出为了增强局部搜索算法在求解最大割问题上的寻优能力,提高解质量,提出了一种多启动禁忌搜索(MSTS)算法。算法主要包括两个重要组件:一是用于搜索高质量局部优化解的禁忌搜索算法;二是具有全局搜索能力的重启策略。算法首先通过禁忌搜索组件获取局部优化解;然后应用设计的重启策略重新生成初始解并重启禁忌搜索过程。重启策略基于随机贪心的思想,综合利用了"构造"和"扰动"这两种方法生成新的起始解,来逃离局部最优的陷阱从而找到更高优度的解。采用了国际文献中公认的21个算例作为本算法的测试实验集并进行实算,并与多个先进算法进行比较,MSTS算法在18个算例上得到最好解值,高于其他对比算法。实验结果表明,MSTS算法具有更强的寻优能力和更高的解质量。(本文来源于《计算机应用》期刊2014年05期）
刘建军[8]（2011）在《改进的Tabu Machine网络求解最大割问题》一文中研究指出为了提高Tabu Machine网络处理最大割问题时解的质量,改进原有算法的禁忌搜索策略,并且通过结合局部搜索策略和分布估计策略,形成一种新的网络HNNTS-EDA。此网络有较强的局部搜索能力和脱离局部最优值的能力。将HNNTS-EDA网络与多种经典算法在相同测试数据上进行对比测试,实验结果表明HNNTS-EDA网络具有更强的寻优能力。(本文来源于《计算机应用与软件》期刊2011年08期）
刘运龙,王建新[9]（2010）在《带权最大割问题的一种基于划分技术的固定参数可解算法》一文中研究指出运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题及其相关概念进行了参数化定义,然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行[1n(1/ε)]×2~k(0<ε<1)次随机划分,并选择其中权值最大的k-划分作为输出解,因而能在时间O~*(1n(1/ε)2~k)内以至少1-ε的概率找到目标解。接着在此基础上着重运用最新改进的(n,k)-全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O~*(2~(2k+12log~2(2k))的确定性算法,表明了带权最大割问题是固定参数可解的。(本文来源于《高技术通讯》期刊2010年03期）
丁海军,杨乐好[10]（2009）在《求解最大割问题的交叉熵算法》一文中研究指出交叉熵方法(Cross Entropy)是近几年发展而来的一种启发式方法,在求解组合优化问题中显示出其简单有效的特点,将运用交叉熵方法(CE)寻求图论中一个典型的NP困难问题—最大割问题的最优解。为了解决最大割问题,CE方法借助Bernoulli分布的思想,将一个确定性的网络转换成一个具有一定随机性的关联网络,接下来首先按照一个多维的Bernoulli概率分布生成样本,同时计算出随机割;其次,基于前一步的数据,更新Bernoulli概率分布P参数,使得分布参数逐步逼近最优值产生最大割的稳定估计值。数值实验表明,CE方法具有很好的稳定性和收敛性,最终也获得了比较好的近似解。(本文来源于《计算机工程与应用》期刊2009年30期）
最大割问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
给出了任意流网络及其残留网络Petri网模型的构造流程;通过对模型中各元素的实际意义进行分析,指出如何得到最大流的各个分布;从理论上证明达到最大流的条件并给出通过活性分析可以得到一个最小割的结论;将残留网络和流网络Petri网模型结合起来给出最大流-最小割问题完整的解决方案。Petri网图形化的仿真过程为研究网络流从局部到整体的变化提供了直观的描述。仿真结果证实该方法准确、有效。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
最大割问题论文参考文献
[1].许莹莹.面向最大割问题的启发式算法及其应用[D].太原科技大学.2018
[2].刘石坚,邹峥,乐晓波.基于Petri网的最大流-最小割问题建模与求解[J].福建工程学院学报.2018
[3].魏华珍.基于商空间理论的最大流/最小割问题求解研究[D].安徽大学.2017
[4].孙婷,李改弟,徐文青.最大割问题和最大平分割问题基于半定规划松弛的近似算法[J].运筹学学报.2016
[5].邓瑾.图与定向图的最大割问题的研究[D].福州大学.2016
[6].孔树锋.启发式算法求解最大割问题的性能分析与优化[D].华南理工大学.2014
[7].张爱君,秦新强,龚春琼.求解最大割问题的多启动禁忌搜索算法[J].计算机应用.2014
[8].刘建军.改进的TabuMachine网络求解最大割问题[J].计算机应用与软件.2011
[9].刘运龙,王建新.带权最大割问题的一种基于划分技术的固定参数可解算法[J].高技术通讯.2010
[10].丁海军,杨乐好.求解最大割问题的交叉熵算法[J].计算机工程与应用.2009
论文知识图
