最小控制集论文_张志强,叶安胜,周晓清

导读:本文包含了最小控制集论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:算法,圆盘,区间,最小,近似,独立,单位。

最小控制集论文文献综述

张志强,叶安胜,周晓清^[1]（2014）在《最小控制集问题的群集策略智能算法研究》一文中研究指出图的最小控制集是一个经典的NP完全问题,其广泛应用在生物信息学、计算机通讯、工程设计等方面。目前搜索最小控制集算法有多种,例如:贪心算法、模拟退火算法、基于禁忌搜索的模拟退火算法等。当搜索结构复杂的多点图时,很多算法的搜索效果并不好。为了提高搜索效果,提出并实现一种群集策略智能算法;同时还对群集策略算法进行了非常重要的扰动改进。为了验证算法的搜索效果,利用Petersen图和随机图完成了对群集策略算法的搜索测试实验;同时也完成了对群集策略算法、贪心算法、基于禁忌搜索的模拟退火算法的比较测试实验,通过实验结果也验证了群集策略算法搜索效果最好。(本文来源于《科学技术与工程》期刊2014年16期）

帅天平,李业芳,艾文宝^[2]（2012）在《传感器网络中最小k-连通m-控制集问题的近似算法》一文中研究指出在当前无线传感器网络的相关研究中,虚拟骨干网的构造引起广泛的关注.通过引进虚拟骨干网来设计路由协议,使得路由更加可靠和高效,从而减少广播风暴.无线传感器网络中具有容错功能的虚拟骨干网的构造可转化为圆盘图中的最小k-连通m-控制集问题.本文研究了具有不同传输半径的双向圆盘图中的最小k-连通m-控制集问题,给出了一个构造最小k-连通m-控制集的多项式时间近似算法,理论分析表明该算法具有较好的近似比.最后,在不同的网络拓扑上进行了仿真实验,仿真结果进一步验证了算法的有效性.(本文来源于《工程数学学报》期刊2012年05期）

马文凯,李德英,张昭^[3]（2011）在《构建最小k重控制集的概率算法》一文中研究指出点集D V(G)称为图G的k重控制集,如果D满足V(G)-D中任意结点在D中至少有k个邻居.在无线网络中,最小k重控制集(MkDS)用以构建健壮的虚拟骨干网.构建虚拟骨干网是无线网络中最基本也是最重要的问题.在本文中,我们提出一种快速的分布式概率算法来构建k重控制集.我们构建的k重控制集的期望大小不超过最优解的O(k2)倍.算法的运行时间复杂度为O((△log△+loglogn)n),其中△=max{|D(p)|},D(p)是以p为中心半径为1的圆盘中的结点,最大值的比较范围是给定集合中所有的p点.(本文来源于《中国科学:数学》期刊2011年08期）

李秀英^[4]（2011）在《求最小2连通r步控制集的两种算法》一文中研究指出随着信息网络的飞速发展,网络中的许多理论性问题越来越来引起人们的重视.比如说,网络中的节能与容错度.无线传感网络是由大量的传感器组成的,它们相互合作,感应,收集和处理原始信息,并且将处理过的信息传递给观察者.不同于有线网络,无线传感器网络没有任何实际的框架.在工作中,如果每一个感应器都将它接收到的每一个信息传播出去,就可能产生很多的麻烦.首先,它是很浪费能量的,这对于无线传感器网络是很重要的,因为每一个传感器只有一定量的能量,并且通常不可再生.再次,这可能导致许多噪音,从而导致所谓的传播风暴.为了避免这些问题,实质骨架的概念在无线网络中被提出来,它与图中的连通控制集相对应.如果我们将网络的拓扑结构抽象为图G.在图G = (V,E)中,称一个顶点子集D (?) V为一个控制集,如果V ? D中的每一点u都与D中的至少一个点是相邻的.如果控制集D满足G[D]是连通的,则称D是一个连通控制集.对于一个整数r,及顶点u ,称顶点子集U在r步内控制住顶点u,如果u与U中的某些点的距离至多为r.如果D在r步内控制住V D中的每一个点u,则称顶点子集D是一个r步控制集.如果r步控制集导出的子图为连通的,则称为连通r步控制集.本文共分叁章.第一章,我们介绍了研究背景以及本文的主要概念和主要结果.第二章,我们给出贪婪算法来计算最小的2连通r步控制集.它主要利用了2连通图的耳朵分解,这个算法可以用在一般的2连通图上.第叁章,我们给出了叁阶段算法来计算最小的2连通r步控制集.这个算法仅适用于单位圆盘图.对于这两种算法,我们都给出了它们的理论分析.(本文来源于《新疆大学》期刊2011-05-30）

皮军德,林浩^[5]（2007）在《直线簇上区间图的最小全控制集和最小配对控制集》一文中研究指出研究了广义区间图的最小全控制集和最小配对控制集的计算问题.对有一个公共交点的直线簇上的区间图,给出了计算其最小全控制集的O(n)时间算法和其最小配对控制集的O(n+m)时间算法.(本文来源于《河南科学》期刊2007年04期）

皮军德,康丽英,许光俊^[6]（2006）在《直线簇上区间图的最小独立控制集》一文中研究指出本文研究了在叁种情况下直线上的区间图的最小独立控制集的计算问题:1．相交于一点的直线簇,2．除一条直线外,其余的直线都平行的直线簇,3．一条直线和直线上t个赋权的点,使得其最小独立控制集所覆盖的点的权和最大．本文给出了这叁个问题的多项式时间算法,问题1可以在O(n)时间内求解,借助动态规划方法问题2和问题 3分别可以在O(n log n),O(n+t)时间内求解．(本文来源于《运筹学学报》期刊2006年01期）

皮军德,康丽英,赵敏^[7]（2005）在《直线簇上区间图的最小连通控制集》一文中研究指出研究了在3种情况下直线上的区间图的最小连通控制集的计算问题:(1)相交于一点的直线簇;(2)除一条直线外,其余的直线都平行的直线簇;(3)一条直线和直线上t个赋权的点,使得其最小连通控制集所覆盖的点的权和最大.给出了这3个问题的多项式时间算法,问题1和问题2可以在O(n)时间内求解,借助动态规划方法问题3可以在O(n+t)时间内求解.(本文来源于《上海大学学报(自然科学版)》期刊2005年06期）

段惠琴^[8]（2000）在《求图最小控制集的逻辑算法》一文中研究指出本文介绍了求图的全部最小控制集的逻辑算法 ,并用此方法对监狱看守通讯系统等问题给予求解(本文来源于《运城高等专科学校学报》期刊2000年03期）

陈东灵,蒋昌俊,阎春钢^[9]（1989）在《图的最小控制集的一个算法》一文中研究指出本文引进了关于图的控制向量概念,以向量和矩阵为工具,把一个图的最小控制集问题转化为一个0—1规划问题,从而给出了寻找图的控制数的一个算法和算例。(本文来源于《山东矿业学院学报》期刊1989年04期）

最小控制集论文开题报告

（1）论文研究背景及目的

此处内容要求：

首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。

写法范例：

在当前无线传感器网络的相关研究中,虚拟骨干网的构造引起广泛的关注.通过引进虚拟骨干网来设计路由协议,使得路由更加可靠和高效,从而减少广播风暴.无线传感器网络中具有容错功能的虚拟骨干网的构造可转化为圆盘图中的最小k-连通m-控制集问题.本文研究了具有不同传输半径的双向圆盘图中的最小k-连通m-控制集问题,给出了一个构造最小k-连通m-控制集的多项式时间近似算法,理论分析表明该算法具有较好的近似比.最后,在不同的网络拓扑上进行了仿真实验,仿真结果进一步验证了算法的有效性.

（2）本文研究方法

调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。

实证研究法：依据现有的科学理论和实践的需要提出设计。

定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。

定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。

跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。

模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

最小控制集论文参考文献

[1].张志强,叶安胜,周晓清.最小控制集问题的群集策略智能算法研究[J].科学技术与工程.2014

[2].帅天平,李业芳,艾文宝.传感器网络中最小k-连通m-控制集问题的近似算法[J].工程数学学报.2012

[3].马文凯,李德英,张昭.构建最小k重控制集的概率算法[J].中国科学:数学.2011

[4].李秀英.求最小2连通r步控制集的两种算法[D].新疆大学.2011

[5].皮军德,林浩.直线簇上区间图的最小全控制集和最小配对控制集[J].河南科学.2007

[6].皮军德,康丽英,许光俊.直线簇上区间图的最小独立控制集[J].运筹学学报.2006

[7].皮军德,康丽英,赵敏.直线簇上区间图的最小连通控制集[J].上海大学学报(自然科学版).2005

[8].段惠琴.求图最小控制集的逻辑算法[J].运城高等专科学校学报.2000

[9].陈东灵,蒋昌俊,阎春钢.图的最小控制集的一个算法[J].山东矿业学院学报.1989

论文知识图

标签：算法论文;  圆盘论文;  区间论文;  最小论文;  近似论文;  独立论文;  单位论文;