Ch 3 Dynamic Programming (動態規劃).

Presentation on theme: "Ch 3 Dynamic Programming (動態規劃)."— Presentation transcript:

1 Ch 3 Dynamic Programming (動態規劃)

2 Dynamic Programming 將問題切成兩個或以上較小的問題來獲得解答 不像Divide & Conquer去盲目計算
計算小實例的結果並加以儲存 Bottom-up

3 Fibonacci Sequence f0=1 f1=1 fn=fn-1+fn-2 for n>=2 T(n) > 2n/2

4 Fibonacci Sequence 演算法1.6(Divide & Conquer)

5 Fibonacci Sequence 演算法1.7(Dynamic programming)

6 Fibonacci Sequence 演算法1.6(Divide and Conquer) vs. 1.7(Dynamic programming)

7 Binomial Coefficient 0≦k≦n 0<k<n 遞迴表示式 k=0 or k=n

8 Binomial Coefficient 驗算法3.1 T(n)=

9 Binomial Coefficient(DP版)
Pascal’s triangle

10 Binomial Coefficient(DP版)

11 Binomial Coefficient(DP版)
演算法3.2 (nk)

12 Floyd’s shorest length
Weighted graph

13 Weighted graph

14 Shortest length

15 Floyd’s shortest length I
演算法3.3 T(n)=n3

16 Floyd’s shortest length II
W  P  D

17 Floyd’s shortest length II

18 最佳化原則 最佳化原則(principle of optimality)： 當一個問題存在著最佳解，則表示其所有的子問題也必存在著最佳解

19 連鎖矩陣相乘 M:相乘最少次數 P:分割點

20 連鎖矩陣相乘 矩陣相乘： 列x行 與相乘順序無關 不同順序會影響乘法總次數 目的： 找出最佳順序使得乘法次數最少

21 連鎖矩陣相乘 標註： 矩陣Ak的列數為dk-1，行數為dk，維度= dk-1 x dk M[i][j]=矩陣Ai乘到Aj所需的最少乘法數

22 連鎖矩陣相乘(Pascal’s triangle)
d0=5, d1=2, d4=6 132=0+72+5x2x6

23 演算法3.6 T(n) (n3)

24 演算法3.6所產生的陣列P 可以由此陣列得出矩陣相乘 的最佳順序(即乘法次數最少)

25 演算法3.7

26 最佳二元搜尋樹 A:平均時間 R:二元樹根節點

27 最佳二元搜尋樹 二元搜尋樹(binary search tree)定義： 每個節點包含一個key
節點N的左子樹中任一節點的key，必需小於或等於節點N的key 節點N的右子樹中任一節點的key，必需大於或等於節點N的key

28 最佳二元搜尋樹 目的： 從一堆資料建立搜尋時間最短的二元搜尋樹 名詞： key search key機率pi 搜尋keyi所需時間ci

29 演算法3.8 Ci=搜尋keyi所需時間(指令數目) Pi=keyi被當成search key的機率 平均搜尋時間=

30 最佳二元搜尋樹 範例3.7

31 最佳二元搜尋樹

32 演算法3.9 T(n) (n3)

33 最佳二元搜尋樹 演算法3.10

34 售貨員旅行問題 W, D, P

35 售貨員旅行問題 有向權重圖

36 售貨員旅行問題 每個點都需要經過一次，再回到原出發點 旅程：由某頂點出發，經過所有頂點一次，再回到該點 W:相鄰矩陣 D:最短路徑長度
D[vi][A]=從vi出發經過A所有頂點一次再回到v1 P:紀錄路徑上的頂點

37 售貨員旅行問題 V:所有頂點集合 A:V的子集合 D[vi][A]=從vi出發經過A所有頂點一次再回到v1的最短路徑
P[i][A]:紀錄路徑上的頂點，從vi出發經過所有頂點一次，回到v1的路徑上，位在vi後面的第一個頂點

38 售貨員旅行問題 最佳TOUR長度=min(W[1][j]+D[vj][V-{v1,vj}]) 一般式： T(n)(n22n)

39 售貨員旅行問題-演算法3.11