計(jì)算復(fù)雜性的概念

11網(wǎng)

絡(luò)

優(yōu)

化

第1章概論

NetworkOptimization1.4計(jì)算復(fù)雜性的概念

2定義1.3所謂組合(最)優(yōu)化(CombinatorialOptimization)又稱離散優(yōu)化（DiscreteOptimization），它是通過(guò)數(shù)學(xué)方法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等.這類問(wèn)題可用數(shù)學(xué)模型描述為：

優(yōu)化問(wèn)題三要素:(Min,f,F)或

(Max,f,F)

其中D表示有限個(gè)點(diǎn)組成的集合(定義域)

,f為目標(biāo)函數(shù),F={x|xD,g(x)0}為可行域

1.4.1組合優(yōu)化問(wèn)題1、定義3給定n個(gè)容積分別為ai，價(jià)值分別為ci的物品.設(shè)有一個(gè)容積為b的背包，如何以最大的價(jià)值裝包？用數(shù)學(xué)規(guī)劃模型表示為：

D={0,1}n

2、例子例1.70-1背包問(wèn)題(knapsackproblem)4一個(gè)商人到n城市推銷商品，兩個(gè)城市之間的距離為dij，如何選擇一條道路使得商人每個(gè)城市走一遍之后回到起點(diǎn)，且所走的路徑最短？其數(shù)學(xué)模型描述為：

例1.8旅行商問(wèn)題(TSP)D={0,1}n×(n-1)5例1.9整數(shù)線性規(guī)劃(IntegerLinearProgramming)

(ILP)

.

我們假設(shè)線性整數(shù)規(guī)劃的參數(shù)（約束矩陣和右端項(xiàng)系數(shù)）都是整數(shù)(或有理數(shù)).ILP中系數(shù)是有理數(shù)時(shí)，都可以處理成整數(shù)的情況。6以尺寸為1的箱子裝進(jìn)給定的n個(gè)尺寸不超過(guò)1的物品，物品的尺寸為wj，如何使所用的箱子個(gè)數(shù)最少? 說(shuō)明：許多組合優(yōu)化問(wèn)題可以用整數(shù)規(guī)劃模型表示,但有時(shí)不如直接用自然語(yǔ)言描述簡(jiǎn)潔，故，大量的組合優(yōu)化問(wèn)題是通過(guò)文字語(yǔ)言敘述的。例1.10裝箱問(wèn)題(BinPacking)71.4.2多項(xiàng)式時(shí)間算法對(duì)于組合優(yōu)化問(wèn)題，我們關(guān)心的一般不是最優(yōu)解的存在性和唯一性，而是如何找到有效的算法求得一個(gè)最優(yōu)解.那么如何衡量算法的優(yōu)劣、有效與無(wú)效呢？

完全枚舉法可以求得最優(yōu)解,但枚舉時(shí)間有時(shí)不可能接受

ATSP:(n-1)!枚舉(TOUR,周游或環(huán)游)設(shè)計(jì)算機(jī)每秒進(jìn)行100億次枚舉,需

30!/10e+10>2.65e+22(秒)即2.65e+22/(365*24*60*60) >8.4e+13(年)8問(wèn)題（Problem）：是需要回答的一般性提問(wèn)，通常含有若干個(gè)滿足一定條件的參數(shù).實(shí)例(instance)：?jiǎn)栴}中的參數(shù)賦予了具體值的例子。一、問(wèn)題與實(shí)例的定義：

問(wèn)題通過(guò)下面的描述給定：（1）描述所有參數(shù)的特性（2）描述答案所滿足的條件.

問(wèn)題實(shí)例TSP問(wèn)題中各參數(shù):100個(gè)城市，城市間距離已知.背包問(wèn)題問(wèn)題中各參數(shù):4個(gè)物品，大小分別為4,3,2,2.價(jià)值分別為8,7,5,7.包的大小為6.整數(shù)線性規(guī)劃問(wèn)題中的n,A,b,c已知.9構(gòu)造算法的目的是能夠解決問(wèn)題（或至少是問(wèn)題某個(gè)子類）的所有實(shí)例而不單單是某一個(gè)實(shí)例。

衡量一個(gè)算法的好壞，通常由以下兩個(gè)要素的關(guān)系來(lái)衡量：(1)C(I)：求解實(shí)例I的計(jì)算時(shí)間，即算法中的加、減、乘、除和比較等基本運(yùn)算的總次；(2)d(I)：實(shí)例I的輸入規(guī)模/長(zhǎng)度，即實(shí)例I在計(jì)算機(jī)計(jì)算時(shí)的二進(jìn)制輸入數(shù)據(jù)的大小.

輸入長(zhǎng)度/規(guī)模的計(jì)算方法：

對(duì)于一個(gè)正整數(shù)x，其二進(jìn)制為：二、多項(xiàng)式時(shí)間算法10正整數(shù)x輸入長(zhǎng)度的估計(jì)：

11定義1.4假設(shè)問(wèn)題和解決該問(wèn)題的一個(gè)算法已經(jīng)給定，若存在g(x)為多項(xiàng)式函數(shù)且對(duì)該問(wèn)題任意的一個(gè)實(shí)例I，使得計(jì)算時(shí)間成立，則稱該算法為解決該問(wèn)題的多項(xiàng)式(時(shí)間)算法(Polynomialtimealgorithm).輸入規(guī)模增大時(shí)，多項(xiàng)式時(shí)間算法的基本計(jì)算總次數(shù)的增加速度相對(duì)較慢。當(dāng)不存在多項(xiàng)式函數(shù)g(x)使得上式成立時(shí)，稱相應(yīng)的算法是非多項(xiàng)式時(shí)間算法,或指數(shù)(時(shí)間)算法(Exponentialtimealgorithm)12例1：上述的非對(duì)稱ATSP問(wèn)題，設(shè)城市數(shù)為n，第1個(gè)城市為始終點(diǎn)。假設(shè)每一個(gè)數(shù)據(jù)(距離)的絕對(duì)值都有上界K，則：

說(shuō)明：輸入長(zhǎng)度不超過(guò)n的一個(gè)多項(xiàng)式函數(shù)。13所以，枚舉算法對(duì)TSP來(lái)說(shuō)，不是一個(gè)多項(xiàng)式時(shí)間的算法。TSP問(wèn)題至今沒(méi)有找到多項(xiàng)式時(shí)間算法,但尚未證明其不存在TSP是否存在多項(xiàng)式時(shí)間算法?----這是21世紀(jì)數(shù)學(xué)和計(jì)算機(jī)科學(xué)的挑戰(zhàn)性問(wèn)題之一14例2：構(gòu)造算法將n個(gè)自然數(shù)從小到大排列起來(lái)

算法輸入自然數(shù)a(1),a(2),…,a(n).for(i=1;i<n;i++) for(j=i+1;j<=n;j++) if(a(i)>a(j)){ k=a(i);a(i)=a(j);a(j)=k; }即該算法的計(jì)算復(fù)雜性（度）為O(n2)，是一個(gè)多項(xiàng)式算法?；具\(yùn)算的總次數(shù)(最壞情形）：2n(n-1)=O(n2)

比較：（n-1)+(n-2)+…+1=n(n-1)/2

賦值：

3{(n-1)+(n-2)+…+1}=3n(n-1)/215三、強(qiáng)多項(xiàng)式算法和偽多項(xiàng)式算法算法復(fù)雜性研究中:常將算法的計(jì)算時(shí)間表示為：?jiǎn)栴}中的簡(jiǎn)單而典型的參數(shù)(如網(wǎng)絡(luò)優(yōu)化中n,m)問(wèn)題中出現(xiàn)的數(shù)值(如弧上的權(quán))的最大值(按絕對(duì)值)K等自變量的函數(shù)關(guān)系如果算法運(yùn)行時(shí)間的上界是m,n和K的多項(xiàng)式函數(shù)，則稱相應(yīng)的算法為偽多項(xiàng)式（Pseudopolynomial）（時(shí)間）算法，或擬多項(xiàng)式（時(shí)間）算法.實(shí)際問(wèn)題的輸入規(guī)模/長(zhǎng)度一定是m,n和logK的一個(gè)多項(xiàng)式函數(shù).所以：多項(xiàng)式算法等價(jià)于其運(yùn)行時(shí)間的上界是m,n和logK的多項(xiàng)式函數(shù).特別地,如果運(yùn)行時(shí)間的上界是m,n的多項(xiàng)式函數(shù)（即該多項(xiàng)式函數(shù)不包含logK）,則稱相應(yīng)的算法為強(qiáng)多項(xiàng)式(StronglyPolynomial)時(shí)間算法.一般來(lái)說(shuō)，偽多項(xiàng)式算法并不是多項(xiàng)式算法.16定義1.5對(duì)于給定的一個(gè)優(yōu)化問(wèn)題，若存在一個(gè)求解該問(wèn)題最優(yōu)解的多項(xiàng)式時(shí)間算法，則稱給定的優(yōu)化問(wèn)題是多項(xiàng)式可解問(wèn)題，或簡(jiǎn)稱多項(xiàng)式問(wèn)題，