Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 10: Chiến lược thiết kế giải thuật - Nguyễn Thị Xuân Hương

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 10: Chiến lược thiết kế giải thuật - Nguyễn Thị Xuân Hương

1. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.1. Lý thuyết tổ hợp 10.1.1 Sơ lƣợc về lý thuyết tổ hợp - Nghiên cứu về sự phân bố các phần tử vào các tập hợp. Thông thường các phần tử này là hữu hạn và việc phân bố chúng phải thoả mãn một số điều kiện nhất định(phụ thuộc vào bài toán). - Một số dạng bài toán thường gặp: a) Bài toán đếm: Trả lời câu hỏi: "có bao nhiêu cấu hình thoả mãn điều kiện đã nêu" - Phương pháp: thường dựa vào một số nguyên lý cơ bản và một số kết quả đếm các cấu hình đơn giản. -Thường được áp dụng vào những công việc mang tính chất đánh giá như: tính xác suất của một sự kiện, độ phức tạp của thuật toán. 1
2. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.1.1 Sơ lƣợc về lý thuyết tổ hợp b) Bài toán liệt kê: quan tâm đến cả cấu hình có thể có được. - Phương pháp: cần được biểu diễn dưới dạng "vét cạn" tất cả các cấu hình. - Được làm nền cho nhiều bài toán khác. - Một số bài toán đếm, bài toán tối ưu, bài toán tồn tại vẫn chưa có cách nào giải ngoài cách liệt kê c). Bài toán tối ưu: chỉ quan tâm đến cấu hình "tốt nhất" theo một nghĩa nào đấy. -Có nhiều ứng dụng trong thực tế. Lý thuyết tổ hợp đã có nhiều đóng góp đáng kể trong việc xây dựng những thuật toán hữu hiệu. 2
3. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.1.1 Sơ lƣợc về lý thuyết tổ hợp d). Bài toán tồn tại: việc "có hay không có " cấu hình còn là điều nghi vấn. - Có hai tình huống đặt ra cho bài toán này là: không chỉ ra được cấu hình nào nhưng cũng không khẳng định là chúng không tồn tại. 3
4. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.1.2. Một số bài toán tối ƣu a) Phát biểu bài toán: Thực tế, các cấu hình tổ hợp còn được gán cho một giá trị sử dụng của cấu hình đối với mục đích sử dụng cụ thể nào đó. => Bài toán lựa chọn trong số các cấu hình tổ hợp chấp nhận được, cấu hình có giá trị sử dụng tốt nhất. => Bài toán tối ưu tổ hợp. Tổng quát: Tìm cực tiểu của hàm: f(x) -> min(max) với x D, D là tập hữu hạn các phần tử. f(x): hàm mục tiêu; mỗi x D là một phương án, D: tập các phương án của bài toán. - D: là tập các cấu hình thoả mãn một số tính chất cho trước. - x* D có giá trị nhỏ nhất (lớn nhất) của hàm mục tiêu được gọi là giá trị tối ưu của bài toán. 4
5. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.1.2. Một số bài toán tối ƣu b) Một số mô hình tối ưu tổ hợp truyền thống. 1. Bài toán người bán hàng: Saleman Travelling Problem (TSP) Một người bán hàng phải đi chào hàng n thành phố T1, T2, .,Tn. Xuất phát từ một thành phố nào đó, người bán hàng phải đi qua tất cả các thành phố còn lại đúng một lần, rồi quay trở về thành phố xuất phát. Biết cij là chi phí đi từ thành phố Ti đến thành phố Tj (i,j = 1,2, n). Hãy tìm hành trình với tổng chi phí là nhỏ nhất. 2. Bài toán xếp ba lô: Một tên trộm có ba lô dung lượng b. Có thể lấy được n loại đồ vật. Đồ vật thứ j có trọng lượng là wj và giá trị sử dụng là aj. (j = 1,2, n). Hỏi rằng, tên trộm có thể lấy được các đồ vật nào mà tổng giá trị 5 sử dụng của các đồ vật đem theo là lớn nhất.
6. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.1.2. Một số bài toán tối ƣu b) Một số mô hình tối ưu tổ hợp truyền thống. 3. Bài toán cho thuê máy: Một ông chủ có một cái máy để cho thuê. Đầu tháng ông nhận được yêu cầu thuê máy của m khách hàng. Mỗi khách hàng i sẽ cho biết số ngày sử dụng máy trong tháng ( i = 1,2, m). Ông chủ có quyền từ chối hoặc chấp nhận bố trí máy cho khách hàng i thuê dùng thời gian họ yêu cầu. Hỏi rằng ông chủ phải tiếp nhận các yêu cầu của khách như thế nào để cho tổng số ngày sử dụng máy là lớn nhất. 6
7. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.2. Phƣơng pháp vét cạn: -Tư tư tưởng chính là “ vét cạn” một cách có hệ thống tất cả các khả năng có thể xẩy ra để tìm nghiệm cho bài toán. Thực chất là việc liệt kê mọi cấu hình có thể là nghiệm cho bài toán để xác định nghiệm. 7
8. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.2. Phƣơng pháp vét cạn: PHƢƠNG PHÁP SINH: liệt kê các tập có thứ tự - Áp dụng để giải các bài toán liệt kê tổ hợp nếu thoả mãn hai đk: 1) Có thể xác định được một thứ tự trên tập các cấu hình Từ đó xác định được cấu hình đầu tiên và cấu hình cuối cùng. 2) Xây dựng thuật toán từ cấu hình chưa phải là cuối cùng đang có, đưa ra cấu hình kế tiếp nó. Nhận xét: - Thứ tự được lựa chọn trong điều kiện 1) cần phải được lựa chọn sao cho có thể xây dựng thuật toán sinh kế tiếp. - Điều kiện 2) là thuật toán sinh kế tiếp 8
9. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.2. Phƣơng pháp vét cạn: PHƢƠNG PHÁP SINH: liệt kê các tập có thứ tự Giải thuật sinh kế tiếp: procedure Generate; Begin ; Stop := false; while not stop do begin ; sinh_kế_tiếp; end; End; 9
10. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT PHƢƠNG PHÁP SINH 0 000 Ví dụ: Bài toán liệt kê tất cả các dãy nhị phân n bít: 1 001 Dãy nhị phân có dạng: b1,b2, bn trong đó: bi {0,1} 2 010 VD: n = 3, các dãy nhị phân được biểu diễn như sau: 3 011 Nhận xét: -Đây là dãy có thứ tự được xác định bằng cách dãy sau 4 100 = dãy trước +1 5 101 - Dãy đầu tiên là: 000 và dãy cuối cùng là: 111 6 110 -> Từ một cấu hình đang có, có thể sinh cấu hình kế tiếp 7 111 Giải thuật: tìm số 0 đầu tiên ở bên phải -> chuyển thành 1; tất cả các số bên phải của nó chuyển thành 0 10
11. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT PHƢƠNG PHÁP SINH Bài toán Liệt kê các tập con m phần tử của tập n phần tử: Cho X= {1,2, ,n}. Liệt kê tất cả các tập con m phần tử của X. Mỗi tập con m phần tử của X có thể biểu diễn là một bộ có thứ tự m thành phần: a = (a1, a2, am) thoả mãn: 1 a1 a2 . am < n Nhận xét: Trên tập con m phần tử của X có thể xác định nhiều thứ tự khác nhau. Định nghĩa Thứ tự từ điển: Tập con a = (a1, a2, am) đi trước tập a' = (a'1, a'2, a'm) trong thứ tự từ điển và ký hiệu a < a', nếu tìm được chỉ số k (1 k m) sao cho: a1= a'1, a2= a'2 , ak-1= a'k-1, ak < a'k. 11
12. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Liệt kê các tập con m phần tử của tập n phần 1 2 3 tử: 1 2 4 Thí dụ: X=(1,2,3,4,5), m = 3. Các tập con gồm 3 phần tử trong X theo thứ tự từ điển 1 2 5 Vậy: tập con đầu tiên là: (1,2, m) và tập con cuối 1 3 4 cùng là: ( n-m+1, n-m+2, , n). 1 3 5 Giả sử a = (a1, a2, am) là tập con đang có chưa phải cuối cùng, khi đó tập con kế tiếp có hể xây 1 4 5 dựng bằng cách: 2 3 4 •Tìm từ bên phải dãy a1, a2, am phần tử ai n- m+i. 2 3 5 •* Thay a bởi a +1; i i 2 4 5 * Thay aj bởi ai +j-i , với j = i+1, i+2, ,,,m. 3 4 5 12
13. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Liệt kê các tập con m phần tử của tập n phần tử: Ví dụ: n =5, m = 3. Giả sử đang có tập con (1,2,5) Ta có ai = 2, thay a2 = 3, và a3 = 4 được tập con kế tiếp: (1,3,4) Thuật toán sinh kế tiếp: procedure Next_Combination; begin i = m; while ai = n-m+i do i := i-1; ai := ai +1; for j := i+1 to m do aj := ai + j -i; end; 13
14. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Bài toán liệt kê các hoán vị của tập n phần tử: Cho X = {1,2, n}. Hãy liệt kê tất cả các hoán vị từ n phần tử của X. Mỗi hoán vị từ n phần tử của X có thể biểu diễn là một bộ có n thành phần: a = (a1, a2, an) thoả mãn ai X, i = 1,2, n, ap aq với p q Trên tập các hoán vị từ n phần tử của X có thể xác định nhiều thứ tự khác nhau. Thứ tự đơn giản nhất là thứ tự từ điển được định nghĩa như sau: Ta nói: hoán vị a = (a1, a2, an) đi trước hoán vị a' = (a'1, a'2, a'n) trong thứ tự từ điển và kí hiệu a < a' nếu tìm được chỉ số k (1 k n) sao cho a1 = a'1, a2 = a'2, . ak-1 = a'k-1, a1 < a'k 14
15. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Bài toán liệt kê các hoán vị của tập n phần tử: 1 2 3 Thí dụ: các hoán vị X = {1,2,3} như sau: 1 3 2 Hoán vị đầu tiên là (1,2, n) và cuối cùng là (n, n-1,, 2 1 3 2,1) 2 3 1 Giả sử hoán vị a = (a1, a2, an) chưa phải là cuối cùng. Có thể chứng minh được hoán vị kế tiếp trong 3 1 2 thứ tự từ điển có thể được xây dựng từ hoán vị đang có: 3 2 1 * Tìm từ phải qua trái hoán vị đạng có chỉ số j đầu tiên thoả mãn aj < aj+1 ( j là chỉ số lớn nhất thoả mãn aj < aj+1) * Tìm ak là số nhỏ nhất còn lón hơn aj trong các số ở bên phải aj; * Đổi chỗ a với a ; j k 15 * Lật ngược đoạn từ aj+1 đến an.
16. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Bài toán liệt kê các hoán vị của tập n phần tử: Thí dụ: giả sử đang có hoán vị (3,6,2,5,4,1), cần xây dựng tập con kế tiếp trong từ điển của nó. Ta có: j = 3 ( a3 = 2 < a4 =5). Số nhỏ nhất còn lớn hơn a3 trong số các phần tử bên phải a3 là a5 = 4. Đổi chỗ a3 với a5 ta thu được (3,6,4,1,2,5). 16
17. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT procedure Next_Permutation; { //tìm j là chỉ số lớn nhất thoả mãn aj aj-1 ) j := j -1; //tìm ak nhỏ nhất trong số phần tử bên phải aj còn lớn hơn aj k := n; while (aj > ak) k := k -1; Đổi_chỗ (aj,ak) //lật ngược đoạn aj+1đến an r := n; s := j +1; while (r > s) { đổi_chỗ(ar,as) ; r := r -1;s := s+1; } } 17
18. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.2. Phƣơng pháp vét cạn: Thảo luận: - Trình bày ưu, nhược điểm của phương pháp vét cạn. - Phương pháp vét cạn có thể giải được các bài toán dạng nào? - Khi nào áp dụng được phương pháp sinh để giải bài toán? 18
19. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.3. Phƣơng pháp vét cạn – quay lui: - Là một cải tiến cho phương pháp vét can Tư tưởng chính là việc xây dựng từng thành phần nghiệm từng bước một bằng cách thử các khả năng có thể có của thành phần nghiệm thứ i dựa trên thành phần nghiệm thứ (i-1) đã chọn trước đó – phuơng pháp “ thử sai”. 19
20. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.3. Phƣơng pháp vét cạn – quay lui: Giải thuật vét cạn - quay lui: - Giả thiết nghiệm của bài toán là một bộ : x1, x2, xn. - Giả sử đã xác định được (i-1) thành phần x1, x2, xi-1 Ta xây dựng thành phần nghiệm i bằng cách chọn khả năng j trong số các đề cử cho nó. * Nếu chấp nhận đề cử j thì: xác định xi theo j và ghi nhớ trạng thái mới nếu i = n đã xây dựng thành công một bộ nghiệm, ngược lại tiếp tục thử xây dựng thành phần nghiệm thứ i+1 (đệ qui). * Nếu không có đề cử j nào được chấp nhận thì xoá các ghi nhớ và quay lui lại bước trước để thử xác định lại xi-1. 20
21. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.3. Phƣơng pháp vét cạn – quay lui:Thủ tục tổng quát: void Try(int i) { int j; for (j= 1; j ) { ; ; if i = n then else Try(i+1); ; //quay lui }; } 21
22. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.3. Phƣơng pháp vét cạn – quay lui:Thủ tục tổng quát: Sau khi xây dựng thủ tục đệ quy Try, đoạn chương trình giải bài toán quay lui có dạng { khởi_tạo; Try(1); } 22
23. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.3. Phƣơng pháp vét cạn – quay lui:Thủ tục tổng quát: Quá trình tìm kiếm lời giải theo thuật toán quay lui có thể mô tả bằng cây không gian trạng thái tìm kiếm lời giải sau đây. 23
24. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.3. Phƣơng pháp vét cạn – quay lui:Thủ tục tổng quát: Ví dụ: cây liệt kê các dãy nhị phân có độ dài 3: 24
25. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.3. Phƣơng pháp vét cạn – quay lui: Ví dụ: Giải bài toán 8 hậu Bàn cờ quốc tế 8 x8 ô. Cần đặt tám con hậu trên đó sao cho chúng không thể ăn nhau được Đây là một bài toán cổ điển có từ thế kĩ 18 mà các nhà toán học rất quan tâm cả hai khía cạnh: chỉ ra một cách xếp các con hậu và có bao nhiêu cách xếp hậu khác nhau. 25
26. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Ví dụ: Giải bài toán 8 hậu Nhận xét:: - Để các quân hậu không ăn nhau: Không có quá 1 con hậu trên mỗi dòng, mỗi cột, mỗi đường chéo. - Các quân hậu được đánh số thứ tự từ 1 đến 8. - Giả sử, Quân hậu i đứng ở cột thứ i => Cần đặt quân hậu i (ở cột i) tại hàng thứ j nào sao chúng không ăn lẫn nhau: hàng : 1 Cần xác định các giá trị của hậu tại các hàng h1,h2, ,h8 sao cho chúng không nằm trên cùng một đường chéo. 26
27. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Ví dụ: Giải bài toán 8 hậu Quân hậu xếp tại vị trí (5,5) đường chéo tăng: có giá trị i+j = hằng số ( 2 Ta có thể đánh thứ tự cho giá trị đường chéo tăng cho quân hậu tại vị trí (i,j) từ 2 đến 2n -> đường chéo giảm: có giá trị i-j = hằng số (1-n Ta có thể đánh thứ tự cho giá trị đường chéo giảm cho quân hậu tại vị trí (i,j) từ 1-n đến n-1 27
28. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Ví dụ: Giải bài toán 8 hậu Biểu diễn dữ liệu Mảng h[n] chứa vị trí h[i] đăt quân hậu thứ i ở hàng h[i] Mảng a[n] với a[i] = 0 nếu hàng i chưa có quân hậu nào và ngược lại thì a[i] =1 Mảng b[2 2n] với b[i] = 0 nếu đường chéo tăng chưa có quân hậu nào và ngược lại thì b[i] =1 Mảng c[1-1 n-1] với c[i] = 0 nếu đường chéo giảm chưa có quân hậu nào và ngược lại thì c[i] =1 28
29. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Ví dụ: Giải bài toán 8 hậu Thuật toán: thử đặt quân hậu i (ở cột i) đặt ở hàng thứ j -Giả sử đã đặt được i-1 quân hậu -Đặt quân hậu thứ i -Với mỗi hàng j -Nếu hàng j chưa có quân hậu nào và đường chéo tăng i+j và đường chéo giảm i-j cũng chưa có quân hậu nào chiếm giữ -> đặt quân hậu i ở hàng j (ghi nhớ các vị trí hàng, đường chéo tăng, đường chéo giảm đã đặt hậu) -Nếu i == n => đã hoàn thành 1 cấu hình đặt 8 quân hâu -Ngược lại -> Thử đặt quân hậu thứ i+1 -Nếu không có hàng j nào thỏa mãn để đặt hậu -> xóa ghi nhớ và quay lui lại bước thử đặt hậu thứ i-1 để chọn các ứng cử khác 29
30. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Ví dụ: Giải bài toán 8 hậu Thuật toán: thử đặt quân hậu i (ở cột i) đặt ở hàng thứ j -Giả sử đã đặt được i-1 quân hậu -Đặt quân hậu thứ i -Với mỗi hàng j -Nếu hàng j chưa có quân hậu nào và đường chéo tăng i+j và đường chéo giảm i-j cũng chưa có quân hậu nào chiếm giữ -> đặt quân hậu i ở hàng j (ghi nhớ các vị trí hàng, đường chéo tăng, đường chéo giảm đã đặt hậu) -Nếu i == n => đã hoàn thành 1 cấu hình đặt 8 quân hâu -Ngược lại -> Thử đặt quân hậu thứ i+1 -Nếu không có hàng j nào thỏa mãn để đặt hậu -> xóa ghi nhớ và quay lui lại bước thử đặt hậu thứ i-1 để chọn các ứng cử khác 30
31. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.3. Phƣơng pháp vét cạn – quay lui: Thảo luận: - Để giải bài toán bằng chiến lược quay lui, ta cần quan tâm đến vấn đề gì? Ưu, nhược điểm, Những bài toán nào giải được với chiến lược quay lui? 31
32. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.4. CHIẾN LƢỢC NHÁNH CẬN - là một cải tiến cho phương pháp quay lui nhằm loại bỏ bớt các khả năng không có thể là nghiệm của bài toán. Tƣ tƣởng: trong quá trình liệt kê lời giải trên cây không gian tìm kiếm, ta sử dụng các thông tin đã tìm được để loại bỏ các nhánh của cây mà nếu phát triển theo hướng đó chắc chắn sẽ không cho lời giải. 32
33. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.4. CHIẾN LƢỢC NHÁNH CẬN Thuật toán nhánh cận: - Giả thiết nghiệm của bài toán là một bộ gồm n thành phần x1, x2, xn. - Bằng phương pháp thực nghiệm ta đánh giá nghiệm tốt nhất có thể có là một giá trị lowcost. - Giả sử đã xác định được (i-1) thành phần x1, x2, xi-1 Ta xây dựng thành phần nghiệm i bằng cách chọn khả năng j trong số các đề cử cho nó. 33
34. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Thuật toán nhánh cận: thử xây dựng thành phần nghiệm xi - Nếu đề cử j cho bước thứ i được chấp nhận thì: + xác định xi theo j, ghi nhớ trạng thái mới chọn + Đánh giá nghiệm của bài toán qua i thành phần đã có và (n-i) thành phần phải xây dựng tiếp theo (cận dưới). Nếu nghiệm đó tốt hơn nghiệm tốt nhất lowcost đã có thì ta tiếp tục thử xây dựng thành phần nghiệm thứ i+1 (đệ qui). Trong trường hợp ngược lại thì ta không phát triển nghiệm theo bước thứ i nữa mà quay lui lại bước trước để thử xác định lại xi-1. (cắt nhánh). - Nếu không có đề cử j nào được chấp nhận cho bước i thì quay lui lại bước trước để thử xác định lại xi-1. 34
35. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.4. CHIẾN LƢỢC NHÁNH CẬN: Thủ tục tổng quát: void Try(i); { for với mỗi j ni do if { xi := j; ; if (i = n) ; else if (cost(x1, x2, xi) lowcost ) Try (i+1); ; //quay lui } } 35
36. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.4. CHIẾN LƢỢC NHÁNH CẬN: Thủ tục tổng quát: void Nhanh_can() { lowcost := + ; try(1); if (lowcost else ; } 36
37. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.4. CHIẾN LƢỢC NHÁNH CẬN: Ví dụ bài toán TSP Có n thành phố T1,T2, Tn với thành phố xuất phát là T1. Bài toán TSP có thể dẫn về bài toán: tìm giá trị nhỏ nhất của hàm f((x2, x3, xn) = c[x1,x2] + c[x2,x3] + c[xn-1,xn]+ c[xn,x1] đạt min với điều kiện (x2, x3, xn) là các hoán vị của 2,3, n. ký hiệu: cmin = min{c[i,j], i,j = 1,2, ,n, i j} là chi phí nhỏ nhất đi lại giữu các thành phố. 37
38. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT Ví dụ bài toán TSP Giả sử đang có phương án bộ phận (x1, x2, xk). Phương án này tương ứng với hành trình bộ phận qua k thành phố: T1-> T, Tk Vậy chi phí phải trả theo hành trình này là: g = c[x1,x2] + c[x2,x3] + .+ + c[xk-1,xk]. Để phát triển hành trình đầy đủ ta còn phải đi qua n-k thành phố nữa rồi quay về thành phố T1 -> phải đi qua n-k+1 đoạn đường. Do chi phí phải trả cho việc đi qua mỗi đoạn đường đều không nhỏ hơn cmin, nên cận dưới cho phương án bộ phận này là: cost(x1, x2, xk) = g + (n-k+1)cmin. Nếu phương án bộ phận (x1, x2, xk) có cận dưới cost(x1, x2, xk) tiếp tục thử xây dựng thành phần xk+1. Ngược lại, quay lui về xk-1 Nếu không còn đề cử nào cho xk-1 38
39. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT •Ví dụ: 1 2 3 4 5 •Ta có cmin =3. 1 0 3 10 18 12 2 3 0 4 20 17 3 17 9 0 16 5 4 5 3 8 0 13 5 9 15 10 5 0 •Quá trình thực hiện thuật toán đuợc mô tả bằng cây không gian trạng thái sau: 39
40. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.4. CHIẾN LƢỢC NHÁNH CẬN: Thảo luận: - Ưu, nhược điểm của chiến lược nhánh cận? - Những bài toán nào giải được với chiến lược nhánh – cận? 41
41. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.5. Chiến lƣợc chia để trị (Divide and Conquer ) - Là chiến lược được áp dụng rộng rãi nhất để thiết kế thuật toán Tư tưởng : Chia bài toán ban đầu thành các bài toán con có kích thước nhỏ hơn. Tiếp tục chia cho đến khi nhận được bài toán con đã có thuật giải hoặc có thể dễ dàng đưa ra thuật giải. Giải các bài toán con. Kết hợp nghiệm ( combaine). Nghiệm các bài toán con được kết hợp để cho nghiệm bài toán con lớn hơn và cuối cùng cho nghiệm của bài toán xuất phát. Thông thường, các bài toán con nhận được trong qúa trình phân chia là đồng dạng với bài toán ban đầu, với kích thước nhỏ hơn - > thường kết hợp phương pháp chia để trị và kỹ thuật đệ qui. 42
42. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.5. Chiến lƣợc chia để trị (Divide and Conquer ) VD: QuickSort, Merge Sort, tìm kiếm nhị phân, Thảo luận: - Ưu, nhược điểm của chiến lược chia để trị? - Những bài toán nào giải được với chiến lược chia để trị? 43
43. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.6 Chiến lƣợc quy hoạch động (Dynamic programming): làm tốt hơn cho chiến lược chia để trị. - Một số bài toán khi thiết kế theo kiểu Top-Down: ta giải bài toán con theo quá trình chia nhỏ một cách độc lập. Tuy nhiên trong quá trình phân chia, thông thường sẽ gặp rất nhiều lần cùng một bài toán con => phải tính lại nhiều lần cùng một bài toán. Vì vậy thuật toán sẽ kém hiệu quả. - Để tránh phải tính lại nhiều lần cùng một bài toán con: có thể sử dụng phương pháp quy hoạch động: thiết kế thuật toán theo kiểu bottom- up: 44
44. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.6 Chiến lƣợc quy hoạch động (Dynamic programming): Tƣ tƣởng 1. Giải tất cả các bài toán cơ sở và lưu nghiệm của chúng vào các vị trí tương ứng trong bảng phương án. 2. Dùng công thức truy hồi, dựa vào nghiệm các bài toán con đã lưu trong bảng phương án để tính nghiệm bài toán lớn hơn và lưu kết quả vào vị trí tương ứng trong bảng phương án. Tiếp tục quá trình đó cho đến khi bảng phương án được tính xong hoàn toán. 3. Dựa vào bảng phương án, truy vết để tìm nghiệm. 45
45. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.6 Chiến lƣợc quy hoạch động (Dynamic programming): Ví dụ: Bài toán tính số Fibonaci. Nhận xét: nếu sử dụng thuật toán đệ quy để tìm n số Fibonaci, ta phải lại nhiều lần các số Fibonaci trước đó nên rất tốn thời gian => để khắc phục, ta dùng một mảng một chiều F chẳng hạn để lưu trữ các số Fibonaci Với n=6 : 0 1 2 3 4 5 1 1 2 3 5 8 Thực hiện: - Gán F[0]=1, F[1]=1 - Tình F[i]=F[i-1]+ F[i-2], với I = 2->6 46
46. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.6 Chiến lƣợc quy hoạch động (Dynamic programming): Thảo luận: - Ưu, nhược điểm của chiến lược quy hoạch động? - Những bài toán nào giải được với chiến lược quy hoạch động? 47
47. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.7. CHIẾN LƢỢC THAM LAM (Greedy strategy) Nhiều vấn đề cần giải quyết có thể quy về bài toán sau: Cho trước một tập A các đối tượng nào đó, đòi hỏi phải chọn ra một tập con S gồm các đối tượng thoả mãn một số điều kiện nào đó. Bất kỳ một tập con S nào của A thoả mãn các yêu cầu của A được goi là nghiệm chấp nhận được của bài toán. Mỗi nghiệm của tập S được gắn với một giá trị nào đó. Một nghiệm chấp nhận được mà tại đó giá trị hàm mục tiêu đạt giá trị lớn nhất hoặc nhỏ nhất (nghiệm tối ưu). 48
48. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.7. CHIẾN LƢỢC THAM LAM (Greedy strategy) 10.7.1. Tƣ tƣởng: cố gắng chọn đƣợc các phần tử thỏa mãn càng nhiều tiêu chí của bài toán đƣa ra càng tốt. 10.7.2 Giải thuật : - Ta xây dựng tập S dần từng bước. bắt đầu từ tập rỗng - Tại mỗi bước sẽ chọn phần tử "tốt nhất" trong số các phần tử còn lại của A để đưa vào tập S Việc lựa chọn như vậy được thực hiện bởi hàm chọn. Phần tử được chọn sẽ bị loại khỏi tập A. - Nếu khi thêm phần tử được chọn vào tập S mà S vẫn thoả mãn điều kiện của bài toán thì phần tử đó được thêm vào S. 49
49. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.7. CHIẾN LƢỢC THAM LAM (Greedy strategy) 10.7.2 Giải thuật : void Greedy { S:= ; while (A <>  hoặc S chưa đủ) { Chọn x từ A; {x là nghiệm tốt nhất cục bộ trong S} A := A -{x}; if (S  x chấp nhận được) S := S + {x}; } } 50
50. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.7. CHIẾN LƢỢC THAM LAM (Greedy strategy) 10.7.3 Ví dụ: Bài toán tô màu đồ thị Input: Cho đồ thị vô hướng G= , trong đó các đỉnh đánh số từ 1 đến n, m màu để tô Output: Đồ thị đã được tô màu sao cho hai đỉnh kề nhau không có màu giống nhau, và số màu ít nhất có thể. * Thuật toán tham lam: B1: chọn một màu chưa dùng để tô, chọn một đỉnh trong số các đỉnh chưa tô, tô màu vừa chọn B2: Với các đỉnh không kề với đỉnh vừa tô, tô màu vừa chọn. B3: Nếu chưa tô hết các đỉnh, quay lại B1 51
51. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.7.3 Ví dụ: Bài toán tô màu đồ thị * Thuật toán tham lam: B1: chọn một màu chưa dùng để tô, chọn một đỉnh trong số các đỉnh chưa tô, tô màu vừa chọn B2: Với các đỉnh không kề với đỉnh vừa tô, tô màu vừa chọn. B3: Nếu chưa tô hết các đỉnh, quay lại B1 52
52. Chƣơng 10: CHIẾN LƢỢC THIẾT KẾ GiẢI THUẬT 10.7. CHIẾN LƢỢC THAM LAM (Greedy strategy) Thảo luận: Để giải bài toán bằng chiến lược tham lam cần có điều kiện gì? Những bài toán nào giải được bằng chiến lược tham lam. Ưu, nhược điểm của việc giải bài toán bằng chiến lược tham lam? 53