計算復雜性的概念

11網

絡

優

化

第1章概論

NetworkOptimization1.4計算復雜性的概念

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

優化問題三要素:(Min,f,F)或

(Max,f,F)

其中D表示有限個點組成的集合(定義域)

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

1.4.1組合優化問題1、定義3給定n個容積分別為ai，價值分別為ci的物品.設有一個容積為b的背包，如何以最大的價值裝包？用數學規劃模型表示為：

D={0,1}n

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

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

(ILP)

.

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

完全枚舉法可以求得最優解,但枚舉時間有時不可能接受

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

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

問題通過下面的描述給定：（1）描述所有參數的特性（2）描述答案所滿足的條件.

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

衡量一個算法的好壞，通常由以下兩個要素的關系來衡量：(1)C(I)：求解實例I的計算時間，即算法中的加、減、乘、除和比較等基本運算的總次；(2)d(I)：實例I的輸入規模/長度，即實例I在計算機計算時的二進制輸入數據的大小.

輸入長度/規模的計算方法：

對于一個正整數x，其二進制為：二、多項式時間算法10正整數x輸入長度的估計：

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

說明：輸入長度不超過n的一個多項式函數。13所以，枚舉算法對TSP來說，不是一個多項式時間的算法。TSP問題至今沒有找到多項式時間算法,但尚未證明其不存在TSP是否存在多項式時間算法?----這是21世紀數學和計算機科學的挑戰性問題之一14例2：構造算法將n個自然數從小到大排列起來

算法輸入自然數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; }即該算法的計算復雜性（度）為O(n2)，是一個多項式算法。基本運算的總次數(最壞情形）：2n(n-1)=O(n2)

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

賦值：

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