tailieunhanh - Bài giảng Phân tích và thiết kế giải thuật: Chương 3 - PGS.TS. Dương Tuấn Anh

Chương 3 giới thiệu về chiến lược giảm để trị trong phân tích và thiết kế giải thuật. Các nội dung chính trong chương này gồm có: Chiến lược giảm để trị, sắp thứ tự bằng phương pháp chèn, các giải thuật duyệt đồ thị, sắp xếp tôpô, giải thuật sinh các hoán vị từ một tập. | Chương 3 Chiến lược giảm-để-trị (Decrease-and-conquer) Nội dung Chiến lược giảm-để-trị Sắp thứ tự bằng phương pháp chèn Các giải thuật duyệt đồ thị Sắp xếp tôpô Giải thuật sinh các hoán vị từ một tập 1. Chiến lược thiết kế giải thuật giảm-để-trị (Decrease-and-conquer) Kỹ thuật thiết kế giải thuật giảm-để-trị lợi dụng mối liên hệ giữa lời giải cho một thể hiện của một bài toán và lời giải cho một thể hiện nhỏ hơn của cùng một bài toán. Có ba biến thể của chiến lược này. Giảm bởi một hằng số (decrease by a constant) Giảm bởi một hệ số (decrease by a factor) Giảm kích thước của biến (variable size decrease) Sắp thứ tự bằng phương pháp chèn (insertion sort) là một thí dụ điển hình của chiến lược giảm-để-trị. Chiến lược thiết kế giải thuật giảm-để-trị (tt.) Giải thuật tìm ước số chung lớn nhất của 2 số theo công thức gcd(m,n) = gcd(n, m mod n) cũng là thí dụ của chiến lược giảm-để-trị theo lối giảm kích thước của biến. Algorithm Euclid(m,n) /* m,n : two nonnegative integers m and n */ while n0 do r := m mod n; m:= n; n:= r endwhile return m; Thí dụ: m = 60 và n = 24 m = 60 và n = 24 m = 24 và n = 12 m = 12 và n = 0 Vậy 12 là ước số chung lớn nhất Chiến lược thiết kế giải thuật giảm-để-trị (tt.) Tại mỗi bước của giải thuật duyệt đồ thị theo chiều sâu trước (DFS) hay duyệt theo bề rộng trước (BFS), giải thuật đánh dấu đỉnh đã được viếng và tiến sang xét các đỉnh kế cận của đỉnh đó. Hai giải thuật duyệt đồ thị này đã áp dụng kỹ thuật giảm-bớt-một (decrease-by-one), một trong 3 dạng chính của chiến lược Giảm-để-trị. 2. Sắp thứ tự bằng phương pháp chèn Ý tưởng : Xét một ứng dụng của kỹ thuật “giảm để trị” vào việc sắp thứ tự một mảng a[0n-1]. Theo tinh thần của kỹ thuật, ta giả sử rằng bài toán nhỏ hơn: sắp thứ tự một mảng a[0n-2] đã được thực hiện. Vấn đề là phải chèn phần tử a[n-1] vào mảng con đã có thứ tự a[0n-2]. Có hai cách để thực hiện điều này. - Một là ta duyệt mảng con đã có thứ tự từ trái sang phải cho đến khi tìm thấy phần tử đầu tiên lớn | Chương 3 Chiến lược giảm-để-trị (Decrease-and-conquer) Nội dung Chiến lược giảm-để-trị Sắp thứ tự bằng phương pháp chèn Các giải thuật duyệt đồ thị Sắp xếp tôpô Giải thuật sinh các hoán vị từ một tập 1. Chiến lược thiết kế giải thuật giảm-để-trị (Decrease-and-conquer) Kỹ thuật thiết kế giải thuật giảm-để-trị lợi dụng mối liên hệ giữa lời giải cho một thể hiện của một bài toán và lời giải cho một thể hiện nhỏ hơn của cùng một bài toán. Có ba biến thể của chiến lược này. Giảm bởi một hằng số (decrease by a constant) Giảm bởi một hệ số (decrease by a factor) Giảm kích thước của biến (variable size decrease) Sắp thứ tự bằng phương pháp chèn (insertion sort) là một thí dụ điển hình của chiến lược giảm-để-trị. Chiến lược thiết kế giải thuật giảm-để-trị (tt.) Giải thuật tìm ước số chung lớn nhất của 2 số theo công thức gcd(m,n) = gcd(n, m mod n) cũng là thí dụ của chiến lược giảm-để-trị theo lối giảm kích thước của biến. Algorithm Euclid(m,n) /* m,n : two nonnegative integers m and