11網(wǎng)

絡

優(yōu)

化

第1章概論

NetworkOptimization1.4計算復雜性的概念

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

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

(Max,f,F)

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

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

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

D={0,1}n

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

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

(ILP)

.

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

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

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

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

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

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

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

輸入長度/規(guī)模的計算方法：

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

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

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

算法輸入自然數(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; }即該算法的計算復雜性（度）為O(n2)，是一個多項式算法?；具\算的總次數(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三、強多項式算法和偽多項式算法算法復雜性研究中:常將算法的計算時間表示為：問題中的簡單而典型的參數(shù)(如網(wǎng)絡優(yōu)化中n,m)問題中出現(xiàn)的數(shù)值(如弧上的權)的最大值(按絕對值)K等自變量的函數(shù)關系如果算法運行時間的上界是m,n和K的多項式函數(shù)，則稱相應的算法為偽多項式（Pseudopolynomial）（時間）算法，或擬多項式（時間）算法.實際問題的輸入規(guī)模/長度一定是m,n和logK的一個多項式函數(shù).所以：多項式算法等價于其運行時間的上界是m,n和logK的多項式函數(shù).特別地,如果運行時間的上界是m,n的多項式函數(shù)（即該多項式函數(shù)不包含logK）,則稱相應的算法為強多項式(StronglyPolynomial)時間算法.一般來說，偽多項式算法并不是多項式算法.16定義1.5對于給定的一個優(yōu)化問題，若存在一個求解該問題最優(yōu)解的多項式時間算法，則稱給定的優(yōu)化問題是多項式可解問題，或簡稱多項式問題，