數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性.ppt

1、1,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,組合優(yōu)化理論,Combinatorial Optimization Theory,2,第一章 組合優(yōu)化模型 與計(jì)算復(fù)雜性,1 組合優(yōu)化模型與算法,2 計(jì)算復(fù)雜性問題,3 啟發(fā)式算法,3,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,模型（model ）是所研究的系統(tǒng)、過程、事物或 概念的一種表達(dá)形式 .,1 組合優(yōu)化模型與算法,（一) 模型的概念,模型不是研究對象本身，而是對研究對象的一種 抽象，它反映現(xiàn)實(shí)中對象系統(tǒng)的主要特征，但它又高 于現(xiàn)實(shí)，因而具有同類問題的共性 .,由于研究目的的不同，對于同一個(gè)對象系統(tǒng)， 可以建立完全不同的模型，分別反映該系統(tǒng)的不同 側(cè)面；出

2、于相同的研究目的，對于同一個(gè)對象系 統(tǒng)，也可能建立不同的模型，反映不同的研究角 度、考察因素和價(jià)值取向 .,一、關(guān)于模型,4,1 組合優(yōu)化模型與算法,（二） 模型的本質(zhì),從系統(tǒng)概念上看，模型是系統(tǒng)中各種關(guān)系的表達(dá) 形式 . 因此，建立模型要從狀態(tài)和過程兩個(gè)方面去尋 找、把握和描述各系統(tǒng)要素之間的相互關(guān)系 .,狀態(tài)：事物在某個(gè)時(shí)刻所處的狀況或表現(xiàn)形態(tài),過程：事物狀態(tài)的變化在時(shí)間上的持續(xù)和空間上的延伸,過程和狀態(tài)兩者緊密聯(lián)系、不可分割，狀態(tài)決 定和影響過程，過程又決定和影響新的狀態(tài) .,狀態(tài)和過程是相對的 .,5,從認(rèn)識論上看，模型是作為認(rèn)識與實(shí)踐活動的中介 .,現(xiàn)實(shí)世界,認(rèn)識（信息）,模 型,實(shí)

3、踐活動,概念化,用信息載體表達(dá),決策（行動方案）,產(chǎn)品和服務(wù),模型化過程示意圖,模型既是認(rèn)識的表達(dá)，又是實(shí)踐活動的先導(dǎo) .,模型參與認(rèn)識世界和改造世界的不斷的循環(huán)往復(fù) 過程，既是認(rèn)識不斷深化的體現(xiàn)，又是實(shí)踐活動不斷 拓展的體現(xiàn) .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,6,1 組合優(yōu)化模型與算法,從信息論上看，模型和認(rèn)識之間存在密切的反饋 關(guān)系 . 從已知信息可以通過模型加工產(chǎn)生出新的信 息，相關(guān)信息的積累可以從量變產(chǎn)生質(zhì)變，形成新的 概念，促使認(rèn)識深化 .,因此，模型的建立和完善不僅要注重對系統(tǒng)物質(zhì) 形態(tài)和能量形態(tài)的認(rèn)識、把握和描述，而且也依賴于 對系統(tǒng)相關(guān)信息不斷的采集、積累和加工，這就是用

4、模型研究問題的現(xiàn)實(shí)活動 .,7,（三） 模型的分類,1、原樣模型,原樣模型是在工程開發(fā)末期建立的一種具象實(shí) 體，是具有實(shí)物形態(tài)的模型 .,它與目的工程在結(jié)構(gòu)和過程方面基本相同 .,原樣模型經(jīng)過試驗(yàn)改進(jìn)和完善后便是所要開發(fā) 的目的工程 .,新產(chǎn)品的樣機(jī)、新著作的原稿 ,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,8,1 組合優(yōu)化模型與算法,2、相似模型,相似模型是根據(jù)不同系統(tǒng)間的相似規(guī)律（包括幾 何相似、邏輯相似和過程相似等）而建立的用于研究 的模型 .,3、圖形模型,地球儀、船體放樣 模型、飛機(jī)風(fēng)洞實(shí)驗(yàn)?zāi)?擬模型等等,圖形模型可以表達(dá)非常豐富的內(nèi)容，主要有：, 圖畫 一種可以示形的圖形；, 草圖 一種可

5、以示意的圖形；, 框圖 一種可以表示系統(tǒng)的部分之間或部分 與整體之間聯(lián)系的圖形；,稱為不嚴(yán)格圖 （沒有嚴(yán)格的規(guī)范）,系統(tǒng)分析和設(shè)計(jì)人員常常借助于這些圖形模型來 開發(fā)、構(gòu)建一個(gè)新系統(tǒng)的想象力和創(chuàng)造力，逐步引申 出與之有關(guān)的問題和需要進(jìn)一步探索的問題，使所要 開發(fā)的系統(tǒng)變得越來越清晰、越來越具體 .,9, 邏輯圖 一種可以反映因素或?qū)ο箝g邏輯關(guān)系 的圖形；,如：程序流程圖、控 制關(guān)系圖 etc., 工程圖 一種可以反映物體確定的結(jié)構(gòu)和順序 關(guān)系的圖形；,如：建筑工程圖、鐵路站場配置圖 etc., 圖論圖 包括圖論所定義的無向圖 G(V，E) 、 有向圖 G(V，A)、加權(quán)有(無)向圖G(V，A(E

6、)，w).,關(guān)系,稱為嚴(yán)格圖 （有嚴(yán)格確定的結(jié)構(gòu)形式和規(guī)范）,4、數(shù)學(xué)模型,數(shù)學(xué)模型是指運(yùn)用數(shù)學(xué)符號和公式來表達(dá)、研究 對象系統(tǒng)的結(jié)構(gòu)或過程的模型 .,數(shù)學(xué)模型是用數(shù)學(xué)的語言、方法去近似地刻畫實(shí)際 , 是由數(shù)字、字母或其他數(shù)學(xué)符號組成的，描述現(xiàn)實(shí)對 象數(shù)量規(guī)律的數(shù)學(xué)公式、圖形或算法 .,是對現(xiàn)實(shí)對象本質(zhì)屬性的抽象而又簡潔的刻畫， 它或能解釋某些客觀現(xiàn)象，或能預(yù)測未來的發(fā)展規(guī) 律，或能為控制某一現(xiàn)象的發(fā)展提供某種意義下的最 優(yōu)策略或較好策略 .,Go back,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,10,二、 數(shù)學(xué)模型,Example 1,七橋問題,18世紀(jì)的德國有個(gè)哥尼斯堡城，在流貫全城的普 雷爾

7、河兩岸和河中兩個(gè)島之間架設(shè)了七座橋，把河的 兩岸和兩島連接起來，能否有這樣一種走法，它通過 每座橋一次且僅一次 .,該問題由Euler在1736年解決,Solution :,1 組合優(yōu)化模型與算法,11,A,B,C,D,顯然，解決該問題時(shí)， 兩岸和島的大小、形狀以及 橋的長短曲直都無關(guān)，重要 的是什么？,每塊陸地間有幾座橋,對問題進(jìn)行數(shù)學(xué)抽象：,把兩岸和兩島都看做頂點(diǎn)，將連接這些頂點(diǎn)的橋 當(dāng)作邊，于是得到一無向圖 .,則七橋問題就成為無向圖中是否存在通過每一邊 一次且僅一次的路（即一筆畫）問題 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,12,1 組合優(yōu)化模型與算法,A,B,C,D,Euler 在他

8、的論文中證明：,一個(gè)圖中存在一筆畫的 充要條件是同時(shí)滿足：,1、圖是連通的；,2、與圖中每一頂點(diǎn)（可能有兩點(diǎn)例外）相連的邊 （線度）必須是偶數(shù)條 .,這是關(guān)于圖論 的第一篇論文,見圖可知，與四個(gè)頂點(diǎn)相連的邊都是奇數(shù)條，因 而不可能存在通過每條邊一次且僅一次的畫法，即一 筆畫不存在 . 故七橋問題不可能有解 .,問題原型 七橋問題,數(shù)學(xué)模型 一筆畫問題,無 解 (一次過七座橋不可能),無 解 (一筆畫不可能),數(shù)學(xué)抽象,邏輯推理,翻譯回去,有無解？,這是利用數(shù)學(xué)模型分析和解決問題的一個(gè)成功范例,13,（一） 數(shù)學(xué)模型的特點(diǎn),1、高度的抽象性,數(shù)學(xué)方法不僅要拋開事物的次要屬性，突出事物 的本質(zhì)屬性

9、，而且要舍棄事物的物質(zhì)和能量方面的具 體內(nèi)容，只考慮其數(shù)量關(guān)系和空間形式，同時(shí)還要把 這些數(shù)量關(guān)系和空間形式作進(jìn)一步的抽象，加以形式 化和符號化，以便能夠進(jìn)行邏輯推理和數(shù)值運(yùn)算 .,這種高度的抽象性，實(shí)質(zhì)是對事物認(rèn)識上的高度 概括和深化，對同類問題包含更多的經(jīng)驗(yàn)和理解 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,14,1 組合優(yōu)化模型與算法,2、高度的精確性,數(shù)學(xué)方法的高度精確性表現(xiàn)在三個(gè)方面：,一是表達(dá)各種因素、變量和它們之間的關(guān)系相當(dāng) 明確、清楚；二是邏輯推演和運(yùn)算規(guī)則十分嚴(yán)密；三 是結(jié)論非常確定 .,數(shù)學(xué)方法可以處理多變量、關(guān)系復(fù)雜的問題，可 在有意義的范圍內(nèi)獲得令人滿意的計(jì)算精度 .,特別適

10、合于揭示事物的量的規(guī)定性，成為定量研 究的有力工具 .,15,3、應(yīng)用的普適性,數(shù)學(xué)方法的高度抽象和精確，使之比任何一種科 學(xué)方法的應(yīng)用范圍都更為廣泛 .,只存在尚未運(yùn)用數(shù)學(xué)方法的領(lǐng)域而不存在不能運(yùn) 用數(shù)學(xué)方法的領(lǐng)域 .,許多相同形式的數(shù)學(xué)模型可用于不同的實(shí)際問 題，具有重要類比和借鑒意義 .數(shù)學(xué)方法的形式化和 公理化，使模型本身、計(jì)算過程和計(jì)算結(jié)果都便于交 流，數(shù)學(xué)模型易變動，便于修改和改變計(jì)算關(guān)系，分 析和求解問題速度快，求解成本低 .,數(shù)學(xué)模型缺乏直觀性、形象性和實(shí)時(shí)感,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,16,1 組合優(yōu)化模型與算法,（二） 數(shù)學(xué)模型分類,數(shù)學(xué)模型分類的方法很多，如：,1

11、、按所研究問題的性質(zhì)分類, 靜態(tài)模型與動態(tài)模型, 確定型模型與隨機(jī)型模型, 連續(xù)模型與離散模型, 線性模型與非線性模型, 宏觀模型與微觀模型,17,2、按模型的解的特征分類,解析模型與數(shù)值模型,3、按模型所用的數(shù)學(xué)方法分類,初等模型、微分方程模型、差分方程模型、優(yōu) 化模型等,4、按模型研究的實(shí)際范疇分類,人口模型、生態(tài)系統(tǒng)模型 、交通流模型、經(jīng)濟(jì) 模型、 基因模型等,5、按對實(shí)際問題了解的程度分類,白箱模型、灰箱模型、黑箱模型,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,18,1 組合優(yōu)化模型與算法,（三） 數(shù)學(xué)建模的基本步驟,數(shù)學(xué)模型因問題不同而異，對同一問題，從不同 角度、不同要求出發(fā)，甚至問題的解

12、表示結(jié)構(gòu)不同， 都可以建立不同的數(shù)學(xué)模型. 建立數(shù)學(xué)模型也沒有固 定的方法、標(biāo)準(zhǔn) . 不同的實(shí)際問題，建模模式千差萬 別.,在此介紹通常的幾個(gè)步驟：,數(shù)學(xué)建模問題直接來源各領(lǐng)域?qū)嶋H，往往含糊不 清（目的、條件、類型 etc.）. 首先，要對該問題進(jìn) 行全面的、深入細(xì)微的調(diào)查和研究. 明確所解決問題 的性質(zhì)，著手收集數(shù)據(jù) ；,1、明確問題,合理地、有目的地,注意精度,19,2、合理假設(shè),現(xiàn)實(shí)問題錯(cuò)綜復(fù)雜，涉及面非常之廣. 一個(gè)數(shù)學(xué) 模型面面俱到、無所不包地反映一個(gè)現(xiàn)實(shí)是不可能 的，即使可能，也因其過于復(fù)雜而很難求解，也是沒 有必要的 . 所以，要作合理的假設(shè) .,1、簡化問題 2、限定適用范圍,

13、但也不能忽略實(shí)質(zhì)相關(guān)的因素,作假設(shè)的依據(jù)通常是出于對問題內(nèi)在規(guī)律的認(rèn)識, 或來自對數(shù)據(jù)或現(xiàn)象的分析，也可以是二者的綜合. 善于辨別問題的主次，抓住主要因素，通過合理假設(shè), 使問題簡化以便進(jìn)行數(shù)學(xué)描述 .,假設(shè)是在模型的建立、求解和分析過程中完善 .,通常開始讓問題盡可能簡化,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,20,1 組合優(yōu)化模型與算法,3、建立模型,建模時(shí)，要分清問題的類型恰當(dāng)使用數(shù)學(xué)工具； 抓住問題的本質(zhì)簡化變量之間的關(guān)系 .,用什么樣的方法建立數(shù)學(xué)模型，沒有絕對的標(biāo) 準(zhǔn)；數(shù)學(xué)模型的形式可以是多種多樣，數(shù)學(xué)公式、表 格、圖形、算法 .,模型的優(yōu)劣在于是否采用了恰當(dāng)?shù)姆椒ǎ侠淼?描述了實(shí)際

14、問題，而不在于是否用到了高深的數(shù)學(xué)工 具 .,數(shù)學(xué)建模是一個(gè)過程 .,21,4、模型求解,不同的模型要用到不同的數(shù)學(xué)工具求解 . 這就要 求從事實(shí)際工作者對相應(yīng)的數(shù)學(xué)分支知識有一定的了 解 .,可借助計(jì)算機(jī)，特別是利用數(shù)學(xué)工具軟件 .,5、模型分析,對模型求出的解進(jìn)行數(shù)學(xué)上的分析，有助于對實(shí) 際問題的解決 .,如：, 結(jié)果的誤差分析,誤差是否在允許的范圍內(nèi),分析誤差來源：,建模假設(shè)的誤差；,數(shù)據(jù)測量的誤差；,近似求解方法的誤差；,計(jì)算工具的舍入誤差 ., 結(jié)果的統(tǒng)計(jì)分析,結(jié)果是否符合特定的統(tǒng)計(jì)規(guī)律, 模型對數(shù)據(jù)的靈敏度分析,模型的結(jié)果是否會因數(shù)據(jù)的微小改變而發(fā)生大的變化, 對假設(shè)的魯棒性分析,

15、模型的結(jié)果是否對某一假設(shè)非常依賴, 不同模型間的對比分析,robustness,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,22,1 組合優(yōu)化模型與算法,6、模型檢驗(yàn),將求解結(jié)果和分析結(jié)果翻譯回到實(shí)際問題之中， 與實(shí)際現(xiàn)象、實(shí)際數(shù)據(jù)進(jìn)行比較，檢驗(yàn)是否與實(shí)際吻 合 . 如果吻合較好，則模型及其結(jié)果可以應(yīng)用于實(shí)際 問題；如果吻合不好，則需要對模型進(jìn)行修正 .,7、改進(jìn)模型,吻合不好，問題常常出現(xiàn)在模型假設(shè)上 . 可能由 于假設(shè)了過于苛刻的條件，或者忽略了一些不該忽略 的因素. 所以, 要對實(shí)際問題中的主次因素再次分析, 對模型進(jìn)行修改、補(bǔ)充、完善 . 需要多次反復(fù)才能達(dá) 到比較滿意的程度 。,23,8、模型

16、應(yīng)用,數(shù)學(xué)建模最終的目的是為了解決問題 . 一方面可 以解釋以前的實(shí)踐成果；另一方面可以為現(xiàn)在的實(shí)際 問題提供解決方案，甚至可以對一些不確定的現(xiàn)象或 規(guī)律作出預(yù)測 .,現(xiàn)實(shí)問題,簡化、假設(shè),建立模型,求解模型,檢驗(yàn)分析模型,模型應(yīng)用,觀察、分析,收集數(shù)據(jù),確定主要因素,及相互關(guān)系,Go back,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,24,三、 組合優(yōu)化模型,Example 2,某商場根據(jù)客流量統(tǒng)計(jì)得出一周中每天所需要的 營業(yè)員數(shù)如表：,營業(yè)員配置問題,如果規(guī)定每個(gè)營業(yè)員每周連續(xù)工作 5 天，休息 2 天，求總?cè)藬?shù)最少的營業(yè)員排班方案 .,Solution :,設(shè) xj 為從周 j 開始連續(xù)工作

17、5 天的營業(yè)員 人數(shù)，j = 1,7 (其中 x7 為周日開始連續(xù)工作 5 天的 營業(yè)員數(shù))，則,可行解集是有限集,1 組合優(yōu)化模型與算法,25,Example 3 旅行商問題,（Traveling Salesman Problem）,TSP :,有一位旅行售貨員，欲到城市 v1，v2,，vn 進(jìn)行商品銷售，已知： 的距離為 wij.( , ).他從其中某個(gè)城市出發(fā)，需訪問每一個(gè) 城市一次而回到出發(fā)的城市.問應(yīng)如何計(jì)劃他的旅行 路線，使他所走路線的總長度最短？,TSP可分為：對稱（dij = dji) 和非對稱（dij dji）距離兩種,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,26,1 組合優(yōu)化模型

18、與算法,Hamilton 回路：,不含平行邊及自環(huán),這是1856年，Hamilton 首先提出的所謂環(huán)球 航行問題而得名。它的存在性遠(yuǎn)比 Eular 回路的存 在性復(fù)雜得多。,最優(yōu) Hamilton 回路：,在賦權(quán)圖中，權(quán)和最小的 Hamilton 回路 .,過簡單圖 G 的每一個(gè)頂點(diǎn)一次且僅一次的回路 .,27,最優(yōu)旅行商問題與最優(yōu) Hamilton 回路一樣嗎？,如果不滿足三角不等式，則可通 過求最短路方法，構(gòu)造新圖，使之滿 足三角不等式 . 所以以下僅討論最優(yōu) 的 Hamilton 回路 .,2 5,2 3,Theorem 1 如果賦權(quán)圖滿足三角不等式 （歐氏距離），則它的最優(yōu)旅行商回路

19、 與最優(yōu) Hamilton 回路相同 （Hamilton 回路存在時(shí)）.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,28,1 組合優(yōu)化模型與算法,TSP 問題的數(shù)學(xué)模型（非對稱的）：,v6,v4,v5,v3,v2,v1,Note：條件(1)，(2)表示每個(gè)城市經(jīng)過一 次，但不能保證它可行.,要求局部不構(gòu)成圈，條件(3)就是為 了約束這一點(diǎn) .,29,共同特點(diǎn)：可行方案是有限的 組合優(yōu)化問題,Definition 1 組合優(yōu)化問題是一個(gè)極小化（或極大 化）的問題，它是由以下三部分組成：,（1）實(shí)例集合 ；,（2）對每個(gè)實(shí)例 I，有一個(gè)有窮的可行解集合 S(I)；,（3）目標(biāo)函數(shù) f ，它對于每個(gè)實(shí)例 I

20、 和每個(gè)可行解 S(I)，賦以一個(gè)實(shí)數(shù) f (I, ). 則實(shí)例I的最優(yōu)解為 這樣一個(gè)可行解 * S(I) ,它使得對于所有S(I)， 都有 (I, *) f (I, ) （f (I, *) f( I, )）.,問題：一類實(shí)際問題的數(shù)學(xué)模型的總稱，如TSP、 LP etc ； 實(shí)例：（一個(gè)問題中總包含了若干個(gè)參數(shù)）對問題 給定一組參數(shù)所得到的例子.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,30,1 組合優(yōu)化模型與算法,組合優(yōu)化的數(shù)學(xué)模型：,Min f(x) s.t. g(x) 0 xD,其中x為決策變量,f(x)為目標(biāo)函數(shù),g(x)為約束函數(shù),D為決策變量的定義域,F=x|x D, g(x) 0可行

21、域(有限集),很多組合優(yōu)化問題都可以給出整數(shù)線性規(guī)劃描 述，甚至在一些時(shí)候還不得不利用整數(shù)線性規(guī)劃的技 巧來解 . 當(dāng)然也可以用文字、網(wǎng)絡(luò)等來敘述 .,線性規(guī)劃是連續(xù)模型，但由于它的解的特殊結(jié) 構(gòu)，也可以作為組合優(yōu)化問題考慮 .,31,四、 關(guān)于算法,有兩種思想，像珠寶商放在天鵝絨上的寶石一樣 熠熠生輝，一個(gè)是微積分，另一個(gè)就是算法，微積分 以及在微積分基礎(chǔ)上建立起來的數(shù)學(xué)分析體系造就了 現(xiàn)代科學(xué)，而算法則造就了現(xiàn)代世界 .,伯林斯基（D. Berlinski ）,算法思想：指通過把數(shù)學(xué)問題的求解分解為簡單的、 刻板的、重復(fù)的機(jī)械動作，達(dá)到以數(shù)目較多的、簡單 的量的工作去實(shí)現(xiàn)較復(fù)雜的質(zhì)的目的

22、.,算法思想是數(shù)學(xué)發(fā)展的一個(gè)重要源泉,20 世紀(jì)中葉計(jì)算機(jī)的問世是人類智力最偉大的成 就之一 . 算法是計(jì)算機(jī)的靈魂，隨著計(jì)算機(jī)融入現(xiàn)代 科學(xué)實(shí)踐和社會生活的各個(gè)方面，算法思想的意義與 作用日益為數(shù)學(xué)家所認(rèn)識 . 是數(shù)學(xué)發(fā)展的機(jī)械化之路.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,32,一個(gè)科學(xué)的計(jì)算過程，指一步步求解問題的通 用程序，它是解決問題的程序步驟的一個(gè)清晰 描述 .,算法是相對問題而言的，不單單是針對問題的 某個(gè)實(shí)例 .,算法：,Note：,假設(shè)你想把某個(gè)解決問題的方法傳授給一臺沒有 任何智能的機(jī)器，以便由它來幫你完成解決這類問題, 機(jī)器會要求你怎么做？,( 算法的能行性 ),你當(dāng)然不能只

23、告訴它一個(gè)大概或者模棱兩可、含 糊其辭，而應(yīng)該明確無誤地告訴它所有解決問題的細(xì) 節(jié)，而且這些細(xì)節(jié)應(yīng)詳細(xì)到機(jī)器可以執(zhí)行的程度（機(jī) 械性）；你當(dāng)然也不可能無休止地進(jìn)行傳授，而只能 用到一些有限的符號，告訴它一些有限的規(guī)則（有限 性） .,1 組合優(yōu)化模型與算法,33,如果算法從前一步到后一步的運(yùn)行是由 當(dāng)時(shí)狀態(tài)唯一確定的. 如：單純形 法，表上作業(yè)法 .,遺傳算法是隨機(jī)性算法 .,確定性算法：,數(shù)學(xué)上常常將算法分為數(shù)值算法和非數(shù)值算法 . 一般來說，數(shù)值算法用于科學(xué)計(jì)算，主要進(jìn)行代數(shù)運(yùn) 算；而非數(shù)值算法則用于數(shù)據(jù)處理，主要進(jìn)行比較和 邏輯運(yùn)算（也含代數(shù)運(yùn)算） .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,

24、34,對于一個(gè)極小化（極大化）優(yōu)化問題， 如果給定任意一個(gè)實(shí)例I，算法A總能找到一個(gè)可 行解* S（I）。 使得 f(I, *) f(I, )（f(I, *) f(I, )）,啟發(fā)式算法（近似算法，在4 中介紹）,組合優(yōu)化總存在最優(yōu)算法，僅討論可計(jì)算問題,最優(yōu)算法：,是否任何數(shù)學(xué)問題都有算法求解嗎？,答案是否定的 （不可計(jì)算）,停機(jī)問題：給定一個(gè)帶輸入的計(jì)算機(jī)程序，它會停機(jī) 嗎？,英國數(shù)學(xué)家圖靈 (Turing) 證明了不存在一 個(gè)算法，它能對該問題的一切實(shí)例給出正確答案 .,D.Hilbert 23個(gè)問題之10 Diophantus 方程的 可解性 . （求出一個(gè)整系數(shù)方程的整數(shù)根）,算法的

25、正確性不蘊(yùn)含算法的有效性,1 組合優(yōu)化模型與算法,35,五、 算法設(shè)計(jì)的基本方法,本節(jié)介紹算法設(shè)計(jì)的一些基本方法 . 在進(jìn)行復(fù)雜 的算法設(shè)計(jì)時(shí)，常常利用這些基本方法（思想），有 必要熟練掌握 .,（一） 窮舉法,窮舉法：窮舉所有可能的解并進(jìn)行比較和選優(yōu)的方法 .,優(yōu)點(diǎn)：獲得最優(yōu)解是確切無疑的（算法的正確性）,對于運(yùn)算規(guī)模較小的、運(yùn)算時(shí)間允許的優(yōu)化問 題，如無適合該問題的優(yōu)化算法時(shí)，可采用窮舉法 .,缺點(diǎn)：需要大量的機(jī)時(shí)和內(nèi)存空間（算法的有效性）,引言中對TSP問題已有說 明，復(fù)雜性為O(n-1)!),采用窮舉法的關(guān)鍵在于： 1、能否在理論上確定所求解問題的全部可行解集； 2、對所求解問題的全部

26、可行解集進(jìn)行比選是否可能. （計(jì)算時(shí)間復(fù)雜性）,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,36,（二） 登山法 （也稱貪心法）,登山法：從對問題的某一初始推測或初始解出發(fā)，逐 步逼近給定的目標(biāo)，并盡可能快地逼近更好的解；當(dāng) 進(jìn)行到某一步，不能再繼續(xù)逼近時(shí)，算法便終止 .,得到的是近似解 或局部最優(yōu)解,方法簡單、 適用面廣,登山法是一個(gè)多步?jīng)Q策過程，每一步的選擇都是 為了能構(gòu)成問題的一個(gè)可行解，同時(shí)使目標(biāo)函數(shù)的值 增加最大或最小 .,選擇過程是以某些最優(yōu)化量度為依據(jù) .,最優(yōu)化量度可以是目標(biāo)函數(shù)，也可以是別的量 度，它的選擇是登山法的關(guān)鍵 .,1 組合優(yōu)化模型與算法,37,TSP 的距離矩陣,Examp

27、le 2 用登山法求 TSP .,v5,v4,v3,v2,v1,4,1,4,3,2,3,5,7,2,1,Solution :,優(yōu)化準(zhǔn)則：最短距離.,從 v1 出發(fā)，有4 個(gè)選擇， 按優(yōu)化準(zhǔn)則：選 v2 ;,得： v1 v2 v5 v3 v4 v1,總距離為：14,復(fù)雜性為 O(n2) .,記?。簺]有免費(fèi)的午餐！,從選擇 p 個(gè)不同的 城市出發(fā)，分別用登山法得到 p 個(gè)結(jié)果 . 比較得距離和最短 的路線 .,復(fù)雜性為 O(pn2) .,但求得的解更接近于最優(yōu)解，如從 v2 出發(fā)，得：,v2 v1 v3 v4 v5 v2,總距離為：10,這是最優(yōu)解（運(yùn)氣好）.,也可以從一個(gè)可行解出 發(fā)，交換相鄰兩

28、個(gè)城市位置, 優(yōu)化準(zhǔn)則：總距離下降.,v1 v2 v5 v3 v4 v1,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,38,（三） 分枝與定界法,分枝與定界法的基本思想是對有約束條件的最優(yōu)化問 題的所有可行解（其數(shù)目為有限集）空間適當(dāng)?shù)剡M(jìn)行 搜索 .,具體執(zhí)行時(shí)，把可行解空間不斷分割為越來越小 的子集（稱為分枝），并確定每個(gè)分枝內(nèi)的解值的下 界或上界（稱為定界）. 在每次分枝后，對凡是界超 出已知可行解值的子集被剪去，從而不斷縮小搜索范 圍.,這個(gè)過程一直進(jìn)行到找出最優(yōu)解為止，該可行解 的值不大于或不小于任何子集的界 .,優(yōu)點(diǎn)：1、適用面廣 2、可檢查較少的解（運(yùn) 氣好）3、可獲得最優(yōu)解,缺點(diǎn)：本質(zhì)是窮

29、 舉，復(fù)雜性大于窮舉法,給出一個(gè)重要思想: 設(shè)門檻 (稱為隱枚舉),1 組合優(yōu)化模型與算法,39,設(shè),如果 則稱問題（2）是問題（1）的松弛問題.,Note :,1、松弛問題未必比原問題難解；,如：整數(shù)規(guī)劃與線性規(guī)劃；TSP 與指派問題 etc.,如： A：尋找全國18 歲百米最快的運(yùn)動員.,B：尋找全國所有百米最快的運(yùn)動員.,顯然，B 問題是 A 問題的松弛問題，且B 問題更易解 .,2、如果松弛問題易解，則先解松弛問題是有益的 .,1）設(shè) x0 是松弛問題的最優(yōu)解，且 則原問題已解,2）即使 給出了原問題最優(yōu)值的界 f(x0) .,x0,B,A,B,A,x0,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜

30、性,40,分枝與定界法為什么能少檢查一些解？,B,10s,B1,B2,10.2s,*,10s,B3,B4,10.3s,*,幾點(diǎn)注意：, 確定問題（子問題）的最優(yōu)值的界,通常是通過求解松弛問題， 用松弛問題的解作為界，也可 以用啟發(fā)式算法得到 .,Note : 松弛問題選擇的原則,1、松弛問題要與原問題的 最優(yōu)值盡量接近；,2、松弛問題要盡量容易解 .,這兩個(gè)原則不易統(tǒng)一，所以可選擇不同的松弛問題,1 組合優(yōu)化模型與算法,41, 劃分方法的選擇,原則是希望分出來的子問題容易被查清，可加快計(jì)算., 選哪個(gè)活問題先檢查,1、先檢查最大上界（極大化問題）的活問題,優(yōu)點(diǎn)：檢查子問題較其他規(guī)則為少；,缺點(diǎn)

31、：計(jì)算機(jī)儲存量較大 .,2、先檢查最新產(chǎn)生的最大上界的活問題,優(yōu)點(diǎn)：計(jì)算機(jī)儲存量較少 ；,缺點(diǎn)：需要更多的分支運(yùn)算 .,選擇的不同，提供了發(fā)揮的余地,分枝與定界法的重要在于它提出了一類新的思 路（隱枚舉法），使得許多原來不好解決的問題有 了解決的可能性. （具有普適性）,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,42,（四） 分治法,分治法就是把原問題分成若干個(gè)規(guī)模較小的子問題， 這些子問題互相獨(dú)立且與原問題形式相同，對每個(gè)子 問題分別求解，然后將各子問題的解合并得到原問題 的解 .,如果子問題仍較復(fù)雜，可遞歸使用上述方法 .,Note：問題的類別在細(xì)分過程中不允許改變，改變的 只是問題的尺度 .,分

32、治法的基本步驟：,分治法在每一層遞歸上都有三個(gè)步驟：,分解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立， 與原問題形式相同的子問題；,解決：若子問題規(guī)模較小而容易被解決則直接解，否 則遞歸地解各個(gè)子問題；,合并：將各個(gè)子問題的解合并為原問題的解.,1 組合優(yōu)化模型與算法,43,整序問題的快速算法是典型的分治策略運(yùn)用.,8 1 9 6 7 5 3 2,8,1,9,6,7,5,3,2,合并,合并,合并,合并,1 8,6 9,5 7,2 3,1 6 8 9,2 3 5 7,1 2 3 5 6 7 8 9,合并,合并,合并,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,44,分治法所能解決的問題一般具有以下幾個(gè)特征：

33、,1、該問題的規(guī)?？s小到一定的程度就可以容易地解決;,2、該問題可以分解為若干個(gè)規(guī)模較小的相同問題；,3、利用該問題分解出的子問題的解可以合并為該問 題的解；,4、該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即 子問題之間不包含公共的子子問題 .,如何使用，因問題而異.,分治法的應(yīng)用很廣，如鐵路運(yùn)輸技術(shù)計(jì)劃中的 空車調(diào)度計(jì)劃等.,1 組合優(yōu)化模型與算法,45,（五） 遞歸方法,遞歸就是自己調(diào)用自己的過程 . 這里的“自己”可以 是函數(shù)、過程、語言結(jié)構(gòu)和解題方法等 .,遞歸方法思路: 第一步驟（遞歸步驟）：將規(guī)模較大的原問題分 解為一個(gè)或多個(gè)規(guī)模更小、但具有類似于原問題特性 的子問題。即較大的問題遞

34、歸地用較小的子問題來描 述，解原問題的方法同樣可用來解這些子問題. 第二步驟：確定一個(gè)或多個(gè)無須分解、可直接求 解的最小子問題（稱為遞歸的終止條件）.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,46,Example 4,斐波那契數(shù)定義為下列無窮整數(shù)的序列：,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89，,第 n 個(gè)元素是緊接在它之前的兩個(gè)元素之和，用 FIB(n) 表示第 n 個(gè)斐波那契數(shù)，則可用如下遞歸關(guān)系 式定義：,FIB(n) = FIB(n-1) + FIB(n-2) FIB(1) = 1 FIB(2) = 1,為了計(jì)算 FIB(n) ，要遞歸調(diào)用 FIB(n-1)

35、 、FIB(n-2) , 而為了計(jì)算 FIB(n-1) ，除了利用已調(diào)用的 FIB(n-2) 外，還要調(diào)用FIB(n-3)，因此，為了計(jì)算FIB(n) 需作 n-1 次遞歸調(diào)用 .,遞歸調(diào)用次數(shù) 遞歸深度,分治與遞歸像一對孿生兄弟，經(jīng)常同時(shí)應(yīng) 用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法.,1 組合優(yōu)化模型與算法,47,（六） 動態(tài)規(guī)劃法,Example 5,100多年前，有位美國推銷員乘驛站馬車 向西旅行 ，從州A (state ,狀態(tài)) 到州E 如圖，需要4個(gè) 驛程（stage，階段）。問題為求從 State A到 State E 走哪條途徑使他最安全？,原問題為求從 A 到 E 走哪條途徑使

36、保險(xiǎn)單 （policy，策略）的總費(fèi)用達(dá)到最??？,6,4,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,48,6,4,Note :,作出各相繼驛程上最佳決策。不一定產(chǎn)生總 的最佳決策（即Greedy 算法未必取得最佳策略）.,如： A 2 B1 4 C2 3 D2 4 E,費(fèi)用和為13,而 A 3 B3 1 C2,費(fèi)用更低廉,窮舉法：,即列出所有的可行路徑，逐個(gè)路徑進(jìn)行比 較，并從中選出最佳路徑.,共有路徑 18 條 .,1 組合優(yōu)化模型與算法,49,如果 s1s2sk sk+1 sn 是 s1 sn 的最短路， 則該路上任一點(diǎn)sksk+1sn 是sk sn 的最短路 .,結(jié)論：,設(shè) Sk 表示在第k個(gè)驛

37、程上出發(fā)州的集合（狀態(tài)集 合）， S1 = A ， S2 = B1，B2，B3 ， S3 = C1， C2，C3 ，S4 = D1，D2 ，,uk(sk) = sk+1 表示在第k個(gè)驛程從 sk 出發(fā)所作的決 策 , 如：u2(B1) = C1 或 C2 或 C3 ( C1，C2，C3 表示第k 驛程從B1出發(fā)的允許決策集合) .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,50,6,4,fk(sk) 表示從第 k 個(gè)驛程的出發(fā)州 sk E 的最短 路的費(fèi)用和，f1(s1) 即為所求.,若已知 f2(B1)、f2(B2)、f2(B3)，則,當(dāng)k = 4時(shí)，,3,4,1 組合優(yōu)化模型與算法,51,6,4,

38、3,4,當(dāng)k = 3時(shí)，,5,7,6,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,52,6,4,3,4,5,7,6,當(dāng) k = 2 時(shí)，,8,8,11,1 組合優(yōu)化模型與算法,53,6,4,3,4,5,7,6,8,8,11,當(dāng) k = 1 時(shí)，,11,u2( B3 ) = C2 u3( C2 ) = D2 u4( D2 ) = E 最安全道路為AB3C2D2E，最小費(fèi)用為11 .,Note 優(yōu)點(diǎn)： 減少計(jì)算量，（共 18 次加法，11次比較）； 豐富了計(jì)算結(jié)果 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,54,動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的數(shù)量化方法.,動態(tài)規(guī)劃的成功之處在于，它可以把一個(gè) n 維決 策

39、問題變換為 n 個(gè)一維最優(yōu)化問題 ；,另外，動態(tài)規(guī)劃能夠得到全局最優(yōu)解 .,以空間換時(shí)間；,動態(tài)規(guī)劃是求解某類問題的一種方法，是一種算 法設(shè)計(jì)的策略，而不是一種特殊的算法（不像 LP 有 統(tǒng)一的數(shù)學(xué)模型和算法）.,必須對具體問題進(jìn)行具體 分析：適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無 后效性；以豐富的想象力和靈活的技巧建立動態(tài)規(guī)劃 模型及求解 .,動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問 題，只在第一次遇到時(shí)加以求解，并把答案保存起 來，讓以后再遇到時(shí)直接引用，不必重新求解.,最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）：一個(gè)最優(yōu)化策略具 有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的 決策所形成的狀態(tài)而言

40、，余下的諸決策必須構(gòu)成最優(yōu) 策略. 簡言之, 一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的.,無后效性（馬爾科夫性）是指：如果給定某一階段的 狀態(tài)，則在這一階段以后過程的發(fā)展，不受這階段以 前各階段狀態(tài)的影響，而只與當(dāng)前的狀態(tài)有關(guān). 換句 話說，過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響未 來的發(fā)展 . 每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié).,用到了遞歸，與貪 心法、分治法、分 枝與定界區(qū)別？,1 組合優(yōu)化模型與算法,55,動態(tài)規(guī)劃問題具有以下基本特征： 1、問題具有多階段決策的特征； 2、每一階段都有相應(yīng)的“狀態(tài)”與之對應(yīng)； 3、每一階段都面臨一個(gè)決策； 4、每一階段的最優(yōu)解問題可以遞歸地歸結(jié)為下一階 段各個(gè)

41、可能狀態(tài)的最優(yōu)解問題，各子問題與原問 題具有完全相同的結(jié)構(gòu) .,動態(tài)規(guī)劃的基本概念：,1、階段（stage） 是對整個(gè)過程的自然劃分. 用 k = 1,2, n 表示階段序號，把 k 稱為階段變量 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,56,2、狀態(tài) (state) 狀態(tài)表示每個(gè)階段開始時(shí)所面臨的自然 狀況或客觀條件. 既是該階段某支路的始點(diǎn)，又是前 一階段某支路的終點(diǎn).,描述狀態(tài)的變量稱為狀態(tài)變量，記作sk，它表示第 k 階段所處的狀態(tài). 狀態(tài)變量取值的全體，稱為允許 狀態(tài)集合，記作Sk . 顯然有 sk Sk,如前例 S1= A ，S2= B1，B2，B3 ，etc. 而 s2 可取B1，

42、B2，B3 .,3、決策 (decision) 當(dāng)某階段的狀態(tài)確定后，可以作 出各種不同的選擇，從而確定下一階段的狀態(tài)，這種 選擇稱為決策.,1 組合優(yōu)化模型與算法,57,描述決策的變量稱為決策變量，用 uk(sk) 表示第 k 階段當(dāng)狀態(tài)處于 sk 時(shí)的決策變量.,決策變量允許取值的范圍稱為允許決策集合，常 用Dk(sk) 表示第 k 階段從狀態(tài) sk 出發(fā)的允許決策集 合， 顯然有 uk(sk) Dk(sk) .,在前例中，D1(A) = B1，B2，B3 ， D2(B1) = C1，C2，C3 etc .,4、策略 (policy) 是一個(gè)按順序排列的決策組成的集合,由過程的第 k 階段

43、開始到終止?fàn)顟B(tài)為止的過程, 稱 為問題的后部子過程 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,58,由每階段的決策按順序排列組成的可行決策函數(shù) 序列 uk(sk) ，uk+1(sk+1) , ，un(sn) ，稱為 k 子過程 策略，簡稱子策略.,記為 pk , n(sk)= uk(sk) , uk+1(sk+1) , , un(sn) .,當(dāng) k = 1 時(shí)，此決策函數(shù)序列稱為全過程的一個(gè) 策略，簡稱策略，記 p1，n(s1) .,可供選擇的策略有一定的范圍，稱為允許策略集 合，用 P1, n(s1) 表示 . 從 P1, n(s1) 中找出達(dá)到最優(yōu)效果 的策略稱為最優(yōu)策略，記 p1,n*= p

44、1,n*(s1)= u1*(s1) ，u2*(s2),，un*(sn) .,1 組合優(yōu)化模型與算法,59,5、狀態(tài)轉(zhuǎn)移方程 (equation of state transition) 反映 前后階段狀態(tài)之間的關(guān)系的方程 記為：sk+1=Tk(sk，uk) .,體現(xiàn)了無后效性，正是能將多階段化為單階段決策的理論依據(jù),（前例： sk+1 = uk(sk)）,6、指標(biāo)函數(shù)和最優(yōu)值函數(shù) (objective function and optimal value function) 階段的指標(biāo)函數(shù)是對應(yīng)某一階 段狀態(tài)和從該狀態(tài)出發(fā)的一個(gè)決策的某種效益度量， 用vk(sk，uk) 表示 .,過程指標(biāo)函數(shù)

45、（又稱目標(biāo)函數(shù)） 是用來衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，它是定 義在全過程和所有后部子過程上的數(shù)量函數(shù)，記作 Vk,n =Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) ( k = 1,2,，n ),當(dāng) k = 1 時(shí)，就是全過程的指標(biāo)函數(shù) . 指標(biāo)函數(shù)也是初始狀態(tài)和策略的函數(shù) 即 Vk,n = Vk,n（sk，pk,n（sk）.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,60,Note 指標(biāo)函數(shù)應(yīng)具有可分離性，即Vk,n可表示為：,Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) =,且 對于Vk+1 , n 嚴(yán)格單調(diào).,常見的指標(biāo)函數(shù)

46、的形式有： 全過程和它的任一后部子過程的指標(biāo)函數(shù)等于各 階段指標(biāo)函數(shù)之和，即：,Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) =,或,1 組合優(yōu)化模型與算法,61, 全過程和它的任一后部子過程的指標(biāo)函數(shù)等于各階 段指標(biāo)函數(shù)之積，即：,指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)，記 fk(sk),（opt 即 optimization, 具體問題可取 min，max）,或,f1(s1) 即為全過程的最優(yōu)策略.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,62,Note 當(dāng)初始狀態(tài)給定時(shí)，用逆序的方式比較好，當(dāng) 終止?fàn)顟B(tài)給定時(shí)，用順序的方式比較好，通常初始 狀態(tài)給定的情況居多，所以用

47、逆序的方式比較多 .,對第一類指標(biāo)函數(shù)其基本方程為：,1 組合優(yōu)化模型與算法,63,Example 6,用動態(tài)規(guī)劃法解 TSP,距離矩陣如右：,Solution :,不妨設(shè)從 v1 出發(fā)回 到 v1 .,用 f( vi; V) 表示從 vi 出 發(fā)，經(jīng)頂點(diǎn)集合 V 中的點(diǎn)各一 次，回到 v1 點(diǎn)的最短路 .,則動態(tài)規(guī)劃函數(shù)方程為：,用 f(v1; v2,v3,v4) 表示從 v1 出發(fā)經(jīng) v2,v3,v4 各一次 最后返回 v1 的最短路長度 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,TSP 的距離矩陣,64,由動態(tài)規(guī)劃函數(shù)方程有：,為了計(jì)算 ，,必須先計(jì)算,而,1 組合優(yōu)化模型與算法,65,計(jì)算

48、順序?yàn)椋?第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,TSP 的距離矩陣,66,TSP 的距離矩陣,最后計(jì)算：,通過下標(biāo)，不難得最優(yōu)回路為: v1v3v4v2v1,用動態(tài)規(guī)劃算法求 TSP , 其時(shí)間復(fù)雜性為 O(n 2n) .,1 組合優(yōu)化模型與算法,67,（七） 探索法,探索法是一種對給定的問題能通過某種途徑（容易得 到、比求最優(yōu)解的算法速度快）進(jìn)行探索而找到一個(gè) 較好的解（不一定是最優(yōu)解，有時(shí)探索甚至失?。┑?算法 .,設(shè)計(jì)探索法的一種常用方法是列出精確解的所有 要求，并把這些要求分成兩類： 1、必須滿足的要求；2、允許折衷的要求 . 探索算法的設(shè)計(jì)目標(biāo)就是保證第一類要求得到滿 足，對第二類要求要

49、盡量滿足，但并不一定滿足 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,啟發(fā)式算法,68,（八） 倒推法,倒推法是從某個(gè)目標(biāo)或某個(gè)解出發(fā)，倒推到這個(gè)問題 的初始陳述 . 如果這個(gè)過程是可以逆轉(zhuǎn)的，則從問題 的陳述可以推得問題的解 .,倒推法不是從某個(gè)解推導(dǎo)出什么新的結(jié)論，而是 猜測能使結(jié)論成立的前提條件，然后再從這些前提條 件出發(fā)，找出能導(dǎo)致它們成立的新的前提條件，如此 繼續(xù)尋找 .,有可能在進(jìn)行到某一步時(shí)新的前提條件會 與已知條件（即問題的初始陳述）一致 . 這時(shí)，由于 已知條件成立，所以在已知條件和解之間所有的前提 條件都成立，從而解必定成立 .,適用于倒推法的問題應(yīng)滿足以下兩個(gè)條件： 1、問題必

50、須有唯一解； 2、在問題中出現(xiàn)的函數(shù)是單值的，或者說對每一條 輸出信息都可以找到唯一的一條輸入信息（又稱 1 對 1 運(yùn)算）.,1 組合優(yōu)化模型與算法,69,Example 7,水罐問題,有兩個(gè)水罐，它們的容積分別為 7L 和 3L，除此 之外沒有別的容器 . 水的供應(yīng)是充分的 . 怎樣用這兩 個(gè)水罐量出 5L 水？,Solution :,這個(gè)問題的解是在大罐里裝有 5L 水 .,從解往前倒推，有五種情況可能導(dǎo)致解的產(chǎn)生：, 大罐里有 2L 水，再從小罐里倒入 3L 水；, 大罐里裝滿水，小罐里有 1L 水，從大罐里倒出2L 水到小罐里，剩下 5L；, 大罐里有 3L 水，再從小罐里倒入 2L

51、 ；, 大罐里有 4L 水，再從小罐里倒入 1L ；, 大罐里有 6L 水，小罐里有 2L ，從大罐里往 小罐里倒入 1L 水，剩下 5L 水 .,在這五種情況中，第一和第二兩種情況的可能性 大，下面從第二種情況出發(fā)再往前推 .,先把大罐裝滿，再用小罐從大罐里量出兩次共 6L 水，使之剩下 1L 水，把它倒入小罐，然后把大罐 再裝滿 . 這就得到了上述第二種情況 . 這種情況發(fā)生 后，從大罐往小罐到2L 水，剩下 5L 水，問題得到了 解決 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,70,（九） 回溯法,回溯法是一種滿足一定約束條件的窮舉式搜索法，它 的搜索方式與對樹的深度優(yōu)先搜索方式相似，但由于

52、 規(guī)定了問題的解必須滿足一些約束條件，因此需要搜 索的空間大大減少 .,如果問題的解能表示為一個(gè) n 元組 (x1, x2, , xn) 則可采用回溯法求解 .,回溯法求解的約束條件一般分為兩類：,1、顯約束，每個(gè) xi 的取值范圍；,2、隱約束，滿足判定函數(shù)的關(guān)于解空間上的多元式 .,1 組合優(yōu)化模型與算法,71,Example 8,設(shè)有一 44 的棋盤（即每行每列都有 4 個(gè)正方格的棋盤），用 4 個(gè)棋子布到格子上，要求滿 足一下兩個(gè)條件：,1、任意兩個(gè)棋子不在同一行和同一列上；,2、任意兩個(gè)棋子不在一對角線上 .,試問有多少種的布局 ？,Solution :,如果采用窮舉式搜索，先不考慮

53、 1、2 兩 個(gè)條件，則布到每一行的棋子有 4 個(gè)選擇，故共有 44 = 256種方案 .,設(shè) xi 表示放在第 i 行上的棋子的列數(shù)，,這是顯約束,顯然沒有必要！,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,72,隱約束有：,不同列,不在一對角線上,搜索過程如下：,這種一旦發(fā)現(xiàn)前面已是“此路不通”，立即回頭， 改換路徑，而不是一條道走到底的策略，就是回溯法 的基本思想 .,向前走，碰壁回頭,1 組合優(yōu)化模型與算法,73,（十） 模擬法,在實(shí)際科研和生產(chǎn)中有許多大系統(tǒng)，要構(gòu)造大系 統(tǒng)的模型、對它們分析和求解都是相當(dāng)困難的 . 變量 之間的關(guān)系難以確定，隨機(jī)變量的分布不得而知，甚 至影響因素就找不全 .

54、利用計(jì)算機(jī)對大系統(tǒng)進(jìn)行模擬是研究大系統(tǒng)的一 種好方法 .,模擬法有許多優(yōu)點(diǎn)： 1、它能按預(yù)定要求去研究系統(tǒng)的各個(gè)方面，借助計(jì)算 機(jī)的高速運(yùn)算和邏輯判斷能力，可以同時(shí)顧及系統(tǒng)各 個(gè)方面的結(jié)構(gòu)，容易展現(xiàn)系統(tǒng)動態(tài)變化的具體細(xì)節(jié) ；,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,直接解決問題的方法，是一種建模方法.,74,2、模擬的方法比將系統(tǒng)置于實(shí)際環(huán)境直接進(jìn)行試驗(yàn) 的方法要節(jié)省很多時(shí)間和經(jīng)費(fèi)； 3、模擬可用不同的時(shí)間比例尺進(jìn)行, 可放慢時(shí)間，在 微觀上認(rèn)真考察系統(tǒng)的性態(tài)；也可加快時(shí)間，在宏觀 和大范圍上觀察系統(tǒng)的行為；還可以使時(shí)間暫停、返 回和重置，以便反復(fù)、詳盡地研究系統(tǒng)在任意時(shí)段的 各種反常的或重要的性態(tài)

55、及行為，這些都是在實(shí)際系 統(tǒng)中很難或根本不可能實(shí)現(xiàn)的 .,模擬是一項(xiàng)實(shí)驗(yàn)技術(shù)，其實(shí)驗(yàn)結(jié)果取決于所采用 的模型和數(shù)據(jù) .,其他需要應(yīng)用模擬的情況： 1、有危險(xiǎn)性或代價(jià)過高的事情； 2、一旦實(shí)施，無法復(fù)原或產(chǎn)生嚴(yán)重后果的事情； 3、某種理論研究的結(jié)果需要驗(yàn)證 . etc .,以上介紹了十種基本的算法設(shè)計(jì)方法，在實(shí)際應(yīng) 用中，常常是幾種方法配合使用，以提高算法的效率 .,Go back,1 組合優(yōu)化模型與算法,75,在廣泛的意義下，執(zhí)行算法的效率是用執(zhí)行算法 所用的全部計(jì)算資源的多少來衡量(時(shí)間、空間),但通 常用時(shí)間作為衡量標(biāo)準(zhǔn)，這就是計(jì)算(時(shí)間)復(fù)雜性問題.,一、 如何計(jì)算時(shí)間,1 與實(shí)例的輸入

56、規(guī)模有關(guān)，是輸入規(guī)模 的函數(shù)（輸入規(guī)模指的是：一個(gè)問題的實(shí)例所有參數(shù) 的二進(jìn)制表示的長度的總和?？珊喕癁闆Q策變量的個(gè) 數(shù)n，或者頂點(diǎn)的個(gè)數(shù)m .）f(n) , g(m) etc.,用初等運(yùn)算算術(shù)運(yùn)算、比較、轉(zhuǎn)移等指令的次 數(shù)，來表示一個(gè)算法在假設(shè)的計(jì)算機(jī)上執(zhí)行時(shí)所需的 時(shí)間。,相關(guān)因素:,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,2 計(jì)算復(fù)雜性問題,76,2 與實(shí)例的參數(shù)有關(guān) ， 如LP 問題： max z=cx s.t. Axb x0, c 0 , b 0,算法的時(shí)間復(fù)雜性是關(guān)于實(shí)例輸入長度 的函數(shù)，用來表示算法的時(shí)間需求. 對于每一個(gè)可能 的輸入長度，它是該算法解此輸入長度的最壞可能的 實(shí)例所需的

57、時(shí)間（基本運(yùn)算步驟）.,相關(guān)因素:,Definition 1,2 計(jì)算復(fù)雜性問題,77,研究計(jì)算復(fù)雜性問題主要是針對n很大的情形,1 9n2 與 2n2 O(n2),2 f(n) = 12n4 - 8n3 + 5n2 + 2n - 80,f(n) = O(n4),當(dāng)n無限增大時(shí)，,Ln n , n( 0) , an （a 1）,趨向于無窮大的速度如何？,Note：,問：,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,78,復(fù)雜性分析的一個(gè)研究方向：對算法進(jìn)行評價(jià),給定n個(gè)整數(shù)x1，x2，xn， 要求將他們從小到大重新排列,取出x1，x2，xn中的最小者（需比較 n-1次）令其為b1（需n次賦值），從x1，

58、x2，xn中去 掉b1，在余下的n-1個(gè)數(shù)中選出最小者，令其為b2， 直到得到b1,b2,bn，易知其算法共做了n(n-1)/2次比 較，至多n(n+1)/2次賦值，計(jì)算復(fù)雜性為，O(n2).,Example 9 整序問題：,比較交換法：,二、如何評價(jià)算法的好壞（從計(jì)算復(fù)雜性角度）,2 計(jì)算復(fù)雜性問題,79,先 將兩個(gè)單調(diào)不減的數(shù)列u1，u2um與v1，v2vm 合并為一個(gè)單調(diào)不減的數(shù)列w1，w2w2m方法為u1與v1 比較,若u1 v1，w1 :=v1 . 再對u1與v2進(jìn)行比較， 依次對 w2，w3w2m賦值，計(jì)算量為O(m).,快速算法：,將 x1，x2，xn從小到大重新排列（設(shè)：n=2p+1 如果n 不是2的冪次可補(bǔ)充 若干個(gè)很大的數(shù)字使之成 為2的冪次）.,確定一個(gè)wj 需要一次比較一次賦值，共需要（2m-1）次比較，2m次賦值 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,80,將2p+1個(gè)數(shù)分成2p個(gè)單調(diào)不減的2元組,計(jì)算量為O(2p),O(2p)= 2p-1 O(2),計(jì)算量為O（2p）,綜上，算法總工作量為： (p+1) *O(2p)=O(n logn),8 1 9 6 7 5 3 2,(8 1)(9 6)(7 5)(3 2),1 8 6 9 5 7 2 3,(1 8 6 9) (5 7 2