【摘 要】
：
本文主要研究混合图上最小-最大圈覆盖问题。依据不同的覆盖对象,具体分为两种情形:一是覆盖对象仅为弧的情形,二是覆盖对象既包含弧又包含边的情形。该类问题是计算机科学和运筹学中一个重要的组合优化问题,它和它的变形在诸如快递配送、垃圾回收、积雪清理等相关领域具有广泛应用。因此,对其进行科学研究具有重要的理论和实际价值。本文主要从近似算法的角度对其开展研究,针对两种情形,分别给出了较好的近似算法,具体内容
论文部分内容阅读
本文主要研究混合图上最小-最大圈覆盖问题。依据不同的覆盖对象,具体分为两种情形:一是覆盖对象仅为弧的情形,二是覆盖对象既包含弧又包含边的情形。该类问题是计算机科学和运筹学中一个重要的组合优化问题,它和它的变形在诸如快递配送、垃圾回收、积雪清理等相关领域具有广泛应用。因此,对其进行科学研究具有重要的理论和实际价值。本文主要从近似算法的角度对其开展研究,针对两种情形,分别给出了较好的近似算法,具体内容如下:本文研究的第一个问题是覆盖对象仅为弧的最小-最大圈覆盖问题。该问题可以描述为:给定一个混合加权图G=（V,E,A）,这里V表示顶点集,E表示边集,A表示弧集;E中的每条边和A中的每条弧分别关联一个权重,每个权重为正整数且权重函数满足三角不等式;给定一个正整数k,问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧;问题的目标是极小化权重最大环游的权重。针对该问题,我们给出一个近似比为37/5的近似算法。算法的基本思想如下:首先,给出问题实例最优值OPT的一个猜测值λo然后,删除图G中权重大于λ/2的边,得到若干连通分支;针对每个连通分支,依赖图G的结构,设计两个能够覆盖落在该分支的所有弧的环游;选择上述两个环游中权重较小的环游,应用环游撕裂算法,将该环游撕裂成若干条路;连接每条路的两个端点,得到若干个子环游,这些子环游能够覆盖落在该分支的所有弧;计算所有分支的子环游总数目,若其小于等于k,则意味着OPT≤λ,此时输出这些环游,否则意味着OPT>λ,此时返回失败。最后,根据三角不等式易知,2maxa∈A w（a）≤OPT≤2w（G）;故在区间[2maxa∈A w（a）,2w（G）]内应用二分搜索,找到一个最小猜测值λ*,使得此时可以输出目标值不超过3 7λ*/5的可行解;按λ*的定义知,OPT>λ*-1,即λ*≤OPT。综合上述,我们可以得到一个近似比为37/5的近似算法。本文研究的第二个问题是覆盖对象既包含弧又包含边的最小-最大圈覆盖问题。该问题是第一个问题的推广,其主要差异在问题的输入和问题的要求上。该问题的输入增加了弧集A的一个子集AR和边集E的一个子集ER,问题的要求是寻找k个环游,使得这些环游能够覆盖AR中的所有弧和ER中的所有边。问题的目标仍是极小化权重最大环游的权重。除了在每个连通分支依赖图G的结构设计三个环游外,利用和第一个问题类似的思想,我们给出了一个近似比为min{33/5,12+21α/2+3α}的近似算法,这里α>0是一个与输入图G有关的常数。
其他文献
评分预测是推荐系统中的一个核心问题,用于量化用户对不同商品的偏好。由于训练数据中评级分布的不平衡,现有的推荐模型通常会产生有偏差的预测。因此,它们在预测长尾样本的性能通常不能令人满意。针对上述问题,本文提出两个解决方案。第一个模型命名为TADO（Time-v arying Attention with Dual-Optimizer Model）。此方法在第三章进行详细介绍。TADO专注于解决基于评
随着人工智能、物联网以及5G服务的到来,以数据知识为基础的企业,才能在全球市场上保持竞争优势,现如今越来越多的企业建立了不同的信息系统,这些信息系统数据库中存在大量的事件日志,然而,管理者很难从数量庞大的事件日志中提取有价值的信息,并且为了在竞争快速发展的世界中,更好的支持业务流程这一需求日益突显,通过对业务流程事件日志进行分析与预测,可以为企业监控提供决策和支持。通过预测不同的业务目标,不断的完
在大面积水产养殖中,水质关键因子监测智能化与信息化日渐普及,国内外相关领域研究不断推进并取得了长足的进展。为方便水产养殖人员对水产品养殖水体实时的、高质量的、准确的把握,本课题在前人的基础上,构建了对水质因素数据实时显示的远程监测系统。针对水产水质监测领域所存在的显著问题,本课题的研究内容如下:针对自适应传感器接口,根据IEEE1451.2智能传感器接口标准,设计了数据采集单元的多接口板。便于根据
台风是最严重的自然灾害之一,北太平洋西部具有世界上最频繁的热带气旋（台风）活动,在过去几十年中,台风造成的生命威胁以及经济损失已成为严重影响沿海地区人民正常生活的因素。因此,如何准确预测台风路径,辅助气象监测部门对台风进行准确预报,已成为当下热门的研究课题。然而由于台风轨迹有诸多影响因素,导致难以进行特征因子的提取,且需要的计算成本高。传统方法需要结合众多相关领域的先验知识,在耗时耗力的同时,预测
解决计算机视觉问题时,分割是最主要的任务。尤其在自动驾驶、室内导航以及医学造影等领域,语义分割技术的影响不容小觑。近年来,基于深度学习方法的图像语义分割算法已经取得了优异的成绩,尤其是基于卷积神经网络的方法,例如FCN、PSPNet。较传统基于图论的分割方法相比,基于卷积神经网络的分割方法可以将更好的将图像进行全局特征分析,并且提取出各像素点之间的隐藏关联信息。凭借此优势,基于卷积神经网络的图像分
现如今物联网的发展速度已经超出了人们的想象,万物互联已经是大势所趋,人们身边已经充斥着各种各样的物联网应用成果,家中有智能家居,农业有农业物联网,工业有工业物联网,汽车有车联网,学校中有教育信息化。针对高校而言,物联网的发展给学校带来了新的提升教育信息化水平、减少能源浪费的机会。论文以此为背景,设计了一个基于物联网的云数据采集分析控制系统,通过在教室安装智能设备（如日光灯、空调、投影等）,以及多种
目前国内陆基工厂化养殖模式得到大力推广和发展,智能机械化设备也在养殖任务中发挥重要的作用。水产养殖中,鱼粪、残饵及微生物菌群等物质会附着在池底和池壁上,影响水质导致病害发生,需要定期的予以清除。传统清洗方式需要人工手持板刷或者拖着水枪机四周环绕清刷,工作繁琐重复且池底易滑,也不符合节能环保的理念。本文的研究对象—鱼池清刷机器人主要用于养殖车间的鱼池池底污染物清理,解决了人工清洗存在的问题,清洁效率
在世界各国进军海洋的进程中,水下作业装备扮演着极其重要的角色,水下机器人作为目前普遍使用的海洋探测作业装置,在民用和军事两大领域的相关海洋活动中,发挥着不可替代的关键作用。水下机器人控制技术作为控制理论在水下作业工程装备方面的具体应用,对水下机器人尤其是自主水下机器人的发展具有重大影响和深远意义。自主水下机器人控制技术的研究方向主要涵盖构建控制系统体系结构、动力学建模与模型的合理简化及相关参数的优
在计算机视觉领域,关于深度学习的研究逐渐增多,其发展也日新月异,特别是在人的面部包括生物特征和表情识别、头部姿态估计、活体检测等领域的应用广泛。日前,在社会发展的需求和促进下,各式各样的计算机技术在不断地被发掘,其中,计算机视觉中的头部姿态估计研究已经成为该领域的一大热点。国内外众多的科学研究院、大学实验室、公司研究机构等陆续都在开展对头部姿态估计的研究,将深度学习应用于头部姿态估计算法,旨在提高
船舶在航行过程中船体表面会附着贝类和藤壶等海生物,船体表面附着物的存在会对航行产生不利的影响。经过研究表明,海生物附着在船体表面会增加船体表面粗糙度,增大船舶航行阻力,增加了运输时间和运输油耗,造成经济损失。目前,潜水员用清洗枪对水下船体表面进行清洗是主要的方式。潜水作业劳动强度大,安全性低,清洗成本高,效率低且受天气影响大。为了解决上述问题,可代替人工的清洗爬壁机器人成为了热门研究方向。清洗爬壁