最大內(nèi)部點(diǎn)生成樹(shù)問(wèn)題的算法及復(fù)雜性.pdf

1、本文重點(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è)新的上界，

2、同時(shí)設(shè)計(jì)了求解路徑覆蓋問(wèn)題的一個(gè)近似算法，利用所給出的上界，本文證明了該近似算法所得到的路徑的總的邊數(shù)至少是最優(yōu)解值的7/10倍。最后，我們證明了路徑覆蓋問(wèn)題是APX-hard的，也就是說(shuō)，如果P≠NP，那么，路徑覆蓋問(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)題的一般化

3、，因?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)

4、最多的生成樹(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)題的平均

5、近似性能十分接近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ù)目的上界

6、。一旦這個(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)