本文選題：算法 + 近似算法��； 參考：《山東大學(xué)》2015年博士論文

【摘要】：計(jì)算問(wèn)題(Computational Problem)是一類(lèi)可以借助計(jì)算機(jī)來(lái)求解的數(shù)學(xué)問(wèn)題。比如,素性測(cè)試問(wèn)題,即判斷一個(gè)給定的整數(shù)是否是素?cái)?shù)的問(wèn)題,是一個(gè)經(jīng)典的計(jì)算問(wèn)題。計(jì)算問(wèn)題由“實(shí)例”和“詢問(wèn)”兩部分組成。實(shí)例可以被看作問(wèn)題的輸入,它刻畫(huà)了問(wèn)題的參數(shù)以及參數(shù)的格式,在素性測(cè)試問(wèn)題中,實(shí)例是給定的一個(gè)整數(shù)。詢問(wèn)刻畫(huà)了問(wèn)題的解需要滿足的性質(zhì)以及解的結(jié)構(gòu)。在素性測(cè)試問(wèn)題中,詢問(wèn)是“所給定的整數(shù)是否是素?cái)?shù)”。根據(jù)詢問(wèn)的解的復(fù)雜程度的不同,計(jì)算問(wèn)題大體可以分為判定問(wèn)題(Decision Problem)和函數(shù)問(wèn)題(Function Problem)。判定問(wèn)題的解很簡(jiǎn)單,是一類(lèi)只要求回答“是”和“否”的計(jì)算問(wèn)題。素性測(cè)試問(wèn)題是一個(gè)典型的判定問(wèn)題。然而函數(shù)問(wèn)題的解就比較復(fù)雜了。它可能是字符串,也可能是數(shù)字。最典型的函數(shù)問(wèn)題是貨郎擔(dān)問(wèn)題。人們?cè)谌粘Ｉ钪杏龅阶疃嗟氖呛瘮?shù)問(wèn)題,有一類(lèi)函數(shù)問(wèn)題的可行解雖然有多個(gè),但是這類(lèi)問(wèn)題只要求我們給出其中的一個(gè)解。“尋找圖的一棵生成樹(shù)”問(wèn)題就是這樣一個(gè)函數(shù)問(wèn)題,這一類(lèi)函數(shù)問(wèn)題被稱為搜索問(wèn)題(Search Problem)。對(duì)于一個(gè)搜索問(wèn)題,人們往往關(guān)心的是它的所有的解當(dāng)中的“最優(yōu)”的,例如,有時(shí)候人們不僅僅想要找到圖的一棵生成樹(shù),人們更希望找到一棵“最大度最小的生成樹(shù)”。人們稱這樣的一類(lèi)問(wèn)題為優(yōu)化問(wèn)題(Optimization Problem)。判定問(wèn)題和優(yōu)化問(wèn)題是算法工作者們研究的最多的兩類(lèi)問(wèn)題。算法工作者希望能夠找到有效的方法讓計(jì)算機(jī)在較短的時(shí)間內(nèi)求到問(wèn)題的解。一個(gè)有效的方法指的是,隨著問(wèn)題實(shí)例的規(guī)模的增大,該方法求解該問(wèn)題所花費(fèi)的時(shí)間的變化速率不是很快。通常情況下,計(jì)算機(jī)的算法工作者認(rèn)為,如果一個(gè)方法能在多項(xiàng)式時(shí)間內(nèi)給出問(wèn)題的答案,那么這個(gè)方法才是有效的。然而,很多問(wèn)題——無(wú)論是判定問(wèn)題還是優(yōu)化問(wèn)題——很難找到有效的方法來(lái)求解它們,NP困難問(wèn)題就是這樣的一類(lèi)問(wèn)題。人們對(duì)NP困難問(wèn)題中的優(yōu)化問(wèn)題研究比較廣泛。人們雖然很難找到有效的方法求到這一類(lèi)優(yōu)化問(wèn)題的最優(yōu)解,但是人們可以設(shè)計(jì)出有效的方法求到可行的次優(yōu)解。這就是近似算法(Approximation Algorithm)的核心思想。近似算法所追求的目標(biāo)是盡可能的讓所得到的可行的次優(yōu)解的解值接近最優(yōu)解的解值。近似算法能夠給出一個(gè)量化的評(píng)價(jià)指標(biāo)——所得到的可行解的解值與最優(yōu)解的解值的偏差,因而近些年來(lái)得到了算法工作者的青睞。NP困難問(wèn)題中的判定問(wèn)題是一類(lèi)比較棘手的問(wèn)題。這一類(lèi)問(wèn)題只要求回答“是”和“否”,并且很難找到有效的算法來(lái)給出正確答案。受近似算法思想的啟發(fā),算法工作者有時(shí)候會(huì)將一個(gè)這樣的判定問(wèn)題轉(zhuǎn)化成為一個(gè)優(yōu)化問(wèn)題,使得判定問(wèn)題的某個(gè)實(shí)例的回答是“是”當(dāng)且僅當(dāng)優(yōu)化問(wèn)題在該實(shí)例上的最優(yōu)解恰好是判定問(wèn)題在該實(shí)例上的回答是“是”的一個(gè)證據(jù),然后,來(lái)研究這個(gè)優(yōu)化問(wèn)題的近似算法,這個(gè)轉(zhuǎn)化過(guò)程被稱為對(duì)這個(gè)判定問(wèn)題的一般化。人們?cè)谘芯窟@個(gè)優(yōu)化問(wèn)題的同時(shí)間接地研究了判定問(wèn)題。例如,人們對(duì)經(jīng)典的合取范式可滿足(SAT)問(wèn)題的研究就是采用了這種方法。人們將SAT問(wèn)題一般化之后得到了MaxSAT問(wèn)題。很容易驗(yàn)證,某個(gè)MaxSAT問(wèn)題的最優(yōu)解使所有的項(xiàng)都滿足當(dāng)且僅當(dāng)它所對(duì)應(yīng)的的SAT問(wèn)題是可滿足的。哈密頓路徑問(wèn)題是另一個(gè)典型的NP困難的判定問(wèn)題。哈密頓路徑問(wèn)題的實(shí)例是一個(gè)無(wú)向簡(jiǎn)單圖,詢問(wèn)的是該圖中是否存在一條含有所有頂點(diǎn)的簡(jiǎn)單路徑。哈密頓路徑問(wèn)題一般化之后能得到很多優(yōu)化問(wèn)題,分支點(diǎn)最少的生成樹(shù)問(wèn)題(Minimum Branching Spanning Tree Problem)、內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題(Maximum Internal Spanning Tree Problem)、葉子最少的生成樹(shù)問(wèn)題(Minimum Leaves Spanning Tree Problem)、路徑覆蓋問(wèn)題(Path Cover Problem)都是一般化的哈密頓路徑問(wèn)題。本文重點(diǎn)研究了路徑覆蓋問(wèn)題和內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題的近似算法。本文的主要貢獻(xiàn)如下。1、路徑覆蓋問(wèn)題的近似算法及其復(fù)雜性的研究給定一個(gè)無(wú)向簡(jiǎn)單圖,路徑覆蓋問(wèn)題要找的是一些沒(méi)有公共頂點(diǎn)的路徑,使得這些路徑能夠覆蓋圖的所有頂點(diǎn)并且它們的邊的總條數(shù)最多。一個(gè)圖的路徑覆蓋問(wèn)題的最優(yōu)解是一條哈密頓路徑當(dāng)且僅當(dāng)該圖存在一條哈密頓路徑,因此,路徑覆蓋問(wèn)題是哈密頓路徑問(wèn)題的一般化。本文給出了路徑覆蓋問(wèn)題的最優(yōu)解值的一個(gè)新的上界,同時(shí)設(shè)計(jì)了求解路徑覆蓋問(wèn)題的一個(gè)近似算法,利用所給出的上界,本文證明了該近似算法所得到的路徑的總的邊數(shù)至少是最優(yōu)解值的7/10倍。最后,我們證明了路徑覆蓋問(wèn)題是APX-hard的,也就是說(shuō),如果P≠ⅣP,那么,路徑覆蓋問(wèn)題不存在多項(xiàng)式時(shí)間近似方案。2、內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題的近似算法及其復(fù)雜性研究給定一個(gè)無(wú)向簡(jiǎn)單圖,內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題要找的是一棵內(nèi)部頂點(diǎn)數(shù)目最多的生成樹(shù)。該問(wèn)題同樣是哈密頓路徑問(wèn)題的一般化,因?yàn)?一個(gè)圖內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題的最優(yōu)解是該圖的一條哈密頓路徑當(dāng)且僅當(dāng)該圖有一條哈密頓路徑。受路徑覆蓋問(wèn)題研究的啟發(fā),我們證明了一個(gè)圖的生成樹(shù)的內(nèi)部頂點(diǎn)的數(shù)目不超過(guò)該圖的路徑覆蓋問(wèn)題的最優(yōu)解值,又由于一個(gè)圖的路徑覆蓋問(wèn)題的最優(yōu)解值不超過(guò)該圖的一個(gè)最大的圈-路徑覆蓋的邊的總條數(shù),所以,一個(gè)圖的生成樹(shù)的內(nèi)部頂點(diǎn)的數(shù)目不超過(guò)該圖的一個(gè)最大的圈-路徑覆蓋的邊的總條數(shù)。借助這個(gè)發(fā)現(xiàn),我們利用圖的一個(gè)最大的圈-路徑覆蓋,首先設(shè)計(jì)了圖的內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題的近似性能比是1.5的多項(xiàng)式時(shí)間算法,該算法的性能已經(jīng)是目前世界上最好的了。然后,我們又進(jìn)一步將該算法的近似性能比改進(jìn)到4/3。最后,我們證明,內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題也是APX-hard的。本文的進(jìn)一步工作主要包括：1、隨機(jī)近似技術(shù)目前是比較熱門(mén)的算法設(shè)計(jì)和分析的技術(shù),通過(guò)實(shí)驗(yàn)我們發(fā)現(xiàn),很多情況下我們所得到的路徑覆蓋問(wèn)題的解值十分接近最優(yōu)解值,我們猜想,是否存在一個(gè)隨機(jī)近似算法,使得該問(wèn)題的平均近似性能十分接近1。目前該問(wèn)題還沒(méi)有一個(gè)隨機(jī)近似算法,所以,該方向應(yīng)該是一個(gè)比較好的研究點(diǎn)。2、對(duì)內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題的近似算法的進(jìn)一步研究主要有如下兩方面。第一,我們可以接著本文的研究思路,進(jìn)一步改進(jìn)該算法的近似性能比。我們發(fā)現(xiàn),該問(wèn)題的障礙是圈-路徑覆蓋問(wèn)題中的長(zhǎng)度是4的路徑分支和長(zhǎng)度是4的圈分支。要想改進(jìn)近似性能比是4/3的算法,我們需要分別給出長(zhǎng)度是4的路徑分支和圈分支所貢獻(xiàn)的內(nèi)部頂點(diǎn)的數(shù)目的上界。一旦這個(gè)上界有了,我們就很容易找到一個(gè)更好的近似算法了。第二,我們可以利用局部搜索技術(shù)來(lái)改進(jìn)算法的性能。局部搜索技術(shù)是目前比較熱門(mén)的算法設(shè)計(jì)和分析技術(shù)。陳建二等人已經(jīng)利用局部搜索技術(shù)給出了一個(gè)內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題的近似性能比是1.5的算法。我們猜想,把本文的算法和局部搜索技術(shù)相結(jié)合,也許會(huì)得到一個(gè)更好的算法。3、路徑覆蓋問(wèn)題和內(nèi)部頂點(diǎn)最多的生成樹(shù)問(wèn)題的不可近似性還是有很大的研究空間的,我們僅僅證明了這兩個(gè)問(wèn)題不存在多項(xiàng)式時(shí)間近似方案,這說(shuō)明,這兩個(gè)問(wèn)題的近似性能比一定存在一個(gè)常數(shù)的下界,這個(gè)下界是有待被發(fā)現(xiàn)的。
[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.
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：TP301.6

【共引文獻(xiàn)】

相關(guān)期刊論文 前1條

1 CHEN Yuan;CHEN GuanTao;HU ZhiQuan;;Spanning 3-ended trees in k-connected K_(1,4)-free graphs[J];Science China(Mathematics);2014年08期

相關(guān)博士學(xué)位論文 前2條

1 陳園;圖中參數(shù)與樹(shù)型結(jié)構(gòu)研究[D];華中師范大學(xué);2013年

2 趙芹;圖中結(jié)構(gòu)及拓?fù)鋮?shù)研究[D];華中師范大學(xué);2013年

，

本文編號(hào)：1988113