【摘 要】
：
树覆盖问题是一个基本的组合优化问题,在电话机房、网络机房及发电厂等规划方面有着重大的研究价值。树覆盖问题主要包括四类,包括最小最大树覆盖问题、有根的最小最大树覆盖问题、有界树覆盖问题和有根的有界树覆盖问题。对树覆盖问题的研究,不只是对问题本身关联的实际有促进作用,对其他相似的问题而言也有重要的研究价值,例如圈覆盖问题、车辆寻路问题、路径覆盖问题和集合覆盖问题等。本文中主要研究的树覆盖问题是最小最大
论文部分内容阅读
树覆盖问题是一个基本的组合优化问题,在电话机房、网络机房及发电厂等规划方面有着重大的研究价值。树覆盖问题主要包括四类,包括最小最大树覆盖问题、有根的最小最大树覆盖问题、有界树覆盖问题和有根的有界树覆盖问题。对树覆盖问题的研究,不只是对问题本身关联的实际有促进作用,对其他相似的问题而言也有重要的研究价值,例如圈覆盖问题、车辆寻路问题、路径覆盖问题和集合覆盖问题等。本文中主要研究的树覆盖问题是最小最大树覆盖问题和有界树覆盖问题。给一个图和正整数k,最小最大树覆盖问题要求用最多k棵树覆盖图上所有的顶点,且费用最大的树的费用最小。给出一个图和边界限制B,有界树覆盖问题要求用尽可能少的树覆盖住图上所有顶点,且解中每一棵树的权重值都不能超过B。当前对这两个问题的研究工作主要集中在近似算法上,其中,最小最大树覆盖问题的最好近似比为3,有界树覆盖问题的最好近似比为2.5。至于精确算法还没有见到已知的结果。文章对最小最大树覆盖问题和有界树覆盖问题的精确算法和启发式算法进行了研究。关于最小最大树覆盖问题,利用该问题与集合覆盖问题的联系,使用动态规划方法,为其设计了一种精确算法,本文证明该精确算法的时间复杂度为O*（3n）,这是关于最小最大树覆盖问题的第一个非平凡精确求解算法。使用类似的方法,本文为有界树覆盖问题设计了第一个非平凡的精确求解算法,证明该算法的时间复杂度为O*（3n）。此外,通过使用容斥原理和动态规划技术,本文还对有界树覆盖问题得到了一个中间解,这是在时间复杂度O*（2n）的情况下得到的。中间解的产生或许会为其他精确算法和启发式算法以启示。另外,本文还对最小最大树覆盖问题的启发式算法进行了研究,为最小最大树覆盖问题设计了六种启发式算法,其中有四种是基于最小生成树设计的,还有两种是基于全局分割的贪心算法。最后为其设计了测试样例,通过改变参数的大小进行实验,发现在不同场景下不同的启发式算法有其不同的效用,得到的解也不尽相同。实验结果最优秀的一种启发式算法是基于全局分割的多次平均算法,此算法在顶点个数n、边权重w和分割数目k的一般取值上有着良好的效果,比其他的五种启发式算法都要优秀,只有当顶点数目n和分割数目k特别大时,此算法才会耗费较多的时间。
其他文献
超像素分割作为重要的图像预处理操作在图像处理和图形学中有着广泛的应用,例如图像分割、显著性检测、目标轮廓提取、图像压缩等。边界的贴合性和形状的规整性是评价算法的主要指标,这两个评价指标很难同时兼顾,大多数分割方法更加重视边界分割准确性而忽视了超像素的紧凑性。传统的基于像素点的分割方法需要对每一个像素点进行分析和聚类,所以生成的每一个区域的边界贴合性很好。因为其边界是锯齿状的,这些超像素方法在一些视
深度神经网络的高效推断过程通常需要高性能计算设备,但在资源受限的移动端或嵌入式实时系统中难以推广。神经网络剪枝技术通过减少网络连接的数量,能降低网络的复杂度,推动神经网络在计算资源受限条件下的应用。深度网络中冗余神经元剪枝算法取得了较大研究进展,但存在两个关键问题:1、目前的剪枝算法缺乏理论分析方法,无法对预先设置的剪枝比例给出合理的解释;2、基于全局剪枝比例的权值或神经元修剪可能会导致神经网络中
可穿戴外肢体机器人通过给人体安装额外独立的机械肢体,为穿戴者提供支撑负载等辅助功能,提高单人作业能力及作业范围。具有四个外肢体的多肢体机器人比单肢体和双肢体机器人的稳定性更好,可实现的任务模式更多,作业能力和作业效率也会有极大的提高,可广泛应用于工业、建筑、医疗、军事、航天等领域,具有极其广阔的发展前景。对多肢体机器人肢体和背板的建模及运动控制方法等方面进行研究分析可以促进多肢体机器人的实用化,具
随着深度学习、大数据等应用对计算机性能的要求逐渐提高,传统的基于CPU的架构已难以满足这些应用的计算需求,将CPU与作为加速器的GPU结合构成的异构多处理器片上系统（Heterogeneous Multiprocessor Systems-on-Chip,HMPSoC）成为主流趋势,GPU除擅长处理3D图像渲染外,还能进行大规模通用并行计算。在CPU-GPU异构架构中,高速缓存（Cache）是缩小
随着数据技术的发展,个性化推荐算法逐渐成为研究重点。在个性化推荐算法中,协同过滤方法使用最多。近年来,在机器学习的发展中,传统的协同过滤方法逐步与新技术结合,最近的一些工作开始应用深度学习方法,但主要是针对辅助信息进行建模。当要建模关键信息时,依旧使用矩阵分解的方法,用户和项目的隐含特征仍然用内积表示。因此,在嵌入过程中,对于互动中隐含的协同信号无法获得有效编码。在协同过滤中,用户和项目的嵌入表示
葛根是江西道地药材之一，在江西具有悠久的种植历史。作为药食两用价值极高的中药植物，葛根在江西的产业规模已初步形成，但发展却有所停滞。此文通过总结分析江西葛根的使用价值和产业现状，针对江西葛根产业目前发展存在的主要问题提出相关建议，旨在通过葛根发展战略制定、资源库构建、技术提升、相关保健产品重点研发、立体化生态产业建立等多种手段，促进葛产业的健康化、系统化及规模化发展。
随着信息技术的发展以及网络社交平台的普及,互联网上出现了海量的图像数据,对这些图像数据的快速检索是互联网相关产业的核心任务之一。哈希学习是图像快速检索的重要方法,因其良好的性能,近年来引起了研究者的广泛关注。基于哈希学习的图像检索方法通过将图像数据映射为具有固定长度的离散二进制码,可以实现高效率、低存储的图像近似近邻检索。但是,随着图像采集设备软硬件技术的发展,海量的图像数据在满足用户需求的同时,
随着科学与经济的发展以及“工业4.0”概念的提出,制造业开始纷纷向着“智能化、智慧化”的方向发展。基于AGV的“货到人”拣选系统是当前物流行业的主流选择,该系统中以自动导引小车（Automated Guided Vehicle,AGV）为搬运工具。本文所研究的多仓位机器人存取系统（Muti-position Robotic Storage and Retrieval System,MP-RSRS）
戒毒所作为一个人员聚集的场所,需要更加方便快捷的监管方式,从而提高监管人员的监管效率。同时,消防安全知识和消防技能是如今社会每个公民都必备的一项重要内容,因此,除了常规的监管操作,戒毒所也需要监管消防安全问题。随着虚拟现实技术的发展,其拥有的沉浸感较强、不受实际场地限制、可多次重复的特点,受到了人们的广泛欢迎,进而应用于各行各业。使用虚拟现实技术对戒毒所进行监管和消防演练比起传统方式具有成本低、可
复杂网络的链路预测一直是复杂网络领域一个非常重要的研究方向。链路预测既有着对未知但已存在的边的预测,也有着对未来的可能存在的边的预测。将复杂网络从静态网络扩展到动态网络可以有效区分未知和未来的边预测,而链路的权重预测也将链路预测的链路存在有无扩展到链路的正负以及可能形成的链路的值。在交易系统中,尤其是像使用比特币进行交易的这样匿名性强,欺诈风险较大的交易系统中,提前对交易对方的可靠性有一个大致的估