Thiết kế và đánh giá thuật toán

f[i,j]:= max(f[i-1,j - x[i]] + x[i] , f[i-1,j]) Nếu không thì f[i,j]:= f[i-1,j]

Đánh giá độ phức tạp của thuật toán:

0(n.m)

3. Bài toán đường đi của người giao hàng

Có một người giao hàng cần đi giao hàng tại n thành phố. Xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác là xác định được. Giả thiết rằng mỗi thành phố đều có đường đi đến các thành phố còn lại. Khoảng cách giữa hai thành phố có thể là khoảng cách địa lý, có thể là cước phí di chuyển hoặc thời gian di chuyển. Ta gọi chung là độ dài. Dùng kỹ thuật quy hoạch động tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất.

Hướng dẫn:

n thành phố được đánh số từ 1 đến n. Đường đi từ thành phố i đến thành phố j xem như là cung đi từ đỉnh i đến đỉnh j của đơn đồ thị có hướng. Ðộ dài từ i đến j là trọng số m(i,j) của cung (i,j).

Vậy bài toán trên có thể xem là tìm một chu trình xuất phát từ đỉnh

i nào đó của đơn đồ thị có hướng có trọng số G=(V,E), đi qua mỗi đỉnh đúng 1 lần sao cho có trọng số nhỏ nhất.

Giả sử có một chu trình thỏa yêu cầu bài toán và bắt đầu từ đỉnh 1 về đỉnh 1. Khi đó chu trình này bao gồm cung (1,k), với k  V{1}, và đường đi từ k đến 1, đi qua mỗi đỉnh còn lại thuộc V{1,k}, mỗi đỉnh đúng 1 lần.

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

Nếu chu trình này có trọng số nhỏ nhất (tối ưu ), thì khi đó đường đi từ k đến 1 cũng có trọng số nhỏ nhất (tối ưu ).

Biểu diễn G bằng ma trận kề : C = cij (1 i,jn) như sau: cij = m(i,j) nếu (i,j)E

cij = 0 nếu i=j cij =  nếu (i,j)E

Xét tập S  V{1} và i(V{1})S. Ta gọi :

d(i,S) = Trọng số của đường đi ngắn nhất đi từ đỉnh i đến đỉnh 1 đi qua mỗi đỉnh trong S đúng 1 lần.

Vậy với 2 ≤ i ≤ n thì:

- Nếu S = , ta có : d(i, ) = Ci1 ;

- Nếu S  thì :

d(i, S ) = Min{Cik + d(k, S {k})}

Khi đó, trọng số của chu trình ngắn nhất đi từ 1 đến 1 sẽ là : d (1, V {1}) = Min{C1k + d (k ,V {1, k})}

Để tính d(1,V {1}) ta cần có d(k ,V {1, k}) , với 2 k n. Tổng quát, ta cần tính các d(i, S ) , S V{1} và i (V{1})S .

Đầu tiên ta tính và lưu trữ d(i, ) ; d(i, S) với S chỉ có 1 phần tử ; d(i, S) với S có 2 phần tử , . . .cho đến khi tính được các d(k, V{1, k}) với 2 ≤ k ≤ n.

Input : C

Output : d (1,V {1}) Mô tả:

Bước 0 :

Khởi tạo : d(i, ) = Ci1 ; 2 ≤ i ≤ n Bước 1 :

Với S ? V{1} và |S| = 1; ∀ i  1 và iS :

d(i, S ) = Min{Cik + d(k, S{k})} với kS

.....

Bước n-2:

Với S ? V{1} và |S| = n-2; ∀ i1 và i S :

d (i, S ) = Min{C ik + d (k , S {k})} với kS Bước n-1 :

d(1, V{1}) = Min{C1k + d(k ,V{1, k})} với 2 ≤ k ≤ n

Ðánh giá độ phức tạp tính toán:

Ta xét thời gian thực hiện T(n) của d(i,S): i có n-1 lựa chọn.

n2

Với mọi i =2,..,n : Số các tập S có k phần tử khác 1,i là Ck

Do dĩ

n2

T( n ) ( n 1 )C

n2

( n 1 )2n2

k 0

Mặt khác khi tính d(i,S) với S gồm k phần tử, ta cần thực hiện k-1 phép so sánh để xác định min. Nên thời gian thực hiện của thuật toán là O(n22n)

4. Dãy con tăng dài nhất

Cho dãy số nguyên A = a1, a2, .., an. Áp dụng kỹ thuật quy hoạch động chọn ra một dãy con tăng B của A (bao gồm một số các phần tử trong A nhưng vẫn giữ nguyên thứ tự) có độ dài lớn nhất.

Ví dụ : A = ( 1, 2, 3, 4, 5, 9, 10, 5, 6, 7, 8)

=> B = (1, 2, 3, 4, 5, 6, 7, 8)

Hướng dẫn:

Ta thêm vào dãy ban đầu 2 phần tử : A[0] = - và A[n+1] =  làm hai đầu mút. Vậy dãy con tăng dài nhất sẽ bắt đầu là A[0] và kết thúc là A[n+1]. Với i : 0<=i<n+1 thì ta gọi Fa[i] là độ dài của dãy con bắt đầu bởi A[i]. Điều đó có nghĩa là Fa[n+1] là độ dài của dãy con bắt đầu từ n+1. Dãy này chỉ có 1 phần tử nên có độ dài là 1 Fa[n+1] = 1. Ta sẽ bắt đầu xét các phần tử A[i] với i từ n đến 0 ta tính Fa[i] dựa trên các Fa[i+1],Fa[i+2],…,Fa[n+1] đã tính được trước đó. Dãy con đơn điệu tăng dài nhất bắt đầu từ A[i] có thể được cập nhật thêm

A[i] theo cách như sau :

Xét tất cả các chỉ số j trong khoảng i+1 đến n+1 mà A[j] >A[i], ta chọn ra chỉ số jmax có Fa[jmax] lớn nhất. Và lúc này thì : Fa[i] = Fa[jmax] +1.

Để có thể lần lại được kết quả thì khi gán Fa[i]= Fa[jmax]+ 1, ta cũng gán T[i] = jmax để biết rằng dãy con bắt đầu từ A[i] thì sẽ có phần tử thứ 2 kế tiếp là A[jmax]

Thuật toán

daytang(A)

{

A[0] = -;

A[n+1]= ; Fa[n+1]=1;

for(i=n;i>=0;i--)

{

Jmax = n+1; for(j=i+1;j<=n+1;j++)

if ((A[j] > A[i]) && (Fa[j]>Fa[jmax])) jmax=j; Fa[i]:=Fa[jmax]+1;

T[i]:= jmax;

}

Việc in ra dãy con tăng dài nhất được thực hiện bởi hàm: hienthi(A,T)

{

I=T[0];

While (i<> n+1)

{

printf(A[i]);

I=T[i];

}

5. Giả sử có hai đội A và B tham gia một trận thi đấu thể thao, đội nào thắng trước n hiệp thì sẽ thắng cuộc. Chẳng hạn một trận thi đấu bóng chuyền 5 hiệp, đội nào thắng trước 3 hiệp thì sẽ thắng cuộc. Giả sử hai đội ngang tài ngang sức. Đội A cần thắng thêm i hiệp để thắng cuộc còn đội B thì cần thắng thêm j hiệp nữa. Gọi P(i,j) là xác suất để đội A cần i hiệp nữa để chiến thắng, B cần j hiệp. Dĩ nhiên i,j đều là các số nguyên không âm.

Ðể tính P(i,j) ta thấy rằng nếu i=0, tức là đội A đã thắng nên P(0,j) = 1. Tương tự nếu j=0, tức là đội B đã thắng nên P(i,0) = 0. Nếu i và j đều lớn hơn không thì ít nhất còn một hiệp nữa phải đấu và hai đội có khả năng 5 ăn, 5 thua trong hiệp này. Như vậy P(i,j) là trung bình cộng của P(i-1,j) và P(i,j-1). Trong đó P(i-1,j) là xác suất để đội A thắng cuộc nếu thắng hiệp đó và P(i,j-1) là xác suất để A thắng cuộc nếu nó thua hiệp đó. Tóm lại ta có công thức tính P(i,j) như sau:

P(i,j) =1Nếu i = 0 P(i,j) =0Nếu j = 0

P(i,j) =(P(i-1,j) + P(i,j-1))/2Nếu i > 0 và j > 0

a. Viết một hàm đệ quy để tính P(i,j).

b. Dùng kĩ thuật quy hoạch động để viết hàm tính P(i,j).

6. Mét con tµu cã träng l•îng W. Cã n mÆt hµng ®•îc ®¸nh sè tò 1, 2, … , n. Mçi mÆt hµng lo¹i i cã sè l•îng lµ qi, khèi l•îng lµ ai vµ gi¸ trÞ lµ ci. Dïng kü thuËt quy ho¹ch ®éng t×m c¸ch xÒp hµng ho¸ lªn tµu sao cho tæng gi¸ trÞ ®¹t ®•îc lµ lín nhÊt.

H•íng dÉn:

Gọi xi là số lượng hàng hoá loại i (i = 1 .. n )

Bước 1: Tìm cơ sở của phương án hay chính là tìm điều kiện dừng của bài toán.

Xét trường hợp có 1 mặt hàng (n=1, có số lượng là q1, có khối lượng là a1, có giá trị là c1.

- Cần xếp hàng lên tàu cho đến khi không xếp được nữa thì thôi (tổng khối lượng của hàng lớn hơn trọng tải của tàu), Vậy số mặt hàng xếp lên tàu có tổng khối lượng bao giờ cũng nhỏ hơn hoặc bằng trọng tải của tàu do vậy số lượng hàng hoá xếp được lên tàu sẽ là x1=W div a1

- Số lượng mặt hàng q1 vẫn còn đủ (x1<= q1 ) thì giá trị đạt được là x1*c1 .

- Số lượng mặt hàng q1 hết ( x1> q1 ) thì giá trị đạt được là q1*c1.

Bước 2: Tìm công thức truy hồi:

Xét trường hợp có n mặt hàng (n >= 1, có số lượng là qi, có khối lượng là ai, có giá trị là ci.

*) Gọi f(k,v) là giá trị lớn nhất của tàu với k loại mặt hàng 1<= k <= n và v khối lượng (1 <= v <= W)

*) Theo bước 1 ta có:

+ x1 = W div a1.

+ Nếu x1 > q1 thì f(1,v) = q1*c1.

+ Nếu x1<= q1 thì f(1,v) = x1*c1.

*) Giả sử đã tính được f(l,m) với 1<= l<= k và 1<= m <= v

+ cần tính f(k,v) với 1<= k <= n và 1 <= v <= W

+ Gọi yk = v div ak ta có f(k,v) = max {f(k-1,m) + xk*ck} (Giá trị hàng hoá trên tàu tăng lên một lượng xk*ck)

+ Trong đó max được lấy:

Nếu yk <= qk với xk = 1, 2, …, yk Nếu yk > qk với xk = 1, 2, …, qk

+ Giá trị lớn nhất của tàu sẽ là f(n,W).

+ u = v - xk*ak (Trọng tải của tàu phải giảm xuống một lượng xk*ak) Bước 3: Lập bảng phương án

- Dùng mảng hai chiều KQ[1..n, 1..W] để lưu bảng phương án trung gian

- Một trường chứa giá trị tàu f(k, v) đạt được tại thời điểm k mà trong công thức truy hồi f(k,v) = max {f(k-1,m) + xk*ck} đạt tới max.

- Một trường chứa số lượng mặt hàng xk.

Bước 4: Tính nghiệm của bài toán con thông qua nghiệm của bài toán nhỏ hơn Sử dụng công thức truy hồi ở bước 3 để tính.

Bước 5: Xây dựng nghiệm của bài toán dựa trên bảng phương án (ma trận KQ)

- Từ công thức truy hồi f(k,v) = max {f(k-1,m) + xk*ck} giá trị của bảng KQ có thể tính lần lượt theo dòng 1, 2, …, n.

- Từ mảng KQ đã làm đầy ta xác định giá trị x và f(n,W)

+ Ta thấy ô KQ[n,W] chứa f(n,W) và xn. Như vậy xác định được giá trị của f(n,W) và xn.

+ Tính v = W – xn*an

+ Tìm đến ô KQ[n-1,v] biết được f(n,W) và xn-1

+ Tiếp tục quá trình trên ta tìm được xn-2, xn-3, …, x1.

+ Không tìm xi khi giá trị v = 0.

+ Các xi tìm thấy lưu vào mảng X. Đánh giá thuật độ phức tạp tính toán: O(n2)

PHỤ LỤC

1. Cài đặt thuật toán quy hoạch động giải bài toán chiếc ba lô

/* Doc du lieu tu file Balo.txt: Dong thu nhat ghi so do vat (n) va trong luong toi da cua ba lo (m), n dong tiep theo ghi trong luong va gia tri cua vat*/

#define max 100

int v[max], w[max]; int n, W;

int L[max][max]; int vmax;

int pa[max]; void DocDL()

{

FILE *f;

f = fopen("BaLo.txt", "r"); if(!f)

{

puts("Loi mo tep"); getch();

exit(0);

}

fscanf(f, "%d", &n);

fscanf(f, "%d", &W); for(int i=1; i<=n; i++)

{

fscanf(f, "%d", &w[i]);

fscanf(f, "%d", &v[i]);

}

fclose(f);

}

int Max(int a, int b)

{

if(a>b)

return a; return b;

}

void QHD()

{

int i, j;

for(i = 1; i<=n; i++) for(j=0; j<=W; j++)

if(j>=w[i])

L[i][j] = Max(v[i]+L[i-1][j-w[i]], L[i-1][j]);

}

void TruyVet()

{

int i, j;

i = n; j = W; int k;

k = 1;

vmax = 0; while(i && j)

{

if(L[i][j] == L[i-1][j]) i--;

if(L[i][j] == (v[i] + L[i-1][j-w[i]]) && (j>w[i]))

{

pa[k] = i; vmax += v[i]; j -= w[i]; k++;

i--;

}