Bài giảng Thiết kế thuật toán - Lê Sỹ Vinh

Nội dung text: Bài giảng Thiết kế thuật toán - Lê Sỹ Vinh

1. Thit k thut toỏn Lờ S Vinh B mụn Khoa Hc Mỏy Tớnh – Khoa CNTT ði Hc Cụng Ngh ðHQGHN Email: vinhioi@yahoo.com
2. Chia ủ tr (Divide and Conquer) • Chia bài toỏn ln thành cỏc bài toỏn nh cựng dng vi bài toỏn ln nhưng cú kớch thưc nh hơn. • Gii quyt cỏc bài toỏn nh ủc lp • Kt hp nghim ca nhng bài toỏn nh ủ thu ủưc bài toỏn ln
3. Vớ d: Merge sort ð sp xp mt mng A[start end], ta chia mng A thành 2 mng con A1 và A2. Sp xp A1 và A2, sau ủú hũa nhp chỳng thành mt ủ ủưc mang A ủó sp xp. 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); } }
4. Vớ d: Quick sort Tư tưng ca Quick sort: Phõn chia danh sỏch d liu cn sp xp ra thành hai phn “phn bờn trỏi” và “phn bờn phi” sao cho cỏc phn t phn bờn trỏi nh hơn hoc bng cỏc phn t phn bờn phi. Sau khi phõn chia, tip tc thc hin “quick sort trờn hai phn d liu 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) } }
5. 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) } }
6. Tỡm phn t ln nht 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); } }
7. Chin lưc vột cn (Backtracking) Ln lưt duyt qua tt c cỏc trng thỏi cú th trong khụng gian tỡm kim • A = (a 0, a 1, a n1): Là mt trng thỏi gm N thành phn, nu trng thỏi A tha món cỏc yờu cu ca bài toỏn thỡ gi là vector nghim. Trong ủú a i ∈ S i • ð lit kờ ủưc tt c cỏc trng thỏi A cú th, ta tin hành gi ủ quy qua N vũng, ti bưc th i s ln lưt tin hành th tt c cỏc ai ∈ S i
8. Chin lưc vột cn (Backtracking) Backtracking (A, i) { for ai ∈ Si { A = A ⋃ ai ; if (i < N) Backtracking (A, i+1) else CheckConfiguration (A); A = A – {ai} } }
9. Vớ d: Lit kờ tt 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; } }
10. Vớ d: Lit kờ tt 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; } }
11. Tỡm ủưng ủi ngn nht qua tt c cỏc ủnh ca ủ th
12. Bài toỏn cỏi ba lụ Cú N ủ vt, ủ vt i cú khi lưng wi và giỏ tr ti. Mt tờn trm cú 1 chic ba lụ cú th mang ủưc khụng qỳa M kg. Hóy tỡm cỏch mang mt s ủ vt ủ tng giỏ tr ly ủưc là ln nht.