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à thuật toán: Chương 2 - Thuật toán cài đặt đệ quy

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:13

Báo xấu

15
lượt xem 5
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à thuật toán: Chương 2 - Thuật toán cài đặt đệ quy" trình bày các nội dung chính sau đây: Khái niệm thuật toán cài đặt đệ quy; Đánh giá thuật toán đệ quy; Một số chú ý với thuật toán đệ quy; Thuật toán quy lui – back tracking. 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à thuật toán: Chương 2 - Thuật toán cài đặt đệ quy

9/29/2021 Nội dung Chương 2. Thuật toán cài dặt • Khái niệm thuật toán cài đặt đệ quy • Đánh giá thuật toán đệ quy đệ quy • Một số chú ý với thuật toán đệ quy • Thuật toán quy lui – back tracking Đệ quy, cây đệ quy, định lý thợ, back tracking hiep.nguyenduy@hust.edu.vn 1 hiep.nguyenduy@hust.edu.vn 2 Thuật toán đệ quy Thuật toán đệ quy • Thuật toán có thể được cài đặt/biểu diễn theo 2 cách • Định nghĩa đệ quy: Đối tượng bao gồm chính • Dùng vòng lặp: dùng các vòng lặp for, do..while, while nó hoặc được định nghĩa dưới dạng chính • Dùng đệ quy: Dùng lời gọi đệ quy trong phần cài đặt nó. • Thuật toán được cài đặt đệ quy (gọi tắt là thuật toán đệ quy) 1 𝑛ế𝑢 𝑛 = 0 • Thường tồi hơn dùng vòng lặp: Máy tính được thiết kế tự nhiên xử lý các lệnh • 𝑛! = 𝑛× 𝑛−1 ! 𝑛ế𝑢 𝑛 > 0 dạng lặp chứ không phải dạng đệ quy • Thời gian gọi đệ quy cũng phải được tính vào thời gian thực hiện 1 𝑛ế𝑢 𝑛 = 1, 2 • 𝐹𝑖𝑏 𝑛 = • Đệ quy thường ngắn gọn hơn vòng lặp 𝐹𝑖𝑏 𝑛 − 1 + 𝐹𝑖𝑏 𝑛 − 2 𝑛ế𝑢 𝑛 > 2 • Đệ quy khó gỡ lỗi hơn vòng lặp 0 𝑛ế𝑢 𝑛 = 0 • Nếu số lần gọi đệ quy quá lớn có thể dẫn đến STACK OVER FLOW • 𝑃 𝑛 = 1 𝑛ế𝑢 𝑛 = 1 • Không phải mọi thuật toán đều có thể cài đặt đệ quy 2𝑃 𝑛 − 1 + 𝑃 𝑛 − 2 𝑛ế𝑢 𝑛 > 1 hiep.nguyenduy@hust.edu.vn 3 hiep.nguyenduy@hust.edu.vn 4
9/29/2021 Thuật toán đệ quy Thuật toán đệ quy • Mọi định nghĩa đệ quy đều gồm 2 phần • Một trường hợp cơ sở (nhỏ nhất) có thể xử lý trực tiếp mà không cần đệ • VD1 . Tính tổng các phần tử trong dãy A gồm n phần tử quy, và int sum_loop(int *A, int n) int sum_rec(int *A, int n) • 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 khi về int sum = 0; if (n key) end = mid - 1; } return binSearch_rec(A, mid + 1, end, key); else start = mid + 1; } } } return -1; Hàm Merge trộn 2 danh sách với thời gian O(n) } hiep.nguyenduy@hust.edu.vn 7 hiep.nguyenduy@hust.edu.vn 8
9/29/2021 Thuật toán đệ quy Thuật toán đệ quy • Xây dựng công thức đệ quy tổng quát • Đánh giá thuật toán được cài đặt đệ quy: • Xác định trường hợp cơ sở: • Rất khó thuật toán được gọi đệ quy bao nhiều lần • Độ phức tạp tính toán trong trường hợp cơ sở • Cần phải chuyển thuật toán về dạng công thức đệ quy tổng quát • Với thuật toán đầu vào tối thiểu là 0 (không có đầu vào âm) • Trình tự đánh giá • Xác định trường hợp tổng quát: • Lời gọi đệ quy thực hiện bao nhiều lần • Xây dựng công thức đệ quy tổng quát (từ mô tả của thuật toán) • Đâu là trường hợp sẽ dẫn đến thời gian tồi nhất • Dùng các phương pháp giải công thức đệ quy tổng quát đưa ra dạng O-lớn • Chi phí phụ bên cạnh lời gọi đệ quy là bao nhiêu • Phương pháp phân rã • Phương pháp thế int sum_rec(int *A, int n) { Trường hợp cơ sở n=0, thời gian O(1) • Cây đệ quy if (n 0: T(n) = T(n-1) + O(1) • Định lý thợ if (n == 1) return A[0]; return A[n - 1] + sum_rec(A, n - 1); 1, 𝑛 = 0 𝑇 𝑛 = hiep.nguyenduy@hust.edu.vn 9 } 𝑇 𝑛 − 1 + 1, 𝑛 > 0 hiep.nguyenduy@hust.edu.vn 10 int binSearch_rec(int *A, int start, int end, int key) MergeSort(int A[], int start, int end) Thuật toán đệ quy Thuật toán đệ quy { if (start > end) return -1; { int mid = (start + end) / 2; if(start key) return binSearch_rec(A,start,mid - 1,key); Hàm MergeSort int mid = (start+end)/2; return binSearch_rec(A, mid + 1, end, key); } • Gọi đệ quy 2 lần MergeSort(A, start, mid); • Số lượng phần tử n = end – start + 1 MergeSort(A, mid+1, end); • Kích thước bài toán con là n/2 • Trường hợp cơ sở: Dãy rỗng hoặc có 1 phần tử, 1, 𝑛 = 0,1 • Chi phí phụ là O(n) + O(1) = O(n) Merge(A,start,mid,end); thời gian O(1) hoặc 1 𝑇 𝑛 = 𝑛 } 𝑇 + 1, 𝑛 > 1 • Trường hợp tổng quát: 2 } O(n) có thể biểu diễn bằng n cho • Có 3 lệnh return gọn vì nó sẽ ko làm thay đổi tốc độ • 2 lệnh return ứng với lời gọi đệ quy sẽ cho thời gian thực Hàm Merge trộn 2 danh sách với thời gian O(n) hiện lâu nhất tăng trong O-lớn Thường khi đánh giá theo O-lớn ta chỉ cần quan • Lời gọi đệ quy tâm tới trường hợp tổng quát, nên có thể viết 𝑛 • Kích thước bài toán con còn là n/2 gọn lại 𝑇 𝑛 = 2𝑇 + 𝑛 • Số lời gọi đệ quy : 1 (hoặc với if hoặc với else) 2 • Chi phí phụ là hằng số, O(1) 𝑇 𝑛 = 𝑇 +1 hiep.nguyenduy@hust.edu.vn 11 hiep.nguyenduy@hust.edu.vn 12
9/29/2021 Thuật toán đệ quy Thuật toán đệ quy • Phương pháp phân rã Ví dụ: Hãy giải các công thức đệ quy sau và đưa ra dạng O-lớn a) T(n) = T(n/2) + 1 1, 𝑛 = 0 𝑇 𝑛 = 𝑇 𝑛 − 1 + 1, 𝑛 > 0 b) T(n) = 2T(n/3) + 1 𝑇 𝑛 = 𝑇 𝑛 − 1 + 1 = 𝑇 𝑛 − 2 + 1 + 1 = 𝑇 𝑛 − 3 + 1 + 1 + 1 = 𝑇 1 + 1+. . +1 = 1 + 1+. . +1 = 𝑛 c) T(n) = T(n-1) + 2 d) T(n) = 3T(n-1) Thời gian cỡ 𝑂(𝑛) Phương pháp này chủ yếu cho các công thức đệ quy dạng đơn giản hiep.nguyenduy@hust.edu.vn 13 hiep.nguyenduy@hust.edu.vn 14 Thuật toán đệ quy Phương pháp thay thế • Phương pháp thay thế: • Xác định cận trên của công thức đệ quy 𝑛 • Dự đoán dạng của O-lớn (cần có kinh nghiệm) 𝑇 𝑛 = 2𝑇 2 + 𝑛 • Chứng minh dự đoán bằng quy nạp Dự đoán 𝑇 𝑛 = Ο(𝑛log𝑛) Cần chứng minh 𝑇(𝑛) ≤ 𝑐𝑛log𝑛 với hằng số 𝑛 > 0 được chọn phù hợp • Chú ý: • Trong O-lớn việc sai khác 1 KHÔNG ảnh hưởng đến tốc độ tăng của hàm, nên • Giả sử 𝑇(𝑛) ≤ 𝑐𝑛log𝑛 đúng với ⁄ tức là 𝑇( ) ≤ 𝑐 log . 𝑇 𝑛 = 2𝑇 ⁄ + 𝑛 , 𝑇 𝑛 = 2𝑇 ⁄ + 𝑛 và 𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑛 là có tốc • Thay vào 𝑇 𝑛 độ tăng giống nhau • Việc cộng thêm số hạng tăng chậm hơn KHÔNG ảnh hưởng tới tốc độ tăng, nên 𝑇 𝑛 ≤ 2 𝑐 log + 𝑛 ≤ 𝑐𝑛log + 𝑛 = 𝑐𝑛log𝑛 − 𝑐𝑛log2 + 𝑛 ≤ 𝑐𝑛log𝑛 𝑇 𝑛 = 𝑇 𝑛/2 + 𝑛 và 𝑇 𝑛 = 𝑇 𝑛/2 + 100𝑛 + 5 có tốc độ tăng giống nhau Đúng với 𝑐 ≥ 1 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ở). hiep.nguyenduy@hust.edu.vn 15 hiep.nguyenduy@hust.edu.vn 16
9/29/2021 Phương pháp thay thế Phương pháp thay thế • Giả sử trường hợp cơ sở 𝑇 1 = 1 nhưng 𝑐1log1 = 0. Kết quả quy nạp sai trong Ví dụ. Hãy chứng minh trường hợp cơ sở. 𝑛 • Ta có thể giải quyết vấn đề này bằng cách chọn giá trị 𝑛 sao cho a) 𝑇 𝑛 = 𝑇 + 1 là Ο(log 𝑛) 2 𝑇 𝑛 = 𝑐𝑛log𝑛 với 𝑛 ≥ 𝑛 . 𝑛 b) 𝑇 𝑛 = 2𝑇 + 𝑛 là Ο(𝑛 log 𝑛) 2 VD với 𝑛 = 2 thì 𝑇 2 = 2𝑇 1 + 2 = 4 < 𝑐2log2 𝑛 ta chọn hằng số c đủ lớn đủ lớn (VD 𝑐 = 5). c) 𝑇 𝑛 = 𝑇 + 12 + 1 là Ο(log 𝑛) 2 • Vậy 𝑇 𝑛 = Ο(𝑛log𝑛) với 𝑐 = 5 và 𝑛 ≥ 2 𝑛 d) 𝑇 𝑛 = 4𝑇 + 𝑛 là 𝑂(𝑛2 ) 2 • Nhận xét: 𝑛 • Phương pháp thay thế chặt trẽ về mặt toán học e) 𝑇 𝑛 = 2𝑇 + 1 là 𝑂(𝑛) 2 • Yêu cầu phải dự đoán được dạng  ta co thể dự đoán dạng tốc độ tăng lớn rồi giảm dần để tìm dự đoán sát nhất có thể hiep.nguyenduy@hust.edu.vn 17 hiep.nguyenduy@hust.edu.vn 18 Thuật toán đệ quy Cây đệ quy • Cây đệ quy: • Công thức đệ quy • Tìm dạng O-lớn một 𝑛 2𝑛 𝑇 𝑛 = 𝑇 + 𝑇 + Ο(𝑛) cách trực quan, nhưng 3 3 chưa chặt trẽ về toán • Cây đệ quy lệch học • Nhánh đi theo 𝑛/3 là thấp nhất • Có thể chứng minh lại bằng phương pháp thế • Nhánh đi theo 2𝑛/3 là cao nhất 𝛰 1 𝑛ế𝑢 𝑛 = 1 • Cây đệ quy cho mergeSort 𝑇 𝑛 = 2𝑇 + 𝛰 𝑛 𝑛ế𝑢 𝑛 > 1 hiep.nguyenduy@hust.edu.vn 19 hiep.nguyenduy@hust.edu.vn 20
9/29/2021 Cây đệ quy Cây đệ quy • Dùng phương pháp thế để chứng minh lời giải công thức đệ quy tìm được. VD. 𝑇 𝑛 = 𝑇 + 𝑇 + Ο 𝑛 = Ο(𝑛log𝑛) 𝑛 • VD 1. Xác định một cận trên tốt cho công thức đệ quy 𝑇 𝑛 = 3𝑇 + 𝑛 dùng • 𝑇 𝑛 ≤ 𝑇 + 𝑇 + 𝑐𝑛 2 phương pháp thế để xác nhận lại kết quả. ≤ 𝑑 log + 𝑑 log + 𝑐𝑛 𝑛 𝑑𝑛 𝑑𝑛 2𝑑𝑛 2𝑑𝑛 • VD 2. Vẽ cây đệ quy cho 𝑇 𝑛 = 4𝑇 + 𝑐𝑛 với 𝑐 là hằng số. Đưa ra tiệm cận 2 = log 𝑛 − log 3 + log 2𝑛 − log 3 + 𝑐𝑛 chặt cho công thức đệ quy trên. Xác nhận lại lời giải bằng phương pháp thế. 3 3 3 3 2𝑑𝑛 = 𝑑𝑛 log 𝑛 − 𝑑𝑛 log 3 + log 2 + 𝑐𝑛 3 ≤ 𝑑𝑛 log 𝑛 Với 𝑑 ≥ (chú ý log 2 = 1) hiep.nguyenduy@hust.edu.vn 21 hiep.nguyenduy@hust.edu.vn 22 Thuật toán đệ quy Định lý thợ • Định lý thợ - Master theorem Định lý thợ xét mối quan hệ về tốc độ tăng của 𝑛 và 𝑓(𝑛) • Dùng để giải các công thức đệ quy dạng 𝑇 𝑛 = 𝑎𝑇 + 𝑓 𝑛 , với a ≥ 1, 𝑏 > 1, 𝑓 𝑛 là • TH 1. Nếu 𝑓 𝑛 = Ο(𝑛 ), với hằng 𝜖 > 0 thì 𝑇 𝑛 = Θ(𝑛 ) hàm tiệm cận dương • TH 2. Nếu 𝑓 𝑛 = Ο(𝑛 ) thì 𝑇 𝑛 = Θ(𝑛 log 𝑛) • 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í để • TH 3. Nếu 𝑓 𝑛 = Ω(𝑛 ), với hằng 𝜖 > 0, và tổng hợp các bài toán con là 𝒇(𝒏) nếu 𝑎𝑓 < 𝑐𝑓(𝑛) với hằng 𝑐 < 1 và với mọi n đủ lớn thì 𝑇 𝑛 = Θ(𝑓(𝑛)) 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à Ο(𝑛) • Với các dạng công thức đệ quy không áp dụng được định lý thợ, vẫn có thể áp dụng các • Có thể hiểu dạng phương pháp trước để giải • TH 1. tốc độ tăng 𝑛 nhanh hơn so với 𝑓(𝑛) (lim → ( ) = ∞) • TH 2. tốc độ tăng 𝑛 bằng với 𝑓(𝑛) (0 < lim ( ) = 𝐶 < ∞) → • TH 3. tốc độ tăng 𝑛 chậm hơn so với 𝑓(𝑛) hiep.nguyenduy@hust.edu.vn 23 hiep.nguyenduy@hust.edu.vn 24
9/29/2021 Dùng định lý thợ Dùng định lý thợ Áp dụng định lý thợ: • 𝑇 𝑛 = 9𝑇 + 𝑛. • Chú ý: Không phải trường hợp nào cũng áp dụng được định lý thợ ! 𝑎 = 9, 𝑏 = 3 𝑣à 𝑓 𝑛 = 𝑛 ta có 𝑛 ≡ 𝑛 = 𝑛 . Đây là trường hợp 1 (với 𝜖 = • VD. 𝑇 𝑛 = 2𝑇 + 𝑛 log 𝑛 1) do đó 𝑇 𝑛 = Θ(𝑛 ) 𝑎 = 2, 𝑏 = 2 và 𝑓 𝑛 = 𝑛 log 𝑛 • 𝑇 𝑛 = 𝑇 + 1. 𝑎 = 1, 𝑏 = 3/2 và 𝑓 𝑛 = 1 ta có 𝑛 / = 𝑛 = 1. Đây là trường hợp 2, do đó 𝑛 ≡ 𝑛 = 𝑛 do đó có vẻ áp dụng trường hợp 3. Tuy nhiên 𝑓 𝑛 = 𝑇 𝑛 = Θ(log 𝑛) 𝑛 log 𝑛 tiệm cận lớn hơn 2𝑓 với mọi hằng số 𝜖 do đó không thể áp dụng • 𝑇 𝑛 = 3𝑇 + 𝑛 log 𝑛 được. 𝑎 = 3, 𝑏 = 4 và 𝑓 𝑛 = 𝑛 log 𝑛 ta có 𝑛 ≡ 𝑛 = Ο(𝑛 . ), 𝑓 𝑛 = Ω(𝑛 ) với 𝜖 ≈ 0.2, 𝑎𝑓 ⁄ < 𝑐𝑓 𝑛 ≡ 3𝑓 < 𝑐𝑛 log 𝑛 với 𝑐 = do vậy 𝑇 𝑛 = Θ(𝑛 log 𝑛) (TH3) hiep.nguyenduy@hust.edu.vn 25 hiep.nguyenduy@hust.edu.vn 26 Định lý thợ mở rộng Dùng định lý thợ 𝑐, 𝑛 ≤ 1 • Cho dạng hàm 𝑇 𝑛 = Bài 1. Dùng định lý thợ để đưa ra các tiệm cận chặt cho các công thức đệ quy sau 𝑎𝑇 𝑛 − 𝑏 + 𝑓 𝑛 , 𝑛 > 1 𝑛 • 𝑇 𝑛 = 4𝑇 + 𝑛 • Với các hằng số 𝑐, 𝑎 > 0, 𝑏 > 0, 𝑘 ≥ 0 và hàm 𝑓(𝑛), nếu hàm 𝑓 𝑛 có cận trên 2 𝑛 là 𝑂(𝑛 ) thì • 𝑇 𝑛 = 4𝑇 + 𝑛2 2 𝑂 𝑛 , 𝑎1 𝑇 𝑛 = 𝑇 + Θ(1) là Θ(log 𝑛) 2 𝑛 Bài 3. Định lý thợ có thể áp dụng cho công thức đệ quy 𝑇 𝑛 = 4𝑇 + 𝑛2 log 𝑛 được • Dạng hàm 𝑇 𝑛 = 𝑇 𝛼𝑛 + 𝑇 1 − 𝛼 𝑛 + 𝛽𝑛, trong đó 0 < 𝛼 < 1, 𝛽 > 0 thì 2 không, Tại sao? Tìm tiệm cận giới hạn trên cho 𝑇(𝑛) 𝑇 𝑛 = 𝑂(𝑛𝑙𝑜𝑔𝑛) hiep.nguyenduy@hust.edu.vn 27 hiep.nguyenduy@hust.edu.vn 28
9/29/2021 Thuật toán đệ quy Dùng định lý thợ • Bài toán tháp Hà Nội Bài 4. Đánh giá thời gian thực hiện của thuật toán đệ quy sau theo mô hình O-lớn • Có n đĩa với kích thước khác nhau và 3 cọc A, B, C int findMin(int S[], int start, int end) { • Ban đầu n đĩa nằm ở cọc A theo thứ tự đĩa nhỏ A B C if(start>=end) return S[end]; nằm trên và đĩa lớn nằm dưới • Tìm cách chuyển n đĩa này từ cọc A sang cọc B, Lời giải với n=3 int div = (end-start)/2; sử dụng cọc C làm trung gian theo nguyên tắc  B1: A  B int A,B; • Mỗi lần chỉ được chuyển 1 đĩa trên cùng từ  B2: A  C 1 cọc sang cọc khác  B3: B  C A=findMin(S,start,start+div);  B4: A  B B=findMin(S,start+div+1,end); • Không được phép để xảy ra tình trạng đĩa to  B5: C  A nằm bên trên đĩa nhỏ  B6: C  B return Min(A,B);  B7: A  B } Trong đó hàm Min(A,B) trả về giá trị hiep.nguyenduy@hust.edu.vn 2 số A, B và thời gian thực hiện là Θ(1) nhỏ nhất trong 29 hiep.nguyenduy@hust.edu.vn 30 THÁP HÀ NỘI Hàm move di chuyển từ cột A sang cột B với cột Thuật toán đệ quy trung gian là C • Tính giá trị 𝑥 nhanh (với x là giá trị thực và n là mũ nguyên dương) void move(int n, char A, char B, char C) { double fastPower1(double x, int n) if (n == 1) { A B C { printf("Move 1 disk from %c to %c", A, B); if (n == 0) return 1; } if (n % 2 == 0) return fastPower(x, n / 2)*fastPower(x, n / 2); Lời giải với n=3 else { return fastPower(x, n / 2)*fastPower(x, n / 2)*x;  B1: A  B move(n - 1, A, C, B); }  B2: A  C move(1, A, B, C);  B3: B  C 𝑛 move(n - 1, C, B, A); 𝑇 𝑛 = 2𝑇 + 1 = 𝑂(𝑛)  B4: A  B 2 } double fastPower2(double x, int n)  B5: C  A } { int main() {  B6: C  B Chỉ cần dùng thêm 1 biến if (n == 0) return 1; int n = 3;  B7: A  B phụ hạn chế bớt gọi đệ double y = fastPower(x, n / 2); 𝑛 move(n, 'A', 'B', 'C’); quy, hiệu quả thuật toán 𝑇 𝑛 = 𝑇 + 1 = 𝑂(log 𝑛) if (n % 2 == 0) return y*y; return 0; 2 return y*y*x; } hiep.nguyenduy@hust.edu.vn 31 thay đổi rõ rệt hiep.nguyenduy@hust.edu.vn 32 }
9/29/2021 Thuật toán đệ quy Thuật toán đệ quy • Tính số Fibonacci public int Print(int n) { 1 𝑛ế𝑢 𝑛 = 0,1 if (n == 0) // this is the terminating base case 𝑓 𝑛 = return 0; 𝑓 𝑛 − 1 + 𝑓 𝑛 − 2 𝑛ế𝑢 𝑛 ≥ 2 else { System.out.println(n); Tính 𝑓(5) return Print(n - 1); // recursive call to itself again • 𝑓(5)= 𝑓(4)+ 𝑓 3 = 𝑓 3 + 𝑓 2 + 𝑓 3 = ⋯ } } • Đệ quy có nhớ: Trường hợp bài toán con có thể trùng lặp • Để cải thiện hiệu năng của thuật toán được cài đặt đệ quy, nên hạn chế tối thiểu gọi đê quy nếu có thể (thay bằng biến phụ, hoặc bảng tra nếu các bài toán con có xu hướng lặp lại) • Khi gặp bài toán con, kiểm tra xem lời giải đã có trong bảng tra hay chưa. • Nếu chưa có thì giải và cập nhật lời giải vào bảng tra • Nếu đã có thì lấy lời giải để sử dụng hiep.nguyenduy@hust.edu.vn 33 hiep.nguyenduy@hust.edu.vn 34 Thuật toán đệ quy • Đệ quy trực tiếp VS Đệ quy gián tiếp Thuật toán quay lui Back-tracking algorithm hiep.nguyenduy@hust.edu.vn 35 hiep.nguyenduy@hust.edu.vn 36
9/29/2021 Thuật toán quay lui Thuật toán quay lui • Thuật toán quay lui • Là một cải tiến của lớp các bài toán vét cạn – brute force • Một số bài toán dùng thuật toán quay lui • Tại một thời điểm chỉ thử đi theo theo một hướng chứ không thử đồng thời tất cả các • Bài toán tìm đường đi trong mê cung khả năng (dùng ít bộ nhớ phụ hơn) • Bài toán sinh tất cả chuỗi nhị phân độ dài n • Nếu hướng hiện tại gặp bế tắc – dead end, quay lại và thử đi theo hướng mới • Bài toán xếp hậu, mã đi tuần,… • Từng bước xây dựng lời giải bộ phận để thu được lời giải cuối cùng • Bài toán cái túi • Trong trường hợp tồi nhất thuật toán vẫn phải vét cạn hết tất cả các khả năng có thể có • Bài toán chu trình Hamiltonian trong không gian các phương án tiềm năng • Bài toán tô màu đồ thị • Để chứng minh bài toán không có lời giải, cần phải vét hết toàn bộ không gian tìm kiếm • Nếu không gian bài toán lớn, thời gian tìm lời giải có thể rất lâu • Thường cài đặt đơn giản dùng đệ quy, thay vì dùng vòng lặp (vẫn có thể cài đặt bằng vòng lặp được) hiep.nguyenduy@hust.edu.vn 37 hiep.nguyenduy@hust.edu.vn 38 Thuật toán quay lui Thuật toán quay lui Solve_from (Current_config) { • Bài toán 8 con hậu: “Hãy xếp 8 if (Current_config đã chứa lời giải đầy đủ) con hậu trên bàn cờ 8x8 sao cho print Current_config chúng không thể ăn lẫn nhau” Sơ đồ tổng quát của else thuật toán quay lui Với tập các lựa chọn chưa được xét đến trong Current_config Ý tưởng: { • Các quân hậu cần được xếp riêng trên mỗi cột (hoặc hàng) Thêm 1 lựa chọn P; • Thử xếp các quân hậu trong các cột lần lượt từ 1 tới 8 Cập nhật lại Current_config; • Mỗi cột thử đặt quân hậu tại lần lượt các hàng (của cột đó) solve_from(Current_config); • Nếu có vị trí đặt hợp lệ thì chuyển qua đặt hậu ở cột kế bên Loại bỏ lựa chọn P khỏi Current_config; //quay lui • Ngược lại, nếu không thể tìm được vị trí đặt hậu tại cột hiện tại, cần quay lui lại lựa } chọn vị trí đặt của cột ngay trước để sửa lại } • Nếu đặt đủ 8 hậu  tìm được 1 phương án giải hiep.nguyenduy@hust.edu.vn 39 hiep.nguyenduy@hust.edu.vn 40
9/29/2021 Thuật toán quay lui Kiểm tra An toàn • Dead end: trạng thái chưa kết thúc, nhưng ta không thể đặt thêm được 1 quân hậu nào nữa. solve_from (Current_config){ • Khi rơi vào trạng thái dead end ta phải tiến hành quay lui (back track) lại lựa chọn gần nhất để thử một khả năng có thể khác. if Current_config đã chứa đủ 8 hậu print Current_config else Với tập p các ô trên bàn cờ mà chưa bị ảnh hưởng bởi Current_config { 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; } Dead end với bài toán xếp 4 hậu } hiep.nguyenduy@hust.edu.vn 41 hiep.nguyenduy@hust.edu.vn 42 Giải thuật Thuật toán quay lui import java.util.*; function Try (column) { Thử lần lượt từng vị trí hàng public class BinaryStrings { int[] A; • Bài toán sinh các chuỗi nhị phân độ dài n (tổng for (row = 1; row
9/29/2021 {1, 0, 0, 0} Thuật toán quay lui void printSolution(int *x, int n) { Thuật toán quay lui {1, {0, 1, 1, 0, 0, 1} 0} {1, 1, 1, 1} for (int k = 0; k < n; k++) printf("%d", x[k]); • Bài toán tìm đường đi trong mê cung • Bài toán sinh các chuỗi nhị phân printf("\n"); • Mê cung có thể biểu diễn thành ma trận nhị phân mở rộng: Không có 2 bit 1 đứng } Tường sẽ là bit 0, điểm bắt đầu [0,0], kết thúc [N-1,M-1] cạnh nhau int TRY(int *x, int n, int k) { void printSolution(int sol[N][N]) for (int v = 0; v 0 && v + x[k - 1] == 2) continue; for (int i = 0; i < N; i++) { x[k] = v; vào bước continue trong vòng lặp if (k == n - 1) printSolution(x, n); for (int j = 0; j < N; j++) vì bài toán khá đơn giản else TRY(x, n, k + 1); printf(" %d ", sol[i][j]); printf("\n"); } } bool isSafe(int maze[N][N], int x, int y) } { } if (x >= 0 && x < N && y >= 0 int main() { && y < N && maze[x][y] == 1) int x[5], n = 5; return true; TRY(x, n, 0); } return false; hiep.nguyenduy@hust.edu.vn 45 hiep.nguyenduy@hust.edu.vn 46 } bool solveMazeUtil(int maze[N][N], int x,int y, int sol[N][N]) { if (x == N - 1 && y == N – 1 && maze[x][y] == 1) { sol[x][y] = 1; Thuật toán quay lui return true; } • Bài toán giải ô chữ SUDOKU: 2x2, 3x3, 4x4 if (isSafe(maze, x, y) == true) { // Check if the current block is already part of solution path. if (sol[x][y] == 1) return false; sol[x][y] = 1; // mark x, y as part of solution path if (solveMazeUtil(maze, x + 1, y, sol)== true) return true; if (solveMazeUtil(maze, x, y + 1, sol)== true) return true; if (solveMazeUtil(maze, x-1, y, sol)== true) return true; if (solveMazeUtil(maze, x, y - 1, sol)== true) return true; sol[x][y] = 0; /* unmark x, y as part of solution path */ return false; 𝑇 𝑛 = 𝑂(9 ) } 𝑇 𝑛 = 𝑂(2 ) return false; https://www.geeksforgeeks.org/sudoku-backtracking-7/ } https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-2/ hiep.nguyenduy@hust.edu.vn 47 hiep.nguyenduy@hust.edu.vn 48
9/29/2021 58 10011111 Thuật toán quay lui 01110011 10111101 Thuật toán quay lui 10101111 10111101 • Bài 1. Liệt kê các hoán vị của xâu “ABCDE” và “AEBEA” • Bài 6. Cho đầu vào là 1 danh sách số nguyên gồm n phần tử với thứ tự bất kỳ. Hãy xây • Bài 2. In ra các xâu độ dài k với các ký tự lấy ra từ xâu “ABCDEFGH” dựng chương trình in ra dãy số sao cho phần tử có giá trị lớn nhất ở giữa, sau đó giá trị các phần tử giảm dần về 2 phía (có thể có nhiều cách in thỏa mãn) • Bài 3. Điền các chữ số 0-9 vào thay cho các ký tự trong đoạn mật mã sau VD. 54,7,25,45,78,12,6,8  7, 12, 54, 78, 45, 25, 8, 6 • Bài 4. Xây dựng thuật toán in ra những cách xếp k quân tượng trên bàn cờ • Bài 7. Bài toán cắt dây vua kích thước nxn sao cho các quân tượng này không đe dọa nhau Anh công nhân A được giao n cuộn dây với độ dài d bằng nhau (d

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.