Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Trần Đăng Hưng

Chia sẻ: Lê Thị Na | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

78
lượt xem 6
download

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

Nội dung chương 2 của Bài giảng Cấu trúc dữ liệu và giải thuật cung cấp cho sinh viên các kiến thức về đệ quy và giải thuật đệ quy. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.

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: Chương 2 - Trần Đăng Hưng

BÀI GIẢNG CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trần Đăng Hưng Khoa CNTT - ĐHSPHN
Nội dung  Chương 1: Giới thiệu  Chương 2: Đệ quy và Giải thuật đệ quy  Chương 3: Quy hoạch động  Chương 4: Danh sách móc nối  Chương 5: Stack và Queue  Chương 6: Cây và Ứng dụng  Chương 7: Đồ thị và Ứng dụng  Chương 8: Các thuật toán sắp xếp  Chương 9: Các thuật toán tìm kiếm 2 CTDL&GT - Trần Đăng Hưng 1 September 2015
Nội dung  Chương 1: Giới thiệu  Chương 2: Đệ quy và Giải thuật đệ quy  Chương 3: Quy hoạch động  Chương 4: Danh sách móc nối  Chương 5: Stack và Queue  Chương 6: Cây và Ứng dụng  Chương 7: Đồ thị và Ứng dụng  Chương 8: Các thuật toán sắp xếp  Chương 9: Các thuật toán tìm kiếm 3 CTDL&GT - Trần Đăng Hưng 1 September 2015
Đệ quy  Môt đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với chính nó  Ví dụ: Hình ảnh phát thanh viên ngồi trên màn hình, …  Trong toán học gặp nhiều công thức dạng đệ quy  Ví dụ: Tính N!, Tìm USCLN,… 4 CTDL&GT - Trần Đăng Hưng 1 September 2015
Giải thuật đệ quy  Lời giải của bài toán P được gọi là đệ quy nếu nó được thực hiện thông qua lời giải của bài toán P’ cùng dạng với nó  P’ thường nhỏ hơn P và việc giải P’ không cần dùng đến P  Hàm đệ quy gồm hai phần:  Phần neo: Được thực hiện khi lời giải đơn giản, có thể tìm được ngay mà không cần đến bài toán con nào  Phần đệ quy: Khi bài toán chưa giải được bằng phần neo, thì xác định các bài toán con và gọi đệ quy giải các bài toán con này, khi đã có lời giải các bài toán con thì phối hợp lại để được lời giải.  Phần đệ quy thể hiện tính quy nạp, phần neo thể hiện sự hữu hạn của giải thuật. Sau một số lần gọi đệ quy sẽ tiến đến phần neo. 5 CTDL&GT - Trần Đăng Hưng 1 September 2015
Ví dụ giải thuật đệ quy (1/2)  Tìm ước số chung lớn nhất của 2 số nguyên dương  Tính giai thừa: 6 CTDL&GT - Trần Đăng Hưng 1 September 2015
Ví dụ giải thuật đệ quy (2/2)  Dãy số fibonaxi (bài toán sinh sản của Thỏ) 7 CTDL&GT - Trần Đăng Hưng 1 September 2015
Trò chơi Tháp Hà Nội (1/2)  Có n chiếc đĩa, và 3 cái cọc, ban đầu tất cả đĩa xếp trên 1 cọc, cần di chuyển số đĩa này sang 1 cọc khác theo nguyên tắc: 8 CTDL&GT - Trần Đăng Hưng 1 September 2015
Trò chơi Tháp Hà Nội (2/2) 9 CTDL&GT - Trần Đăng Hưng 1 September 2015
Đệ quy hỗ tương  Việc gọi hàm không chỉ là tự gọi nó mà còn có gọi đến hàm khác, và hàm kia có khả năng gọi lại hàm ban đầu  Cứ như vậy tạo vòng lặp xen kẽ nhau, và tất nhiên dù là lặp dạng nào thì cũng cần có điểm dừng  Ví dụ: 10 CTDL&GT - Trần Đăng Hưng 1 September 2015
Nhận xét  Đệ quy là một công cụ mạnh để giải các bài toán  Thiết kế giải thuật đệ quy thường đơn giản, dễ viết  Tuy nhiên, nhược điểm là tốn bộ nhớ khi phải gọi đệ quy nhiều lần, và thường không làm việc được với dữ liệu lớn  Một số thuật toán có thể khử đệ quy bằng cách sử dụng các vòng lặp  Đệ quy và quy nạp toán học quan hệ chặt chẽ, nên những bài toán có tính chất quy nạp thì có thể giải bằng đệ quy  Thường chỉ dùng đệ quy khi không còn phương án nào khác 11 CTDL&GT - Trần Đăng Hưng 1 September 2015
ĐỆ QUY QUAY LUI (Backtracking) 12 CTDL&GT - Trần Đăng Hưng 1 September 2015
Giới thiệu  Thực tế có nhiều bài toán cần trả lời các câu hỏi dạng  Có bao nhiêu khả năng…?  Có tồn tại hay không một khả năng…?  ….  Kỹ thuật quay lui là một kỹ thuật được sử dụng để tìm nghiệm của các bài toán có không gian nghiệm lớn bằng cách thử-sai và loại bỏ các khả năng.  Thông thường, ứng viên nghiệm của các bài toán này có dạng x = (x1, x2, x3,…, xn); trong đó xi là thành phần thứ i.  Ý tưởng cơ bản của các thuật toán quay lui: sinh ra tất cả các khả năng có thể có của nghiệm và kiểm tra mỗi khả năng xem nó có thoả mãn các điều kiện của bài toán không 13 CTDL&GT - Trần Đăng Hưng 1 September 2015
Thuật toán quay lui  G/s nghiệm của bài toán có dạng véc-tơ: x = (x1, x2,…,xn)  Ý tưởng xây dựng nghiệm: mỗi véc-tơ nghiệm được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử lần lượt các khả năng có thể của phần tử đó.  Cụ thể, các bước thực hiện:  Xét tất cả các giá trị của x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó, với mỗi giá trị thử gán cho x1 thì:  Xét tất cả các giá trị của x2 có thể nhận, thử cho x2 nhận lần lượt các giá trị đó, với mỗi giá trị thử gán cho x2 thì:  …… o Xét tất cả các giá trị của xn có thể nhận, thử cho xn nhận lần lượt các giá trị đó, kiểm tra xem bộ nghiệm (x1, x2,…, xn) hiện thời có thỏa mãn các ràng buộc không. Nếu có thì thông báo nghiệm. 14 CTDL&GT - Trần Đăng Hưng 1 September 2015
Mô hình của thuật toán quay lui 15 CTDL&GT - Trần Đăng Hưng 1 September 2015
MỘT SỐ VÍ DỤ KINH ĐIỂN 16 CTDL&GT - Trần Đăng Hưng 1 September 2015
Bài toán liệt kê dãy nhị phân x[i] được nhận  Hãy liệt kê tất cả các dãy nhị phân có độ dài n. các giá trị 0, 1  Ví dụ: n = 3 000 001 đưa dãy x ra màn hình. 010 011 100 101 110 111 17 CTDL&GT - Trần Đăng Hưng 1 September 2015
Bài toán liệt kê hoán vị  Liệt kê tất cả các hoán vị độ dài n.  Ví dụ: n = 3 123 132 213 231 312 321 Lưu ý: ngoài mảng x để lưu cấu hình hiện tại, cần thêm mảng C để đánh dấu các số đã được chọn. Vì các mảng để chỉ số từ 0, nên lời gọi của thủ tục là Try(0). 18 CTDL&GT - Trần Đăng Hưng 1 September 2015
Bài toán liệt kê tổ hợp  Liệt kê các tổ hợp chập k của n phần tử.  Ví dụ: n = 5, k = 3 Nhận xét: vì x[1] < x[2] < x[3]
Bài toán xếp hậu  Trong bàn cờ kích thước n x n, cần xếp n con hậu vào các ô của bàn cờ sao cho không con nào ăn được con nào  http://www.hbmeyer.de/backtrack/achtdamen/eight.htm#up 20 CTDL&GT - Trần Đăng Hưng 1 September 2015