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
Nội Dung
C1 THUẬT TOÁN VÀ ĐỘ PHỨC TẠP
C2 CHIA ĐỂ TRỊ
C3 QUY HOẠCH ĐỘNG
C4 THUẬT TOÁN THAM LAM
Nguyễn Thanh Cẩm
C5 THUẬT TOÁN QUAY LUI
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
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
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
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
QUY HOẠCH ĐỘNG
Thuật toán quy hoạch động tổng quát 2.1
Một số thí dụ minh họa 2.2
2.2.1
Bài toán thực hiện dãy phép nhân ma trận
2.2.2
Bài toán tìm đường đi ngắn nhất thuật toán Floy
Bài toán dãy con lớn nhất
2.2.3
2.2.4
Bài toán dãy con chung dài nhất
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
Tìm nghiệm của các bài toán con (các trường hợp
ta cần tiến hành những công việc sau:
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ấ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
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à:
QUY HOẠCH ĐỘNG
Thuật toán quy hoạch động tổng quát 2.1
Một số thí dụ minh họa 2.2
2.2.1
Bài toán thực hiện dãy phép nhân ma trận
2.2.2
Bài toán tìm đường đi ngắn nhất thuật toán Floy
Bài toán dãy con lớn nhất
2.2.3
2.2.4
Bài toán dãy con chung dài nhất
Nguyễn Thanh Cẩm
3.2 Một số thí dụ minh họa
3.2.1
Bài toán thực hiện dãy phép nhân ma trận
3.2.2
Bài toán tìm đường đi ngắn nhất thuật toán Floy
Bài toán dãy con lớn nhất
3.2.3
3.2.4
Bài toán dãy con chung dài nhất
Nguyễn Thanh Cẩm
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:
q
c
,
ij
ba ik
kj
3.2.1 Bài toán thực hiện dãy phép nhân ma trận
k
1
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.
1987 5432
321 654
29 74
35 89
41 104
38 83
9876
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];
Nguyễn Thanh Cẩm
} 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.
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
Nguyễn Thanh Cẩm
trận A và B là: 2×3×4 = 24 phép nhân.
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 (*)
Nguyễn Thanh Cẩm
[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,…
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:
Nguyễn Thanh Cẩm
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
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
Nguyễn Thanh Cẩm
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 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 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 Nguyễn Thanh Cẩm i<= k 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 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à Nguyễn Thanh Cẩ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 đó. 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 } return M[1][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
} 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 {k = 1} 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),
F[1,2] + F[3,4] + 20 x 30 x 8,
F[1,3] + F[4,4] + 20 x 12 x 8, {k = 2}
{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 3.2.1 Bài toán thực hiện dãy phép nhân ma trận j=1 2 3 4 i=1 1200 1200 1232 0 0 2 720 912 d = 3 3 0 2880 d = 2 4 0 d = 1 d = 0 Nguyễn Thanh Cẩm Giá trị F được cho trong bảng dưới đây
Bảng 3.1 Bảng giá trị F 3.2.1 Bài toán thực hiện dãy phép nhân ma trận 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 Để 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: 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: j=1 2 3 4 1 2 i=1 1 1 2 2 3 2 d =3 3 3 4 d =2 4 4 d =1 d =0 Nguyễn Thanh Cẩm Bảng 3.2 Các giá trị của P[i, j] 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ỡ n
1 n
1 n
1 2 ddn ) n d
(
d
1
d
2
nn
( 2/)1
1
s
nn
(
1
d
2)(1 n 6/)1 3 ( n n 6/) 3 nO
( ) 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 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: nhân dãy Mi . . . Mj */ {for (i = 1;i<= n;i++) F[i,i] = 0;
for (d = 1 ;d<= n;d++) //khởi tạo
// 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] = q; P[i,j] = k; } } } } Nguyễn Thanh Cẩm void MatrixChain(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 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 để void Mult(i,j);
{ if(i { k = P[i,j];
X = Mult(i,k); // X = M[i] / . . . M[k]
Y = Mult(k+1,j);
return X*Y; // Y = M[k+1] . . . M[j]
// Nhân ma trận X và Y } else return M[i]; } Nguyễn Thanh Cẩm đưa ra trình tự nhân tối ưu. 3.2.1 Bài toán thực hiện dãy phép nhân ma trận Xét thuật toán đệ quy sau đây để tính F[i,j] là số phép nhân ít 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 Nguyễn Thanh Cẩm Để 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),
….. 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ó: T 1)1(
n 1
nT 1)( (( k ) knT ( )1)
1
k 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) n 1
= 2n. nT 1)( kT
)(( knT ( )1)
k 1
n 1
n 1
1
2 iT
)(
k
i 1
k 1
n 1
n
2 iT
)( i 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 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 V1 V2 3 9 5 1 V5 2 3 V4 V3 3 2
4 Hình 3.2 Đồ thị có hướng có trọng số 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à: Nguyễn Thanh Cẩm 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ố. 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ũ. Nguyễn Thanh Cẩ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. 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 0 1 1 5 ∞ 9 0 3 2 ∞ 0 4 ∞ ∞ ∞ 2 0 3 ∞ ∞ 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 0 1 3 1 4 8 0 3 2 5 10 11 0 4 7 6 7 2 0 3 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ì Nguyễn Thanh Cẩm D(k)[i][j] = D(k-1)[i][j] (3.1) 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] + D(k-1)[k][j]) 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ụ:
Cho một đồ thị ở hình 3.2 đồ thị đã mô tả bởi ma trận kề W như
ở bảng 3.3, một vài tính toán đơn giản như sau (với D(0) = W): = min(2, 9+1) = 2 = min(∞, 3+1) = 4 = min(∞, 3+1) = 4 D(1)[2][4] = min(D(0)[2][4], D(0)[2][1] + D(0)[1][4])
D(1)[5][2] = min(D(0)[5][2], D(0)[5][1] + D(0)[1][2])
D(1)[5][4] = min(D(0)[5][4], D(0)[5][1]+D(0)[1][4])
Đầu tiên ta đã có mảng D(1) , mảng D(2) được tính toán như sau:
D(2)[5][4] = min(D(1)[5][4], D(1)[5][2] + D(1)[2][4])
= min(4, 4+2) = 4
Sau khi đã tính D(2) chúng ta tiếp tục tính tương tự cho đến D(5)
mảng D cuối cùng là chiều dài của các đường đi ngắn nhất, nó
thể hiện ở trong bảng 3.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 Thuật toán Floyd tìm đường đi ngắn nhất
Bài toán: tính những đường đi ngắn nhất từ một đỉnh trong đồ thị có trọng số đến các đỉnh còn lại. (trọng số không âm) Input: (W[i][j])n*n là ma trận trọng số n đỉnh của đồ thị đã cho.
Output: (D[i][j])n*n là ma trận trọng số của đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị n đỉnh. void floyd (int n, cónt number W[][], number D[][])
{ index I, j,k:
D=W
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
D[i][j]=min(D[i][j],D[i][k]+D[k][j]); } 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 Phân tích thuật toán:
Vòng lặp bên trong j chạy từ 1 đến n, có 3 vòng for lồng nhau nên: Nguyễn Thanh Cẩm T(n)=n×n×n=O(n3).
Để lưu lại các đường đi ta đưa vào mảng P[][]
P[i][j] = một đỉnh trung gian trên đường đi ngắn
nhất, hoặc bằng 0 nếu không có đỉnh trung gian 3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy void floyd2 (int n, const number W[][], number D[][], index P[][])
{index I,j,k; for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
P[i][j] =0;
D=W;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(D[i][k]+D[k][j] D[i][j]=D[i][k]+D[k][j]; } } 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 Dưới đây là mảng P lưu lại vết các đường đi của bảng 3.4 0 0 4 0 4 5 0 0 0 4 5 5 0 0 4 5 5 5 0 0 0 1 4 1 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 Để in đường đi ngắn nhất ta có thuật toán sau:
void path (index q, r)
{if (P[q][r] !=0)
{path(q,p[q][r]); cout<<”v”< Nguyễn Thanh Cẩm }
} Nguyễn Thanh Cẩm 3.2.3 Bài toán dãy con lớn nhất Trong chương 2 ta đã trình bày thuật toán chia để trị
để giả bài toán dãy con lớn nhất với thời gian tính
T(n) = O(logn) . Nguyễn Thanh Cẩm Một câu hỏi đặt ra là: Có cách nào để giảm thời gian
tính của thuật toán hay không? Câu trả lời là có, nếu
ta tiếp cận bằng phương pháp quy hoạch động để giải
bài toán này. Để đơn giản ta chỉ xét cách tính tổng
của dãy con lớn nhất. 3.2.3 Bài toán dãy con lớn nhất Phân rã. Gọi si là tổng thứ i của dãy con lớn nhất
a1, a2, …., ai
i = 1,2,…, n. Rõ ràng sn là giá trị cần tìm.
Tổng hợp lời giải. Trước hết, ta có sn = a1. Bây Nguyễn Thanh Cẩm giờ giả sử i > 1 và ta đã tính được si-1 . Ở bước thứ i
để tính si là tổng của dãy con lớn nhất của dãy a1,
a2, …, ai-1, ai. 3.2.3 Bài toán dãy con lớn nhất Rõ ràng dãy con lớn nhất của dãy này hoặc là có chứa
phần tử ai hoặc là không chứa phần tử ai, vì thế chỉ
có thể là một trong hai dãy sau đây: ·
· Dãy con lớn nhất của dãy a1, a2, …, ai-1.
Dãy con lớn nhất của dãy a1, a2, …, ai kết thúc tại ai. Từ đó suy ra Si = max {si-1, ei },
Trong đó ei là tổng của dãy con lớn nhất của dãy a1, Nguyễn Thanh Cẩm a2, …, ai kết thúc tại ai. 3.2.3 Bài toán dãy con lớn nhất Lưu ý rằng để tính ei, i = 1, 2, …, n, ta cũng có thể sử dụng công thức đệ quy sau: e1 = a1;
ei = max {ai, ei-1 + ai }, i > 1.
Ví dụ: cho dãy a = (3, 2, -7, 3, -5, 5, 3) thì dãy con lớn nhất là dãy b = (3,-5,5,3) Nguyễn Thanh Cẩm Từ đó, ta có thuật toán sau để giải bài toán đặt ra: 3.2.3 Bài toán dãy con lớn nhất Nguyễn Thanh Cẩm Nguyễn Thanh Cẩm 3.2.4 Bài toán dãy con chung dài nhất Bài toán: Cho hai dãy số nguyên a = (a1, a2, …, am) và b = (b1, b2, …, bn). Cần tìm dãy số nguyên c = (c1, c2,…, ck)
sao cho c a, c b và c có độ dài lớn nhất. Ví dụ: nếu a = (3, 5, 1, 3, 5, 5, 3) và b = (1, 5, 3, 5, 3, 1) thì dãy con chung dài nhất là Nguyễn Thanh Cẩm c = (5, 3, 5, 3) hoặc
c = (1, 3, 5, 3) hoặc
c = (1, 5, 5, 3). 3.2.4 Bài toán dãy con chung dài nhất Thiết kế thuật toán: Duyệt tất cả các dãy con của dãy a và kiểm tra mỗi dãy như vậy có phải là dãy con của b, và Thuật toán đơn giản: Nguyễn Thanh Cẩm Mỗi dãy con của a tương ứng với dãy chỉ số 3.2.4 Bài toán dãy con chung dài nhất Áp dụng quy hoạch động: Nếu m = 0 hoặc n = 0, ta thấy dãy con dài nhất là dãy Nếu m >0 và n >0 ta gọi: (a1, a2,…, ai) là dãy con của dãy a có độ dài i với (b1, b2,…, bj) là dãy con của dãy b có độ dài j với Gọi L(i, j) là độ dài lớn nhất của dãy con chung của hai dãy (a1, a2,…, ai) và (b1, b2,…, bj). Như vậy, L(m, n) sẽ là độ dài lớn nhất của dãy con chung của a và b. Nguyễn Thanh Cẩm 3.2.4 Bài toán dãy con chung dài nhất Bây giờ ta tìm cách tính L(i, j) thông qua L(s, t) với s<= i, t<= j. Nếu i = 0 hoặc j = 0 thì L(i, j) = 0 Nếu i >0 và j >0 và ai <> bj thì Dễ dàng ta thấy sự đúng đắn của các công thức sau: Nếu i >0 và j >0 và ai = bj thì L(i, j) = 1 + L(i-1, j-1) Nguyễn Thanh Cẩm 3.2.4 Bài toán dãy con chung dài nhất Lưu các giá trị L(i, j) vào mảng L[0..m, 0..n]. Nếu biết L[i, j-1], L[i-1, j] và L[i-1, j-1] ta sẽ tính được L[i, j], do đó ta có thể tính được các phần tử của mảng L[0..m, 0..n] 0 1 2 n 0
1
2 m Nguyễn Thanh Cẩm 3.2.4 Bài toán dãy con chung dài nhất Bây giờ từ mảng L đã được làm đầy, ta xây dựng dãy Ta xác định các thành phần của c = (c1, c2,…, ck) lần con chung dài nhất là k = L[m, n]. Trong bảng L ta đi từ ô L[m, n]. Nguyễn Thanh Cẩm 3.2.4 Bài toán dãy con chung dài nhất Giả sử ta đang ở ô L[i, j] và ta đang cần xác định cl Nếu ai = bj thì ta lấy cl = ai, giảm l đi một đơn vị và đi (1<= l<= k). Nếu ai <> bj thì Trong trường hợp L[i, j] = L[i, j-1] ta đi tới ô L[i, j-1]. Còn nếu L[i, j] = L[i-1, j] thì ta đi lên ô L[i-1, j]. Tiếp tục quá trình trên ta xác định được tất cả các Nguyễn Thanh Cẩm thành phần của dãy con dài nhất c. 3.2.4 Bài toán dãy con chung dài nhất void LCS(X[m],Y[n]); Nguyễn Thanh Cẩm 3.2.4 Bài toán dãy con chung dài nhất void Print LCS (b,X,i,j); Nguyễn Thanh Cẩm abcd Nguyễn Thanh Cẩm Nguyễn Thanh Cẩm Bài 1-8/trang 68 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.
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;
}
}
3.2 Một số thí dụ minh họa
3.2.1
Bài toán thực hiện dãy phép nhân ma trận
3.2.2
Bài toán tìm đường đi ngắn nhất
thuật toán Floy
Bài toán dãy con lớn nhất
3.2.3
3.2.4
Bài toán dãy con chung dài nhất
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
3.2 Một số thí dụ minh họa
3.2.1
Bài toán thực hiện dãy phép nhân ma trận
3.2.2
Bài toán tìm đường đi ngắn nhất
thuật toán Floy
Bài toán dãy con lớn nhất
3.2.3
3.2.4
Bài toán dãy con chung dài nhất
void Maxsub(a);
{
// smax tổng của dãy con lớn nhất
// imax vị trí kết thúc của dãy con lớn nhất
smax = a[1];
maxendhere = a[1];
s=1; //vị trí đầu của dãy
imax = 1;
for( i = 2;i<= n;i++)
{
u = maxendhere + a[i];
v = a[i];
if (u > v) maxendhere = u else {maxendhere = v;s=i};
if (maxendhere > smax)
{
smax = maxendhere;
imax = i;
}
Else {smax=0;imax=i}
}
}
Dễ thấy thuật toán Maxsub có thời gian tính là O(n).
3.2 Một số thí dụ minh họa
3.2.1
Bài toán thực hiện dãy phép nhân ma trận
3.2.2
Bài toán tìm đường đi ngắn nhất
thuật toán Floy
Bài toán dãy con lớn nhất
3.2.3
3.2.4
Bài toán dãy con chung dài nhất
giữ lại dãy con dài nhất.
rổng.
0<= i <= m,
0<= j <= n.
L(i, j) = max{L(i, j-1), L(i-1, j)}
lượt từ bên phải.
lên ô L[i-1, j-1].
hoặc L[i, j] = L[i, j-1]
hoặc L[i, j] = L[i-1, j].
{
for (i =1;i<= m;i++) L[i,0]=0;
for (j =1;j<= n;j++) L[0,j]=0;
for( i =1;i<= m;i++)
for( j = 1;j<= n;j++)
if (xi == yi)
{
L[i,j] =L[i-1,j-1]+1;
b[i,j] =1;
}
else
if (L [i-1,j] >= L[i,j-1])
{
L[i,j] =L[i-1,j];
b[i,j] =0;
}
else
{
L[i,j] =L[i,j-1];
b[i,j] =-1;
}
}
Sử dụng bảng b[i, j] để ghi nhận tình huống tối ưu khi tính giá trị
c[i, j] và đưa ra dãy con chung dài nhất của hai dãy X và Y nhờ
hàm sau đây:
{
if (i=0) or (j=0) return 0;
if (b[i,j]=1)
{
// Đưa ra phân tử xi
print LCS (b,X,i1,j1);
print xi;
}
else
if (b[i,j]=0)
PrintLCS (b,X,i1,j)
else
Print LCS (b,X,i,j1);
}
Dễ dàng đánh giá được thời gian tính của thuật toán LCS là O(m.n).
Tổng kết chương
Bài tập
TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN
KHOA KHOA HỌC MÁY TÍNH
-----------***-----------
camcntt@yahoo.com
