"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 4: Kỹ thuật quay lui (Backtracking)" với những kiến thức khái niệm về kỹ thuật quay lui, bài toán 8 con hậu - eight queen problem, bài toán mã đi tuần - knight tour problem, bài toán chiếc ba lô - knapsack problem. | Cấu trúc dữ liệu và giải thuật Bài 4 Kỹ thuật quay lui Backtracking Lecturer PhD. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 @Copyright PhD. Ngo Huu Phuc Le Quy Don Technical University Bài 4. Kỹ thuật quay lui Backtracking Nội dung . Khái niệm về kỹ thuật quay lui 6 . Bài toán 8 con hậu - Eight Queen Problem 7 . Bài toán mã đi tuần - Knight Tour Problem 5 . Bài toán chiếc ba lô - Knapsack Problem 6 Tham khảo 1. Lecture 11 2 @Copyright PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm kỹ thuật quay lui 1 6 Kỹ thuật quay lui là quá trình phân tích từ trên xuống trong không gian tìm kiếm. Trong trường hợp tổng quát giả sử lời giải là một vector a a 1 a 2 a n trong đó mỗi phần tử a i chọn từ tập hữu hạn S i các khả năng của a i . 3 @Copyright PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm kỹ thuật quay lui 2 6 Ta s ẽ giải quyết bài toán với kích thước k có dạng a a 1 a 2 a k và cố gắng mở rộng bằng việc thêm phần tử tiếp theo vào trong vector. Sau khi thêm phần tử kiểm tra xem có thể thực hiện tiếp được không. Nếu vẫn có khả năng mở rộng tiếp tục thực hiện Nếu không xóa phần tử a k và làm lại bài toán từ tập S k . 4 @Copyright PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm kỹ thuật quay lui 3 6 Gọi S 1 tập các khả năng của a tại bước đầu tiên. k 1 While k gt 0 do While S k do advance a k an element in S k If a 1 a 2 a k is solution print it k k 1 Tính S k tập khả năng của a tại bước k. k k - 1 backtrack 5 @Copyright PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm kỹ thuật quay lui 4 6 Sub Backtrack a k If a is a solution get it Else k k 1 compute S k While S k do a k an element in S k S k S k a k Backtrack a k End Sub 6 @Copyright PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm kỹ thuật quay lui 5 6 Kỹ thuật đệ quy có thể được dùng trong kỹ thuật quay lui đơn giản trong ứng dụng . Kỹ thuật quay lui chắc chắn đúng khi .
