计算问题(Computational Problem)是一类可以借助计算机来求解的数学问题。比如,素性测试问题,即判断一个给定的整数是否是素数的问题,是一个经典的计算问题。计算问题由“实例”和“询问”两部分组成。实例可以被看作问题的输入,它刻画了问题的参数以及参数的格式,在素性测试问题中,实例是给定的一个整数。询问刻画了问题的解需要满足的性质以及解的结构。在素性测试问题中,询问是“所给定的整数是否是素数”。根据询问的解的复杂程度的不同,计算问题大体可以分为判定问题(Decision Problem)和函数问题(Function Problem)。判定问题的解很简单,是一类只要求回答“是”和“否”的计算问题。素性测试问题是一个典型的判定问题。然而函数问题的解就比较复杂了。它可能是字符串,也可能是数字。最典型的函数问题是货郎担问题。人们在日常生活中遇到最多的是函数问题,有一类函数问题的可行解虽然有多个,但是这类问题只要求我们给出其中的一个解。“寻找图的一棵生成树”问题就是这样一个函数问题,这一类函数问题被称为搜索问题(Search Problem)。对于一个搜索问题,人们往往关心的是它的所有的解当中的“最优”的,例如,有时候人们不仅仅想要找到图的一棵生成树,人们更希望找到一棵“最大度最小的生成树”。人们称这样的一类问题为优化问题(Optimization Problem)。判定问题和优化问题是算法工作者们研究的最多的两类问题。算法工作者希望能够找到有效的方法让计算机在较短的时间内求到问题的解。一个有效的方法指的是,随着问题实例的规模的增大,该方法求解该问题所花费的时间的变化速率不是很快。通常情况下,计算机的算法工作者认为,如果一个方法能在多项式时间内给出问题的答案,那么这个方法才是有效的。然而,很多问题——无论是判定问题还是优化问题——很难找到有效的方法来求解它们,NP困难问题就是这样的一类问题。人们对NP困难问题中的优化问题研究比较广泛。人们虽然很难找到有效的方法求到这一类优化问题的最优解,但是人们可以设计出有效的方法求到可行的次优解。这就是近似算法(Approximation Algorithm)的核心思想。近似算法所追求的目标是尽可能的让所得到的可行的次优解的解值接近最优解的解值。近似算法能够给出一个量化的评价指标——所得到的可行解的解值与最优解的解值的偏差,因而近些年来得到了算法工作者的青睐。NP困难问题中的判定问题是一类比较棘手的问题。这一类问题只要求回答“是”和“否”,并且很难找到有效的算法来给出正确答案。受近似算法思想的启发,算法工作者有时候会将一个这样的判定问题转化成为一个优化问题,使得判定问题的某个实例的回答是“是”当且仅当优化问题在该实例上的最优解恰好是判定问题在该实例上的回答是“是”的一个证据,然后,来研究这个优化问题的近似算法,这个转化过程被称为对这个判定问题的一般化。人们在研究这个优化问题的同时间接地研究了判定问题。例如,人们对经典的合取范式可满足(SAT)问题的研究就是采用了这种方法。人们将SAT问题一般化之后得到了MaxSAT问题。很容易验证,某个MaxSAT问题的最优解使所有的项都满足当且仅当它所对应的的SAT问题是可满足的。哈密顿路径问题是另一个典型的NP困难的判定问题。哈密顿路径问题的实例是一个无向简单图,询问的是该图中是否存在一条含有所有顶点的简单路径。哈密顿路径问题一般化之后能得到很多优化问题,分支点最少的生成树问题(Minimum Branching Spanning Tree Problem)、内部顶点最多的生成树问题(Maximum Internal Spanning Tree Problem)、叶子最少的生成树问题(Minimum Leaves Spanning Tree Problem)、路径覆盖问题(Path Cover Problem)都是一般化的哈密顿路径问题。本文重点研究了路径覆盖问题和内部顶点最多的生成树问题的近似算法。本文的主要贡献如下。1、路径覆盖问题的近似算法及其复杂性的研究给定一个无向简单图,路径覆盖问题要找的是一些没有公共顶点的路径,使得这些路径能够覆盖图的所有顶点并且它们的边的总条数最多。一个图的路径覆盖问题的最优解是一条哈密顿路径当且仅当该图存在一条哈密顿路径,因此,路径覆盖问题是哈密顿路径问题的一般化。本文给出了路径覆盖问题的最优解值的一个新的上界,同时设计了求解路径覆盖问题的一个近似算法,利用所给出的上界,本文证明了该近似算法所得到的路径的总的边数至少是最优解值的7/10倍。最后,我们证明了路径覆盖问题是APX-hard的,也就是说,如果P≠ⅣP,那么,路径覆盖问题不存在多项式时间近似方案。2、内部顶点最多的生成树问题的近似算法及其复杂性研究给定一个无向简单图,内部顶点最多的生成树问题要找的是一棵内部顶点数目最多的生成树。该问题同样是哈密顿路径问题的一般化,因为,一个图内部顶点最多的生成树问题的最优解是该图的一条哈密顿路径当且仅当该图有一条哈密顿路径。受路径覆盖问题研究的启发,我们证明了一个图的生成树的内部顶点的数目不超过该图的路径覆盖问题的最优解值,又由于一个图的路径覆盖问题的最优解值不超过该图的一个最大的圈-路径覆盖的边的总条数,所以,一个图的生成树的内部顶点的数目不超过该图的一个最大的圈-路径覆盖的边的总条数。借助这个发现,我们利用图的一个最大的圈-路径覆盖,首先设计了图的内部顶点最多的生成树问题的近似性能比是1.5的多项式时间算法,该算法的性能已经是目前世界上最好的了。然后,我们又进一步将该算法的近似性能比改进到4/3。最后,我们证明,内部顶点最多的生成树问题也是APX-hard的。本文的进一步工作主要包括：1、随机近似技术目前是比较热门的算法设计和分析的技术,通过实验我们发现,很多情况下我们所得到的路径覆盖问题的解值十分接近最优解值,我们猜想,是否存在一个随机近似算法,使得该问题的平均近似性能十分接近1。目前该问题还没有一个随机近似算法,所以,该方向应该是一个比较好的研究点。2、对内部顶点最多的生成树问题的近似算法的进一步研究主要有如下两方面。第一,我们可以接着本文的研究思路,进一步改进该算法的近似性能比。我们发现,该问题的障碍是圈-路径覆盖问题中的长度是4的路径分支和长度是4的圈分支。要想改进近似性能比是4/3的算法,我们需要分别给出长度是4的路径分支和圈分支所贡献的内部顶点的数目的上界。一旦这个上界有了,我们就很容易找到一个更好的近似算法了。第二,我们可以利用局部搜索技术来改进算法的性能。局部搜索技术是目前比较热门的算法设计和分析技术。陈建二等人已经利用局部搜索技术给出了一个内部顶点最多的生成树问题的近似性能比是1.5的算法。我们猜想,把本文的算法和局部搜索技术相结合,也许会得到一个更好的算法。3、路径覆盖问题和内部顶点最多的生成树问题的不可近似性还是有很大的研究空间的,我们仅仅证明了这两个问题不存在多项式时间近似方案,这说明,这两个问题的近似性能比一定存在一个常数的下界,这个下界是有待被发现的。