【摘 要】
:
许多组合最优问题都可以抽象为计算图的生成树问题。最小标记生成树就是其中之一,它的目标是给出一个边上带有颜色的图,计算使用颜色种类最少的生成树。这个问题在通信网络领
论文部分内容阅读
许多组合最优问题都可以抽象为计算图的生成树问题。最小标记生成树就是其中之一,它的目标是给出一个边上带有颜色的图,计算使用颜色种类最少的生成树。这个问题在通信网络领域有广泛应用,其中颜色代表了通信使用材料,这些材料可能是由竞争关系的厂商提供,如果能找到使用材料种类最少的通信网络的生成树,就可以减少构造成本和网络复杂性。最小标记生成树问题最早由Chang R.S.和Leu S.J.在1997年提出。它是NP-hard问题,而且不存在近似度为常数的近似算法,除非P=NP。本文使用了另一种研究方向,研究一类满足特殊性质的图,也就是树宽为常数的一类图,在这类图上得到了时间复杂度良好的算法。另外,在一般图上,本文基于MVCA贪婪算法提出了基于一般图的几个重要的启发式算法,包括轴方法算法、变邻域搜索算法,并给出了实验结果,得出了一些有用的结论,为未来的进一步研究提供了借鉴,指出了方向。此外,我们对最小生成树的变体问题,多重标记最小标记生成树做了初步研究,提出了启发式算法并和MVCA做了对比,下一步的研究方向可能从理论上给出严格的证明,并且挖掘更多高效的启发式算法。
其他文献
动态类型语言已经被广泛地应用于实践应用之中。Python是一种典型的动态类型语言,具有语法简单,开发迅速,使用灵活的优势。但是由于Python语言不具备类型声明语法,也没有提供静态
近几年来,随着黑客技术特别是Rootkit技术的发展,攻击者们已经把触角伸入到了操作系统的内核。操作系统的内核代码面临着严重的威胁。目前,保护操作系统安全的办法有防火墙、
21世纪的人类社会是信息化的社会,数字化后的信息,尤其是视频和音频信息具有数据海量性,它给存储和传输造成较大的困难。数字视频内在的高带宽特性限制了多媒体业务的扩展,故
生物代谢一直是生命科学研究的基础领域之一,对生物代谢网络中众多反应的途径、作用、原理等进行透彻研究,对生物学、医学甚至是制药学等等各种领域都有着重要的意义。生物代
20世纪80年代,模式分析领域经历了一场“非线性革命”:为摆脱计算和统计上的线性局限的算法,支持向量机(Support Vector Machine,SVM)被第一次作为核方法提了出来。随后,基于
随着电信业务迅速发展,传统电信网逐渐显现出其不适应性,不能满足电信业务发展的需要。因此,传统的电信网正与互联网新技术相融合,演化为下一代电信网。下一代电信网的发展是
本体搜索引擎是本体选择与重用过程中的重要工具,在语义网快速发展的今天,随着本体文档的数量级不断攀升,本体搜索引擎的研究得到了越来越多的关注并发挥了日益重要的作用。近几
图像分割在计算机视觉领域应用广泛,是图像分析与图像处理中研究的重点和难点之一。生活中常见的图像为彩色图像,与灰度图像相比,彩色图像包含有更丰富的颜色和纹理信息,这些信息
计算机辅助的三维颅面复原采用计算机图形学技术从颅骨数据样本复原人脸面貌,可以应用于刑侦、考古、医学等领域。本文研究内容作为计算机辅助的三维颅面复原项目的一部分,研