【正文】 = 2T 第一臺機器所需時間 :∑ ????????=1 + ??2 = 3??2 例：有 n=4 個作業(yè)，每個作業(yè)兩個任務： （ a1， a2， a3， a4） =（ 3， 4， 8， 10） （ b1， b2， b3， b4） =（ 6， 2， 9， 15） →（ b2 a1a2 b1 a3 b3 a4 b4），即 t1t3t4t2。 八、 TSP 問題 這是一個 NP hard 問題，時間復雜度為 O（ n!）。 令 g（ i， S）為從 i出發(fā)，經(jīng)過 S（ S 圖中點集的子集）， g（ i， S）表示從 i 點出發(fā)，經(jīng)過S 中所有的結點一次且僅一次，回到出發(fā)點 i 的最短路徑。 g（ i， {1,2,3，……， n}） =min{cik+ g（ k， S{k}） }。 例如對于矩陣： C(4,4) = [0 10 15 205 0 9 106 13 0 128 8 9 0] g（ 2， ? ） =C21=5； g（ 3， ? ） =C31=6； g（ 4， ? ） =C41=8； g（ 2， {3}） =min{C23+ g（ 3， ? ） }=15； g（ 2， {4}） =min{C24+ g（ 4， ? ） }=18； g（ 3， {2}） =min{C32+ g（ 2， ? ） }=18； g（ 3， {4}） =min{C34+ g（ 4， ? ） }=20； g（ 4， {2}） =min{C42+ g（ 2， ? ） }=13； g（ 4， {3}） =min{C43+ g（ 3， ? ） }=15； g（ 2， {3， 4}） =min{C23+ g（ 3， {4}）， C24+ g（ 4， {3}） }=25； g（ 3， {2， 4}） =min{C32+ g（ 2， {4}）， C34+ g（ 4， {2}） }=25； g（ 4， {2， 3}） =min{C42+ g（ 2， {3}）， C43+ g（ 4， {2}） }=23； g（ 1， {2， 3， 4}） =min{C12+ g（ 2， {3， 4}） ， C13+ g（ 3， {2， 4}）， C14+ g（ 4， {2， 3}） }=35； 所以路徑為 1?2?4?3?1，時間復雜度 O（ 2nn2）。 計算機算法設計與分析 18 / 24 第五章 基本檢索與周游算法 一、 一般方法 樹的三種遍歷方式 圖 51 給定 二叉樹 中根： FDHGIBEAC 先根： ABDFGHIEC 后根： FHIGDEBCA 圖的生成樹 圖 52 給定連通圖 A B C D E G H F 1 2 3 4 5 6 7 8 I 計算機算法設計與分析 19 / 24 圖 53 寬度優(yōu)先生成樹 圖 54 深度優(yōu)先生成樹： 二、 雙連通圖和深度優(yōu)先檢索 圖 55 雙連通分圖 雙連通分圖深度優(yōu)先檢索樹 ： 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 計算機算法設計與分析 20 / 24 143 291 068571234567891 0 圖 56 雙連通分圖深度優(yōu)先檢索樹 深度優(yōu)先生成樹中的虛線條代表逆邊，實線條代表樹邊，結點旁的數(shù)代表深度優(yōu)先樹用DFN 表示。最低深度優(yōu)先數(shù) L（ u） =min{DFN（ u）， min（ L(w)|w 是 u 的兒子） }， min{DFN（ w） |（ u,w）是一條逆邊 }}，而且當且僅當 u 有一個使得 L（ w） =DFN(u)的兒子 w 時， u是一個關節(jié)點。 按后根的次序去各結點的最低深度優(yōu)先數(shù) DFN(u)是： L(10)=4 L(9)=5 L(6)=8 L(8)=6 L(7)=6 L(5)=6 L(2)=1 L(3)=1 L(4)=1 L(1)=1 對于關節(jié)點： 除根結點以外的其它結點， L（ w）≥ DFN（ u）且 w 是 u 的兒子的結點是關節(jié)點，當然葉子結點不用考慮 。 結點 3：兒子結點 10 有 L(10)＝ 4 而 DFN(3)=3。 結點 2：兒子結點 5 有 L(5)=6 而 DFN(2)＝ 6 結點 5：兒子結點 6 有 L(6)＝ 8 而 DFN(5)＝ 7 由連通圖的分類可知分為單連通分圖、雙連通分圖兩種類型，每一個圖上都有一定的關節(jié)點，要識別出圖上所有的關節(jié)點，根據(jù)各個關節(jié)點的連通性，找到符合條件的通路。 對于寬度優(yōu)先搜索和深度優(yōu)先搜索，在這里，首先要對各個關節(jié)點之間的連接是單連通還是雙連通的關系進行確定，再找到在一個連通圖中關結點之間是有實邊連接時，還有沒有逆邊連接，實邊用實線來表示，逆邊用虛線來表示，再根據(jù) DFS 算法和 BFS 算法進行實現(xiàn)，找出符合條件的最優(yōu)路徑。 計算機算法設計與分析 21 / 24 三、 決策樹 （博弈樹） 對策樹類問題的本質(zhì)思想，是起源于博弈類游戲，比如，在一盤棋賽中，對弈各 方都要根據(jù)當前的局勢，分析和預見以后可能出現(xiàn)的局面，決定自己要采取的各種對策，以爭取更好的結果，博弈類問題是一種競爭，終局是表示為勝局、負局或者和局的情況的棋局，其它的都是非終止棋局。 博弈過程在計算機里表示為對策樹，對棋局進行判斷的評價函數(shù) E（ X）是 max??min的過程，該過程可采用剪枝策略，如 ? ? 截斷。 ? 截斷：如果一個求最小值位置的值判斷為小于或等于它父親的 ? 值，那么可以停止生成這個求最小值位置其余兒子的值，在這種規(guī)則下終止生成結點值的行動稱為 ? 截斷。 ? 截斷：如果一個求最大值位置的值判斷為大于或等于它父親的 ? 值，那么可以停止生成這個求最大值位置其余兒子的值，在這種規(guī)則下終止生成結點值的行動稱為 ? 截斷。 計算機算法設計與分析 22 / 24 第六章 回溯法 第七章 分支限界法 回溯法：深度優(yōu)先搜索 +限界函數(shù) 分支限界法：寬度優(yōu)先搜索 +限界函數(shù) +LC（最小成本） 一、 一般方法 回溯法 其實是求 n 元組的問題。 所要求的解必須能表示成一個 n元組（ x1， x2，…， xn），其中 x1是取自某個有窮集 Si。 ||Si||= mi， ， m1*m2… mn。 例： 8皇后問題 8皇后問題實際上 是一個 8 元組問題。 計算本質(zhì)上是基于規(guī)劃的一組符號的變換過程，是物理狀態(tài)的變遷，而其中的狀態(tài)及狀態(tài)的轉(zhuǎn)移（深度優(yōu)化和寬度優(yōu)化）本質(zhì)上就是離散狀態(tài)的變遷，對于離散問題，可以用迭代法來進行解決，利用迭代法，公式有收斂和發(fā)散兩種情況，針對不同的情況，對問題進行求解，再就是得用寬度優(yōu)先和限界函數(shù)兩者進行求解，對于不同類型的問題采取不同的方法實現(xiàn)對問題的求解。 二、 回溯法解 01 背包問題 設有 0/1 背包問題 ： n=8, M=110, p=[11,21,31,33,43,53,55,65]， w=[1, 11,21, 23,33,43,45,55]。 即（ x1， x2，…， x8）為 28個元組，要從中找到能使價值最大的元組， xi∈{0， 1}。 計算 效益值使用的是 01 背包問題的效益不會超過部分背包問題的效益值，計算部分背包問題的效益值。 圖 71 回溯法生成的樹 很容易看出最優(yōu)解是 (1， 1， 1， 0， 1， 1， 0， 0)，得到的效益值是 159。 計算機算法設計與分析 23 / 24 算法分析效率：狀態(tài)空間樹共有 291=151 個結點，而算法僅生成了 35 個結點，占總結點的 %。 三、 分支限界法解 01 背包問題 例 ： 已知背包問題 n=4, M=15 (p1, p2, p3, p4) =(10,10,12,18) (w1,w2,w3,w4)=(2, 4, 6, 9) 下面的 數(shù)字： 背包的下界 u， 上面 的數(shù)字： 背包的上界 c’。 首先將根，即結點 1 作為 E結點， c’(1)=38， u(1)=32。由于它不是 答案結點，因此過程 LCBB 置 ans=0 和 U=32+ε。擴展此 E結點，生成它的兩個兒子結點 2和 3，放入活結點表中，結點 2變成下一個 E結點 ，生成結點 4和 5。這樣一步一步向下擴展，在找到結點 8的情況下終止檢索，此時打印出值 38和路徑 8， 7， 4， 2， 1，算法結束。 圖 72 LC 分支限界樹 計算機算法設計與分析 24 / 24 第八章 總結 經(jīng)過這段時間的學習，我不僅僅了解到了書本上的算法知識，還學到了很多算法的思想和設計思路。感謝戴老師這段時間的精彩講述，戴老師堅持親自板書的認真態(tài)度打動了我。 老師不僅僅是講述課本的內(nèi)容，同時還進行擴展 ，講圖靈的故事 、 阿爾法狗 2的事情 ，還有老師探索多邊形的最小外切矩形的故事 。 學習這門課 ， 我最大的收獲是學習理工科的人同時還要對社會科學的東西多了解，這樣自己才會有機會成為大師，而不僅僅是一個技術人員。 在 8 節(jié)算法課里， 我對算法 的設計與分析 有 了更為深入的理解，并主要掌握了分治法、貪心算法、動態(tài) 規(guī)劃法、回溯法和分枝限界算法等。其中分治法主要包括二分檢索、歸并分類、快速分類等，貪心算法則可以較好的解決背包問題、最小生成樹問題以及單源點最短路徑問題，而動態(tài)規(guī)劃法則可以較好的解決多段圖問題，每對結點之間的最短路徑問題，最優(yōu)二分檢索樹問題， 0/1 背包問題，矩陣連乘問題， TSP 問題以及調(diào)度問題等，動態(tài)規(guī)劃將問題實例分解為相似的更小的子問題，并通過求解子問題產(chǎn)生全局最優(yōu)解。它與分治法和貪心法類似，但不同的是，貪心法的當前選擇依賴于已經(jīng)做出的所有選擇，分治法中的各個子問題是獨立的子問題，因而一旦遞歸地求出各個子 問題的解后，即可將子問題的解合并成問題的解。總之，不同的算法各有特點，各有優(yōu)劣，并在解決不同的實際問題中 也帶給了我很多啟示 。 最后，再次慶幸自己選擇了這門課，讓我在學習算法知識的同時，還學到了戴老師認真的科研精神，向班上了學霸們學到了上課 時認真努力的態(tài)度。同時認識到了自己的不足，在以后一定要見賢思齊，寫好程序，做好項目，學以致用。