Bài giảng Thuật toán ứng dụng - Chương 3: Đệ quy và nhánh cận. Chương này cung cấp cho học viên những nội dung về: các mô hình giải bài cơ bản; quay lui đệ qui; nhánh và cận; . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | Đệ qui và Nhánh cận THUẬT TOÁN ỨNG DỤNG Đỗ Phan Thuận Bộ môn Khoa Học Máy Tính Viện CNTT amp TT Trường Đại Học Bách Khoa Hà Nội. Ngày 3 tháng 10 năm 2019 1 32 1 Giới thiệu 2 Quay lui đệ qui 3 Nhánh và Cận 2 32 Các mô hình giải bài cơ bản Mô hình giải bài một phương pháp xây dựng bài giải cho một loại bài toán riêng biệt Duyệt toàn bộ Chia để trị Quy hoạch động Tham lam Mỗi mô hình ứng dụng cho nhiều loại bài toán khác nhau 3 32 Phương pháp vạn năng Duyệt toàn bộ Brute force Exhaustive search I bài toán yêu cầu tìm một đối tượng có đặc tính riêng loại bài toán I áp dụng mô hình Duyệt toàn bộ duyệt qua tất cả các đối tượng với mỗi đối tượng kiểm tra xem nó có đặc tính cần tìm không nếu có dừng lại nếu không tiếp tục tìm 4 32 Duyệt toàn bộ Cho một tập hữu hạn các phần tử Yêu cầu tìm một phần tử trong tập thỏa mãn một số ràng buộc I hoặc tìm tất cả các phần tử trong tập thỏa mãn một số ràng buộc Đơn giản Chỉ cần duyệt qua tất cả các phần tử trong tập với mỗi phần tử thì kiểm tra xem nó có thỏa mãn các ràng buộc không Tất nhiên là cách này không hiệu quả. Nhưng nhớ là ta luôn tìm bài giải đơn giản nhất mà chạy trong giới hạn thời gian Duyệt toàn bộ luôn là mô hình giải bài đầu tiên bạn nên nghĩ đến khi giải một bài toán 5 32 Phân tích thời gian tính khấu trừ Amortized time Đối với các thuật toán duyệt toàn bộ khi số lượng lời giải lên đến hàm mũ ta cần đánh giá hiệu quả của thuật toán thông qua thời gian tính khấu trừ. Thời gian tính khấu trừ là thời gian tính trung bình toàn bộ thuật toán mà một cấu hình lời giải được liệt kê ra. Như vậy đại lượng này được tính bởi tổng độ phức tạp thuật toán chia cho tổng số cấu hình lời giải của bài toán. 6 32 Bài toán ví dụ Vito s family http external 100 7 32 1 Giới thiệu 2 Quay lui đệ qui 3 Nhánh và Cận 8 32 Thuật toán quay lui Tư tưởng chính của thuật toán này là xây dựng dần các thành phần của cấu hình lời giải S bằng cách thử tất cả các khả năng có thể. Xuất phát từ .
