zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Cấu trúc dữ liệu và giải thuật: Thuật toán đệ quy

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:12

Báo xấu

223
lượt xem 22
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu và giải thuật - Thuật toán đệ quy gồm có những nội dung chính sau đây: Định nghĩa đệ quy, thuật toán đệ quy, phân tích thuật toán đệ quy, đệ quy có nhớ, thuật toán quay lui (backtracking algorithm). Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Thuật toán đệ quy

1/10/2011 REVIEW  Xác định mối quan hệ giữa các cặp hàm và sau đây . a 3 1 , 6 b 3 1 , . c 2 , THUẬT TOÁN ĐÊ QUY Nội dung Định nghĩa đệ quy  Đối tượng bao gồm chính nó  Định nghĩa đệ quy hoặc được định nghĩa dưới dạng chính nó.  Thuật toán đệ quy VD. Định nghĩa một công thức hợp  Phân tích thuật toán đệ quy lệ của các biến, số và các phép toán , ,∗,/, ^  Đệ quy có nhớ  là công thức hợp lệ nếu là  Thuật toán quay lui (backtracking algorithm) biến hoặc số  Nếu , là công thức hợp lệ thì , , ∗ , / , ^ cũng là công thức hợp lệ 1
1/10/2011 Hàm được định nghĩa đệ quy Định nghĩa đệ quy  Mọi định nghĩa đệ quy đều gồm 2 phần 1 ế 0  !  Một trường hợp cơ sở (nhỏ nhất) có thể xử lý trực tiếp mà không 1 ! ế 0 cần đệ quy, và  Một phương thức tổng quát mà biến đổi một trường hợp cụ thể về các trường hợp nhỏ hơn. Do đó biến đổi các trường hợp cho đến 1 ế 1, 2 khi về trường hợp cơ sở.  1 2 ế 2 0 ế 0  1 ế 1 2 1 2 ế 1 Danh sách ban đầu Thuật toán đệ quy Chia lần 1 Thuật toán có chứa lời gọi đệ quy đến chính nó với đầu vào kích thước nhỏ hơn. Chia lần 2  VD. Sắp xếp trộn – MergeSort MergeSort(int A[], int start, int end) { Chia lần 3 if(start
1/10/2011 Thuật toán đệ quy Phân tích thuật toán đệ quy  Mô tả thời gian thực hiện của thuật toán đệ quy bằng công thức đệ quy  Giải công thức đệ quy để tìm Θ hoặc Ο bằng:  VD. MergeSort có Ο 1 ế 1  Phương pháp thay thế 2 Ο ế 1  Phương pháp cây đệ quy 2  Dùng định lý thợ Bỏ qua với các giá trị n nhỏ (coi là hằng). Ta có thể viết lại là 2 Ο 2 Phương pháp thay thế  Gồm 2 bước:  Đoán dạng của lời giải  Sử dụng quy nạp toán học để tìm ra các hằng và chứng minh lời giải  Xác định cận trên của công thức đệ quy Phương pháp thay thế 2 2 Đoán Ο log Cần chứng minh log với hằng số 0 được chọn phù hợp 3
1/10/2011 Phương pháp thay thế Phương pháp thay thế  Giả sử log đúng với ⁄ tức là  Giả sử trường hợp cơ sở 1 1 nhưng 1log1 0. ⁄ ⁄ log ⁄ . Thay vào Kết quả quy nạp sai trong trường hợp cơ sở.  Ta có thể giải quyết vấn đề này khi sử dụng các ký hiệu 2 ⁄ log ⁄ tiệm cận (Ο, Ω, Θ) log ⁄ log log2 log với log  Chọn sao cho với mọi thì kết quả luôn đúng VD với 2 thì 2 2 1 2 4 2log2 với hằng số ta chọn đủ lớn (VD 5). Đúng với 1  Vậy Ο log với 5 và 2 Ta cần chỉ ra kết quả quy nạp này đúng trong mọi trường hợp (đúng cả trong trường hợp cơ sở). Phương pháp thay thế Phương pháp thay thế Đoán dạng lời giải tốt:  Tránh lỗi hay mắc  Thêm bớt 1 hằng số không làm thay đổi dạng kết quả 2 2 Ο 2 12 3 vẫn có dạng Ο log Sai do ta không chứng minh  Ban đầu nới lỏng cận trên, dưới để chứng minh rồi sau đó  Thay đổi biến giảm dần. 2 log ⁄ đặt log ta có 2 2 2 VD. Với trong ví dụ ban đầu ta có thể chọn Ω và đặt 2 ta có 2 ⁄ Ο rồi sau đó giảm giới hạn trên, tăng giới hạn dưới cho Ο log Ο log loglog tới khi hội tụ về giá trị chính xác 4
1/10/2011 Một số tính chất của hàm mũ, loga, giai thừa  Ta có các công thức: a = blogb a ; logb a = 1/(loga b)  Do đó, trong ký hiệu tiệm cận cơ số của log là không quan trọng: O(lg n) = O(ln n) = O(log n)  Ví dụ. Chứng minh rằng  Công thức Stirling: 2 1 là Ο log   1  n n n !  2 n   1      e   n   Giai thừa và hàm mũ: 2n < n! < nn với n > 5 ; log n! = (n log n). Vấn đề với phương pháp thay thế Ví dụ 2 (tiếp) T(n) = 1 n=1 Dự đoán (chặt hơn!): T(n) = 1 n=1 T(n) = 4T(n/2) + n n>1 T(n)  cn2 n>n0 T(n) = 4T(n/2) + n n>1 Sử dụng dự đoán chính xác hơn. Chuyển qui nạp: Giả sử T(k)  ck2, kn0 = cn2 + n Không  cn2 ! Giả sử T(k)  ck2 - dn, k
1/10/2011 Ví dụ 2 (tiếp) Ví dụ 2 (tiếp) T(n) = 1 n=1 Dự đoán: T(n) = 1 n=1 Dự đoán: T(n) = 4T(n/2) + n n>1 T(n)  cn 2 - dn n>n 0 T(n) = 4T(n/2) + n n>1 T(n)  cn 2 - dn n>n 0 Giả sử T(k)  ck2 - dn, k1 Đã chứng minh: T(n)  2n2 – 1n n>0 Phương pháp cây đệ quy Vậy, T(n) = O(n2). 6
1/10/2011 Phương pháp cây đệ quy Phương pháp cây đệ quy  Xét công thức đệ quy Ο  Cây đệ quy cho mergeSort 1 ế 1 2 ế 1 Phương pháp cây đệ quy Phương pháp cây đệ quy  Dùng phương pháp thay thế để chứng minh lời giải công thức đệ quy tìm được. VD. Ο Ο log  Bài tập: Xác định một cận trên tốt cho công thức đệ quy  3 log log 2 2 dùng phương pháp thế để xác nhận lại kết quả. log log 3 log 2 log 3 3 3 3 3 2 log log 3 log 2 3 log Với (chú ý log 2 1) 7
1/10/2011 Dùng định lý thợ  Dùng để giải các công thức đệ quy dạng , đó 1, 1, à à ệ ậ ươ một cách hiệu quả.  Bài toán ban đầu được chia thành bài toán con có kích thước mỗi bài là ⁄ , chi phí để tổng hợp các bài toán con Định lý thợ là Master theorem VD. Thuật toán sắp xếp trộn chia thành 2 bài toán con, kích thước /2. Chi phí tổng hợp 2 bài toán con là Ο Dùng định lý thợ Dùng định lý thợ Áp dụng định lý thợ: Định lý thợ (Master Theorem) 1, 1 là các hằng số, là một hàm. định nghĩa đệ  9 . quy trên các tham số không âm 9, 3 à ta có ≡ . Đây ⁄ , trong đó ⁄ có thể hiểu là ⁄ hoặc là trường hợp 1 (với 1) do đó Θ ⁄ . Thì có thể bị giới hạn một cách tiệm cận như sau:  1. 1, 3/2 và 1 ta có / 1. Đây là  Nếu Ο , với hằng 0 thì Θ trường hợp 2, do đó Θ log  Nếu Ο thì Θ log  3 log  Nếu Ω , với hằng 0, và nếu 3, 4 và log ta có ≡ ⁄ với hằng 1 và với mọi n đủ lớn thì . Ο , Ω với 0.2, ⁄ Θ ≡3 log với do vậy Θ log (TH3) 8
1/10/2011 Dùng định lý thợ  Chú ý: Không phải trường hợp nào cũng áp dụng được định lý thợ !  VD. 2 log 2, 2 và log ≡ do đó có vẻ áp dụng trường hợp 3. Tuy nhiên log tiệm cận lớn hơn 2 với Đệ quy có nhớ mọi hằng số do đó không thể áp dụng được. Đệ quy có nhớ  Trong thuật toán đệ quy, những bài toán con có thể được giải đi giải lại nhiều lần!  VD. Tính số Fibonacci 1 ế 0,1 1 2 ế 2 Tính 5  Ghi nhận lời giải: dùng mảng Thuật toán quay lui  Khi gặp bài toán con cần giải: Kiểm tra xem bài toán con Back‐tracking algorithm đã được giải chưa:  Nếu đã giải: lấy kết quả  Ngược lại, giải bài toán con và cập nhật lời giải vào bảng 9
1/10/2011 Thuật toán quay lui Thuật toán quay lui  Bài toán 8 con hậu: “Hãy xếp 8 con hậu trên bàn cờ 8x8  Thuật toán xếp hậu: đặt lần lượt các quân hậu lên bàn cờ sao cho chúng không thể ăn lẫn nhau” (theo 1 cách nào đó) sao cho quân hậu đặt sau không ăn được quân đã đặt trước đó.  Thuật toán quay lui Thuật toán quay lui solve_from (Current_config)  Dead end: trạng thái chưa kết thúc, nhưng ta không thể if Current_config đã chứa đủ 8 hậu đặt thêm được 1 quân hậu nào nữa. print Current_config  Khi rơi vào trạng thái dead end ta phải tiến hành quay lui else (backtrack) lại lựa chọn gần nhất để thử một khả năng có Với tập p các ô trên bàn cờ mà chưa bị ảnh hưởng bởi Current_config thể khác. { Thêm 1 quân hậu vào p; Cập nhật lại Current_config solve_from(Current_config); Loại bỏ quân hậu khỏi p của Current_config; } 10
1/10/2011 Thuật toán quay lui Bài toán 8 con hậu Thuật toán quay lui – backtracking algorithm:  Thử tìm kiếm lời giải đầy đủ cho bài toán từ việc xây dựng  Nhận xét: lời giải bộ phận, trong đó lời giải bộ phận phải luôn phù  Mỗi cột phải có 1 con hậu hợp với yêu cầu bài toán.  Con hậu 1 nằm trên cột 1  Trong quá trình thực hiện, thuật toán mở rộng dần lời giải  … bộ phận. Nếu việc mở rộng khiến lời giải bộ phận vi phạm  Con hậu j nằm trên cột j yêu cầu bài toán thì tiến hành quay lui, loại bỏ sửa đổi  … gần nhất và thử một khả năng xây dựng lời giải bộ phận có thể (hợp lệ) khác.  Con hậu 8 nằm trên cột 8  Các con hậu phải không cùng hàng  Các con hậu phải không nằm trên đường chéo của nhau Giải thuật function Try (column) { Thử lần lượt từng vị trí hàng Kiểm tra An toàn for (row = 1; row
1/10/2011 12

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.