組合優(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ī)劃：隨機規(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為目標函數(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的箱子裝進給定的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）目標函數(shù) ，對每一個實例I和每一個可行解 ，賦以一個有理數(shù) .如果 是極小化（極大化）問題，則實例I 的最優(yōu)解為這樣一個可行解 ，它使得對于所有 ，它都有,算法 定義,定義：算法是指一步步求解問題的通用程序，它是解決問題的程序步驟的一個清晰描述.,定型算法，即算法從前一步到后一步的運行是由當時狀態(tài)唯一確定的.,如果存在一

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

5、.設(shè)有一個容積為b的背包，如何以最大的價值裝包？,平行機排序問題,M個完全相同的機器，n個相互獨立的工件，加工時間互不相同，每個工件只需在任一臺機器上不中斷建工一次，如果安排加工方案，才能使預(yù)定的加工時間最短？,計算復(fù)雜性的概念,多項式時間算法,對于組合優(yōu)化問題，我們關(guān)心的一般不是最優(yōu)解的存在性和唯一性，而是如何找到有效的算法求得一個最優(yōu)解. 那么如何衡量算法的優(yōu)劣、有效與無效呢？,完全枚舉法可以求得最優(yōu)解,但枚舉時間有時不可能接受,ATSP: (n-1)!枚舉(TOUR,周游或環(huán)游) 設(shè)計算機每秒進行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在計算機計算時的二進制輸入數(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、). 當不存在多項式函數(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)的算法為強多項式(Strongly Polynomial)時間算法.,一般來說，偽多項式算法并不是多項式算法.,計算復(fù)雜性的概念,TSP等許多問題至今沒有找到多項式時間算法,但尚未證明其不存在,定義 對于給定的一個優(yōu)化問題，若存在一個求解該問題最優(yōu)解的多項式時間算法，則稱給定的優(yōu)化問題是多項式可解問題，或簡稱多項式問題，所有多項式問題集記為P(Polynomial).,同樣道理, 可以定義強多項式問題,偽多項式問題等.,TSP是否存在多項式時間算法? - 這是21世紀數(shù)學(xué)和計算機科學(xué)的挑戰(zhàn)性問題之一,多項式問題,問題、實例與輸入規(guī)模,評價一個算法的依據(jù)是該算法在最壞實例