导读:本文包含了度约束最小生成树论文开题报告文献综述及选题提纲参考文献，主要关键词:不确定理论,不确定变量,最小生成树,不确定网络
度约束最小生成树论文文献综述
贾利芬[1]（2017）在《不确定随机网络下的度约束最小生成树问题》一文中研究指出最小生成树问题是网络优化中的基本问题之一,在通信网络、交通网络、物流网络等领域中有广泛的应用。电路设计中为了减小节点的脆弱性,Narula和Ho在1980年提出度约束最小生成树问题。该问题旨在寻找最小权重的生成树,且每个节点的度满足给定的约束的要求。在经典网络中,所有权重都是已知的常数,因此可以利用经典的算法求解。然而在现实网络中,由于非决定性因素的存在,导致网络中的权重是非决定性的。为了描述非决定性的网络,Frank和Hakimi在1965年首先提出了随机网络的概念,目的是描述通信网络的随机现象。在2010年,Knowles和David首先把度约束最小生成树问题引入到随机网络中,但该方法对权重的估计十分依赖历史数据。然而在现实网络中,很多网络是没有历史数据的,因此Liu在2010年提出了不确定网络的概念。本文主要研究了不确定网络下的度约束最小生成树问题。基于不确定变量的不同的比较原则,我提出了叁种不确定规划模型:不确定期望值度约束最小生成树模型,不确定?-度约束最小生成树模型和不确定最大机会度约束最小生成树模型。论文运用改进的遗传求解模型,并给出数值算例。在实际生活的网络中,有的权重没有历史数据,有的权重有历史数据,因此不确定性和随机性往往同时出现在一个复杂的网络。最近,Liu在不确定网络的基础上进一步提出了不确定随机网络的概念。本文首次研究了不确定随机网络下的度约束最小生成树问题,提出了一个理想机会分布的概念。为了寻找与理想机会分布最接近的度约束生成树作为度约束最小生成树,建立了一个不确定随机规划模型,最后论文给出了数值算法求解该模型。(本文来源于《华北电力大学(北京)》期刊2017-03-01）
孙小军[2]（2016）在《基于Prim算法的度约束最小生成树问题研究》一文中研究指出针对一类度约束最小生成树问题,基于传统最小生成树问题的Prim算法,设计了一种求解算法.该算法在保证网络中指定节点的度不变的前提下,构造了网络关于指定节点的最大度最小生成树.与经典的Gloveklingman算法进行了仿真比较,结果表明,该算法是求解度约束最小生成树问题的一种有效算法.(本文来源于《内蒙古师范大学学报(自然科学汉文版)》期刊2016年04期）
范凯翔[3]（2015）在《基于多种群的度约束最小生成树算法研究》一文中研究指出当前,社会经济飞速发展,科学技术革故鼎新,社会资源的利用趋于寻求高效率和有效化的解决,最小生成树的研究在实际生活中得到了越来越广泛的应用和认可。度约束最小生成树(DCMST)司题是一个着名的NP-hard问题。因为现实应用问题的多样性和复杂性,经常是对最小生成树问题加以条件限制,因此这类度约束的最小生成树问题在实际研究领域得到了广泛的应用,如交通运输和计算机网络设计,都利用DCMST问题实现和解决。本论文针对DCMST问题进行了如下研究：本课题主要是采用基于多种群蚁群智能算法的改进方法实现度约束的最小生成树的构造,该算法流程主要包括多种群蚁群探索、生成树的构造和生成树的优化叁部分。多种群蚂蚁在搜索过程中算法利用蚁群寻找边集,如果蚂蚁寻找最小生成树失败,针对此弊端首次采取产生新的蚂蚁且使该类蚂蚁在搜索过程中采取只用启发式信息素搜索的策略防止蚁群算法陷入局部最优,之后将找到的边集利用Kruskal算法构造最小生成树并利用局部优化算法对其进行局部优化,增加了解的多样性。在多种群中,各个蚂蚁种群通过信息熵进行自适应信息交流,采取动态改变信息素和设置干扰因子的策略增加路径选择的多样性,同时加入最大最小蚂蚁系统等算法的策略对蚁群算法进行了优化,以此加快解的收敛程度和得到更多的解。并通过大量仿真实验证明,该算法在DCMST问题的最优解求解中解的优化方面有明显的优越性。(本文来源于《天津工业大学》期刊2015-12-01）
张丽慧[4]（2015）在《基于遗传算法的度约束最小生成树问题的研究》一文中研究指出度约束最小生成树(Degree Constrained Minimum Spanning Tree, DCMST)问题是网络优化中一个常见的问题。近年来,度约束最小生成树在计算机网络、通信网络和运输网络设计等领域得到了广泛的应用,许多网络设计问题都和度约束最小生成树问题有关。比如,在构建通讯网络时,网络布局就是寻找连通图的生成树,建网费用最少就是寻找最小生成树,每个结点负载不能太多就是对结点的度约束。然而,度约束的最小生成树的求解被证明是一个NP难问题,因此对大规模DCMST问题,目前还没有有效的算法。本文介绍了求解DCMST问题的古典算法、启发式算法以及现代优化算法。设计了一种在非完全图下求解度约束最小生成树问题的遗传算法,为此构造了新的编码方法、适应度函数、初始化方法、遗传算子。为了加快优化进度,设计了寻优算子,取得了较好的效果。(本文来源于《内蒙古大学》期刊2015-05-01）
郭仁杰[5]（2014）在《度约束最小生成树问题概述》一文中研究指出度约束最小生成树问题是经典的组合优化难题。本文对度约束最小生成树问题进行了综述,介绍了研究背景、数学模型及相关概念,并对该问题的求解算法进行了分类总结。(本文来源于《阴山学刊(自然科学版)》期刊2014年02期）
郭仁杰[6]（2014）在《基于单亲遗传算法的度约束最小生成树问题研究》一文中研究指出最小生成树问题是组合优化中的经典问题,并在通信网络设计和最短路连接等方面有广泛的应用。在实际应用中,生成树顶点的度往往需要满足某些条件。比如通信网络设计中为了防止节点故障带来的脆弱性,对节点的度要有一定的限制。这种顶点带有度约束的最小生成树问题称为度约束最小生成树问题。遗传算法作为一种启发式搜索优化算法,它为求解度约束最小生成树问题提供了一个有效的途径。本文通过结合遗传算法的思想,针对度约束最小生成树问题的特点,提出了采用单亲遗传算法求解这一问题,并设计了新的编码方案和相应的遗传操作。本文首先对度约束最小生成树问题的研究背景作了介绍。其次,介绍了一些求解度约束最小生成树问题的常用算法。最后,提出了在完全图下求解度约束最小生成树问题的单亲遗传算法。本文通过对prufer编码的改进提出了新的编码方式和解码方式,这样的改进使得整个解码过程是静态的,提高了算法的运行效率,并且通过对新的编码的分析可直观得出树的结构。设计了新的变异算子,新算子保持了种群多样性的同时,又可使后代保留了父代的优良品质。设计了两种局部寻优算子,改善了优化质量,同时又提高了搜索效率。(本文来源于《内蒙古大学》期刊2014-04-23）
秦轶[7]（2013）在《用单亲遗传算法求解度约束最小生成树问题》一文中研究指出最小生成树问题是一类非常重要的组合优化问题,在现实中被广泛应用于各个领域,如通信网设计、道路系统设计、管道铺设等。如果在最小生成树问题中对每个顶点加以度约束即限制连接到顶点的边的数量,这时问题就成为度约束最小生成树问题。度约束最小生成树问题有很重要的现实意义,比如设计通信网时,如果不考虑度约束,某些重要节点一旦出现故障可能会导致整个网络瘫痪,因此限定连接到节点的边的数量是很有必要的。度约束最小生成树问题的求解方法有启发式算法、遗传算法等。本文讨论完全图下的度约束最小生成树问题,使用单亲遗传算法求解。该算法首先利用Prufer数对生成树进行编码,保证产生的初始种群不含有任何不可行解；设计了叁种变异操作,并分析叁种变异操作对图的影响而采用按比例执行变异操作,保证产生优秀的可行的子代染色体,拓展搜索空间；构造了两种局部寻优算子,增强了算法在较小区域内搜寻更加适应环境的个体的能力,使得最终能够输出更优秀的个体。(本文来源于《内蒙古大学》期刊2013-04-01）
石磊,冯祖针,杨建强[8]（2012）在《蚁群算法求解直径约束最小生成树问题》一文中研究指出给定无向赋权图G和直径约束值D,直径约束最小生成树问题是查找一个直径不超过D最小权重的生成树.当时,其是NP-hard问题.用蚁群算法对其进行求解,设计了一种新的当前节点选择规则.分析和实验表明,基于新的节点选择规则的蚁群算法对直径约束最小生成树问题有较好的求解效果.(本文来源于《红河学院学报》期刊2012年04期）
石磊,冯祖针,杨建强,龙瑶[9]（2012）在《度、半径约束最小生成树问题及其算法》一文中研究指出提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.(本文来源于《沈阳大学学报(自然科学版)》期刊2012年04期）
石磊,冯祖针,杨建强[10]（2012）在《度、直径约束最小生成树问题及其算法》一文中研究指出提出了度、直径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法,其时间复杂性为O(mn).分析和实例实验表明,该算法有良好的效果.(本文来源于《云南民族大学学报(自然科学版)》期刊2012年04期）
度约束最小生成树论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
针对一类度约束最小生成树问题,基于传统最小生成树问题的Prim算法,设计了一种求解算法.该算法在保证网络中指定节点的度不变的前提下,构造了网络关于指定节点的最大度最小生成树.与经典的Gloveklingman算法进行了仿真比较,结果表明,该算法是求解度约束最小生成树问题的一种有效算法.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
度约束最小生成树论文参考文献
[1].贾利芬.不确定随机网络下的度约束最小生成树问题[D].华北电力大学(北京).2017
[2].孙小军.基于Prim算法的度约束最小生成树问题研究[J].内蒙古师范大学学报(自然科学汉文版).2016
[3].范凯翔.基于多种群的度约束最小生成树算法研究[D].天津工业大学.2015
[4].张丽慧.基于遗传算法的度约束最小生成树问题的研究[D].内蒙古大学.2015
[5].郭仁杰.度约束最小生成树问题概述[J].阴山学刊(自然科学版).2014
[6].郭仁杰.基于单亲遗传算法的度约束最小生成树问题研究[D].内蒙古大学.2014
[7].秦轶.用单亲遗传算法求解度约束最小生成树问题[D].内蒙古大学.2013
[8].石磊,冯祖针,杨建强.蚁群算法求解直径约束最小生成树问题[J].红河学院学报.2012
[9].石磊,冯祖针,杨建强,龙瑶.度、半径约束最小生成树问题及其算法[J].沈阳大学学报(自然科学版).2012
[10].石磊,冯祖针,杨建强.度、直径约束最小生成树问题及其算法[J].云南民族大学学报(自然科学版).2012