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

BÀI TẬP CHƯƠNG 5

	1	2	3	4	5	6
1		5	23	6	18	5
2	4		9	12	7	11
3	16	8		5	10	7
4	6	7	9		16	21
5	15	9	18	5		30
6	8	12	7	4	28	

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

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

1. Dùng thuật toán nhánh cận (bằng cách chọn cạnh phân nhánh) tìm hành trình tối ưu của người du lịch có ma trận chi phí sau:

C =

2. Giải bài toán chiếc ba lô sau bằng thuật toán nhánh cận:

Chiếc ba lô có thể đựng được trọng lượng 19, có 4 loại đồ vật với số lượng mỗi loại là không hạn chế. Trọng lương và giá trị của từng loại đồ vật được cho trong bảng sau:

Đồ vật

1	2	3	4
Trọng lượng	7	6	4	2
Giá trị	17	8	6	3

3. Giải bài toán chiếc ba lô sau bằng thuật toán nhánh cân: 16x1 + 9x2 + 7x3 + 5x4 -> max

6x1 + 5x2 + 3x3 + 2x4 17

xi  0, nguyên, i = 1, 2, 3, 4.

4. Viết chương trình giải bài toán chiếc ba lô bằng thuật toán nhánh cận.

5. Dãy ABC

Cho trước một số nguyên dương n (n1000). Hãy tìm một xâu chỉ gồm các ký tự A, B, C thoả mãn điều kiện:

a. Có độ dài n

b. Hai đoạn con bất kỳ liền nhau đều khác nhau (đoạn con là một dãy ký tự liên tiếp của xâu)

c. Có ít ký tự C nhất

Hướng dẫn:

Ta coi xâu gồm n ký tự là một dãy x= (x1, x2, ..., xn). Ta nhận thấy rằng nếu dãy x thoả mãn điều kiện: hai đoạn con bất kỳ liền nhau đều khác nhau thì với 4 ký tự liền nhau bất kỳ luôn phải có ít nhất một ký tự 'C'. Như vậy một dãy gồm k ký tự liên tiếp của dãy x thì phải có ít nhất [k/4] ký tự 'C'.

Giả sử với phương án bộ phận (a1, a2, ...ak) nếu ta đã có Sk ký tự 'C' trong đoạn đã chọn từ a1 đến ak thì ở các bước chọn tiếp theo để được đủ n ký tự ta phải chọn ít nhất [(n-k)/4] ký tự 'C'. Tức là nếu theo phương án bộ phận này thì xâu kết quả sẽ có số ký tự 'C' ít nhất là Sk + [(n-k)/4]. Do vậy hàm cận dưới sẽ được xác định như sau:

g(a1, a2, ...ak)= Sk + [(n-k)/4] Thiết kế thuật toán:

Dữ liệu:

- Mảng x lưu trữ phương án đang xây dựng

- Mảng t lưu trữ phương án tốt nhất tìm được

- Mảng s có s[i] lưu trữ số ký tự 'C' của phương án bộ phận (a1, a2, ...ak)

Các hàm:

/*hàm kt1(i,l) cho biết đoạn gồm l ký tự kết thúc tại x[i] có khác đoạn gồm l ký tự liền trước đó không*/

kt1(i,l)

{

j=i-1; //j là vị trí cuối đoạn liền trước đó for(k=0;k<=l-1;k++)

if(x[i-k]!=x[j-k]) return(1);

return(0);

}

/*hàm kt(i) cho biết x[i] có thoả mãn yêu cầu b trong đoạn từ x[1] đến x[i] không*/ kt(i)

{

for(l=1;l<=i/2;l++) // kiểm tr các đoạn độ dài l

if(kt1(i,l)) //nếu có đoạn độ dài l trùng với xâu liền trước return(0);

return(1)

}

/*hàm ketqua() giữ kết quả vừa tìm được: min lưu trữ số ký tự 'C' ít nhất; gán các phần tử mảng x cho các phần tử mảng t*/

ketqua()

{

min=s[n] t=x;

}

/*hàm try(i): xác định thành phần thứ i của x */ try(i)

{

for(j='A';j<='C';j++)

{

x[i]=j;

if(kt(i)) // x[i]=j thoả mãn điều kiện b trong đoạn từ x[1] đến x[i]

{

if(j=='C') s[i]=s[i-1]+1;

else s[i]=s[i-1];

if(s[i]+(n-i)/4<min) //đánh giá cận dưới if(i==n)

ketqua(); else

try(i+1);

}

/*hàm hienthi(): hiển thị mảng t và min */ hienthi()

{

for(i=1;i<n;i++) printf(t[i]); printf(min);

}

main()

{

scanf(n);

s[0]=0;

min=n; try(1); hienthi();

}

Ch•¬ng 6

Kü thuËt quy ho¹ch ®éng

6.1. Néi dung kü thuËt

Giống như kỹ thuật chia để trị, quy hoạch động giải quyết các bài toán bằng cách tổ hợp các nghiệm của bài toán con. Kỹ thuật chia để trị phân hoạch bài toán thành các bài toán con độc lập, giải quyết các bài toán con một cách đệ quy, rồi tổ hợp các nghiệm của chúng để giải quyết bài toán ban đầu. Ngược lại, quy hoạch động có thể áp dụng khi các bài toán con không độc lập, nghĩa là khi các bài toán con chia sẻ các bài toán cháu. Trong ngữ cảnh này, một thuật toán chia để trị thực hiện công việc nhiều hơn mức cần thiết, liên tục giải quyết các bài toán con chung. Trong khi đó một thuật toán theo kỹ thuật quy hoạch động giải quyết mọi bài toán con nhất loạt rồi lưu đáp án vào một bảng, nhờ đó tránh được việc phải tính toán lại mỗi khi gặp lại bài toán con.

Kỹ thuật quy hoạch động thường được áp dụng cho các bài toán tối ưu hoá. Trong các bài toán như vậy thường có thể có nhiều giải pháp khả dĩ. Mỗi giải pháp có một giá trị, và ta muốn tìm một giải pháp có giá trị tối ưu – cực tiểu hoặc cực đại. Ta gọi kiểu giải pháp như vậy là một giải pháp tối ưu cho bài toán, trái với tối ưu nghiệm, bởi có thể có vài nghiệm đạt được giá trị tối ưu.

Các bước thực hiện quy hoạch động

Bước 1: Lập hệ thức

Tìm cách chia quá trình giải bài toán thành từng giai đoạn, sau đó tìm hệ thức biểu diễn tương quan quyết định của bước đang xử lý với các bước đã xử lý trước đó. Hoặc tìm cách phân rã bài toán thành các “bài toán con” tương tự có kích thước nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài toán kích thước đã cho với kết quả của các “bài toán con” cùng kiểu có kích thước nhỏ hơn của nó nhằm xây dựng phương trình đệ quy.

Về một cách xây dựng phương trình đệ quy:

Ta chia việc giải bài toán thành n giai đoạn. Mỗi giai đoạn i có trạng thái ban đầu là t(i) và chịu tác động điều khiển d(i) sẽ biến thành trạng thái tiếp theo t(i+1) của giai đoạn i+1 (i=1,2,…,n-1). Theo nguyên lý tối ưu của Bellman thì việc tối ưu giai đoạn cuối cùng không làm ảnh hưởng đến kết quả toàn bài toán. Với trạng thái ban đầu là t(n) sau khi làm giai đoạn n tốt nhất ta có trạng thái ban đầu của giai đoạn n-1 là t(n-1) và tác động điều khiển của giai đoạn n-1 là d(n-1), có thể tiếp tục xét đến giai đoạn n-1. Sau khi tối ưu giai đoạn n-1 ta lại có t(n-2) và d(n-2) và lại có

thể tối ưu giai đoạn n-2 … cho đến khi các giai đoạn từ n giảm đến 1 được tối ưu thì coi như hoàn thành bài toán. Gọi giá trị tối ưu của bài toán tính đến giai đoạn k là Fk giá trị tối ưu của bài toán tính riêng ở giai đoạn k là Gk thì

Fk = Fk-1 + Gk

Hay là:

F1 (t(k)) max {Gk (t(k),d (k)) Fk 1 (t(k 1))}

d (k )

(*)

Bước 2: Tổ chức dữ liệu và chương trình

Tổ chức dữ liệu sao cho đạt các yêu cầu sau:

- Dữ liệu được tính toán dần theo các bước.

- Dữ liệu được lưu trữ để giảm lượng tính toán lặp lại.

- Kích thước miền nhớ dành cho lưu trữ dữ liệu càng nhỏ càng tốt, kiểu dữ liệu được chọn phù hợp, nên chọn đơn giản dễ truy cập.

Cụ thể:

- Các giá trị của Fk thường được lưu trữ trong một bảng (mảng một chiều hoặc hai, ba, v.v… chiều).

- Cần lưu ý khởi tạo các giá trị ban đầu của bảng cho thích hợp, đó là các kết quả của các bài toán con có kích cỡ nhỏ nhất của bài toán đang

giải: F1 (t(1)) max {G1 (t(1),d (1)) F0 (t(0))}

d (1)

- Dựa vào công thức, phương trình đệ quy (*) và các giá trị đã có trong bảng để tìm dần các giá trị còn lại của bảng.

- Ngoài ra còn cần mảng lưu trữ nghiệm tương ứng với các giá trị tối ưu trong từng gian đoạn.

- Dựa vào bảng lưu trữ nghiệm và bảng giá trị tối ưu trong từng giai đoạn đã xây dựng, tìm ra kết quả bài toán.

Bước 3: Làm tốt

Làm tốt thuật toán bằng cách thu gọn hệ thức (*) và giảm kích thước miền nhớ. Thường tìm cách dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng (hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước.

Trong một số trường hợp có thể thay mảng hai chiều với các giá trị phần tử chỉ nhận giá trị 0, 1 bởi mảng hai chiều mới bằng cách dùng kỹ thuật quản lý bit.

Vậy khi nào thì ta phải sử dụng phương pháp quy hoạch động cho một bài toán.

Dưới đây ta sẽ xem xét 2 nhân tố chính mà bài toán tối ưu hoá cần phải có để áp dụng phương pháp quy hoạch động, đó là: cấu trúc con tối ưu và các bài toán phủ chồng.

* Cấu trúc con tối ưu:

Bước đầu tiên trong quá trình giải quyết một bài toán tối ưu hoá bằng quy hoạch động đó là định rò đặc điểm cấu trúc của một giải pháp tối ưu. Ta nói rằng một bài toán thể hiện cấu trúc con tối ưu nếu một giải pháp tối ưu cho bài toán chứa trong nó các cấu trúc con tối ưu cho bài toán con. Mỗi khi một bài toán thể hiện cấu trúc con tối ưu, nó là dấu hiệu tốt cho biết có thể áp dụng phương pháp quy hoạch động.

Cấu trúc con tối ưu của một bài toán thường gợi ý một không gian thích hợp của các bài toán con ở đó có thể áp dụng phương pháp quy hoạch động. Thông thường có vài lớp bài toán con mà ta có thể xem là tự nhiên cho bài toán quy hoạch động. Một thuật toán quy hoạch động dựa trên không gian các bài toán con này sẽ giải quyết thêm nhiều bài toán hơn so với mức bắt buộc.

Quá trình kiểm tra cấu trúc con tối ưu của một bài toán lặp lại trên các trường hợp bài toán con cho ta một cách tốt để nhận biết một không gian các bài toán con thích hợp cho phương pháp quy hoạch động.

* Các bài toán con phủ chồng

Thành tố thứ hai mà một bài toán tối ưu hoá phải có để có thể áp dụng kỹ thuật quy hoạch động đó là không gian các bài toán con phải nhỏ theo nghĩa là một thuật toán đệ quy cho bài toán sẽ giải quyết lặp lại các bài toán con tương tự, thay vì luôn phát sinh các bài toán con mới. Khi một thuật toán đệ quy đề cập đến cùng một vấn đề của bài toán, ta nói rằng bài toán tối ưu hoá có các bài toán con phủ chồng. Ngược lại, một bài toán thích hợp với cách tiếp cận chia để trị thường phát sinh các bài toán hoàn toàn mới tại mỗi bước của đệ quy. Các thuật toán quy hoạch động thường vận dụng các bài toán con phủ chồng bằng cách giải quyết từng bài toán con một rồi lưu trữ giải pháp trong một bảng ở đó nó có thể được tra cứu khi cần, dùng thời gian bất biến cho mỗi lần tra cứu.

Hạn chế của quy hoạch động

 Việc tìm công thức, phương trình đệ quy hoặc tìm cách phân rã bài toán nhiều khi đòi hỏi sự phân tích tổng hợp rất công phu, dễ sai sót, khó nhận ra như thế nào là thích hợp, đòi hỏi nhiều thời gian suy nghĩ. Đồng thời không phải lúc nào kết hợp lời giải của các bài toán con cũng cho kết quả của bài toán lớn hơn.

 Khi bảng lưu trữ đòi hỏi mảng hai, ba chiều … thì khó có thể xử lý dữ liệu với kích cỡ mỗi chiều lớn hàng trăm.

Có những bài toán không thể giải được bằng quy hoạch động.

6.2. C¸c vÝ dô ¸p dông

6.2.1. TÝnh số tổ hợp

Một bài toán khá quen thuộc là tính số tổ hợp chập k của n theo công thức truy hồi:

C k =

1 nếu k = 0 hoặc k = n

n C k 1 + C k

nếu 0 < k < n

n1 n1

Công thức trên đã gợi ý cho chúng ta một giải thuật đệ quy như sau: Comb(n, k)

{

if (k==0) || (k==n) return(1); else

return(Comb(n-1,k-1) + Comb(n-1,k));

}

quy:

Gọi T(n) là thời gian để tính số tổ hợp chập k của n, thì ta có phương trình đệ

T(1) = C1

T(n) = 2T(n-1) + C2

Giải phương trình này ta được T(n) = O(2n). Thật vậy:

T(n) = 2T(n-1) + C2

= 2(2T(n-2) + C2) + C2 = 4T(n-2) + 3C2

...

= 2iT(n-i) + (2i -1)C2

...

= 2n-1T(1) + (2n-3)C2

= 2n-1C1 + (2n-3)C2

Do đó T(n) = O(2n)

Xem toàn bộ nội dung bài viết ᛨ