一、nP-問題的基本概念

 

       本章的內(nèi)容包括了在算法研究方面的最重要的基本理論。這些基本理論對(duì)于計(jì)算機(jī)科學(xué)

家、電氣工程師和從事運(yùn)籌學(xué)等方面的工作者都是十分有用的。因此，凡是在這些領(lǐng)域里的工作者建議讀本章的內(nèi)容。  

不過，在閱讀本章之前，讀者應(yīng)熟悉以下基本概念：一是算法的事先分析計(jì)算時(shí)間，它是在所給定的不同數(shù)據(jù)集下，通過研究算法中語句．的執(zhí)行頻率而得到的，二是算法時(shí)間復(fù)雜度的數(shù)量級(jí)以及它們的漸近表示。如果一個(gè)算法在輸入量為n的情況下計(jì)算時(shí)間為t(n)，則記作t(n)＝o(f(n))，它表示時(shí)間以函數(shù)f(n)為上界。t(n)= (g(n))表示時(shí)間以函數(shù)g(n)為下界。這些概念在第一章都作過詳細(xì)的闡述。

       另一個(gè)重要概念是關(guān)于兩類問題的區(qū)別，其中第一類的求解只需多項(xiàng)式時(shí)間的算法，而第二類的求解則需要非多項(xiàng)式時(shí)間的算法(即，g(n)大于任何多項(xiàng)式)。對(duì)于已遇到和作過研究的許多問題，可按求解它們的最好算法所用計(jì)算時(shí)間分為兩類。第一類問題的求解只需低次多項(xiàng)式時(shí)間。例如本書前面講過的有序檢索的計(jì)算時(shí)間為o(1ogn)，分類為o(nlogn)，矩陣乘法為o( )等。第二類問題則包括那些迄今已知的最好算法所需時(shí)間為非多項(xiàng)式時(shí)間的問題。例如貨郎擔(dān)問題和背包問題的時(shí)間復(fù)雜度分別為o( )和o( )。對(duì)于第二類問題，人們一直在尋求更有效的算法，但至今還沒有誰開發(fā)出一個(gè)具有多項(xiàng)式時(shí)間復(fù)雜度的算法。指出這一點(diǎn)是十分重要的，因?yàn)樗惴ǖ臅r(shí)間復(fù)雜度一旦大于多項(xiàng)式時(shí)間(典型的時(shí)間復(fù)雜度是指數(shù)時(shí)間)，算法的執(zhí)行時(shí)間就會(huì)隨n的增大面急劇增加，以致即使是中等規(guī)模的問題也不能解出。

       本章所討論的nP-完全性理論，對(duì)于第二類問題，既不能給出使其獲得多項(xiàng)式時(shí)間的方法，也不說明這樣的算法不存在。取而代之的是證明了許多尚不知其有多項(xiàng)式時(shí)間算法的問題在計(jì)算上是相關(guān)的。實(shí)際上，我們建立了分別叫做nP-難度的和nP-完全的兩類問題。一個(gè)nP-完全的問題具有如下性質(zhì)：它可以在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)且僅當(dāng)所有其它的nP-完全問題也可在多項(xiàng)式時(shí)間內(nèi)求解。假如有朝一日某個(gè)nP-難度的問題可以被一個(gè)多項(xiàng)式時(shí)間的算法求解，那末所有的nP—完全問題就都可以在多項(xiàng)式時(shí)間內(nèi)求解。下面將會(huì)看到，一切nP-完全的問題都是nP-難度的問題，但一切nP-難度的問題并不都是nP-完全的。

 

二、不確定的算法

 

      到目前為止在已用過的算法中，每種運(yùn)算的結(jié)果都是唯一確定的，這樣的算法叫做確定的算法(deterministic algorithm)。這種算法和在計(jì)算機(jī)上執(zhí)行程序的方式是一致的。從理論的角度看，對(duì)于每種運(yùn)算的結(jié)果“唯一確定”這一限制可以取消。即可以允許算法每種運(yùn)算的結(jié)果不是唯一確定的，而是受限于某個(gè)特定的可能性集合。執(zhí)行這些運(yùn)算的機(jī)器可以根據(jù)稍后定義的終止條件選擇可能性集合中的一個(gè)作為結(jié)果。這就引出了所謂不確定的算法 (nondeterministic algorithm)。為了詳細(xì)說明這種算法，在sParks中引進(jìn)一個(gè)新函數(shù)和兩條新語句：

           choice (s)…任意選取集合s中的一個(gè)元素。

            failure…發(fā)出不成功完成的信號(hào)。

            success…發(fā)出成功完成的信號(hào)。

       賦值語句xßchoice (1：n)使x內(nèi)的結(jié)果是區(qū)域[1，n]中的任一整數(shù)(沒有規(guī)則限定這種選擇是如何作出的)。failure和success的信號(hào)用來定義此算法的一種計(jì)算，這兩條語句等價(jià)于stop語句，但不能起return語句的作用。每當(dāng)有一組選擇導(dǎo)致成功的完成時(shí)，總作出這樣的一組選擇并使算法成功地終止。當(dāng)且僅當(dāng)不存在任何一組選擇會(huì)導(dǎo)致成功的信號(hào)，那末不確定的算法不成功地終止。choice，success和failure的計(jì)算時(shí)間取為o (1)。能按這種方式執(zhí)行不確定算法的機(jī)器稱為不確定機(jī)(nondeterministic machine)。然而這里所定義的不確定機(jī)實(shí)際上是不存在的，因此通過直覺可以感到這類問題不可能用“快速的”確定算法求解。

   

三、本節(jié)實(shí)例

 

[例]：（檢索）考察在給定的元素集a(1：n)中，n≥1，檢索元素x的檢索問題。應(yīng)確定下標(biāo)j，使得a(j)＝x，或者當(dāng)x不在a中時(shí)有j＝0。此問題的一個(gè)不確定算法為

    jßchoice (1：n)

    if a(j)=x then print(j)；success endif 

    print (‘0’)；failure

       由上述定義的不確定算法當(dāng)且僅當(dāng)不存在一個(gè)j使得a(j)＝x時(shí)輸出“0”。此算法有不確定的復(fù)雜度o(1)。

         注意：由于a是無序的，因此確定的檢索算法的復(fù)雜度為 (n)。

[例]：(分類) 設(shè)a(i)，1≤i≤n，是一個(gè)尚未分類的正整數(shù)集。不確定的算法nsort(a，n)將這些數(shù)按非降次序分類并輸出。為方便起見，采用一輔助數(shù)組b(1：n)。第1行將b初始化為零。在第2~6行的循環(huán)中，每個(gè)a(i)的值都賦給b中的某個(gè)位置，第3行不確定地定出這個(gè)位置，第4行弄清b(j)是否還沒用過。因此b中整數(shù)的次序是a中初始次序的某種排列。第7~9行驗(yàn)證b是否已按非降次序分類。當(dāng)且僅當(dāng)整數(shù)以非降次序輸出時(shí)，算法成功地完成。由于第3行對(duì)于這種輸出次序總存在一組選擇，因此算法nsort是一個(gè)分類算法，它的復(fù)雜度為o(n)。回憶前面講過的各種確定的分類算法可知它們的復(fù)雜度應(yīng)為 (nlogn)。

[算法]：不確定的分類算法 [動(dòng)畫]

  procedure nsort(a，n)

    ／／對(duì)n個(gè)正整數(shù)分類／／

    integer a(n)，b(n)，n，i，j

 1    bß0／／b初始化為零／／

 2    for iß1 to n do

 3    ißchoice (1：n)

 4    if b(j) 0 then failure endif

 5    b(j)ßa(i)

 6    repeat

 7    for iß1 to n-1 do／／驗(yàn)證b的次序／／

 8    if b(i)>b(i+1) then failure endif

 9    repeat

 10    print(b) 

 11    success   

   12    end nsort

       通過允許作不受限制的并行計(jì)算可以對(duì)不確定的算法作出確定的解釋。每當(dāng)要作某種選擇時(shí)，算法就好像給自己復(fù)制了若干副本，每種可能的選擇有一個(gè)副本，于是許多副本同時(shí)被執(zhí)行。第一個(gè)獲得成功完成的副本，將引起其它所有副本的計(jì)算終止。如果一個(gè)副本獲得不成功的完成則只該副本終止。前面說過success和failure信號(hào)相當(dāng)于確定算法中的stop語句，但它們不能用來取代return語句。上述解釋是為了便于讀者理解不確定算法。

      注意： 對(duì)一臺(tái)不確定機(jī)來說，當(dāng)算法每次作某種選擇時(shí)，它實(shí)際上是什么副本都不作的，只是在每次作某種選擇時(shí)，具有從可選集合中選擇出一個(gè)“正確的”元素的能力(如果這樣的元素存在的話)。一個(gè)“正確的”元素是相對(duì)于導(dǎo)致一成功終止的最短選擇序列而定義的。在不存在導(dǎo)致成功終止的選擇序列的情況下，則假定算法是在一個(gè)單位時(shí)間內(nèi)終止并且輸出“計(jì)算不成功”。只要有成功終止的可能，一臺(tái)不確定機(jī)就會(huì)以最短的選擇序列導(dǎo)致成功的終止。因?yàn)檫@種不確定機(jī)本來就是虛構(gòu)和假想的，所以沒有必要去注意機(jī)器在每一步是如何作出正確選擇的。

       完全有可能構(gòu)造出一些這樣的不確定算法，它們的多種不同的選擇序列都會(huì)導(dǎo)致成功的完成。例8．2的過程nsort就是這樣的一個(gè)算法。如果整數(shù)a（i）有許多是相同的，那末在一個(gè)分類序列中將出現(xiàn)許多不同的排列。如果不是按已分好類的次序輸出這些a（i），而是輸出所用的排列，那末這樣的輸出將不是唯一確定的。今后只關(guān)心那些產(chǎn)生唯一輸出的不確定算法，特別是只研究那些不確定的判定算法(nondeteministic decision algorithm)。這些算法只產(chǎn)生“0”或“1”作為輸出，即作二值決策，前者當(dāng)且僅當(dāng)沒有一種選擇序列可導(dǎo)致一個(gè)成功的完成，后者當(dāng)且僅當(dāng)一個(gè)成功的完成被產(chǎn)生。輸出語句隱含于success和failure之中。在判定算法中不允許有明顯的輸出語句。顯然，早先對(duì)不確定計(jì)算的定義意味著一個(gè)判定算法的輸出由輸入?yún)?shù)和算法本身的規(guī)范唯一地確定。

       雖然上面所述的判定算法的概念看來似乎限制過嚴(yán)，但事實(shí)上許多最優(yōu)化問題都可以改寫成判定問題并使其具有如下性質(zhì)；該判定問題可以在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)且僅當(dāng)與它相應(yīng)的最優(yōu)化問題可以在多項(xiàng)式時(shí)間內(nèi)求解。從另一方面說，如果判定問題不能在多項(xiàng)式時(shí)間內(nèi)求解，那末與它相應(yīng)的最優(yōu)化問題也不能在多項(xiàng)式時(shí)間內(nèi)求解。

[例]： (最大集團(tuán)) 圖g＝(v，e)的最大完全子圖叫作g的一個(gè)集團(tuán)(clique)。集團(tuán)的大小用所含的結(jié)點(diǎn)數(shù)來量度。最大集團(tuán)問題即為確定g內(nèi)最大集團(tuán)的大小問題。與之對(duì)應(yīng)的判定問題是，對(duì)于某個(gè)給定的k，確定g是否有一個(gè)大小至少為k的集團(tuán)。令dcliq—ue(g，k)是此集團(tuán)判定問題的一個(gè)確定的判定算法。假設(shè)g的結(jié)點(diǎn)數(shù)為n，g內(nèi)最大集團(tuán)的大小可在多次應(yīng)用dclique(g，k)而求得。對(duì)于每個(gè)k，k=n，n一1，n一2，…直到dcliclue輸出l為止，過程dclique都要被引用一次。如果dclique的時(shí)間復(fù)雜度為（b)，則最大集團(tuán)的大小可在n，f(n)時(shí)間內(nèi)求出二假如最大集團(tuán)的大小可以在g(n)時(shí)間內(nèi)確定，于是其判定問題也可在g(n)時(shí)間內(nèi)解出。因此最大集團(tuán)問題可在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)且僅當(dāng)集團(tuán)的判定問題可在多項(xiàng)式時(shí)間內(nèi)求解。  

[例]： (0／1背包) 背包的判定問題是確定對(duì) ，1≤i≤n，是否存在一組o／1的賦值，使得 ≥r和 ≤m。r是一個(gè)給定的數(shù)，而這些 及 都是非負(fù)的數(shù)。顯然，如果背包的判定問題不能在確定的多項(xiàng)式時(shí)間內(nèi)求解，則它的最優(yōu)化問題也同樣不能在確定的多項(xiàng)式時(shí)間內(nèi)求解。

        在進(jìn)一步討論之前，為了量測復(fù)雜度必須先統(tǒng)一參數(shù)n。假設(shè)n是算法的輸入長度；還假定所有的輸入都是整數(shù)。有理數(shù)輸入可以視作一對(duì)整數(shù)。一般說輸入量的長度是以該量的二進(jìn)制表示度量的，即如果輸入量是十進(jìn)制的10，相應(yīng)的二進(jìn)制表示就是1010，因此它的長度就是4。對(duì)于正整數(shù)k，用二進(jìn)制形式表示時(shí)的長度就是|_ _|+1。0的長度規(guī)定為1。算法輸入的大小或長度n是指輸入的各個(gè)數(shù)長度的總和。因此，用不同的進(jìn)位制時(shí)的長度是不同的，以r為基的正整數(shù)k，其長度為|_ _|。在十進(jìn)制中(r＝10) 數(shù)100的長度為 100+1＝3。因?yàn)?/span> ＝ / ，于是以r (r>1)為基輸入的長度為c (r)·n，其中n是以二進(jìn)制表示時(shí)的長度，c(r) 是對(duì)于給定r后的一個(gè)常數(shù)。

       當(dāng)使用基r=1給定輸入量時(shí)，則稱此輸入是一進(jìn)制形式的。在一進(jìn)制形式中，數(shù)5的輸入形式是11111。于是正整數(shù)k的長度即為k。

     注意 ：一進(jìn)制形式輸入的長度與其相應(yīng)的基為r(r>1)的輸入的長度間具有指數(shù)關(guān)系。

[例]：(最大集團(tuán)) 最大集團(tuán)判定問題的輸入可以看作是一個(gè)邊的序列和一個(gè)整數(shù)k。

 e(g)內(nèi)的每條邊又是一對(duì)數(shù)值(i，j)。對(duì)于每條邊(i，j)，如果采用二進(jìn)制表示，則其輸入的大小為 + +2。于是任一實(shí)例的輸人大小為

       n＝

注意：如果g只有一個(gè)連通分圖，則n≥|v|。于是對(duì)于某個(gè)多項(xiàng)式p()，若這個(gè)判定問題不能由一個(gè)復(fù)雜度為p(n)的算法求解，則它也不能被復(fù)雜度為p(|v|)的算法求解。

[例]： (0／1背包) 假設(shè)pi，wi，m和r均為整數(shù)，背包判定問題輸入量的大小為

  m=

其中，m≥n。如果輸入量用一進(jìn)制形式給出，則輸人大小s為 +m+r。對(duì)于某個(gè)多項(xiàng)式p()，背包的判定問題和最優(yōu)化問題均可在p(s)的時(shí)間內(nèi)求解；但對(duì)于某個(gè)多項(xiàng)式p()還不知道有復(fù)雜度為o(p(n))的算法。

       下面給出不確定算法復(fù)雜度的形式定義。

     定義：一個(gè)不確定算法所需的時(shí)間是指當(dāng)存在一選擇序列導(dǎo)致一成功的完成時(shí)，為了完成任意給定的一個(gè)輸入而達(dá)到成功完成所需步驟的最小值。在不可能成功完成的情況下所需的時(shí)間是o(1)。假如對(duì)于所有的大小為n (n≥ )的輸入，導(dǎo)致成功完成需要的時(shí)間至多為c·f(n)，其中c和 是兩個(gè)常數(shù)，則這個(gè)不確定算法的復(fù)雜度為o(f(n))。

         在上述定義中，假定每個(gè)計(jì)算步驟的開銷是固定的。在面向字處理的計(jì)算機(jī)中，每個(gè)宇的有限性確保了固定開銷。當(dāng)每步開銷不固定時(shí)，則應(yīng)考慮各條指令的開銷。例如兩個(gè)m位的數(shù)相加花費(fèi)的時(shí)間為o(m)，而按經(jīng)典方法將這兩數(shù)相乘，則花費(fèi)的時(shí)間為o( )等等。為了弄清注意這一問題的必要性，下面來考察子集和數(shù)判定問題的確定算法sum。它用了一個(gè)m+1位的字s。當(dāng)且僅當(dāng)整數(shù)a(j)，1≤j≤n，不存在和數(shù)為i的子集時(shí)s的第i位為0。s的位數(shù)按從右到左的次序編碼為0，1，2，…，m，且s的第0位總?cè)≈禐?/span>1。函數(shù)shift把s中的各位均向左移動(dòng)a(o位。這個(gè)算法的總步數(shù)只有o(n)。然而每步都要移動(dòng)數(shù)據(jù)m+1位，因此在一臺(tái)傳統(tǒng)的計(jì)算機(jī)上每步實(shí)際上所需的時(shí)間為o(m)。假設(shè)對(duì)于一個(gè)大小固定的字，每個(gè)基本操作都需要一個(gè)單位的時(shí)間，那末該算法的真實(shí)復(fù)雜度是o(nm)而不是o(n)。

[算法]：子集和數(shù)判定的確定算法 [動(dòng)畫]

procedure sum(a，n，m)

    integer a(n)，s，n，m

    s<-1／s是一個(gè)有m+1位的字，第0位是1／／

    for iß1 to n do

sßs or shift(s，a(i))

   repeat

    if mth bit in s=0 then print(‘no subset sums to m’)

    else print(‘a subset sums to m，)

    endif

end sum

    不確定算法的優(yōu)點(diǎn)是對(duì)于那些用確定算法寫起來非常復(fù)雜的問題可以很容易地寫出它們的不確定算法。事實(shí)上，對(duì)于許多可以通過系統(tǒng)檢索指數(shù)大小解空間來確定地求解的問題，要得到它們的多項(xiàng)式時(shí)間的不確定算法是很容易的。

[例]：(背包判定問題) 過程dkP(算法8．3)是背包問題的一個(gè)不確定的多項(xiàng)式時(shí)間算法。第1～3行將0／1值賦給x(0，1≤i≤n。第4行檢查賦值的可行性并且查看所導(dǎo)致的效益值是否至少為r。當(dāng)且僅當(dāng)判定問題的答案為“是”，才可能是一個(gè)成功的終止。時(shí)間復(fù)雜度是o(n)。如果m是用二進(jìn)制表示的輸入長度，則時(shí)間是o (m)。

[算法]：背包問題的不確定算法[動(dòng)畫]

   procedure dkP(P，w，n，m，r，x)

integer P(n)，w(n)，r，x(n)，n，m，i

for iß1 to n do

 x(i)ßchoice (0，1)   

repeat    

if >m or <r then failure

else success

  endif

end dkP

[例]：(最大集團(tuán)) 過程dck(算法8．4)是此集團(tuán)判定問題的一個(gè)不確定算法。算法開始時(shí)試探形成一個(gè)具有k個(gè)不同結(jié)點(diǎn)的集合，然后測試這些結(jié)點(diǎn)是否構(gòu)成一個(gè)完全子圖。若g是由其鄰接矩陣和|v|＝n所給出，則輸入長度m為 + +2。易于看出第2～6行的不確定的執(zhí)行時(shí)間為o(n)。第7～10行的時(shí)間為o( )。于是總時(shí)間為o(n+ )＝o( )＝o(m)。對(duì)于這個(gè)問題，已知它有多項(xiàng)式時(shí)間的確定算法。   

[算法]：集團(tuán)的不確定算法[動(dòng)畫]

    procedure dck(g，n，k)

    1    sß ／s的初值為空’集合／／

    2    for iß1 to k do／選擇k個(gè)不同的結(jié)點(diǎn)／／

    3    tßchoice (1：n)   

    4    if t s then failure endif

  5              sßs t／／將t加到集合s"

  6    repeat ／／此處s含有k個(gè)不同結(jié)點(diǎn)的下標(biāo)／／

     7    for使得i s，j s的每一對(duì)(i,j) and i j do

  8    if (i,j)不是此圖的邊

     9     then failure endif

  10  repeat

  11  success

end dck

[算法]： 可滿足性的不確定算法 [動(dòng)畫]

    procedure eval(e，n)

    ／／判定命題e是否為可滿足的。變量為 ，1≤i≤n／／

    boolean x (n)

    for iß1 to n do／／選取一組真值指派／／

    ßchoice (true，false)

    repeat

    if e ( )＝true then success／／可滿足的／／

    else failure

    endif   

    end eval