Bài giảng "Thuật toán ứng dụng: Đệ qui và nhánh cận" trình bày các nội dung chính sau đây: Giới thiệu đệ qui, mô hình chung của đệ qui, đệ qui đối với các mô hình giải bài, duyệt toàn bộ; Thuật toán quay lui; Bài toán tối ưu tổ hợp; Mô hình thuật toán nhánh cận; . Mời các bạn cùng tham khảo! | Đệ Qui và Nhánh Cận THUẬT TOÁN ỨNG DỤNG Các mô hình giải bài căn bản Các phương pháp căn bản xây dựng lời giải bài toán Duyệt toàn bộ Chia để trị Qui 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 45 1 Giới thiệu 2 Quay lui 3 Nhánh và Cận 4 45 1 Giới thiệu Đệ qui Mô hình chung của đệ qui Đệ qui đối với các mô hình giải bài Duyệt toàn bộ 2 Quay lui 3 Nhánh và Cận 5 45 Đệ qui là gì Trong thực tế ta thường gặp những đối tượng bao gồm chính nó hoặc được định nghĩa dưới dạng của chính nó. Ta nói các đối tượng đó được xác định một cách đệ qui 6 45 Đệ qui là gì Trong thực tế ta thường gặp những đối tượng bao gồm chính nó hoặc được định nghĩa dưới dạng của chính nó. Ta nói các đối tượng đó được xác định một cách đệ qui Đệ qui và qui nạp Đệ qui và qui nạp toán học có những nét tương đồng và là bổ sung cho nhau. Định nghĩa đệ qui thường giúp cho chứng minh bằng qui nạp các tính chất của các đối tượng được định nghĩa đệ qui. Ngược lại các chứng minh bằng qui nạp toán học thường là cơ sở để xây dựng các thuật toán đệ qui để giải quyết nhiều bài toán 1 Bước cơ sở qui nạp gt giống như bước cơ sở trong định nghĩa đệ qui 2 Bước chuyển qui nạp gt giống như bước đệ qui 6 45 Kỹ thuật đệ qui Kỹ thuật đệ qui là kỹ thuật tự gọi đến chính mình với đầu vào kích thước thường là nhỏ hơn Việc phát triển kỹ thuật đệ qui là thuận tiện khi cần xử lý với các đối tượng được định nghĩa đệ qui chẳng hạn tập hợp hàm cây . . . 7 45 Mô hình chung của đệ qui 1 void Try input 2 if lt Kich_Thuoc_Dau_Vao_Du_Nho gt 3 lt Buoc_Co_So gt T r a _ V e _ K Q _ T r u o n g _ H o p _ C o _ S o 4 else Buoc de qui 5 foreach lt Bai_Toan_Con_Trong_CTDQ gt 6 call Try new_input 7 Combine lt Loi_Giai_Cac_Bai_Toan_Con gt 8 return solution 9 10 Độ phức tạp hàm đệ qui có thể được tính tiệm cận đơn giản bởi số lượng lời gọi đệ qui nhân với độ phức tạp tối đa của một lời gọi đệ qui 8 45 Các mô hình giải bài căn bản Các phương pháp căn bản xây dựng lời giải bài toán Duyệt toàn bộ Chia để trị Qui .
