Bài giảng Phân tích thiết kế giải thuật: Thiết kế thuật toán - Chia để trị - GV. Hà Đại Dương

Chia để trị là một phương pháp được áp dụng rộng rãi, ý tưởng chung là phân rã bài toán thành bài toán nhỏ hơn "độc lập" với nhau, giải các bài toán con theo cùng 1 cách thức, "Tổng hợp"” lời các bài toán con để có được kết quả bài toán ban đầu. Để tìm hiểu rõ hơn về phương pháp này, mời các bạn cùng tham khảo bài giảng.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: Thiết kế thuật toán - Chia để trị - GV. Hà Đại Dương 2/2/2017 Phân tích và Thiết kế THUẬT TOÁN Hà Đại Dương duonghd@mta.edu.vn Web: fit.mta.edu.vn/~duonghd Bài 4 - Thiết kế thuật toán Chia để trị Divide&Conquer PHÂN TÍCH VÀ THIẾT KẾ THUẬ TOÁN NỘI DUNG I. II. III. IV. Giới thiệu Lược đồ chung Bài toán áp dụng Bài tập 1 2/2/2017 I. Giới thiệu  Là một phương pháp được áp dụng rộng rãi  Ý tưởng chung là phân rã bài toán thành bài toán nhỏ hơn “độc lập” với nhau.  Giải các bài toán con theo cùng 1 cách thức  “Tổng hợp” lời các bài toán con để có được kết quả bài toán ban đầu.  Tư tưởng chung của cách tiếp cận Chia để trị II. Lược đồ chung Chia: • Bằng cách nào đó chia tập hợp các đối tượng của bài toán thành bài toán con “độc lập” • Tiếp tục chia các bài toán con cho đến khi có thể giải trực tiếp (không cần, hoặc không thể chia nhỏ nữa) Trị: • Trên các bài toán con thực hiện cùng một cách thức: Chia nhỏ nếu cần hoặc giải trực tiếp Tổng hợp: • Khi mỗi bài toán con được giải, tổng hợp để có kết quả bài toán ban đầu. II. Lược đồ chung 2 2/2/2017 III. Bài toán áp dụng 1. Tìm kiếm nhị phân The Manhattan phone book has 1,000,000+ entries. How is it possible to locate a name by examining just a tiny, tiny fraction of those entries? III. Bài toán áp dụng 1. Tìm kiếm nhị phân Key idea of “phone book search”: repeated halving To find the page containing Pat Reed’s number… while (Phone book is longer than 1 page) Open to the middle page. if “Reed” comes before the first entry, Rip and throw away the 2nd half. else Rip and throw away the 1st half. end end III. Bài toán áp dụng 1. Tìm kiếm nhị phân What happens to the phone book length? Original: 3000 After 1 rip: 1500 After 2 rips: 750 After 3 rips: 375 After 4 rips: 188 After 5 rips: 94 : After 12 rips: 1 pages pages pages pages pages pages page 3 2/2/2017 III. Bài toán áp dụng 1. Tìm kiếm nhị phân • Repeatedly halving the size of the “search space” is the main idea behind the method of binary search. • An item in a sorted array of length n can be located with just log2 n comparisons. n log2(n) 100 1000 10000 • “Savings” is significant! 7 10 13 III. Bài toán áp dụng 1 2 3 4 5 6 7 8 9 10 11 12 v 12 15 33 35 42 45 51 62 73 75 86 98 Binary search: target x = 70 L: 1 Mid: 6 R: 12 v(Mid)