CHƯƠNG 16: CÁC CHIẾN LƯỢC THIẾT KẾ THUẬT TOÁN

Tham khảo tài liệu chương 16: các chiến lược thiết kế thuật toán, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
CHƯƠNG 16: CÁC CHIẾN LƯỢC THIẾT KẾ THUẬT TOÁN CHƯƠNG 16 CÁC CHIẾN LƯỢC THIẾT KẾ THUẬT TOÁN Với một vấn đề đặt ra, làm thế nào chúng ta có thể đưa ra thuậttoán giải quyết nó? Trong chương này, chúng ta sẽ trình bày các chiếnlược thiết kế thuật toán, còn được gọi là các kỹ thuật thiết kế thuật toán.Mỗi chiến lược này có thể áp dụng để giải quyết một phạm vi khá rộngcác bài toán. Mỗi chiến lược có các tính chất riêng và chỉ thích hợp chomột số dạng bài toán nào đó. Chúng ta sẽ lần lượt trình bày các chiếnlược sau: chia-để-trị (divide-and-conquer), quy hoạch động (dynamicprogramming), quay lui (backtracking) và tham ăn (greedy method). Trongmỗi chiến lược chúng ta sẽ trình bày ý tưởng chung của phương pháp vàsau đó đưa ra một số ví dụ minh họa. Cần nhấn mạnh rằng, ta không thể áp dụng máy móc một chiếnlược cho một vấn đề, mà ta phải phân tích kỹ vấn đề. Cấu trúc của vấnđề, các đặc điểm của vấn đề sẽ quyết định chiến lược có khả năng ápdụng.16.1 CHIA - ĐỂ - TRỊ16.1.1 Phương pháp chung Chiến lược thiết kế thuật toán được sử dụng rộng rãi nhất là chiếnlược chia-để-trị. Ý tưởng chung của kỹ thuật này là như sau: Chia vấn đềcần giải thành một số vấn đề con cùng dạng với vấn đề đã cho, chỉ kháclà cỡ của chúng nhỏ hơn. Mỗi vấn đề con được giải quyết độc lập. Sauđó, ta kết hợp nghiệm của các vấn đề con để nhận được nghiệm của vấnđề đã cho. Nếu vấn đề con là đủ nhỏ có thể dễ dàng tính được nghiệm,thì ta giải quyết nó, nếu không vấn đề con được giải quyết bằng cách ápdụng đệ quy thủ tục trên (tức là lại tiếp tục chia nó thành các vấn đề con 153nhỏ hơn,…). Do đó, các thuật toán được thiết kế bằng chiến lược chia-để-trị sẽ là các thuật toán đệ quy. Sau đây là lược đồ của kỹ thuật chia-để-trị: DivideConquer (A,x) // tìm nghiệm x của bài toán A. { if (A đủ nhỏ) Solve (A); else { Chia bài toán A thành các bài toán con A1, A2,…, Am; for (i = 1; i A[k] ta tìm x trong mảng A[k+1…n-1]. Thuật toán Tháp Hà Nội (xem mục 15.5), thuật toán sắp xếp nhanh(QuickSort) và thuật toán sắp xếp hoà nhập (MergeSort) sẽ được trình bày 154trong chương sau cũng là các thuật toán được thiết kế bởi kỹ thuật chia-để-trị. Sau đây chúng ta đưa ra một ví dụ đơn giản minh hoạ cho kỹ thuậtchia-để-trị.16.1.2 Tìm max và min Cho mảng A cỡ n, chúng ta cần tìm giá trị lớn nhât (max) và nhỏnhất (min) của mảng này. Bài toán đơn giản này có thể giải quyết bằngcác thuật toán khác nhau. Một thuật toán rất tự nhiên và đơn giản là như nhau. Đầu tiên ta lấymax, min là giá trị đầu tiên A[0] của mảng. Sau đó so sánh max, min vớitừng giá trị A[i], 1 ≤ i ≤ n-1, và cập nhật max, min một cách thích ứng.Thuật toán này được mô tả bởi hàm sau: SiMaxMin (A, max, min) { max = min = A[0]; for ( i = 1 ; i < n , i ++) if (A[i] > max) max = A[i]; else if (A[i] < min) min = A[i]; } Thời gian thực hiện thuật toán này được quyết định bởi số phép sosánh x với các thành phần A[i]. Số lần lặp trong lệnh lặp for là n-1. Trongtrường hợp xấu nhất (mảng A được sắp theo thứ tự giảm dần), mỗi lầnlặp ta cần thực hiện 2 phép so sánh. Như vậy, trong trường hợp xấu nhất,ta cần thực hiện 2(n-1) phép so sánh, tức là thời gian chạy của thuật toánlà O(n). Bây giờ ta áp dụng kỹ thuật chia-để-trị để đưa ra một thuật toánkhác. Ta chia mảng A[0..n-1] thành các mảng con A[0..k] và A[k+1..n-1]với k = [n/2]. Nếu tìm được max, min của các mảng con A[0..k] và 155A[k+1..n-1], ta dễ dàng xác định được max, min trên mảng A[0..n-1]. Đểtìm max, min trên mảng con ta tiếp tục chia đôi chúng. Quá trình sẽ dừnglại khi ta nhận được mảng con chỉ có một hoặc hai phần tử. Trong cáctrường hợp này ta xác định được dễ dàng max, min. Do đó, ta có thể đưara thuật toán sau: MaxMin (i, j, max, min) // Biến max, min ghi lại giá trị lớn nhất, nhỏ nhất trong mảng A[i..j] { if (i = = j) max = min = A[i]; else if (i = = j-1) if (A[i] < A[j]) { max = A[j]; min = A[i]; } else { max = A[i]; min = A[j]; } else { mid = (i+j) / 2; MaxMin (i, m ...