建立最佳二元搜寻树演算法.PPT

動態規劃 Dynamic Programming 演算法方式總覽 The Divide-and-Conquer Strategy (個各擊破) binary Searching、Quick Sort…. The Greedy Method(貪婪演算法) Prim MST、Kruskal MST、Djikstras algorithm Dynamic Programming(動態演算法) 二項是係數、矩陣連乘、最佳二元搜尋樹… Trace Back(回溯) 圖形著色、漢米爾迴路問題…. Tree Searching Strategy(樹的追蹤) 費氏數列(Fibonacci sequence) Fibonacci sequence: 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , … Fi = i if i ? 1 Fi = Fi-1 + Fi-2 if i ? 2 Solved by a recursive program: Much replicated computation is done. It should be solved by a simple loop. Dynamic Programming Dynamic Programming is an algorithm design method that can be used when the solution to a problem may be viewed as the result of a sequence of decisions 動態規劃介紹 當ㄧ個問題可以被分解成數各的性質相同的小問題。 會先計算較小的問題的結果，並且存儲。 如果有需要先前已經計算過的部份，就不需要重新計算，直接從先前存儲的結果中獲得。 由最小的問題開始計算，循序向上求取最後整個問提的答案。 是一種由下而上（bottom-up）的解決問題的方式。 動態規劃設計步驟 建立一個遞迴機制，用它來求取ㄧ個問題經過切割後，所產生較小但性質相同的問題解。 用Bottom-up的方式解題，首先由最小的問題開始，逐步向上求取最後整各問題的解。 動態規劃 VS 個各擊破 相同 將ㄧ個問題切成數個較小問題來解。 相異 會先計算較小的問題並儲存計算結果(動態規劃) 有計算過的小問題就無須重複計算(動態規劃) Bottom-up的方式(動態規劃) 盲目的遞迴計算(個各擊破) 最短路徑(The shortest path) To find a shortest path in a multi-stage graph Apply the greedy method : the shortest path from S to T : 1 + 2 + 5 = 8 The shortest path in multistage graphs e.g. The greedy method can not be applied to this case: (S, A, D, T) 1+4+18 = 23. The real shortest path is: (S, C, F, T) 5+2+2 = 9. 動態規劃 Dynamic programming approach (forward approach): d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)} = min{9+18, 5+13, 16+2} = 18. d(C, T) = min{ 2+d(F, T) } = 2+2 = 4 d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} = min{1+22, 2+18, 5+4} = 9. Backward approach d(S, A) = 1 d(S, B) = 2 d(S, C) = 5 d(S,D)=min{d(S,A)+d(A,D), d(S,B)+d(B,D)} = min{ 1+4, 2+9 } = 5 d(S,E)=min{d(S,A)+d(A,E), d(S,B)+d(B,E)} = min{ 1+11, 2+5 } = 7 d(S,F)=min{d(