【摘 要】
：
最小顶点覆盖问题是一类经典的组合优化问题,无论是在理论上的优化,还是实际中的应用,都有着广泛的研究,如计算复杂度、道路监控、目标追踪等,目前已经提出了各种各样的算法来解决这个问题.该问题有两个变形.考虑实际中网络节点的异质性,就引申出最小加权顶点覆盖问题.在其博弈优化中,之前大多数工作都假设每个玩家完全理性,但实际上并非如此,由权重不同引起的风险或不确定因素可能会使得玩家偏离理性原则.除此之外,基
论文部分内容阅读
最小顶点覆盖问题是一类经典的组合优化问题,无论是在理论上的优化,还是实际中的应用,都有着广泛的研究,如计算复杂度、道路监控、目标追踪等,目前已经提出了各种各样的算法来解决这个问题.该问题有两个变形.考虑实际中网络节点的异质性,就引申出最小加权顶点覆盖问题.在其博弈优化中,之前大多数工作都假设每个玩家完全理性,但实际上并非如此,由权重不同引起的风险或不确定因素可能会使得玩家偏离理性原则.除此之外,基于实际中人们对所选点集信息共享的需求,最小连通顶点覆盖问题受到越来越多的关注,由于该问题比较新颖,故相关工作较少并且收敛时间较长.因此本文主要借助博弈论来研究最小顶点覆盖问题和最小连通顶点覆盖问题的优化,以求得更加贴近实际需求的解.相比于最小顶点覆盖问题,最小加权顶点覆盖问题的优化目标除了保证所选点集是一个顶点覆盖,更要求这个点集的权重尽可能小,故该问题更具有一般性.由于最小加权顶点覆盖问题在一般图上是NP-困难的,本文并不期望能够设计精确算法,因此希望能利用博弈论在较短时间内得到近似解.同时在模型中,考虑到权重因素所引起的不确定性会导致博弈者不是完全理性的,因而本文引入了前景理论来研究博弈者的非理性行为,并且讨论了不同理性参数对算法收敛速度,解的权重大小,解与惩罚参数关系的影响,并做了严格的仿真实验.最小连通顶点覆盖问题就是要找到一个包含顶点数最少的连通点覆盖集.在图中,称点集(3是连通的点覆盖集合如果(3是一个顶点覆盖集并且其导出子图[(3]是连通的.为此本文设计了收益函数和局部更新最佳回应算法,理论分析得出从任一非平凡的初始策略开始博弈,能够在线性时间内得到一个非平凡的纳什均衡,并证明这样的纳什均衡就是极小连通点覆盖.同时将此算法与贪婪算法在解的大小和收敛时间等方面进行了比较,得出该博弈算法优于贪婪算法.
其他文献
文章针对远程放射性测量无线传输系统运行过程中数据传输不稳定的问题，从程序设计出发，结合了常见的按时间读取、按字节读取的上位机串行通信数据接收逻辑，基于串口Serial Port类和计时器Timers类，提出并应用了一种数据接收逻辑，以此提升传输系统稳定性。该接收逻辑综合了按字节读取等待时间弹性大的优点以及按时间读取定时重传的优点，增加掉线重连、超时检测的功能。实验表明采用此数据接收逻辑的测量传输系
聚氯乙烯是世界上产量最大的通用塑料,在诸多领域中广泛应用。乙炔-二氯乙烷耦合法是将煤炭与石油资源共同利用来制备聚氯乙烯单体的一种新工艺。相对于研究较成熟的氢氯化反应,目前耦合反应的研究较少,主要体现在所开发的催化剂活性与氢氯化体系相比仍有数量级的差距,且反应机制存在争议。争议的焦点在于:二氯乙烷首先吸附于催化剂表面发生裂解反应产生氯化氢,再吸附乙炔发生氢氯化反应,抑或是乙炔与二氯乙烷同时在催化剂活
随着日光诱导叶绿素荧光（SIF）遥感的兴起,SIF被广泛应用到植被生产力估算、环境胁迫监测、生态系统碳汇估算和生态系统模型参数模拟等方面的研究中,相比传统的植被指数具有一定的优势。叶绿素荧光与植被光合作用过程密切相关,被认为是光合作用研究的无损探针。越来越多的研究发现SIF与总初级生产力（GPP）在站点尺度、区域尺度下在统计学上为线性相关关系,但是受到物种差异和环境胁迫等因素的影响。目前随着全球环
随着电子行业的不断发展,金属元器件的体积越来越小,逐步趋于功能化、精细化。但在使用过程中,潮湿、恶劣的空气环境如腐蚀性气体、海盐雾、粉尘、霉菌以及人体汗液等因素都会对金属元器件造成不同程度的腐蚀,因此开发高防护性涂层具有重要的应用价值。本文使用二维材料氮化硼和功能性材料苯胺四聚体分别和含氟单体共聚反应,得到了高性能含氟聚合物涂层。主要研究内容如下:1.首先采用球磨法将氮化硼（BN）粉末剥离成片状,
随着工业的快速发展,大量有机废水未经处理排放到江河当中,对生物健康和生态环境造成极大威胁。现今,科学家们正努力攻破染料废水的处理这一难题,已有报道利用自然界中光能激励的光催化等方法来实现对染料废水的处理。然而,光催化对暗环境反应不灵敏、光吸收范围有限、电子空穴复合严重等缺点在一定程度上阻碍了光催化的实际应用。因此,开发一种新兴技术已迫在眉睫。本论文利用水热合成法制备的铌酸钾（KNbO3）纳米材料,
芳香族硝基化合物（NACs）是大气中的重要有机污染物。虽然NACs在大气中的含量比芳香族化合物低一到两个数量级,但其对人体的危害却比芳香族化合物高得多。一旦受光激发,NACs会通过超快的系间窜越（ISC）过程到达最低三重激发态（T1）或者通过超快的内转换（IC）过程到达基态（S0）,且这些激发态弛豫途径存在明显的竞争关系。由于NACs的最低三重激发态（T1）往往具有纳秒到微秒尺度的激发态寿命,因此
未来产业是未来前景广阔，可能对科技、经济、社会产生深远影响，具有突破性、颠覆性意义，目前在技术、市场、模式上尚未具型的前沿性产业。未来产业具有颠覆性、混沌性、稚幼性和风险性。未来产业的成长可以归纳为风动、风口、风投、风向、风控的“五风”模式。我国促进未来产业发展要做好以下“三前”工作：未来技术趋势的前瞻预见、未来产业领域的前期布局和未来产业风险的前置治理。
为保证智能配网安全运行，设计基于规则的调度命令票语义合规性校验模型。设置待处理文本集与服务器集，使用笛卡尔积运算得到调度数据集合，初始化蚁群优化算法中启发函数与信息素函数，从迭代结果内选择最优解实现调度命令票文本数据采集；将欧式距离作为相似度权衡准则，经过若干次聚类检测，统计聚类平均值方差总和，把方差值不变时的对应值作为语义合规性文本分类标准；利用轻量式设计，自定义各板块规则，利用数据格式变换、重
演讲作为一种具有强感染力、说服力和鼓动力的信息传播方式非常值得关注,而句法特征对可读性和可接受度有较大影响,因此研究英语演讲的句法特征具有重要意义。句法复杂度指的是语言产出中句法结构的多样性和复杂性,通常从单位长度、从属和并列结构、特定短语等维度的指标对其进行评价,而这些指标可以反映出口语及书面语篇的句法使用特征。因此,本研究从句法复杂度的角度出发,对中美大学生英语演讲的整体及导入、主体和结论各部
本文首先在Hom-Hopf代数上引入了 Hom-交叉余积的定义,其次给出了 Hom-交叉余积构成Hom-余代数的充分必要条件以及Hom-交叉余积和Hom-冲积形成Hom-双代数的充分必要条件.最后讨论了 Hom-交叉余积的对偶结构.