Chương 3 Quy hoạch động

TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH -----------***----------- THUẬT TOÁN (Algorithms) Nguyễn Thanh Cẩm Nguyễn Thanh Cẩm Nội Dung THUẬT TOÁN VÀ ĐỘ PHỨC TẠPC1 CHIA ĐỂ TRỊC2 QUY HOẠCH ĐỘNGC3 THUẬT TOÁN THAM LAMC4 THUẬT TOÁN QUAY LUIC5 Nguyễn Thanh Cẩm QUY HOẠCH ĐỘNG  Chia để trị là thiết kế thuật toán theo kiểu từ trên xuống (top-down)  Quy hoạch động là quá trình tiếp cận thuật toán theo quá trình ngược lại, đó là thiết kế theo kiểu từ dưới lên (bottom-up).  Điểm khác cơ bản của quy hoạch động với phương pháp chia để trị đó là:  các bài toán con không độc lập với nhau,  nghĩa là các bài toán con cùng có chung các bài toán con nhỏ hơn.  Trong tình huống đó, phương pháp chia để trị sẽ tỏ ra không hiệu quả, khi nó phải lặp đi lặp lại việc giải các bài toán con chung đó.  Quy hoạch động sẽ giải một bài toán con một lần và lời giải của các bài toán con sẽ được ghi nhận, nhằm thoát khỏi việc giải lại các bài toán con mỗi khi ta cần lời giải của nó. Nguyễn Thanh Cẩm QUY HOẠCH ĐỘNG Trong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure). Nhà toán học Richard Bellman đã phát minh phương pháp quy hoạch động vào năm 1953. Nguyễn Thanh Cẩm 2.1 2.2 2.2.1 2.2.2 Thuật toán quy hoạch động tổng quát Một số thí dụ minh họa Bài toán thực hiện dãy phép nhân ma trận Bài toán tìm đường đi ngắn nhất ­ thuật toán Floy QUY HOẠCH ĐỘNG Bài toán dãy con lớn nhất2.2.3 Bài toán dãy con chung dài nhất2.2.4 Nguyễn Thanh Cẩm 3.1 Thuật toán quy hoạch động tổng quát  Để giải một bài toán bằng quy hoạch động, chúng ta cần tiến hành những công việc sau:  Tìm nghiệm của các bài toán con (các trường hợp riêng) đơn giản nhất.  Tìm ra các công thức (hoặc quy tắc) xây dựng nghiệm của bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ hơn.  Tạo ra một bảng để lưu giữ các nghiệm của các bài toán con. Sau đó tính nghiệm của các bài toán con theo các công thức đã tìm ra và lưu vào bảng.  Từ bảng đã làm đầy, tìm cách xây dựng nghiệm của bài toán đã cho. Nguyễn Thanh Cẩm 3.1 Thuật toán quy hoạch động tổng quát  Việc phát triển giải thuật dựa trên quy hoạch động có thể chia làm 3 giai đoạn:  Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ hơn có cùng dạng với bài toán ban đầu sao cho bài toán con kích thước nhỏ nhất có thể giải một cách trực tiếp. Bản thân bài toán xuất phát có thể coi là bài toán con có kích thước lớn nhất trong họ các bài toán con này.  Ghi nhận lời giải: Lưu trữ lời giải của các bài toán con vào một bảng. Việc làm này là cần thiết vì lời giải của các bài toán con thường được sử dụng lại rất nhiều lần, và điều đó nâng cao hiệu quả của giải thuật do không phải giải lặp lại cùng một bài toán nhiều lần.  Tổng hợp lời giải: Lần lượt từ lời giải của các bài toán con kích thước nhỏ hơn tìm cách xây dựng lời giải của bài toán kích thước lớn hơn, cho đến khi thu được lời giải của bài toán xuất phát (là bài toán con có kích thước lớn nhất). Nguyễn Thanh Cẩm 3.1 Thuật toán quy hoạch động tổng quát  Có hai tính chất quan trọng mà một bài toán tối ưu cần phải thoả mãn để có thể áp dụng quy hoạch động để giải nó là:  Cấu trúc con tối ưu: Để giải được bài toán đặt ra một cách tối ưu, mỗi bài toán con cũng phải được giải một cách tối ưu.  Số lượng các bài toán con phải không quá lớn. Rất nhiều các bài toán NP (xem [1] trang 234) – khó có thể giải được nhờ quy hoạch động, nhưng việc làm này là không hiệu quả do số lượng các bài toán con tăng theo hàm mũ. Một đòi hỏi quan trọng đối với quy hoạch động là tổng số các bài toán con cần giải là không quá lớn, cùng lắm phải bị chặn bởi một đa thức của kích thước dữ liệu vào. Nguyễn Thanh Cẩm 2.1 2.2 2.2.1 2.2.2 Thuật toán quy hoạch động tổng quát Một số thí dụ minh họa Bài toán thực hiện dãy phép nhân ma trận Bài toán tìm đường đi ngắn nhất ­ thuật toán Floy QUY HOẠCH ĐỘNG Bài toán dãy con lớn nhất2.2.3 Bài toán dãy con chung dài nhất2.2.4 Nguyễn Thanh Cẩm 3.2.1 3.2.2 Bài toán thực hiện dãy phép nhân ma trận Bài toán tìm đường đi ngắn nhất ­ thuật toán Floy 3.2 Một số thí dụ minh họa Bài toán dãy con lớn nhất3.2.3 Bài toán dãy con chung dài nhất3.2.4 Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Tích của ma trận A = (aik) kích thước p x q với ma trận B = (bkj) kích thước q x r là ma trận C = (cij) kích thước p x r với các phần tử của C được tính theo công thức: 1 <= i <= p, 1 <= j <= r.  Thí dụ: A là ma trận kích thước 2×3, B là ma trận kích thước 3×4, thì C là ma trận kích thước 2×4.    q k kjikij bac 1 ,                        831048974 38413529 9876 5432 1987 654 321 Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Chúng ta có thể sử dụng đoạn chương trình sau đây để tính tích của hai ma trận A, B: for (i =1; i <= p;i++) for (j =1 ; j <= r;j++) { c [i, j] = 0 for( k = 1 ;k<= q;k++) c[i, j] = c[i, j] + a[i, k] *b[k, j]; }  Rõ ràng, đoạn chương trình trên đòi hỏi thực hiện tất cả p.q.r phép nhân vô hướng để tính tích của hai ma trận. Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Thí dụ: như ma trận ở trên thì:  Phần tử dòng 1 cột 1 của ma trận C được tính như sau:1×7 + 2×2 + 3×6 = 29 nên nó có 3 phép nhân vô hướng.  Phần tử dòng 1 cột 2 được tính: 1×8 + 2×3 + 3×7 = 35 nên cũng có 3 phép nhân vô hướng,…  Suy ra số phép nhân vô hướng (phí tổn) của 2 ma trận A và B là: 2×3×4 = 24 phép nhân. Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Bây giờ ta xét tích của 4 ma trận A, B, C, D với kích trước lần lượt như sau: A × B × C × D (*) [20×2] [2×30] [30×12] [12×8] Một điều nên lưu ý là, để thực hiện được tích của các ma trận ở trên, đòi hỏi chúng phải tương thích với nhau. Tức là số cột của A phải đúng bằng số dòng của B, số cột của B phải đúng bằng số dòng của C,… Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Do phép nhân ma trận không có tính chất giao hoán, nhưng lại có tính chất kết hợp nên tích của 4 ma trận trên có thể được tính bằng nhiều cách như sau:  A(B(CD)) 30×12×8 + 2×30×8 + 20×2×8 = 3.680  (AB)(CD) 20×2×30 + 30×12×8 + 20×30×8 = 8.880  A((BC)D) 2×30×12 + 2×12×8 + 20×2×8 = 1.232  ((AB)C)D 20×2×30 + 20×30×12 + 20×12×8 = 10.320  (A(BC))D 2×30×12 + 20×2×12 + 20×12×8 = 3.120 Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Từ kết quả trên ta thấy, trình tự thực hiện có ảnh hưởng lớn tới phí tổn để thực hiện dãy phép nhân của các ma trận. Bài toán đặt ra là tính số phí tổn ít nhất có thể được, khi thực hiện dãy phép nhân của n ma trận. M = M1*M2*…Mn  Với: M1 là ma trận có kích thước a1×a2 M2 là ma trận có kích thước a2×a3 …. Mn là ma trận có kích thước an×an+1  Suy ra a[1..n+1] là vector kích thước của các ma trận. Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Áp dụng phương pháp quy hoạch động chúng ta sẽ giải quyết bài toán theo kiểu “bottom-up”:  Gọi F[i, j] là số phép nhân tối thiểu cần thực hiện để nhân đoạn ma trận liên tiếp: Mi*Mi+1*…*Mj (1 <= i <= j <= n).  Khi đó F[i, i] = 0 với mọi i.  Để tính Mi*Mi+1*…*Mj ta có thể có nhiều cách kết hợp: Mi*Mi+1*…*Mj = (Mi*Mi+1*…*Mk)*(Mk+1*…*Mj-1*Mj) với i<= k <j. Với mỗi cách kết hợp (phụ thuộc vào cách chọn vị trí k), chi phí tối thiểu phải thực hiện bằng:  Chi phí thực hiện phép nhân: Mi*Mi+1*…*Mk = F[i, k]  Cộng với chi phí thực hiện phép nhân: Mk+1*…*Mj-1*Mj = F[k+1, j] Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Cộng với chi phí thực hiện phép nhân hai ma trận cuối cùng: ma trận tạo thành từ phép nhân Mi*Mi+1*…*Mk có kích thước ai×ak+1, và ma trận tạo thành từ phép nhân Mk+1*…*Mj-1*Mj có kích thước ak+1×aj+1, vậy chi phí này là : ai×ak+1×aj+1.  Từ đó suy ra: do có nhiều cách kết hợp, mà ta cần chọn cách kết hợp để có chi phí ít nhất nên ta sẽ cực tiểu hóa F[i, j] theo công thức:  F[i, j] = min(F[i, k] + F[k+1,j] + ai*ak+1*aj+1) mọi i<= k <j. (3.1) Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận Tính bảng phương án: Bảng phương án F là bảng hai chiều, nhìn vào công thức (3.1) ta thấy để tính được F[i, j] khi ta đã biết F[i, k] và F[k+1, j] tức là ban đầu ta điền cơ sở quy hoạch động vào đường chéo chính của bảng (F[i, i] = 0) từ đó tính các giá trị thuộc đường chéo nằm phía trên (tính các F[i, i+1]), rồi lại tính các giá trị nằm phía trên nữa (F[i, i+2])… dến khi tính được F[1, n] thì dừng lại. Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Tìm cách kết hợp tối ưu:  Tại mỗi bước tính F[i, j], ta ghi nhận lại điểm k mà cách tính (Mi*Mi+1*…*Mk)*(Mk+1*…*Mj-1*Mj) cho số phép nhân vô hướng nhỏ nhất, chẳng hạn ta đặt F[i, j] = k. Khi đó muốn in ra phép kết hợp tối ưu để nhân đoạn Mi*Mi+1*…*Mk*Mk+1*…*Mj-1*Mj ta sẽ in ra cách kết hợp tối ưu để nhân đoạn Mi*Mi+1*…*Mk và cách kết hợp tối ưu để nhân đoạn Mk+1*…*Mj- 1*Mj (có kèm theo dấu mở ngoặc) đồng thời viết thêm dấu “*” vào giữa hai biểu thức đó. Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Ta có hàm:  int Minmult(int n, const int a[], index P[][]) //a[] kích thước của các ma trận  { //P[][] là ma trận lưu vị trí kết hơp k tối ưu  index i, j, k, d;  int F[1..n][1..n];  for (i = 1; i <= n; i++)  F[i][i] = 0;  for (d = 1; d <= n-1; d++) //d là đường chéo  for (i = 1; i <= n-d; i++)  {  j = i +d;  for (k = i; k<j; k++)  F[i][j] = min(F[i][k] + F[k+1][j] + ai*ak+1*aj+1);  P[i][j] = k sao cho F[i][j] dat min  }  return M[1][n];  } Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Thí dụ 2: Tìm cách tính tối ưu cho tích của bốn ma trận cho trong (*).  Ta có a = (20, 2, 30, 12, 8).  Với d = 1, F[1,2] = 1200, F[2,3] = 720 và F[3,4] = 2880.  Tiếp theo, với d = 2 ta thu được F[1,3] = min(F[1,1] + F[2,3] + 20 x 2 x 12, F[1,2] + F[3,3] + 20 x 30 x 12) = min(1200, 8400) = 1200 F[2,4] = min(F[2,2] + F[3,4] + 2 x 30 x 8, F[2,3] + F[4,4] + 2 x 12 x 8) = min(3360, 912) = 912  Cuối cùng với d = 3 ta có F[1,4] = min(F[1,1] + F[2,4] + 20 x 2 x 8), {k = 1} F[1,2] + F[3,4] + 20 x 30 x 8, {k = 2} F[1,3] + F[4,4] + 20 x 12 x 8, {k = 3} = min(1232, 8880, 3120) = 1232. Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Giá trị F được cho trong bảng dưới đây  Bảng 3.1 Bảng giá trị F j=1 2 3 4 i=1 0 1200 1200 1232 2 0 720 912 d = 3 3 0 2880 d = 2 4 0 d = 1 d = 0 Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Để tìm lời giải tối ưu, ta sử dụng bảng P[i][j] ghi nhận cách đặt dấu ngoặc tách đầu tiên cho giá trị F[i][j]. Cùng với việc tính các giá trị F[i][j], ta sẽ tính P[i][j] theo quy tắc: d = 1: F[i][i+1] = ai×ak+1×aj+1 P[i][i+1] = i+1 1< d < n: F[i][i+d] = min(F[i][k] + F[k+1][i+d] + aiakai+d) P[i][i+d] = k Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Thí dụ 3: Các giá trị của P[i, j] theo (*) được cho trong bảng dưới đây:  Bảng 3.2 Các giá trị của P[i, j] j=1 2 3 4 i=1 1 2 1 1 2 2 3 2 d =3 3 3 4 d =2 4 4 d =1 d =0 Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Ta có số phép nhân cần thực hiện là F[1,4] = 1232. Dấu ngoặc đầu tiên cần đặt sau vị trí P[1,4] = 1, tức là M = A(BCD). Ta tìm cách đặt dấu ngoặc đầu tiên để có F[2,4] tương ứng với tích BCD. Ta có P[2,4] = 2, tức là tích BCD được tính tối ưu theo cách: BCD = (BC)D. Từ đó suy ra, lời giải tối ưu là: M = A((BC)D).  Bây giờ, ta tính số phép toán cần thực hiện theo thuật toán vừa trình bày. Với mỗi d > 0, có n – d phần tử trên đường chéo cần tính, để tính mỗi phần tử đó ta cần so sánh d giá trị số tương ứng với các giá trị có thể của k. Từ đó suy ra số phép toán cần thực hiện theo thuật toán là cỡ )( 6/)( 6/)12)(1(2/)1( )( 3 3 2 1 1 1 1 1 1 2 nO nn nnnnn ddnddn n d n s n d             Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Thuật toán trình bày có thể mô tả trong hai thủ tục sau:  void Matrix­Chain(a,n) /* F[i,j] - chi phí tối ưu thực hiện nhân dãy Mi . . . Mj; P[i,j] - ghi nhận vị trí đặt dấu ngoặc đầu tiên trong cách thực hiện nhân dãy Mi . . . Mj */ {for (i = 1;i<= n;i++) F[i,i] = 0; //khởi tạo for (d = 1 ;d<= n;d++) // d = chỉ số của đường chéo for (i = 1;i<= n – d;i++) { j = i + d - 1; F[i,j] = +; for (k = i;k<= j – 1;k++) { q = F[i,k] + F[k+1,j] + a[i]*a[k+1]*a[j+1]; if(q <F[i,j]) then { F[i,j] = q; P[i,j] = k; } } } } Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Thủ tục đệ quy sau đây sử dụng mảng ghi nhận h để đưa ra trình tự nhân tối ưu.  void Mult(i,j); { if(i<j) { k = P[i,j]; X = Mult(i,k); // X = M[i] / . . . M[k] Y = Mult(k+1,j); // Y = M[k+1] . . . M[j] return X*Y; // Nhân ma trận X và Y } else return M[i]; } Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Như đã trình bày ở trên một trong những điều kiện để áp dụng được quy hoạch động để giải bài toán tối ưu là số lượng các bài toán con phải không quá lớn, nghĩa là thuật toán đệ quy để giải bài toán phải giải đi, giải lại cùng một bài toán con chứ không phải luôn giải các bài toán con mới. Khi một thuật toán đệ quy phải giải đi, giải lại cùng một bài toán con ta sẽ nói là bài toán tối ưu có các bài toán con trùng lặp. Để minh họa cho tính chất này, ta sẽ tìm hiểu bài toán nhân dãy ma trận.  Xét thuật toán đệ quy sau đây để tính F[i,j] là số phép nhân ít nhất cần thực hiện để tính tích dãy ma trận MiMi+1 … Mj.  RMat(a,i,j); { If( i == j) return 0; F[i,j] = ; for (k = I;k<= j – 1;k++) { q = RMat(a,i,k) + RMat(a, k+1,j) + d[i]*d[k+1]*d[j+1]; if q < F[i,j] then F[i,j]: = q; } } Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Để tính giá trị F[1,4] chúng ta phải thực hiện  · 4 lần gọi RMat(a,1,1),  · 5 lần gọi RMat(a,2,2),  · 5 lần gọi RMat(a,3,3),  · 3 lần gọi RMat(a,4,4),  · 2 lần gọi RMat(a,1,2),  · 2 lần gọi RMat(a,2,3),  · ….. Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Hình vẽ dưới đây cho thấy cây đệ quy thực hiện lệnh gọi RMat(a,1,4). Mỗi đỉnh của cây được đánh dấu bởi giá trị của hai tham số i, j. Nguyễn Thanh Cẩm 3.2.1 Bài toán thực hiện dãy phép nhân ma trận  Ta có thể chứng minh thời gian tính T(n) của lệnh gọi RMat(a,1,n) thực hiện thủ tục đệ quy trên để tính m[1,n] tăng theo hàm mũ của n. Thật vậy, ta có:  Do đó  Với n >1  Từ công thức cuối cùng có thể chứng minh bằng quy nạp là T(n) = 2n.      1 1 )1)()((1)( 1)1( n k knTknT T               1 1 1 1 1 1 1 1 )(2 )(21 )1)()((1)( n i n i n k n k iTn iTk knTkTnT Nguyễn Thanh Cẩm 3.2.1 3.2.2 Bài toán thực hiện dãy phép nhân ma trận Bài toán tìm đường đi ngắn nhất ­ thuật toán Floy 3.2 Một số thí dụ minh họa Bài toán dãy con lớn nhất3.2.3 Bài toán dãy con chung dài nhất3.2.4 Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy  nhắc lại sơ lược về lý thuyết đồ thị. Hình 3.2 ở dưới là một đồ thị có hướng có trọng số. 1 3 9 5 1 2 3 3 2 4 Hình 3.2 Đồ thị có hướng có trọng số V5 V1 V2 V3V4 Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy  ví dụ trong hình 3.2 để đi từ v1 đến v3 ta có 3 đơn đường đi là: [v1, v2, v3], [v1, v4, v3], [v1, v2, v4, v3]. Vì thế độ dài của các đường đi này là:  length [v1, v2, v3] = 1+3 = 4  length[v1, v4, v3], = 1+2 = 3  length[v1, v2, v4, v3] = 1+2+2 = 5  Vậy [v1, v4, v3] là đường đi ngắn nhất từ v1 đến v3. Như đã đề cập ở trên, một ứng dụng phổ biến của đường đi ngắn nhất là xác định lộ trình ngắn nhất giữa các thành phố. Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy  Để tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v, ta liệt kê tất cả các đường đi từ u đến v (có thể có). Sau đó chọn đường đi ngắn. Tuy nhiên thuật toán này là không khả thi vì có độ phức tạp lớn hơn là thời gian hàm mũ.  Nếu gọi T(n) là thời gian thực hiện thuật toán trên thì ta có T(n) = (n-2)! nên suy ra T(n) = O(n!), điều này là tồi hơn thời gian hàm mũ. Mục đích của chúng ta là tìm ra một thuật toán có hiệu quả hơn. Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Áp dụng phương pháp quy hoạch động cho bài toán tìm đường đi ngắn nhất, chúng ta có thể thực hiện như sau:  Gọi W[i][j] là ma trận trọng số của đồ thị và được định nghĩa: 0 , nếu i = j W[i][j]= trọng số trên cạnh , nếu có cung từ vi đến vj ∞ , nếu không có cung từ vi đến vj. Bảng 3.3 dưới đây là ma trận trọng số của đồ thị ở hình 3.2 Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy  Bảng 3.3 Ma trận trọng số của đồ thị ở hình 3.2 1 2 3 4 5 1 0 1 ∞ 1 5 2 9 0 3 2 ∞ 3 ∞ ∞ 0 4 ∞ 4 ∞ ∞ 2 0 3 5 3 ∞ ∞ ∞ 0 Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy  Bảng 3.4 Ma trận D chứa đường đi ngắn nhất giữa các cặp đỉnh trên đồ thị hình 1 2 3 4 5 1 0 1 3 1 4 2 8 0 3 2 5 3 10 11 0 4 7 4 6 7 2 0 3 5 3 4 6 4 0 Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy  Tại sao chúng ta có thể tính D từ W. Minh họa điều này chúng ta sẽ tính một vài giá trị mẫu của D(k)[i][j] cho đồ thị ở hình 3.2  D0[2][5] = length[v2, v5] = ∞  D1[2][5] = min(length[v2, v5], length[v2, v1, v5]) = min(∞,14) = 14  D2[2][5] = D1[2][5] = 14 (vì v2 là đỉnh khởi đầu nên không thể là đỉnh trung gian)  D3[2][5] = D2[2][5] = 14 (vì không có đường đi từ v3 đến v5)  D4[2][5] = min(D3[2][5], length[v2, v4 ,v5]) = min(14, 5) = 5  Và cuối cùng giá trị tính toán D5[2][5] = 5 là chiều dài của đường đi ngắn nhất từ v2 đến v5 đã đi qua các đỉnh trung gian. Điều này có nghĩa nó là chiều dài của đường đi ngắn nhất.  Như vậy D(n)[i][j] là chiều dài của đường đi ngắn nhất từ vi đến vj vượt qua các đỉnh trung gian, và D(0)[i][j] là chiều dài của đường đi ngắn nhất không vượt qua các đỉnh còn lại, nó là trọng số từ vi đến vj chúng ta đã thiết lập D(0) = W và D(n) = D  Vì thế để xác định D từ W chúng ta chỉ cần tìm cách để đạt được D(n) từ D(0). Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy  Sử dụng phương pháp quy hoạch động ta có thể thực hiện như sau:  Cho k chạy từ 1 đến n, tính D(k) thông qua D(k-1). Như vậy ta đã tao ra một dãy  D(0), D(1), D(2), …, D(n) W D  Để tính D(k) thông qua D(k-1) ta có thể thực hiện theo hai trường hợp sau:  Trường hợp 1: đường đi ngắn nhất từ vi đến vj dùng các đỉnh trung gian trong {v1, v2,…,vk} trừ vk thì  D(k)[i][j] = D(k-1)[i][j] (3.1) Nguyễn Thanh Cẩm 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy  một ví dụ của trường hợp này là ở bảng 3.3 D(5)[1][3] = D(4)[1][3] = 3 bởi vì khi chúng ta chọn đỉnh v5 làm đỉnh trung gian trên đường đi ngắn nhất từ v1 đến v3 thì ta không chọn được v5 nên đường đi chỉ còn [v1, v4, v3].  Trường hợp 2: đường đi ngắn nhất từ vi đến vj sử dụng các đỉnh trung gian trong [v1, v2, .., vk] và sử dụng vk trong trường hợp này thì đường đi ngắn nhất là:  D(k)[i][j] = D(k-1)[i][k] + D(k-1)[k][j] (3.2)  Một ví dụ của trường hợp 2 trong bảng 3.3 là:  D(2)[5][3] = 7 = 4 + 3 = D(1)[5][2] + D(1)[2][3]  Bởi vì chúng ta phải có trường hợp 1 hoặc trường hợp hai giá trị của D(k)[i][j] là min của các giá trị bên phải của biểu thức 3.3 và 3.4 điều này có nghĩa là chúng ta xác định D(k) từ D(k-1) theo công thức sau:  D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k