《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第10章

第10章“難”問題求解算法10.1概率算法10.2近似算法

10.1概率算法

概率算法的一個基本特征是對所求解問題的同一個實例用同一個概率算法求解兩次，可能得到完全不同的結(jié)果。

(1)數(shù)值概率算法。

(2)舍伍德算法。

(3)拉斯維加斯算法。

(4)蒙特卡羅算法。10.1.1數(shù)值概率算法

數(shù)值概率算法實際上是在統(tǒng)計意義下求解問題的近似解。

1．用隨機投點法計算π值

設(shè)有一個半徑為r的圓及其外切正方形，如圖10-1(a)所示。向該正方形隨機地投入n個點，設(shè)落入圓內(nèi)的點數(shù)為k。由于隨機投入正方形的點服從均勻分布，因此所投入的點落入圓內(nèi)的概率為πr2/4r2。當n足夠大時，k/n→π/4，因此π=4k/n,由此可得到計算π值的概率算法。圖10-1計算π值的示意圖

2．用隨機投點法計算定積分

設(shè)f(x)是[0，1]上的連續(xù)函數(shù)，且0≤f(x)≤1，計算

I=

f(x)dx的值。積分I的值等于圖10-2中所示的面積G。在圖10-2所示的單位正方形中均勻地做投點試驗，則隨機點落在曲線y=f(x)下方的概率為

假設(shè)向單位正方形內(nèi)隨機投入n個點(xi,yi)，i=?1,2,…,n，如果有m個點落入G內(nèi)，則m/n近似地等于隨機點落入G內(nèi)的概率，即I=m/n。10.1.2舍伍德算法

在平均情況下分析算法的計算復(fù)雜度時，通常假設(shè)算法的輸入數(shù)據(jù)服從某一個特定的概率分布。例如，快速排序算法中，假設(shè)輸入數(shù)據(jù)服從均勻分布，其平均時間復(fù)雜度為O(nlbn)，那么在輸入數(shù)據(jù)都完成排序后，這個時間就不再成立了。此時可采用舍伍德算法消除該算法所需計算時間與輸入實例之間的這種聯(lián)系。設(shè)A是一個確定性算法，當其輸入實例為x時所需的計算時間為tA(x)。假設(shè)算法A的全體輸入規(guī)模為n的實例的集合是XA，算法A所需的平均時間為

(10-1)

這顯然不能排除存在x∈XA使得tA(x)遠大于(n)的可能性。我們期望得到一個概率算法B，使得對問題的輸入規(guī)模為n的每一個實例x∈XA均有tB(x)=

(n)+s(n)。對于某一個具體實例x∈XA，算法B偶爾需要的計算時間比(n)+s(n)多，這是由算法所作的概率選擇引起的，與具體實例x無關(guān)。

定義算法B關(guān)于規(guī)模為n的隨機實例的平均計算時間為

(10-2)

可知tB(n)=

(n)+s(n)，這就是舍伍德算法設(shè)計的基本思想。當s(n)與(n)相比可以忽略時，舍伍德算法可以獲得很好的計算性能。10.1.3拉斯維加斯算法

舍伍德算法的優(yōu)點是其計算時間復(fù)雜度對所有的實例而言是相對均勻的，但與其相對應(yīng)的確定性算法相比，其平均時間復(fù)雜度沒有改進。而拉斯維加斯算法能顯著地改善算法的有效性，甚至對迄今為止找不到有效算法的某些問題也能得到滿意的結(jié)果。下面考慮整數(shù)因子分解的拉斯維加斯算法。

設(shè)n是一個大于1的整數(shù)，關(guān)于整數(shù)n的因子分解問題是，找出n的如下形式的唯一分解式：

其中，p1＜p2＜…＜pk是k個素數(shù)；m1，m2，…，mk是k個整數(shù)。如果n是合數(shù)，則n必有一個非平凡因子x，1＜x＜n，使得x可以整除n。給定一個合數(shù)n，求n的一個非平凡因子的問題稱為因子分割問題。下面算法可實現(xiàn)整數(shù)的因子分割：下面討論求整數(shù)n的因子分割的拉斯維加斯算法——Pollard算法，該算法用與Split算法相同的計算量就可以獲得在1～x4范圍內(nèi)的因子分割。

Pollard算法開始時隨機選取0～n-1范圍內(nèi)的一個整數(shù)x1，然后由式

(10-3)

遞歸產(chǎn)生無窮序列x1，x2，…，xk，…。對于i=2k，k=0,1,2,…，以及2k≤j≤2k+1，Pollard算法計算xj-xi與n的最大公因子為

d=gcd(xj-xi,n)

(10-4)

如果d是n的非平凡因子，則在實現(xiàn)對n的一次因子分割時，該算法輸出n的因子d。10.1.4蒙特卡羅算法

在實際應(yīng)用中常會遇到一些特殊的問題，即無論是采用確定性算法，還是概率算法都無法保證每次都能得到正確解。蒙特卡羅算法在一般情況下可以保證對問題的所有實例都可以高概率地給出正確解，但通常無法判斷一個具體解是否正確。設(shè)p是一個實數(shù)，且＜p＜1。如果蒙特卡羅算法對于問題的任何一個實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-?為該算法的優(yōu)勢。

如果對于同一個實例，蒙特卡羅算法不會給出兩個不同的正確答案，則稱蒙特卡羅算法是一致的。

對于一個一致的p正確蒙特卡羅算法，要提高獲得正確解的概率，只需執(zhí)行算法若干次，并選擇出現(xiàn)頻次最高的解即可。下面討論素數(shù)測試問題。費爾馬小定理為素數(shù)判定提供了一個有力的工具。

費爾馬小定理：如果p是素數(shù)，且0＜a＜p，則ap-1

1

(modp)。

利用費爾馬小定理可以設(shè)計一個素數(shù)判定算法。對于一個給定的整數(shù)n，通過計算d=2n-1modn來判定整數(shù)n的素性：當d≠1時，n肯定不是素數(shù)；當d=1時，n可能是素數(shù)，也可能不是素數(shù)。為了提高素數(shù)測試的準確性，可以隨機地選取整數(shù)a(1＜a＜n-1)，然后利用條件an-1

1(modn)來判定整數(shù)n的素性。但是，費爾馬小定理是素數(shù)判定的必要條件，即滿足費爾馬小定理的整數(shù)n未必是素數(shù)。為此利用二次探測定理可對上述算法做進一步地改進。

二次探測定理：如果p是一個素數(shù)，0＜x＜p，則方程x2

1(modp)的解是x=1,p-1。

利用二次探測定理，在利用費爾馬小定理計算an-1modn的過程中，增加對于整數(shù)n的二次探測，一旦發(fā)現(xiàn)其違背二次探測條件，即可得出n不是素數(shù)的結(jié)論。

10.2近似算法

許多“難”問題實質(zhì)上是最優(yōu)化問題，即要求使某個目標函數(shù)達到最大值或最小值的解。不失一般性，對于確定的問題，假設(shè)其每一個可行解所對應(yīng)的目標函數(shù)值不小于一個確定的正數(shù)。

若一個最優(yōu)化問題的最優(yōu)解為s*，用近似算法求解該

問題得到的解為s，則該近似算法的性能比定義為

η?=?max。通常情況下，該性能比是問題輸入規(guī)模n的函數(shù)ρ(n)，即η≥ρ(n)。根據(jù)定義可知：η≥1，當近似解等于最優(yōu)解時，η=1；η越大，近似最優(yōu)解就越差。

有時使用相對誤差衡量近似算法的精確程度。近似算法的相對誤差定義為

(10-5)若問題的輸入規(guī)模為n，存在一個函數(shù)ε(n)使得λ≤ε(n)，則稱ε(n)為該近似算法的相對誤差界。函數(shù)

ε(n)與ρ(n)的關(guān)系為

ε(n)≤ρ(n)-110.2.1頂點覆蓋問題的近似算法

設(shè)無向圖G=(V,E)的頂點覆蓋是V的一個子集，V'

V,滿足：若(v,u)是G的一條邊，則v

V'或u

V'。頂點覆蓋的大小是它所包含的頂點個數(shù)|V'|。圖10-3頂點覆蓋問題的近似算法10.2.2旅行售貨員問題的近似算法

旅行售貨員問題可描述為給定一個完全無向網(wǎng)絡(luò)G=(V,E)，其中每一條邊(v,u)E有一個非負整數(shù)費用c(v,u)，要求找出G的最小費用哈密頓回路。

從實際應(yīng)用中抽象出的旅行售貨員問題常常具有一些特殊性質(zhì)，如費用函數(shù)c往往具有三角不等式性質(zhì)。當圖G中的頂點是平面上的點時，任意兩個頂點間的費用就是這兩個頂點間的歐氏距離，故費用函數(shù)c具有三角不等式性質(zhì)。下面介紹具有三角不等式性質(zhì)的旅行售貨員問題的近似算法。圖10-4旅行售貨員問題的近似算法由于圖G是一個完全圖，因此可知ApproxTSPTour算法的計算時間為O(|E|)?=?O(|V|2)。

若用H*表示圖G的最小費用旅行售貨員回路，H表示ApproxTSPTour算法的近似最優(yōu)旅行售貨員回路，則c(H)≤2c(H*)。

證明：設(shè)T是ApproxTSPTour算法計算得出的圖G的最小生成樹。從H*中任意刪除一條邊后，可得到圖G的一棵生成樹。由于T是最小生成樹，故有

c(T)≤c(H*)

(10-6)對樹T所做的一個完全遍歷是在訪問T的一個頂點時列出該頂點，而在結(jié)束對T的一棵子樹的訪問并沿途返回時也列出返回時經(jīng)過的頂點。設(shè)W是T的前序完全遍歷，即圖10-4(b)的前序完全遍歷為abcbdbaefgfhfea。由于對樹T的前序完全遍歷W經(jīng)過T的每條邊恰好兩次，因此有

c(W)=2c(T)≤2c(H*)(10-7)然而W不是一個旅行售貨員回路，它訪問了G中某些頂點多次。由于費用函數(shù)滿足三角不等式，因此在W中刪除已經(jīng)訪問過的頂點不會增加旅行的費用。若在W中刪除頂點u和頂點w間的一個頂點v，那么就用邊(u,w)代替原來從u到w的一條路。反復(fù)使用該方法刪除W中多次被訪問的頂點后，可得到G的一條旅行售貨員回路。在圖10-4中，從W中刪除重復(fù)訪問頂點后得到的回路為H?=?abcdefgha，這就是ApproxTSPTour算法計算得出的近似最優(yōu)哈密頓回路。由費用函數(shù)的三角不等式性質(zhì)知

c(H)≤c(W)≤2c(H*)(10-8)

也就是說，算法ApproxTSPTour的性能比為2。10.2.3集合覆蓋問題的近似算法

下面給出集合覆蓋問題的一個實例。設(shè)<X,F>由一個有限集X和X的一個子集族F組成，子集族F覆蓋了有限集X。也就是說，X中的任何一個元素至少屬于F中的一個子集，即

S。對于F中的一個子集C

F，若C覆蓋了