【摘 要】
：
覆盖问题是一类经典的组合优化问题.在生产生活中有着广泛的应用,如:扮演电子警察的控制集问题.本文主要应用博弈论的方法来研究控制集问题的两个变形:连通控制集问题（connected dominating set）与安全控制集问题（secure dominating set）.连通控制集问题的产生是基于人们对网络监控系统中无线传感器之间保持信息共享的需求.对于给定的图G=（V,E）,如果对任意的点vi
论文部分内容阅读
覆盖问题是一类经典的组合优化问题.在生产生活中有着广泛的应用,如:扮演电子警察的控制集问题.本文主要应用博弈论的方法来研究控制集问题的两个变形:连通控制集问题（connected dominating set）与安全控制集问题（secure dominating set）.连通控制集问题的产生是基于人们对网络监控系统中无线传感器之间保持信息共享的需求.对于给定的图G=（V,E）,如果对任意的点vi ∈ V\C,都存在点vj ∈ C∩Ni,其中Ni为点vi的邻点集合,那么我们称点子集C是图G的一个控制集（dominating set）.如果控制集C在图G中的导出子图G[C]还是连通的,我们就称C是图G的一个连通控制集（CDS）.安全控制集问题的产生是基于人们对移动式网络监控系统的安全性的需求.对于给定的一张图G=（V,E）,假设点子集C是图G的一个控制集,如果对于任意的点u ∈ V\C,都存在一个点v∈ C,使得uv∈E,且集合C\{v} ∪{u}仍然是图G一个控制集.我们称这样的点子集C是图G的一个安全控制集（SDS）.本学位论文分为四章,第一章介绍相关概念与背景知识,并介绍研究现状.第二章,设计了一个博弈模型来研究连通控制集问题,证明了从任意一个非平凡的初始状态出发,在博弈者只考虑自身利益的情况下,博弈结果会在O（n）迭代步数内收敛到一个纳什均衡状态.同时证明了任意一个纳什均衡状态对应着一个极小连通控制集.第三章,基于博弈论的方法给出了一个安全控制集问题的完全分布式的局部算法,算法能在O（n）迭代步内输出一个极小安全控制集,同时具有帕累托最优性.数值模拟的结果展示了该算法的优越性.第四章对研究方法与研究结果进行讨论与总结.
其他文献
深度神经网络已成为众多机器学习任务中最先进的模型.然而,对网络架构设计的一般理论指导仍然缺乏.本文的主要内容就是在文献[1]和文献[20]的基础上进一步讨论深度神经网络与动力系统的关系,尤其是与哈密顿系统的关系,进而提出一类新的网络架构.本论文由四章构成:第一章,介绍本文的研究背景,以及内容安排.首先介绍深度残差网络与动力系统的关系,由此导出由动力系统以及相应的离散格式产生深度残差网络的思想.基于
近年来,文本到图像的生成任务在计算机视觉与自然语言领域一直是一个重要的研究热点,该任务的目的是将一句描述性语言文本作为输入,然后输出一张与文本内容一致的图像.随着深度学习中生成对抗网络的出现,文本生成图像这项任务得到了迅速发展,但是由于使用的生成对抗网络在模型训练中会出现梯度消失、模式坍塌等训练不稳定的情况,并且可能造成最终的生成结果与文本语义不一致或者生成内容不具多样性等问题,因此本文在前人的研
图的anti-Ramsey数的研究是图论研究的前沿课题之一,与极值图论、Ramsey 理论等图论核心问题联系十分密切.与经典的Ramsey理论不同的是,图的anti-Ramsey数的研究对象是彩虹图,这一问题也被看作是Ramsey理论的推广之一,并且逐渐成为图论研究的热点课题,其思想日益渗透到代数、组合学、数论等多个分支领域.Anti-Ramsey数是指对于给定的图G和H,使得边染色图G中不存在任
离散非线性系统观测器设计一直以来都吸引着研究者的兴趣,特别地,函数观测器的维数可能比状态观测器的维数更低,因此对离散非线性系统函数观测器的研究具有重要实践意义.本文主要研究一类满足递增二次约束的离散非线性系统的函数观测器设计.具体研究内容如下:首先,研究满足递增二次约束离散非线性系统函数观测器设计.应用Lyapunov稳定性理论,由秩条件和求解线性矩阵不等式,获得函数观测器观测误差指数收敛的充分条
图G的一个正常k-全染色是指一个映射φ:V（G）∪E（G）→{1,2,…,k},使得V（G）∪E（G）中任意两个相邻的或相关联的元素染不同颜色.G的全色数是使G有一个正常k-全染色的最小整数k,用χ"对（G）表示.令Cφ[v]＝{φ（v）}∪{φ（uv）|uv∈E（G）}表示点v的颜色与v的关联边的颜色组成的集合.如果在图G的一个正常k-全染色φ下,对任意一条边uv∈E（G）有|Cφ[u]\Cφ[
图上的随机游走是图论研究的热点课题之一,在计算机科学、信息科学、电网络等多个分支中有着重要的应用.Hitting time是图上随机游走的重要问题之一,hitting time及其相关的不变量已经被学者广泛研究.Doyle等人的专著对电网络与图上随机游走之间的关系做了全面的阐述.Klein等人提出了有效电阻的概念,并建立了有效电阻和随机游走之间的关联.从图的结构出发,有学者研究了树和单圈图的hit
本文主要对几类非局部椭圆方程（组）正解的存在性以及性质进行研究,一共分为五章.在第一章,我们介绍几类问题的研究背景以及得到的主要结果.在第二章,我们研究带Hartree型非局部项的积分方程组正解的性质,其中N ≥ 3,p ≥ 1且0<μ,τ
随着科学技术的不断发展,网络的应用越来越广泛.如人们应用传感器网络完成监控城市交通、监视入侵者、维护设备等任务,而这类任务可以模型化为最小加权顶点覆盖问题及其相关变形.最小加权顶点覆盖问题是经典的组合优化问题,已有好的集中式近似算法.但在高度动态、大规模的网络背景下,人们更倾向于自组织的分布式算法.本论文应用博弈论研究最小加权（连通）顶点覆盖问题,并设计分布式算法.研究的关键在于对异质权重的博弈处
本文共分两部分.第一部分主要研究了p次微分分次Poisson代数的平凡扩张,证明了扩张代数也是p次微分分次Poisson代数.第二部分引入了 p次微分分次Poisson子代数,p次微分分次Poisson理想,p次微分分次Poisson子模,p次微分分次Poisson代数的上同调等,并探究了其相关性质.
汽车的诞生改善了人类的交通运输方式,与此同时带来的能源与环境问题同样不容小觑。未来汽车行业将向着低能耗、清洁环保的新能源汽车方向发展。CVT混合动力汽车(Hybrid Electric Vehicle,HEV)将纯电动汽车和传统燃油汽车的优点结合起来,可实现更高的燃油经济性和更低的污染排放性,以及传动系与发动机工况的最好匹配,因此受到了越来越多的重视。混合动力汽车只有通过有效的能量管理策略(Ene