通信網(wǎng)理論基礎(chǔ)：02-關(guān)于算法

1、通信網(wǎng)理論基礎(chǔ)Part 02: 關(guān)于算法(Intro to Algorithm)2013年春季2 / 30關(guān)于算法1234算法的基本概念 算法的設(shè)計方法算法的分析方法算法的應(yīng)用與實現(xiàn)Algorithms are the “stuff” of computer science: they are central objects of study in many, if not most, areas of the field.- ROBERT SEDGEWICK “Algorithms”3 / 30算法的基本概念名稱的來歷123算法是什么算法的分類2013年春季2013年春季4 / 30Algo

2、rithm的由來Why ?因為：一個使得定量分析大眾化了，另一個使得知識大眾化了。1448 = MCDXLVIIIAlgorithmTo honor the wise Arabian:Al KhwarizmiAD 600十進(jìn)制計數(shù)法及其符號在印度(注意，不是阿拉伯)被發(fā)明。DecimalNine CenturyAl Khwarizmi (Baghdad)寫了一本介紹十進(jìn)制以及相應(yīng)的四則運算(甚至還包括求平方根和求PIE)方法的阿拉伯文教材。并在很多個世紀(jì)之后被介紹到了西方。Algorithm1448一個Mainz(德國城市)的金匠，Johann Gutenberg，發(fā)明了金屬活字印刷。Typo

3、graphyThe Dark Ages ended, the human intellect was liberated, science and technology triumphed, the Industrial Revolution happened.Two ideas changed the world因為那些計算方法具有“算法”的一切特征：Precise / Unambiguous / Mechanical /Efficient / CorrectWhy ?5 / 30算法是什么？求解問題的一個過程(Procedure)。算法過程由一系列步驟構(gòu)成，其中每個步驟都是簡單的，無歧義的

4、，容易實現(xiàn)的。給定任意實例，都能給出所要求的結(jié)果。求解對一系列(甚至無窮多個)實例的統(tǒng)一/無歧義的描述。由輸入(給定條件)和輸出(待求結(jié)果)組成。對一系列(甚至無窮多個)實例的統(tǒng)一/無歧義的描述。由輸入(給定條件)和輸出(待求結(jié)果)組成。問題問題給定一組整數(shù)，求其中最大值。過程比較前2個數(shù)的大小，較大者與第3個比；例子2013年春季6 / 30歷史上三大算法1、求最大公約數(shù)的歐幾里得算法2、求素數(shù)的埃拉托塞尼篩法3、求方根的開方算法X_(n+1)=X_n+【A/(X_n（k-1）)-X_n】1/k 7 / 30算法的分類串處理(String)數(shù)學(xué)：算術(shù)；隨機數(shù)；高斯消元；幾何；求積分；曲線擬合

5、。排序(Sorting)圖(Graph)其他：FFT；線性規(guī)劃；等等。查找(Searching)應(yīng)用2013年春季8 / 30關(guān)于算法2341算法的基本概念 算法的設(shè)計方法算法的分析方法算法的應(yīng)用與實現(xiàn)算法的應(yīng)用是如此廣泛，面對的問題千奇百怪，那么，算法豈不是只能case-by-case地設(shè)計？難道其中還有些什么共同的，統(tǒng)一的設(shè)計方法么？2013年春季9 / 30算法的設(shè)計方法4Divide and Conquer1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季10

6、 / 30Divide and Conquer 將原問題分解為規(guī)模較小的子問題由于所有拆分出來的子問題都是相同性質(zhì)的，因此可以方便地用遞歸(Recursion)方式來實現(xiàn)。Divide 如果子問題仍然困難，就繼續(xù)對子問題進(jìn)行分解。 直到最終分解得到的子問題變得容易“征服”(trivial)。Conquer將子問題的結(jié)果合并成原問題的解Combine例1 求最大值 在一組整數(shù)中求最大值。 分成兩組，分別求最大值，然后比較這兩個值，較大者作為原問題的解。 遞歸。例2 查找 在一組升序整數(shù)中，查找某個特定的整數(shù)。 折半查找。例3 排序 為一個序列按序排列 歸并排序11 / 30 折半查找 請查錯，并

7、修改 Hint : 以A = 2,5,9x = 5為例來思考。偽碼及實例Function search (A, x, k, r)/ find x in A k.r IF k = r THEN RETURN( k )ELSE m = (k + r) / 2 IF x A m THEN RETURN( search( A, x, k, m) ) ELSE RETURN( search( A, x, m, r)基于DC的求最大值Function maximum( S, x, y )/ return maximum in Sx.yIF y x 1 THEN RETURN( max( Sx, Sy )E

8、LSE m1 = maximum( x, (x + y) / 2 ) m2 = maximum( (x + y) / 2 + 1, y ) RETURN( max( m1, m2 ) )偽碼偽碼2013年春季12 / 30算法的設(shè)計方法4Divide and Conquar1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季13 / 30Dynamic Programming串行 仍然劃分為子問題，但是子問題的求解不是遞歸進(jìn)行的，而是順序進(jìn)行的(串行)。 子問題的解存儲

9、在一個表中供后續(xù)的子問題求解時使用。Dynamic Programming is a fancy name for Divide and Conquer with a TABLE.要點 要正確地設(shè)計各個子問題的求解順序。 目的是保證：求解某個子問題時如果需要用到其他子問題的解，那個解已經(jīng)在表中了。用途 用DC方法分解出的子問題數(shù)目很大，而且要反復(fù)用到相同的子問題的解。例1 0-1背包問題 給定n個物品，體積分別為s1, s2, , sn，背包容積為K。 問，是否存在一組物品，其體積之和剛好為K。即剛好能塞滿背包。例2 所有最短路 求給定圖中，所有節(jié)點對之間的最短路徑( All Pair Sho

10、rtest Path)。 Floyd算法。2013年春季14 / 300-1背包問題的DP算法ti,j表示前 i 個物品是否能組合成 j 這么大的體積。如果能，該變量為TRUE；否則為FALSE。思考 “n個物品能否組合成體積K”這個問題可以分解為兩個子問題： 子問題1：前n 1 個物品能否組合成體積K ? 子問題2：前n 1 個物品能否組合成體積 K sn ? 顯然，只要任一答案為TRUE，那么原問題就為TRUE。繼續(xù)思考 子問題1可以分解為 子問題3：前n 2個能否組成體積K? 子問題4：前n 2個能否組成K sn-1?子問題2可以分解為 子問題5：t n 2, K sn 為TRUE么 ?

11、 子問題6：t n 2, K sn sn-1 為TRUE么?干脆 . si可能取任何值，所以干脆不是問某個特定的體積，而是問所有的體積：ti,1? ti,2?.ti,K? 并且反過來計算，計算完t1, 1K，再來計算t2, 1K. 這樣一來，后續(xù)計算所需要問的那些子問題都已經(jīng)求解并記錄下來了。Function knapsack (s1, s2, , sn, K)01 t 0, 0 = TRUE02 FOR j = 1 TO K DO t0, j = FALSE03 FOR i = 1 TO n DO04 FOR j = 1 TO K DO05 t i, j = t i 1, j 06 IF j

12、 si = 0 THEN t i, j = t i, j | t i 1, j si 07 RETURN t n, K 2013年春季15 / 300-1背包問題的DP算法12345678910i=1s1=5i=2s2=4i=3s3=3i=4s4=6XXXXOXXXXXXOOOOOOOOXXXXXXXXXXOOOXXOOOOOO0-1背包問題的一個實例 n = 4，即有4個物品 體積分別為 5，4，3，6 K = 10，即背包容積為10 下面我們來填t i, j 表課堂作業(yè)1：另一個實例 n = 8，體積分別為 15，5，16，7，1，15，6，3 K = 19，即背包容積為19 請?zhí)顃 i,

13、 j 表課后思考：DC vs DP 我們給出了Knapsack問題的DP算法，試用DC方法構(gòu)造一個算法。（Hint：遞歸） 你覺得這兩個算法哪個更好？為什么？Function knapsack (s1, s2, , sn, K)01 t 0, 0 = TRUE02 FOR j = 1 TO K DO t0, j = FALSE03 FOR i = 1 TO n DO04 FOR j = 1 TO K DO05 t i, j = t i 1, j 06 IF j si = 0 THEN t i, j = t i, j | t i 1, j si 07 RETURN t n, K 2013年春季1

14、6 / 30算法的設(shè)計方法4Divide and Conquar1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季17 / 30Greedy Algorithm先從簡單的子問題入手，逐步擴(kuò)展(Augment)子問題的解，最終擴(kuò)展為整個問題的解。擴(kuò)展這種擴(kuò)展是貪婪(Greedy)的。即只以當(dāng)前的已知條件(可能不全面，與DP相反)為依據(jù)，只保證局部最佳，不考慮是否是全局最佳。貪婪Sometimes optimal; Sometimes pretty good; Somet

15、imes lousy.But, always faster and easier (at least than DP).性能The trick is to determine when to be greedy.要點2013年春季18 / 30貪婪算法的例子1連續(xù)背包問題。2 最短路問題。 Dijkstra算法(Label Setting)3最小生成樹問題。Prim算法；Kruskal算法基于貪婪算法的求解思路 核心思想：在體積一定的情況下，要減少重量，只有降低密度。 怎樣才能保證密度最?。?先塞密度最小的；塞完了如果還空，就塞密度次小的。直至最后，只能塞某個物品的一部分。Function C

16、-Knapsack (s1n, w1n, K)01 按密度對物品排序;02 m = K; i = 1;03 WHILE si m DO04 xi = 1; m = m si; i = i + 1;05 xi = m / si;06 FOR j = i + 1 TO n DO xj = 0;07 RETURN x1nWell talk about them later in this course連續(xù)背包問題 給定n個物品，體積分別為s1, s2, , sn，質(zhì)量分別為w1, w2, ., wn，背包容積為K。 要求在塞滿背包的同時，最小化背包的重量。 假定：允許將物品拆分為無限小的部分；且每個

17、物品的密度都是均勻的（注，不同物品密度可以不等）。 Continuous Knapsack 數(shù)學(xué)描述：求一組實數(shù)x1, x2, , xn，0 xi 1。 使得 xi si = K，且xi wi 最小。 一個實例 K = 20; n = 5; s15 = 9, 5, 7, 12, 3; w15 = 4, 4, 8, 5, 1;2013年春季19 / 30算法的設(shè)計方法4Divide and Conquar1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季20 / 30原

18、理窮舉/枚舉/遍歷所有可能。從中尋求最佳解。Its always slow, then, WHY bother?Better than nothing if no other way available.May actually practical for instances with size small enough.Sometimes its not trivial at all 窮舉也有技巧(例如，往往需要產(chǎn)生便于操作、便于排列組合的對象)可以求得最佳，作為比較的對象。技術(shù)最常用的枚舉方法是借助于Divide and Conquer.Exhaustive Search2013年春季21

19、 / 30算法的設(shè)計方法4Divide and Conquar1235Dynamic ProgrammingGreedy AlgorithmExhaustive SearchLocal Search/Metaheuristic2013年春季22 / 30Local Search/Metaheuristics模擬退火模擬晶體的退火過程，跳出局部最優(yōu)解。遺傳算法隨機變異+自然選擇禁忌搜索對隨機的局部搜索施加一定的限制和導(dǎo)向。蟻群/蜂群仿生學(xué)原理神經(jīng)網(wǎng)絡(luò)人工智能Its Exciting, Its Beautiful, and Its full of Fun.2013年春季23 / 30小結(jié)純屬個人觀

20、點復(fù)雜度 Exhaustive Search復(fù)雜度最高，DC和DP次之，但能保證最佳。 貪婪算法思路簡潔，局部搜索應(yīng)用面廣。但無法保證最佳。 通信網(wǎng)絡(luò)應(yīng)用中，沿用成熟算法及其變種占多數(shù)。 需要自行設(shè)計時，優(yōu)先考慮貪婪算法和局部搜索，較少考慮DC和DP。 幾乎從不考慮Exhaustive Search。應(yīng)用 Metaheuristic是很吸引人的研究課題研究 2014年春季24 / 30關(guān)于算法341算法的基本概念 2算法的設(shè)計方法算法的分析方法算法的應(yīng)用與實現(xiàn)我們將學(xué)習(xí)很多算法，也將會去設(shè)計自己的算法。但是，我怎么知道這些算法真的能達(dá)到目標(biāo)？另外，同樣能達(dá)到相同目標(biāo)的多個算法，我應(yīng)該怎么選擇？

21、2013年春季25 / 30測量/評估算法的耗時是很難的計算機硬件不同，OS不同，運行環(huán)境(是否存在其它進(jìn)程)不同。問題實例不同：規(guī)模，輸入條件對算法的影響等。算法的分析算法的正確性(Correctness) 即判斷算法是否能正確求解給定的問題，或者該算法是否能針對所有的問題實例都給出最佳的解。算法的復(fù)雜度(Complexity)其目標(biāo)通常是判斷算法求解問題實例所需要的時間。有時是平均性能，大多數(shù)情況下是求最壞性能。Correctness 從理論上證明算法的正確性，有一個統(tǒng)一的證明模式，所謂Invariant方法。參考算法導(dǎo)論2ed。 本課程僅對少數(shù)算法，從物理意義上去討論其正確性。分析的目標(biāo)

22、2013年春季26 / 30Complexity實例不同，耗時不同？求最壞情況下的耗時。即假定所有的問題實例中使得算法執(zhí)行的操作最多的作為衡量算法的依據(jù)。什么最耗時？循環(huán)。循環(huán)中操作的次數(shù)是可以確定的，只要確定循環(huán)的次數(shù)，就可以估算整個算法的耗時。怎么辦？抓主要矛盾，即關(guān)注算法中最耗時的部分。操作不同，耗時不同？考慮問題規(guī)模足夠大的時候。此時，不同的操作耗時上的差異不占主導(dǎo)地位了。問題的規(guī)模如何定義?基本上，問題中都包含了一些參數(shù)，可以描述輸入信息的規(guī)模。例如，圖算法中節(jié)點的數(shù)目，邊的數(shù)目等。復(fù)雜度分析是要給出最壞情況下，算法的操作次數(shù)與問題規(guī)模的關(guān)系。結(jié)論注意 由于問題的規(guī)模足夠大，因此可以

23、只取最高階。忽略低階項和常系數(shù)。 參見下面的例子。2013年春季27 / 30復(fù)雜度分析實例Function C-Knapsack (s1n, w1n, K)01 按密度對si排序;02 m = K; i = 1;03 WHILE si m DO04 xi = 1; m = m si; i = i + 1;05 xi = m / si;06 FOR j = i + 1 TO n DO xj = 0;07 RETURN x1nFunction knapsack (s1, s2, , sn, K)01 t 0, 0 = TRUE02 FOR j = 1 TO K DO t0, j = FALSE03 FOR i = 1 TO n DO04 FOR j = 1 TO K DO05 t i, j = t i 1, j 06 IF j si = 0 THEN t i, j = t i, j | t i 1, j si 07 RETURN t n, K 問題規(guī)模：n, K 第一個循環(huán)：K個操作； 第二個循環(huán)：循環(huán)體包括賦值、判斷和“或”3個操作，循環(huán)nK次。 共計：3nK + KnKn 問題規(guī)模：n, K 第一個循環(huán)：3n 第二個循環(huán)：n 共計：4n注意 常用的的表達(dá)式：n, n2, log(n), n log(n), 2n, 等。 Polynomial vs. Exponenti