演算法 Algorithm ─ Dynamic Programming

 Dynamic Programming <動態演算法>

解題步驟 & 特性：
          
                           ○  先將問題拆解成各個相同類型的小問題   (同各個擊破法)
                           ○  在由最小的問題開始計算結果並儲存結果
                           ○  有計算過的問題就不重複計算，從之前儲存的結果取出來用
                           ○  分解問題： 由上而下， 解決問題：由下而上

__________________________________________________________________________________________

範例： 用動態演算法求出下圖的最短路徑

      



# d：最短路徑

d(S,T)= min{1+d(A,T), 3+d(B,T), 5+d(C,T)}

d(A,T)= min{7+d(D,T)} = 7+2  =9

d(B,T)= min{9,11+d(D,T),8+d(E,T)}
          
         = min{9,11+2,8+5}
          
         = 9

d(C,T)= min{5+d(E,T)} = 13+1  =14


d(S,T)= min{1+d(A,T), 3+d(B,T), 5+d(C,T)}

         = min{1+9, 3+9, 5+14}
         
         = 10



求出最短路徑為：S→A→D→T  (10)