組合優(yōu)化及算法-共36頁(yè)P(yáng)PT課件

1、組合優(yōu)化Combinatorial Optimization 組合優(yōu)化是運(yùn)籌學(xué)的后繼課程，同時(shí)也是運(yùn)籌學(xué)的一個(gè)重要獨(dú)立分支，是一類(lèi)重要的優(yōu)化問(wèn)題最優(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)又稱(chēng)離散優(yōu)化（Discrete Optimization），它是通過(guò)數(shù)學(xué)方法去尋找離散事件的最優(yōu)編排、分組、次序或篩選等. 這類(lèi)問(wèn)題可用數(shù)學(xué)模型描述為： 優(yōu)化問(wèn)題三要素: (Min,f,F)或(Ma

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

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

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

5、M個(gè)完全相同的機(jī)器，n個(gè)相互獨(dú)立的工件，加工時(shí)間互不相同，每個(gè)工件只需在任一臺(tái)機(jī)器上不中斷建工一次，如果安排加工方案，才能使預(yù)定的加工時(shí)間最短？計(jì)算復(fù)雜性的概念 多項(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 (年) 計(jì)算復(fù)雜性的概

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

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

8、的算法是非多項(xiàng)式時(shí)間算法, 或指數(shù)(時(shí)間)算法(Exponential time algorithm)輸入規(guī)模增大時(shí)，多項(xiàng)式時(shí)間算法的基本計(jì)算總次數(shù)的增加速度相對(duì)較慢. 多項(xiàng)式時(shí)間算法注：上面定義中，要求對(duì)該問(wèn)題的任意一個(gè)實(shí)例均成立 ，這種分析方法稱(chēng)為最壞性能分析（Worst-Case Analysis）1.4 計(jì)算復(fù)雜性的概念 1.4.2 多項(xiàng)式時(shí)間算法 近似值n101001000nlogn336649966n2100104106n31000106109108n41012101610202n10241.27e31.05e3010n101010100101000nlogn20791.93e17

9、.89e29n!3628800101584e2567計(jì)算復(fù)雜性的概念 多項(xiàng)式時(shí)間算法 算法復(fù)雜性研究中:常將算法的計(jì)算時(shí)間表示為： 問(wè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ù)，則稱(chēng)相應(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ù)（即該多

10、項(xiàng)式函數(shù)不包含logK）, 則稱(chēng)相應(yīng)的算法為強(qiáng)多項(xiàng)式(Strongly Polynomial)時(shí)間算法. 一般來(lái)說(shuō)，偽多項(xiàng)式算法并不是多項(xiàng)式算法. 計(jì)算復(fù)雜性的概念 TSP等許多問(wèn)題至今沒(méi)有找到多項(xiàng)式時(shí)間算法,但尚未證明其不存在定義 對(duì)于給定的一個(gè)優(yōu)化問(wèn)題，若存在一個(gè)求解該問(wèn)題最優(yōu)解的多項(xiàng)式時(shí)間算法，則稱(chēng)給定的優(yōu)化問(wèn)題是多項(xiàng)式可解問(wèn)題，或簡(jiǎn)稱(chēng)多項(xiàng)式問(wèn)題，所有多項(xiàng)式問(wèn)題集記為P(Polynomial). 同樣道理, 可以定義強(qiáng)多項(xiàng)式問(wèn)題,偽多項(xiàng)式問(wèn)題等.TSP是否存在多項(xiàng)式時(shí)間算法? - 這是21世紀(jì)數(shù)學(xué)和計(jì)算機(jī)科學(xué)的挑戰(zhàn)性問(wèn)題之一多項(xiàng)式問(wèn)題問(wèn)題、實(shí)例與輸入規(guī)模評(píng)價(jià)一個(gè)算法的依據(jù)是該算法在最壞實(shí)

11、例下的計(jì)算時(shí)間與實(shí)例輸入規(guī)模的關(guān)系：?jiǎ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已知. 比多項(xiàng)式問(wèn)題類(lèi)可能更廣泛的一個(gè)問(wèn)題類(lèi)是非確定多項(xiàng)式 (Nondeterministic Polynomial，簡(jiǎn)記 NP ) 問(wèn)題類(lèi) 存在多項(xiàng)式算法的問(wèn)題集合：多項(xiàng)式問(wèn)題類(lèi)（P）存在多項(xiàng)式函數(shù) g(x) 滿(mǎn)足上式時(shí)，算法為多項(xiàng)式算法NP 類(lèi)是通過(guò)判定問(wèn)題引入的。對(duì)任何一個(gè)優(yōu)化問(wèn)題， 可以考慮其三種形式：最優(yōu)化形式（原形：最優(yōu)解）計(jì)值形式（最優(yōu)值）判定

12、形式（上界）定義 如果一個(gè)問(wèn)題的每一個(gè)實(shí)例只有“是”或“否”兩種答案，則稱(chēng)這個(gè)問(wèn)題為判定問(wèn)題(Decision / recognition / feasibility problem). 稱(chēng)有肯定答案的實(shí)例為“是”實(shí)例(yes-instance). 稱(chēng)答案為“否”的實(shí)例為“否”實(shí)例或非“是”實(shí)例(no-instance). 判定問(wèn)題 - 定義 例 線性規(guī)劃問(wèn)題(LP)的判定形式LP判定問(wèn)題：給定一個(gè)實(shí)數(shù)值z(mì)，(LP)是否有可行解使其目標(biāo)值不超過(guò)z？ 即：給定z，是否有 ? 難度降低就有效算法的存在性而言，通常認(rèn)為三種形式等價(jià)！ 文字集 例 適定性問(wèn)題(Satisfiability proble

13、m)在邏輯運(yùn)算中，布爾變量x的取值只有兩個(gè)：“真”(1)和“假”(0)，邏輯運(yùn)算有“或（+）”，“與（）”和“非（）. 判定問(wèn)題 - 例存在真值分配的表達(dá)式稱(chēng)為適定的(可滿(mǎn)足的) +0000111011110000101001110110文字集的任意一個(gè)子集中各元素（布爾變量）的“或”運(yùn)算組成一個(gè)句子,多個(gè)句子的“與”運(yùn)算組成一個(gè)表達(dá)式，如 適定性問(wèn)題：給定布爾表達(dá)式 ，（SAT）是適定的嗎？ 判定問(wèn)題 - 例例 三精確覆蓋(3-Exact Covering：X3C)已知 的n個(gè)子集構(gòu)成的子集族 ，其中每個(gè)子集包含S中三個(gè)元素，F(xiàn)中是否存在m個(gè)子集 ，使得 ？若m個(gè)子集滿(mǎn)足上式，則稱(chēng)這m個(gè)子集

14、精確覆蓋S. 定義 若存在一個(gè)多項(xiàng)式函數(shù)g(x)和一個(gè)驗(yàn)證算法H，對(duì)一類(lèi)判定問(wèn)題A的任何一個(gè)“是” 實(shí)例I，都存在一個(gè)字符串S是I的可行解，滿(mǎn)足其輸入長(zhǎng)度d(S)不超過(guò)g(d(I)，其中d(I)為I的輸入長(zhǎng)度，且算法H驗(yàn)證S為實(shí)例I的可行解的計(jì)算時(shí)間f(H)不超過(guò)g(d(I)，則稱(chēng)判定問(wèn)題A是非確定多項(xiàng)式的。考慮將求解判定問(wèn)題的算法分為兩個(gè)階段：（1）猜測(cè)階段：求出或猜測(cè)該問(wèn)題的一個(gè)解（2）檢查或驗(yàn)證階段：一旦解已經(jīng)選定，將猜測(cè)的解作為輸入，驗(yàn)證此解是否為該實(shí)例“是”的回答. 我們稱(chēng)實(shí)例“是”回答的解為實(shí)例的可行解，否則稱(chēng)為不可行解. 所有非確定多項(xiàng)式問(wèn)題的集合用NP表示. 非確定多項(xiàng)式問(wèn)題類(lèi)

15、(NP) 定義構(gòu)造字符串（解）的過(guò)程及驗(yàn)證算法H一起構(gòu)成一個(gè)算法，稱(chēng)為非確定多項(xiàng)式（時(shí)間）算法。F中m個(gè)元素 是S的一個(gè)精確三覆蓋的充分必要條件為：相應(yīng)的m個(gè)向量滿(mǎn)足集合S中共有3m個(gè)元素，子集族F中的每個(gè)子集合對(duì)應(yīng)一個(gè)3m維向量：向量的3m個(gè)分量對(duì)應(yīng)3m個(gè)元素，元素包含在對(duì)應(yīng)子集中的分量為1，余下的為0. 例如： S= ，F(xiàn)中的一個(gè)元素 ，對(duì)應(yīng)向量為 = (1,1,0,0,0,1)，表示為一個(gè)字符串(110001). 非確定多項(xiàng)式問(wèn)題類(lèi)(NP) 例按字符串向量問(wèn)題，精確三覆蓋 “是”實(shí)例的任何一個(gè)解可以用長(zhǎng)度為3m2 的字符表示. 驗(yàn)證是否可行解的算法最多需3m2 個(gè)加法和3m個(gè)比較，算法的

16、計(jì)算時(shí)間為3m2 +3m. 例 三精確覆蓋屬于NP三精確覆蓋問(wèn)題任何一個(gè)實(shí)例的輸入長(zhǎng)度d(I)3m. 選g(x)= x2 /3+x ，則定義條件滿(mǎn)足，所以三精確覆蓋屬于NP. 非確定多項(xiàng)式問(wèn)題類(lèi)(NP) 問(wèn)題A2的難度不低于問(wèn)題A1 定義 給定問(wèn)題A1和A2，若存在一個(gè)多項(xiàng)式算法滿(mǎn)足： 對(duì)A1的任何一個(gè)實(shí)例I1，算法將實(shí)例I1的輸入轉(zhuǎn)換為A2的一個(gè)實(shí)例I2的輸入； 這種轉(zhuǎn)換過(guò)程使得實(shí)例I1和I2的解一一對(duì)應(yīng)，即將實(shí)例I1的一個(gè)解x1的輸入轉(zhuǎn)換為實(shí)例I2的一個(gè)解x2的輸入，且x1為I1的“是”答案 x2是I2的一個(gè)“是”答案；則稱(chēng)A1問(wèn)題多項(xiàng)式轉(zhuǎn)換為A2問(wèn)題，算法稱(chēng)為問(wèn)題A1到問(wèn)題A2的一個(gè)多項(xiàng)

17、式轉(zhuǎn)換（算法）(Transformation). 常用的研究方法 - 多項(xiàng)式轉(zhuǎn)換(變換)、多項(xiàng)式歸約(歸結(jié))若A1多項(xiàng)式轉(zhuǎn)換為A2，且A2P，則A1P若A1多項(xiàng)式轉(zhuǎn)換為A2，且A2NP，則A1NP多項(xiàng)式轉(zhuǎn)換(定義)NP完全問(wèn)題類(lèi)(NPC) -定義 已知判定問(wèn)題A1和A2，若存在多項(xiàng)式函數(shù) 和 ，使得對(duì)A1的任何實(shí)例I，在多項(xiàng)式時(shí)間內(nèi)構(gòu)造A2的一個(gè)實(shí)例，其輸入長(zhǎng)度不超過(guò) ，并對(duì)A2的任何一個(gè)算法H2，都存在問(wèn)題A1的一個(gè)算法H1，使得H1算法調(diào)用H2算法且使得計(jì)算時(shí)間，其中fH1(x)和fH2(x)分別表示算法H1和H2的計(jì)算時(shí)間與實(shí)例輸入長(zhǎng)度x之間的關(guān)系，則稱(chēng)問(wèn)題A1多項(xiàng)式歸約為問(wèn)題A2. 根

18、據(jù)A2的算法H2， 構(gòu)造A1的算法H1的過(guò)程，即映射 ：H2 H1稱(chēng)為從A1到A2的一個(gè)多項(xiàng)式歸約(reduction). 多項(xiàng)式歸約(定義)問(wèn)題A2的難度不低于問(wèn)題A1若A1多項(xiàng)式歸約為A2，且A2P，則A1P若A1多項(xiàng)式歸約為A2，且A2NP，則A1NP若A1多項(xiàng)式歸約為A2，則當(dāng)把H1對(duì)H2的一次調(diào)用當(dāng)成一次基本運(yùn)算時(shí)， H1是A1的多項(xiàng)式算法。NP完全問(wèn)題類(lèi)(NPC) - 多項(xiàng)式歸約多項(xiàng)式轉(zhuǎn)換是多項(xiàng)式歸約的特例歸約映射可以如下構(gòu)造： H1：STEP1 用多項(xiàng)式轉(zhuǎn)換將A1的實(shí)例轉(zhuǎn)換為A2的實(shí)例 STEP2 用H2算法求解A2的實(shí)例即多項(xiàng)式轉(zhuǎn)換可以認(rèn)為是只允許調(diào)用一次H2的多項(xiàng)式歸約NP完

19、全問(wèn)題類(lèi)(NPC)- 多項(xiàng)式歸約 （例）例1.22 適定問(wèn)題多項(xiàng)式歸約為三精確覆蓋問(wèn)題 定義（1）對(duì)于判定問(wèn)題A，若ANP且NP中的任何一個(gè)問(wèn)題可在多項(xiàng)式時(shí)間內(nèi)歸約為A，則稱(chēng)A為NP完全問(wèn)題(NP-Complete或NPC).可以表示為ANPC. NPC和NP-hard兩者的區(qū)別是: 驗(yàn)證一個(gè)問(wèn)題A是否為NP-hard無(wú)須判斷A是否屬于NP. 根據(jù)定義可知NPCNPH. 當(dāng)已知一個(gè)問(wèn)題屬于NPC或NPH時(shí)，如果再遇到一個(gè)新問(wèn)題：（1）若已知問(wèn)題多項(xiàng)式歸約為新問(wèn)題，則新問(wèn)題屬于NPH;NP完全問(wèn)題類(lèi)(NPC) 定義（2）對(duì)于判定問(wèn)題A，若NP中的任何一個(gè)問(wèn)題可在多項(xiàng)式時(shí)間歸約為判定問(wèn)題A，則稱(chēng)A

20、為NP困難問(wèn)題(NP-hard 或NPH) .可以表示為ANPH. （2）若還可以驗(yàn)證新問(wèn)題屬于NP，則新問(wèn)題屬于NPC. NP完全問(wèn)題類(lèi)(NPC)定理：如果問(wèn)題A是P問(wèn)題，且B可以在多項(xiàng)式時(shí)間內(nèi)歸約為A，則B也為P問(wèn)題.定理：P=NP當(dāng)且僅當(dāng)存在一個(gè)NPC問(wèn)題有多項(xiàng)式時(shí)間算法.定理：如果問(wèn)題A是NPC問(wèn)題，且B可以在多項(xiàng)式時(shí)間內(nèi)歸約為A，則B也為NPC問(wèn)題.定理：如果問(wèn)題A是NPH問(wèn)題，且B可以在多項(xiàng)式時(shí)間內(nèi)歸約為A，則B也為NPH問(wèn)題.NP完全問(wèn)題類(lèi)(NPC)定理：除非P=NP，否則NPH問(wèn)題沒(méi)有多項(xiàng)式時(shí)間算法.Cook定理：SAT為NP問(wèn)題.Cook計(jì)算復(fù)雜性理論的奠基性工作之一：第一個(gè)被證明的NPC問(wèn)題！是證明許多其他NPC問(wèn)題的出發(fā)點(diǎn).NP完全問(wèn)題類(lèi)(NPC) 證明（例）例 三精確覆蓋（X3C）屬于NPC. SAT多項(xiàng)式歸約為X3CX3CNP （例1.19）X3C NPC例 （特殊）（0-1）背包判定問(wèn)題屬于NPC. X3C多項(xiàng)式變換為背包判定問(wèn)題背包判定問(wèn)題NP背包判定問(wèn)題