Ch 3 Dynamic Programming (動態規劃)
Dynamic Programming 將問題切成兩個或以上較小的問題來獲得解答 不像Divide & Conquer去盲目計算 計算小實例的結果並加以儲存 Bottom-up
Fibonacci Sequence f0=1 f1=1 fn=fn-1+fn-2 for n>=2 T(n) > 2n/2
Fibonacci Sequence 演算法1.6(Divide & Conquer)
Fibonacci Sequence 演算法1.7(Dynamic programming)
Fibonacci Sequence 演算法1.6(Divide and Conquer) vs. 1.7(Dynamic programming)
Binomial Coefficient 0≦k≦n 0<k<n 遞迴表示式 k=0 or k=n
Binomial Coefficient 驗算法3.1 T(n)=2 -1
Binomial Coefficient(DP版) Pascal’s triangle
Binomial Coefficient(DP版)
Binomial Coefficient(DP版) 演算法3.2 (nk)
Floyd’s shorest length Weighted graph
Weighted graph
Shortest length
Floyd’s shortest length I 演算法3.3 T(n)=n3
Floyd’s shortest length II W P D
Floyd’s shortest length II
最佳化原則 最佳化原則(principle of optimality)： 當一個問題存在著最佳解，則表示其所有的子問題也必存在著最佳解
連鎖矩陣相乘 M:相乘最少次數 P:分割點
連鎖矩陣相乘 矩陣相乘： 列x行 與相乘順序無關 不同順序會影響乘法總次數 目的： 找出最佳順序使得乘法次數最少
連鎖矩陣相乘 標註： 矩陣Ak的列數為dk-1，行數為dk，維度= dk-1 x dk M[i][j]=矩陣Ai乘到Aj所需的最少乘法數
連鎖矩陣相乘(Pascal’s triangle) d0=5, d1=2, d4=6 132=0+72+5x2x6
演算法3.6 T(n) (n3)
演算法3.6所產生的陣列P 可以由此陣列得出矩陣相乘 的最佳順序(即乘法次數最少)
演算法3.7
最佳二元搜尋樹 A:平均時間 R:二元樹根節點
最佳二元搜尋樹 二元搜尋樹(binary search tree)定義： 每個節點包含一個key 節點N的左子樹中任一節點的key，必需小於或等於節點N的key 節點N的右子樹中任一節點的key，必需大於或等於節點N的key
最佳二元搜尋樹 目的： 從一堆資料建立搜尋時間最短的二元搜尋樹 名詞： key search key機率pi 搜尋keyi所需時間ci
演算法3.8 Ci=搜尋keyi所需時間(指令數目) Pi=keyi被當成search key的機率 平均搜尋時間=
最佳二元搜尋樹 範例3.7
最佳二元搜尋樹
演算法3.9 T(n) (n3)
最佳二元搜尋樹 演算法3.10
售貨員旅行問題 W, D, P
售貨員旅行問題 有向權重圖
售貨員旅行問題 每個點都需要經過一次，再回到原出發點 旅程：由某頂點出發，經過所有頂點一次，再回到該點 W:相鄰矩陣 D:最短路徑長度 D[vi][A]=從vi出發經過A所有頂點一次再回到v1 P:紀錄路徑上的頂點
售貨員旅行問題 V:所有頂點集合 A:V的子集合 D[vi][A]=從vi出發經過A所有頂點一次再回到v1的最短路徑 P[i][A]:紀錄路徑上的頂點，從vi出發經過所有頂點一次，回到v1的路徑上，位在vi後面的第一個頂點
售貨員旅行問題 最佳TOUR長度=min(W[1][j]+D[vj][V-{v1,vj}]) 一般式： T(n)(n22n)
售貨員旅行問題-演算法3.11