最大内部点生成树问题的算法及复杂性

发布时间：2018-06-06 21:07

本文选题：算法 + 近似算法　；参考：《山东大学》2015年博士论文

【摘要】：计算问题(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、路径覆盖问题和内部顶点最多的生成树问题的不可近似性还是有很大的研究空间的,我们仅仅证明了这两个问题不存在多项式时间近似方案,这说明,这两个问题的近似性能比一定存在一个常数的下界,这个下界是有待被发现的。
[Abstract]:Computational Problem is a class of mathematical problems that can be solved by computer. For example, the problem of primal testing, that is, to judge whether a given integer is a prime number, is a classic calculation problem. The computational problem is composed of two parts, "instance" and "inquiry". It depicts the parameters of the problem and the format of the parameters. In the problem of primal testing, an instance is a given integer. The question depicts the nature of the solution that needs to be satisfied and the structure of the solution. In the primal test question, the question is whether the given integer is a prime. The problem can be divided into Decision Problem and function problem (Function Problem). The solution of the decision problem is very simple. It is a class of computing problems that only require the answer "yes" and "no". The problem of primal testing is a typical decision problem. However, the solution of the function problem is more complex. It may be a string and may be a string. It is a number. The most typical function problem is the problem of the cargo. People have the most function problem in daily life. Although there are many feasible solutions to a class of functional problems, this kind of problem only requires us to give one solution. "Finding a spanning tree" is such a function problem, this kind of function. A number problem is called Search Problem. For a search problem, people are often concerned about "optimal" in all of its solutions. For example, sometimes people do not just want to find a spanning tree of the graph, people want to find a "maximum and minimum spanning tree". Optimization problem (Optimization Problem). Decision problem and optimization problem are the two kinds of problem that the algorithm workers study most. The algorithm worker hopes to find an effective method to get the computer to solve the problem in a short time. An effective method is that the method is solved with the scale of the problem. The rate of time spent on this problem is not very fast. In general, computer algorithms think that if a method can give the answer to the problem in a polynomial time, the method is effective. However, many problems - whether it is the decision question or the optimization problem - it is difficult to find the effective side. The NP difficult problem is such a kind of problem. People have a wide range of research on the optimization problem in the NP difficult problem. Although it is difficult to find an effective method to find the optimal solution of this kind of optimization problem, people can design an effective method to find the feasible suboptimal solution. This is the approximate algorithm (Approximat The aim of the approximate algorithm is to make the solution value of the feasible suboptimal solution close to the solution value of the optimal solution as much as possible. The approximate algorithm can give a quantified evaluation index - the deviation of the solution value of the feasible solution and the solution value of the optimal solution, so the algorithm work has been obtained in recent years. The decision problem in the.NP difficult problem is a kind of difficult problem. This kind of problem only requires the answer "yes" and "no", and it is difficult to find an effective algorithm to give the correct answer. Inspired by the approximate algorithm thought, the algorithmic worker sometimes transforms such a decision problem into an optimal question. The answer to a certain instance of a decision problem is "yes" when and only if the optimal solution on the case is just an evidence that the answer on the case is "yes", and then, to study the approximate algorithm of the optimization problem, the transformation is called the generalization of the decision problem. In the study of this optimization problem, the problem of decision is studied indirectly. For example, the study of the classical conjunctive paradigm satisfaction (SAT) problem is adopted. People get the MaxSAT problem after the generalization of the SAT problem. It is easy to verify that the optimal solution of a MaxSAT question makes all the items satisfied when and only if The SAT problem corresponding to it is satisfactory. The Hamilton path problem is another typical NP difficult decision problem. An example of the Hamilton path problem is an undirected simple graph. The question is whether there is a simple path with all the vertices in the graph. The Hamilton path problem is generalized and many optimization questions can be obtained. Minimum Branching Spanning Tree Problem, the largest spanning tree problem of the internal vertices (Maximum Internal Spanning Tree Problem), the least leaf spanning tree problem (Minimum Leaves), the path cover problem is the general Hamilton path question. The main contributions of this paper are as follows:.1, the approximate algorithm of the path coverage problem and the study of its complexity given a undirected simple graph. The path coverage problem is to find some paths without common vertices, making these paths possible. The optimal solution for the path coverage problem of a graph is a Hamiltonian path when and only if there is a Hamiltonian path of the graph. Therefore, the path coverage problem is a generalization of the Hamiltonian path problem. A new solution of the path coverage problem is given in this paper. In the upper bound, an approximate algorithm for solving the path coverage problem is designed. Using the upper bounds given, this paper proves that the total edge number of the path obtained by the approximate algorithm is at least 7/10 times the optimal solution value. Finally, we prove that the path coverage problem is APX-hard, that is to say, if P IV P, then the path coverage problem. There is no polynomial time approximation scheme.2, the approximate algorithm and its complexity of the spanning tree problem with the most internal vertices are given an undirected simple graph. The generation tree problem with the most internal vertices is to find a spanning tree with the largest number of internal vertices. This problem is also a generalization of the Hamilton path problem, because a graph is a graph. The optimal solution for the spanning tree problem with the most internal vertices is a Hamiltonian path of the graph, when and only if the graph has a Hamiltonian path. Inspired by the study of the path coverage problem, we prove that the number of the internal vertices of the spanning tree of a graph does not exceed the optimal solution value of the path coverage problem of the graph, and the path of a graph. The optimal solution of a path coverage problem does not exceed the total number of edges covered by a maximum circle path of the graph, so the number of the inner vertices of the spanning tree of a graph does not exceed the total number of the edges covered by a maximum circle path of the graph. By this discovery, we use a maximum circle path coverage of the graph, first design. The approximate performance of the spanning tree problem with the most internal vertices of the graph is 1.5 of the polynomial time algorithm, and the performance of the algorithm is the best in the world. Then, we further improve the approximate performance ratio of the algorithm to the last 4/3.. We prove that the problem of generating trees with the most internal top points is also APX-hard. The further work includes: 1, the stochastic approximation technique is currently a relatively hot algorithm design and analysis technology. Through the experiment, we find that in many cases, the solution value of the path coverage problem we get is very close to the optimal solution value. We assume that there is a random approximation algorithm that makes the average approximation of the problem. The performance is very close 1. and there is not a random approximation algorithm at present. So, this direction should be a good research point.2. The further study of the approximate algorithm for the tree problem with the most internal vertices is the following two aspects. First, we can further improve the approach of this paper to further improve the algorithm. We find that the obstacle of this problem is that the length of the loop path coverage problem is 4 of the path branch and the loop branch of the length of 4. To improve the approximate performance ratio is the 4/3 algorithm, we need to give the upper bound of the number of internal top points that the length is 4 of the path branch and the circle branch. Once this upper bound has, We can easily find a better approximation algorithm. Second, we can use local search technology to improve the performance of the algorithm. Local search technology is the most popular algorithm design and analysis technology. Chen Jianer et al. Has used local search technology to give an approximation of a spanning tree problem with the most internal vertices. The performance ratio is 1.5 of the algorithm. We suppose that combining this algorithm with the local search technique may get a better algorithm.3. The path coverage problem and the generation tree problem with the most internal vertices are still a lot of research space. We only prove that these two problems do not exist polynomial time near. Like a scheme, this shows that the approximate performance ratio of these two problems must have a constant lower bound. This lower bound is still to be discovered.
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP301.6

【共引文献】