組合優(yōu)化及算法.ppt

1、組合優(yōu)化,Combinatorial Optimization,組合優(yōu)化是運籌學(xué)的后繼課程，同時也是運籌學(xué)的一個重要獨立分支，是一類重要的優(yōu)化問題,最優(yōu)化(數(shù)學(xué)規(guī)劃) 連續(xù)優(yōu)化(數(shù)學(xué)規(guī)劃)： 數(shù)學(xué)規(guī)劃（線性規(guī)劃、非線性規(guī)劃）、非光滑優(yōu)化、全局優(yōu)化、錐優(yōu)化等 離散優(yōu)化：網(wǎng)絡(luò)優(yōu)化、組合優(yōu)化、整數(shù)規(guī)劃等 不確定規(guī)劃：隨機(jī)規(guī)劃、模糊規(guī)劃等,所謂組合(最)優(yōu)化(Combinatorial Optimization)又稱離散優(yōu)化（Discrete Optimization），它是通過數(shù)學(xué)方法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等. 這類問題可用數(shù)學(xué)模型描述為：,優(yōu)化問題三要素: (Min,f,F)或

2、(Max,f,F),其中D表示有限個點組成的集合(定義域) , f為目標(biāo)函數(shù),F=x|xD, g(x)0為可行域,組合優(yōu)化 定義,組合優(yōu)化 例,例 0-1背包問題(knapsack problem) 給定n個容積分別為ai，價值分別為ci的物品.設(shè)有一個容積為b的背包，如何以最大的價值裝包？用數(shù)學(xué)規(guī)劃模型表示為：,D= 0,1n,例 裝箱問題(Bin Packing) 以尺寸為1的箱子裝進(jìn)給定的n個尺寸不超過1的物品，如何使所用的箱子個數(shù)最少?,組合優(yōu)化 例,整數(shù)線性規(guī)劃(Integer Linear Programming),(IP) .,我們假設(shè)線性整數(shù)規(guī)劃的參數(shù)（約束矩陣和右端項系數(shù)）都

3、是整數(shù)(或有理數(shù)). 許多組合優(yōu)化問題可以用整數(shù)規(guī)劃模型表示,但有時不如直接用自然語言描述簡潔,組合優(yōu)化問題 定義,定義：組合優(yōu)化問題 是一個極小化問題，或者是一個極大化問題，它由下述三部分組成： （1）實例集合； （2）對每一個實例I，有一個有窮的可行解集合S(I). （3）目標(biāo)函數(shù) ，對每一個實例I和每一個可行解 ，賦以一個有理數(shù) .如果 是極小化（極大化）問題，則實例I 的最優(yōu)解為這樣一個可行解 ，它使得對于所有 ，它都有,算法 定義,定義：算法是指一步步求解問題的通用程序，它是解決問題的程序步驟的一個清晰描述.,定型算法，即算法從前一步到后一步的運行是由當(dāng)時狀態(tài)唯一確定的.,如果存在一

4、個算法，他它對問題任意一個給定實例，在有限步之后，一定能得到該實例的答案，那么我們稱算法能解決該問題.,近似算法、最優(yōu)算法,近似算法：對于一個優(yōu)化問題，如果給定任意一個實例I,算法A總能找到一個可行解，那么這個算法稱為該問題的近似算法.,最優(yōu)算法：如果進(jìn)一步，如果這個可行解的目標(biāo)值 總等于最優(yōu)解值，則稱A為最優(yōu)算法.,典型組合優(yōu)化問題,背包問題 裝箱問題 平行機(jī)排序問題 圖與網(wǎng)絡(luò)優(yōu)化問題 最小支撐樹、最短路、最大流、最小費用流、最大基數(shù)匹配問題 指派問題 旅行售貨商問題 斯坦納最小樹問題,本課程的主要目的講授這些問題的數(shù)學(xué)描述和相應(yīng)算法.,背包問題,給定n個容積分別為ai，價值分別為ci的物品

5、.設(shè)有一個容積為b的背包，如何以最大的價值裝包？,平行機(jī)排序問題,M個完全相同的機(jī)器，n個相互獨立的工件，加工時間互不相同，每個工件只需在任一臺機(jī)器上不中斷建工一次，如果安排加工方案，才能使預(yù)定的加工時間最短？,計算復(fù)雜性的概念,多項式時間算法,對于組合優(yōu)化問題，我們關(guān)心的一般不是最優(yōu)解的存在性和唯一性，而是如何找到有效的算法求得一個最優(yōu)解. 那么如何衡量算法的優(yōu)劣、有效與無效呢？,完全枚舉法可以求得最優(yōu)解,但枚舉時間有時不可能接受,ATSP: (n-1)!枚舉(TOUR,周游或環(huán)游) 設(shè)計算機(jī)每秒進(jìn)行100億次枚舉,需 30! / 10e+10 2.65e+22 (秒) 即 2.65e+22

6、 / (365*24*60*60) 8.4e+13 (年),計算復(fù)雜性的概念,多項式時間算法,構(gòu)造算法的目的是能夠解決問題（或至少是問題某個子類）的所有實例而不單單是某一個實例,問題（Problem）是需要回答的一般性提問，通常含有若干個滿足一定條件的參數(shù). 問題通過下面的描述給定：（1）描述所有參數(shù)的特性，（2）描述答案所滿足的條件.,問題中的參數(shù)賦予了具體值的例子稱為實例(instance).,衡量一個算法的好壞通常是用算法中的加、減、乘、除和比較等基本運算的總次數(shù)（計算時間）C（I）同實例I在計算機(jī)計算時的二進(jìn)制輸入數(shù)據(jù)(輸入規(guī)模/長度d（I）)的大小關(guān)系來度量. 計算模型,C(I) =

7、 f(d(I) : 該函數(shù)關(guān)系稱為算法的計算復(fù)雜性（度）,計算復(fù)雜性的概念,多項式時間算法,例 構(gòu)造算法將n個自然數(shù)從小到大排列起來,算法 輸入自然數(shù)a(1),a(2),a(n). for (i=1;ia(j) k=a(i);a(i)=a(j);a(j)=k; ,即該算法的計算復(fù)雜性（度）為O(n2),基本運算的總次數(shù)(最壞情形）：2n(n-1)=O(n2),計算復(fù)雜性的概念,定義1.4 假設(shè)問題和解決該問題的一個算法已經(jīng)給定，若存在g(x)為多項式函數(shù)且對該問題任意的一個實例I，使得計算時間,成立，則稱該算法為解決該問題的多項式(時間)算法(Polynomial time algorithm

8、). 當(dāng)不存在多項式函數(shù)g(x)使得上式成立時，稱相應(yīng)的算法是非多項式時間算法, 或指數(shù)(時間)算法(Exponential time algorithm),輸入規(guī)模增大時，多項式時間算法的基本計算總次數(shù)的增加速度相對較慢.,多項式時間算法,注：上面定義中，要求對該問題的任意一個實例均成立 ， 這種分析方法稱為最壞性能分析（Worst-Case Analysis）,1.4 計算復(fù)雜性的概念,1.4.2 多項式時間算法,計算復(fù)雜性的概念,多項式時間算法,算法復(fù)雜性研究中:常將算法的計算時間表示為： 問題中的簡單而典型的參數(shù)(如網(wǎng)絡(luò)優(yōu)化中n,m), 以及 問題中出現(xiàn)的數(shù)值(如弧上的權(quán))的最大值(按

9、絕對值)K等自變量的函數(shù)關(guān)系,如果算法運行時間的上界是m,n和K的多項式函數(shù)，則稱相應(yīng)的算法為偽多項式（Pseudopolynomial）（時間）算法，或擬多項式（時間）算法.,實際問題的輸入規(guī)模/長度一定是m,n和logK的一個多項式函數(shù). 所以： 多項式算法等價于其運行時間的上界是m,n和logK的多項式函數(shù).,特別地, 如果運行時間的上界是m,n的多項式函數(shù)（即該多項式函數(shù)不包含logK）, 則稱相應(yīng)的算法為強(qiáng)多項式(Strongly Polynomial)時間算法.,一般來說，偽多項式算法并不是多項式算法.,計算復(fù)雜性的概念,TSP等許多問題至今沒有找到多項式時間算法,但尚未證明其不存

10、在,定義 對于給定的一個優(yōu)化問題，若存在一個求解該問題最優(yōu)解的多項式時間算法，則稱給定的優(yōu)化問題是多項式可解問題，或簡稱多項式問題，所有多項式問題集記為P(Polynomial).,同樣道理, 可以定義強(qiáng)多項式問題,偽多項式問題等.,TSP是否存在多項式時間算法? - 這是21世紀(jì)數(shù)學(xué)和計算機(jī)科學(xué)的挑戰(zhàn)性問題之一,多項式問題,問題、實例與輸入規(guī)模,評價一個算法的依據(jù)是該算法在最壞實例下的計算時間與實例輸入規(guī)模的關(guān)系：,比多項式問題類可能更廣泛的一個問題類是非確定多項式 (Nondeterministic Polynomial，簡記 NP ) 問題類,存在多項式算法的問題集合：多項式問題類（P）

11、,存在多項式函數(shù) g(x) 滿足上式時，算法為多項式算法,NP 類是通過判定問題引入的。,對任何一個優(yōu)化問題， 可以考慮其三種形式： 最優(yōu)化形式（原形：最優(yōu)解） 計值形式（最優(yōu)值） 判定形式（上界）,定義 如果一個問題的每一個實例只有“是”或“否”兩種答案，則稱這個問題為判定問題(Decision / recognition / feasibility problem). 稱有肯定答案的實例為“是”實例(yes-instance). 稱答案為“否”的實例為“否”實例或非“是”實例(no-instance).,判定問題 - 定義,例 線性規(guī)劃問題(LP)的判定形式LP判定問題： 給定一個實數(shù)值z

12、，(LP)是否有可行解使其目標(biāo)值不超過z？ 即：給定z，是否有 ?,難度降低,就有效算法的存在性而言，通常認(rèn)為三種形式等價！,文字集,例 適定性問題(Satisfiability problem) 在邏輯運算中，布爾變量x的取值只有兩個：“真”(1)和“假”(0)，邏輯運算有“或（+）”，“與（）”和“非（）.,判定問題 - 例,存在真值分配的表達(dá)式稱為適定的(可滿足的),文字集的任意一個子集中各元素（布爾變量）的“或”運算組成一個句子,多個句子的“與”運算組成一個表達(dá)式，如,適定性問題：給定布爾表達(dá)式 ， （SAT）是適定的嗎？,判定問題 - 例,例 三精確覆蓋(3-Exact Coveri

13、ng：X3C) 已知 的n個子集構(gòu)成的子集族 ， 其中每個子集包含S中三個元素，F(xiàn)中是否存在m個子集 ， 使得 ？ 若m個子集滿足上式，則稱這m個子集精確覆蓋S.,定義 若存在一個多項式函數(shù)g(x)和一個驗證算法H，對一類判定問題A的任何一個“是” 實例I，都存在一個字符串S是I的可行解，滿足其輸入長度d(S)不超過g(d(I)，其中d(I)為I的輸入長度，且算法H驗證S為實例I的可行解的計算時間f(H)不超過g(d(I)，則稱判定問題A是非確定多項式的。,考慮將求解判定問題的算法分為兩個階段： （1）猜測階段：求出或猜測該問題的一個解 （2）檢查或驗證階段：一旦解已經(jīng)選定，將猜測的解作為輸入

14、，驗證此解是否為該實例“是”的回答. 我們稱實例“是”回答的解為實例的可行解，否則稱為不可行解.,所有非確定多項式問題的集合用NP表示.,非確定多項式問題類(NP) 定義,構(gòu)造字符串（解）的過程及驗證算法H一起構(gòu)成一個算法，稱為非確定多項式（時間）算法。,F中m個元素 是S的一個精確三覆蓋的充分必要條件為： 相應(yīng)的m個向量滿足,集合S中共有3m個元素，子集族F中的每個子集合對應(yīng)一個3m維向量：向量的3m個分量對應(yīng)3m個元素，元素包含在對應(yīng)子集中的分量為1，余下的為0. 例如： S= ，F(xiàn)中的一個元素 ，對應(yīng)向量為 = (1,1,0,0,0,1)，表示為一個字符串(110001).,非確定多項式

15、問題類(NP) 例,按字符串向量問題，精確三覆蓋 “是”實例的任何一個解可以用長度為3m2 的字符表示. 驗證是否可行解的算法最多需3m2 個加法和3m個比較，算法的計算時間為3m2 +3m.,例 三精確覆蓋屬于NP,三精確覆蓋問題任何一個實例的輸入長度d(I)3m.,選g(x)= x2 /3+x ，則定義條件滿足，所以三精確覆蓋屬于NP.,非確定多項式問題類(NP) ,問題A2的難度不低于問題A1,定義 給定問題A1和A2，若存在一個多項式算法滿足： 對A1的任何一個實例I1，算法將實例I1的輸入轉(zhuǎn)換為A2的一個實例I2的輸入； 這種轉(zhuǎn)換過程使得實例I1和I2的解一一對應(yīng)，即將實例I1的一個

16、解x1的輸入轉(zhuǎn)換為實例I2的一個解x2的輸入，且x1為I1的“是”答案 x2是I2的一個“是”答案； 則稱A1問題多項式轉(zhuǎn)換為A2問題，算法稱為問題A1到問題A2的一個多項式轉(zhuǎn)換（算法）(Transformation).,常用的研究方法 - 多項式轉(zhuǎn)換(變換)、多項式歸約(歸結(jié)),若A1多項式轉(zhuǎn)換為A2，且A2P，則A1P 若A1多項式轉(zhuǎn)換為A2，且A2NP，則A1NP,多項式轉(zhuǎn)換(定義),NP完全問題類(NPC) -,定義 已知判定問題A1和A2，若存在多項式函數(shù) 和 ，使得對A1的任何實例I，在多項式時間內(nèi)構(gòu)造A2的一個實例，其輸入長度不超過 ，并對A2的任何一個算法H2，都存在問題A1的

17、一個算法H1，使得H1算法調(diào)用H2算法且使得計算時間 ， 其中fH1(x)和fH2(x)分別表示算法H1和H2的計算時間與實例輸入長度x之間的關(guān)系，則稱問題A1多項式歸約為問題A2.,根據(jù)A2的算法H2， 構(gòu)造A1的算法H1的過程，即映射 ：H2 H1 稱為從A1到A2的一個多項式歸約(reduction).,多項式歸約(定義),問題A2的難度不低于問題A1,若A1多項式歸約為A2，且A2P，則A1P 若A1多項式歸約為A2，且A2NP，則A1NP,若A1多項式歸約為A2，則當(dāng)把H1對H2的一次調(diào)用當(dāng)成一次基本運算時， H1是A1的多項式算法。,NP完全問題類(NPC) - 多項式歸約,多項式

18、轉(zhuǎn)換是多項式歸約的特例,歸約映射可以如下構(gòu)造： H1：STEP1 用多項式轉(zhuǎn)換將A1的實例轉(zhuǎn)換為A2的實例 STEP2 用H2算法求解A2的實例,即多項式轉(zhuǎn)換可以認(rèn)為是只允許調(diào)用一次H2的多項式歸約,NP完全問題類(NPC) - 多項式歸約 （例）,例1.22 適定問題多項式歸約為三精確覆蓋問題,定義（1）對于判定問題A，若ANP且NP中的任何一個問題可在多項式時間內(nèi)歸約為A，則稱A為NP完全問題(NP-Complete或NPC).可以表示為ANPC.,NPC和NP-hard兩者的區(qū)別是: 驗證一個問題A是否為NP-hard無須判斷A是否屬于NP. 根據(jù)定義可知NPCNPH.,當(dāng)已知一個問題屬

19、于NPC或NPH時，如果再遇到一個新問題： （1）若已知問題多項式歸約為新問題，則新問題屬于NPH;,NP完全問題類(NPC) 定義,（2）對于判定問題A，若NP中的任何一個問題可在多項式時間歸約為判定問題A，則稱A為NP困難問題(NP-hard 或NPH) .可以表示為ANPH.,（2）若還可以驗證新問題屬于NP，則新問題屬于NPC.,NP完全問題類(NPC),定理：如果問題A是P問題，且B可以在多項式時間內(nèi)歸約為A，則B也為P問題.,定理：P=NP當(dāng)且僅當(dāng)存在一個NPC問題有多項式時間算法.,定理：如果問題A是NPC問題，且B可以在多項式時間內(nèi)歸約為A，則B也為NPC問題.,定理：如果問題

20、A是NPH問題，且B可以在多項式時間內(nèi)歸約為A，則B也為NPH問題.,NP完全問題類(NPC),定理：除非P=NP，否則NPH問題沒有多項式時間算法.,Cook定理：SAT為NP問題.,Cook計算復(fù)雜性理論的奠基性工作之一：第一個被證明的NPC問題！是證明許多其他NPC問題的出發(fā)點.,NP完全問題類(NPC) 證明（例）,例 三精確覆蓋（X3C）屬于NPC.,SAT多項式歸約為X3C,X3CNP （例1.19）,X3C NPC,例 （特殊）（0-1）背包判定問題屬于NPC.,X3C多項式變換為背包判定問題,背包判定問題NP,背包判定問題 NPC,NP完全問題類(NPC) 補(bǔ)充說明:,算法復(fù)雜性研究