Cấu trúc dữ liệu và giải thuật 2008-2009 - Thiết kế thuật toán

Thiết kế thuật toán Lê Sỹ Vinh Bộ môn Khoa Học Máy Tính – Khoa CNTT ðại Học Công Nghệ - ðHQGHN Email: vinhioi@yahoo.com Chia ñể trị (Divide and Conquer) • Chia bài toán lớn thành các bài toán nhỏ cùng dạng với bài toán lớn nhưng có kích thước nhỏ hơn. • Giải quyết các bài toán nhỏ ñộc lập • Kết hợp nghiệm của nhửng bài toán nhỏ ñể thu ñược bài toán lớn Ví dụ: Merge sort ðể sắp xếp một mảng A[start…end], ta chia mảng A thành 2 mảng con A1 và A2. Sắp xếp A1 và A2, sau ñó hòa nhập chúng thành một ñể ñược mang A ñã sắp xếp. void MergeSort( Item A[ ], int start, int end) { if (start < end) { int mid = (start + end)/2; MergeSort ( A, start, mid ); MergeSort ( A, mid+1, end); Merge ( A, start, mid, end); } } Ví dụ: Quick sort Tư tưởng của Quick sort: Phân chia danh sách dữ liệu cần sắp xếp ra thành hai phần “phần bên trái” và “phần bên phải” sao cho các phần tử ở phần bên trái nhỏ hơn hoặc bằng các phần tử ở phần bên phải. Sau khi phân chia, tiếp tục thực hiện “quick sort trên hai phần dữ liệu trên. Void quickSort (Item A[], int start, int end) { if (start < end) { pivotLocation = partition (A, start, end); quickSort (A, start, pivotLocation – 1); quickSort (A, pivotLocation + 1, end) } } Binary search BinarySearch (lookingData, items, start, end) { if (start > end) return (-1) else { mid = (start + end) / 2; if (items[mid] == lookingData) return mid else if (items[mid] > lookingData) BinarySearch (lookingData, items, start, mid -1) else BinarySearch (lookingData, items, mid + 1, end) } } Tìm phần tử lớn nhất trong danh sách findMax (int start, int end, items) { if (start == end) return items[start] else { int med = (start + end) / 2; Item max1 = findMax (start, med, items); Item max2 = findMax (med + 1, end, items); return Max (max1, max2); } } Chiến lược vét cạn (Backtracking) Lần lượt duyệt qua tất cả các trạng thái có thể trong không gian tìm kiếm • A = (a0, a1,..an-1): Là một trạng thái gồm N thành phần, nếu trạng thái A thỏa mãn các yêu cầu của bài toán thì gọi là vector nghiệm. Trong ñó ai ∈ Si • ðể liệt kê ñược tất cả các trạng thái A có thể, ta tiến hành gọi ñệ quy qua N vòng, tại bước thứ i sẽ lần lượt tiến hành thử tất cả các ai ∈ Si Chiến lược vét cạn (Backtracking) Backtracking (A, i) { for ai ∈ Si { A = A ⋃ ai ; if (i < N) Backtracking (A, i+1) else CheckConfiguration (A); A = A – {ai} } } Ví dụ: Liệt kê tất cả xâu nhị phân ñộ dài N Void Binary (A, i) { for (int v = 0; v < 2; v ++) { A[i] = v; if (i < N) Binary (A, i+1) else A.print (); A[i] = -1; } } Ví dụ: Liệt kê tất cả hoán vị ñộ dài N Void Permutation (A, dd, i) { for (int v = 1; v <= N ; v ++) if (not dd[v]) { A[i] = v; dd[v] = true; if (i < N) Permutation(A, dd, i+1) else A.print (); A[i] = -1; dd[v] = false; } } Tìm ñường ñi ngắn nhất qua tất cả các ñỉnh của ñồ thị Bài toán cái ba lô Có N ñồ vật, ñồ vật i có khối lượng wi và giá trị ti. Một tên trộm có 1 chiếc ba lô có thể mang ñược không qúa M kg. Hãy tìm cách mang một số ñồ vật ñể tổng giá trị lấy ñược là lớn nhất.