【摘 要】
：
连通控制集是无线传感器网络的虚拟骨干网广泛采用的模型.在本文中,我们针对最小连通控制集问题（MinCDS）设计了一种进化算法.给定一个连通图G=（V,E）,一个子集C（?）V若满足V\C中的每个顶点在C中都有一个邻居,并且C在G中的导出子图是连通的,则称它是连通控制集（CDS）.MinCDS的目标是找到图G中基数最小的CDS.为了提高网络性能,有学者提出了容错连通控制集以保证部分节点发生故障时网络
论文部分内容阅读
连通控制集是无线传感器网络的虚拟骨干网广泛采用的模型.在本文中,我们针对最小连通控制集问题（MinCDS）设计了一种进化算法.给定一个连通图G=（V,E）,一个子集C（?）V若满足V\C中的每个顶点在C中都有一个邻居,并且C在G中的导出子图是连通的,则称它是连通控制集（CDS）.MinCDS的目标是找到图G中基数最小的CDS.为了提高网络性能,有学者提出了容错连通控制集以保证部分节点发生故障时网络仍能共享信息.给定一个连通图G=（V,E）,一个子集C（?）V若满足V\C中的每个顶点在C中至少有m个邻居,并且C在G中的导出子图是k-连通的,则称它是k-连通m-重控制集（（k,m）-CDS）.最小k-连通m-重控制集问题的目标是找到图G中基数最小的（k,m）-CDS.我们证明了我们的进化算法可以在期望时间O（n3）中找到一个CDS,且近似比为（2+ln△）,其中n和△分别是图的顶点数和图G的最大度.我们对满足m ≥ 2的最小2-连通m-重控制集问题设计了进化算法并证明了我们的进化算法可以在期望时间O（n4）中找到一个（2,m）-CDS,且近似比为α+2（1+lnα）,其中α是我们用来得到（1,m）-CDS算法的近似比.上述研究中,我们用进化算法得到的近似比和由贪婪算法得到的最好近似比一致.揭示了进化算法和近似算法之间潜在的联系.控制集问题是一种特殊的集合覆盖问题,而集合覆盖问题就是经典的覆盖问题.给定一个元素集E和子集族S（?）2E,若一个子集族F（?）S满足∪S∈FS=E,则称它是一个集合覆盖（SC）.假设每个子集S ∈ S有一个费用CS>0.最小集合覆盖问题（MinSC）是找一个费用最小的SC,其中F的费用可表示成c（F）＝∑S∈FCS.本论文还探讨了如何通过多智能体的博弈来寻找覆盖问题的较优解.我们提出了一个集合覆盖博弈,并证明任何纳什均衡都是极小集合覆盖,也是帕累托最优解.还提出了一种分布式算法来实现该博弈.该算法是自组织的,即所有参与者都可以同时自己做出决定;该算法是局部的,每个玩家仅根据其邻居的信息来做出决策;该算法是高效的,当cmax/cmin有一个输入规模的多项式上界时,算法在多项式时间内收敛到一个极小集合覆盖,其中cmax和min分别是集合的最大最小费用.
其他文献
菊芋（Helianthus tuberosus L.）属菊科向日葵属多年生草本植物,因其具有极强的抗逆性、营养价值高等特点在我国多地均有种植。近几十年来,随着酸雨频繁沉降,土壤酸化加剧,铝毒已成为南方酸性土壤中限制农作物生长的主要因素。有机酸分泌是植物适应铝毒胁迫的外部排斥铝的主要机制之一,其种类、数量与铝毒缓解程度密切相关。苹果酸、柠檬酸和草酸是多数植物响应铝毒的主要有机酸种类,也是植物适应铝毒
表情是人类内心世界的外在映射,是分析情感的重要途径,通过研究人脸表情,可以了解情绪的变化,从而正确引导情绪。人脸表情是一种复杂的研究对象,涉及到生物学、社会学、心理学、行为认知科学等多方面领域,如今随着一些关键学科取得重大进展,人脸表情识别的研究已成为热门领域,并在许多场景下有了应用,例如远程医疗、安全驾驶、情感分析等方面。对于人脸表情识别的研究,当前的主流方法是基于卷积神经网络的深度学习方法,该
近年来,微生物对药物的抵抗力逐渐增加,引起了世界范围内的广泛关注。一方面,大多数传统药物（如抗生素）逐渐无法对病原菌进行抑制或灭杀。另一方面,抗菌药物的氧化也是一个非常重要的问题。现如今,大多数食品工业都在使用对人体健康不利或可能产生一定副作用的合成抗氧化剂,因此,制药公司和食品公司都在寻找从天然资源（如动植物）生产生物活性肽的替代方法。这种从天然资中生产的抗菌肽安全、低毒,同时还具有高特异性但是
近年来,分段光滑动力系统受到广泛关注,涉及的问题有奇点分析,极限环个数等.本文考虑一类近Hamilton系统,应用一阶Melnikov函数方法,探究极限环的个数问题.文章分为5个部分,具体的研究工作如下:第一章前言简要介绍本文将要研究的一类哈密顿系统扰动下的极限环分支以及专家学者们所作出的一些结果.第二章介绍了相关的预备引理并给出Melnikov函数表达式以及扩展的完备的Chebyshev系统（即
沉积物的“源-汇”过程是全球物质循环的重要环节,对其循环路径和模式的深入研究是理解地球表生过程的重要途径。长江作为世界第三大河,其“源-汇”效应对于周围海域地形地貌有着强烈的控制和刻画作用。近30年来,长江入海泥沙量持续减少,直接导致了长江入海泥沙对浙闽沿岸沉积物物质贡献的降低。在此背景下,浙闽沿岸沉积物的潜在物源包括浙闽沿岸当地陆源物质（河流陆源物质和海岸基岩）和长江。但是,浙闽沿岸海洋环流十分
本文主要研究了两类流体方程组解的适定性.在第一章中,主要介绍了广义MHD方程组和双曲平衡律方程组相关问题的研究背景及现状,以及本文得到的主要结论;在第二章中,首先回顾了一些重要的基本不等式,然后介绍了不变区域定义和存在性定理;在第二章中,主要研究了二维广义MHD方程组:（?）其中,L2β定义为（?）.当03,初值u0,b0∈Hs（R2）,证明了该方程组解（u,b）
甜菜夜蛾（Spodoptera exigua）是浙北地区特色经济作物芦笋上的主要害虫之一。由于田间甜菜夜蛾抗药性的逐渐增加,大部分化学杀虫剂的药效降低,其防控越来越困难。甜菜夜蛾核型多角体病毒（Spodoptera exigua Nucleo Polyhedro Virus,简称SeNPV）是具有应用前景的重要病原微生物,能够在宿主中造成病毒病流行,是甜菜夜蛾种群数量的重要调节因子。目前国内外对S
本文主要研究了 twin余挠对上的Gorenstein范畴,记为（?）（S）.给出了（?）（S）是扩张封闭和保持余核的条件.并探讨了 Ding投射模的等价刻画,并讨论了Mod（R[t]/（tn））中的Ding投射维数.
令G=（V,E,F）是一个平面图,其中V,E,F分别表示图G的点集,边集和面集.Fabrici,Jendrol’和Vrbjarova于2016年提出了平面图弱点边染色的概念.对于任意的两条相邻边e1和e2,若它们关联同一个面且在该面的边界上连续出现,则称e1和e2是面相邻的.平面图G是弱点边k-可染的是指存在映射π:V（G）∪E（G）→ {1,...,k},使得任意两个相邻的顶点,任意两条面相邻的