【摘 要】
：
本文首先研究了{1,2}-边赋权完全图上的最小最大k-路径覆盖与最小最大k-圈覆盖问题,给出了这两个问题的NP-困难性证明,并分别设计了近似算法。其次,研究了2-连通图上的均衡2-划分问题,设计了一个改进近似算法。论文的各个章节具体内容如下。第一章介绍了图论、计算复杂性和近似算法的一些基础知识,并阐述了{1,2}-边赋权完全图上最小最大k-路径（圈）覆盖问题和连通图上的均衡k-连通划分问题的研究现
论文部分内容阅读
本文首先研究了{1,2}-边赋权完全图上的最小最大k-路径覆盖与最小最大k-圈覆盖问题,给出了这两个问题的NP-困难性证明,并分别设计了近似算法。其次,研究了2-连通图上的均衡2-划分问题,设计了一个改进近似算法。论文的各个章节具体内容如下。第一章介绍了图论、计算复杂性和近似算法的一些基础知识,并阐述了{1,2}-边赋权完全图上最小最大k-路径（圈）覆盖问题和连通图上的均衡k-连通划分问题的研究现状。第二章研究了{1,2}-边赋权完全图上最小最大k-路径覆盖与k-圈覆盖问题。利用经典NP-哈密顿路问题和哈密顿圈问题进行多项式时间归约,证明了两个问题均是NP-难的。对最小最大2-路径覆盖问题,基于旅行售货商问题的一个近似算法,提出了一个近似比不超过11/7的算法,并给出了一个算例;然后将此算法推广到了一般最小最大k-路径覆盖问题,证明了算法的近似比不超过24/7-2/k。对于最小最大k-圈覆盖问题,基于上述最小最大k-路径覆盖问题算法,得到了一个近似比不超过19/7-1/k的算法。第三章研究了2-连通图上的均衡2-连通划分问题,基于局部搜索技术,提出了一个近似比不超过6/5的算法。第四章对全文的内容进行了总结,并对未来的研究方向给出了相关分析和展望。
其他文献
艺术肖像画生成是指让计算机根据给定的人脸图像生成风格化的画像,其在公共安全与数字娱乐领域具有独特的应用价值。近年来,研究人员提出了各种基于生成对抗网络的艺术肖像画生成方法,并取得了令人瞩目的进展。但是,现有的方法在艺术肖像画的细节纹理生成、几何结构保留等方面仍然面临着很大的挑战。为此,本文提出了一种基于人脸语义正则化约束的肖像画生成算法,并将其应用于素描和钢笔画。然后,本文提出了一种基于非对称循环
随着信息技术的发展,人类社会进入大数据时代。知识图谱能连接相关数据并建立关系网络,为影视、医疗等行业提供有力支持。关系分类与关系抽取是构建知识图谱的关键技术,深入研究具有重要意义。关系分类旨在实体已知的情况下,预测实体之间的关系类别。关系抽取旨在实体未知的情况下,抽取文本中的关系三元组。句法分析捕获词汇间的依存关系,包含句法结构与句法依赖。使用句法分析技术能显著提升关系分类与关系抽取任务的效果。本
随着物联网产业的逐渐成熟和5G技术的问世,海量数据从日常生活的各个领域涌现,作为当前主要计算范式的云计算已经逐渐无法负担急剧增长的数据流量。边缘计算技术的出现为解决日益增长的海量数据带来了希望。作为一种分布式计算架构,边缘计算通过将服务器部署在用户端来提供计算能力,从而可以减少骨干网络拥塞,降低计算响应延迟。然而,城市人口密度分布不均,不同区域人口数量差别较大,导致城市基站工作负载极度不平衡,用户
在模糊控制中,区间二型模糊系统不仅具有解决一型模糊系统隶属函数不确定问题的能力,且具有比二型模糊系统计算复杂度更低的优良性质。非齐次Markovian切换系统是一类以非齐次Markovian过程为模型的随机切换系统,对结构随机突变的系统进行建模时具有很大的优势。因此,本文以区间二型模糊模型为框架,研究非齐次Markovian切换系统的H∞控制问题,本文研究内容及创新点如下:一、研究一类不确定非齐次
船舶自动识别系统（AIS）是一种海上辅助导航系统,该系统能够自主连续的在甚高频信道上广播信息,自动交换船舶静态信息和动态信息,实现船与船、船与基站之间实时通信,对可能发生的事故进行提前预警,有效的避免船舶碰撞,保障航行安全,推动了海上交通运输的发展。目前国内AIS设备厂商较少且大部分实现方案都是采用国外AIS信号处理专用芯片,核心技术受制于人。因此,深入研究AIS通信协议,完成AIS控制子系统的设
在深度学习中,面对不断增加的数据样本量与昂贵的人工标注成本,对比学习作为自监督学习的一种重要方法,可以脱离标签进行基于样本本身的训练。相较于传统的有监督学习,通过对比学习训练的模型可获得理解更丰富的高层次特征的能力,为下游任务提供更优秀的预训练模型。对比学习通常会采用实例识别任务（instance discrimination task）作为训练模型的借口任务（pretext task）。然而,实
图像分析在生产生活中有着广泛的应用,传统类别的图像分类已经取得了较大的突破。与传统的图像分析相比,细粒度图像识别是专门针对某一类别的细分类进行识别的课题,比如自然保护区的生物类识别、无人超市的商品识别等。由于细粒度图像数据集难以收集,并且细粒度图像本身存在“类内差异大,类间差异小”的问题,其分类识别存在一定挑战性。细粒度图像分类旨在学习一种鲁棒的图像表示,对相似种类的细微差异进行建模。该领域的现有
计算机辅助工程是用计算机辅助求解复杂工程问题的数值分析方法,在节省产品开发时间和成本、及早发现产品缺陷、避免事故发生等优化产品结构和性能方面发挥着重要作用。如何高效地实现高精度物理仿真以及无缝融合设计与分析过程,是计算机辅助设计与工程、计算机图形学、计算力学等多个学科交叉领域富有挑战性的研究课题。同时,如何更好更快地求解偏微分方程的边值问题是数值仿真分析亟待解决的难题之一。在求解偏微分方程时,通常
随着云计算、大数据、物联网等技术的发展,互联网中层出不穷的应用引发了数据规模的爆炸式增长。大数据中蕴含着丰富的科研价值与商业价值,却也给用户带来了严重的信息过载问题。推荐系统作为解决信息过载的有效方法,在诸如社交网络、电子商务、流媒体推荐等领域已经有了许多成功应用。在个性化推荐领域,用户的行为非常复杂且稀疏。现有的工作大多采用基于深度学习的序列模型建模用户的行为。然而现有的方法仍然存在以下几个问题
本文考虑用标准差（量子方差的平方根）来量化量子可观测量处于随机哈尔（Haar）分布纯态的不确定性.针对可观测量A在纯态上期望值的概率密度函数（PDF）的计算方法,计算出随机量子可观测量A的期望值和A2的期望值的联合PDF,以及在C3和C4上期望值和标准差的联合PDF的解析表达式,画出了联合PDF的支集的具体图像,在此基础上,进一步计算得到其标准差的PDF的表达式和具体图像.这为更详细研究不确定性关