Bài giảng gồm các bài tập minh họa cho phương pháp Quay lui: bài toán 8 hậu, bài toán ngựa đi tuần và trò chơi Sudoku. Tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin để các bạn bổ trợ thêm kiến thức lập trình của mình. . | 2/2/2017 Analysis and Design of Algorithms Lecture 11,12 Backtracking Method Lecturer: Ha Dai Duong duonghd@ 2/2/2017 1 Nội dung 1. 2. 3. 4. 5. 6. 7. Lược đồ chung Bài toán 8 hậu Bài toán ngựa đi tuần Trò chơi Sudoku Liệt kê dãy nhị phân độ dài N Liệt kê các hoán vị Duyệt đồ thị 2/2/2017 2 Nội dung 1. 2. 3. 4. 5. 6. 7. Lược đồ chung Bài toán 8 hậu Bài toán ngựa đi tuần Trò chơi Sudoku Liệt kê dãy nhị phân độ dài N Liệt kê các hoán vị Duyệt đồ thị 2/2/2017 3 1 2/2/2017 Giới thiệu • Phương pháp quay lui dùng để giải các bài toán mà lời giải của nó X là một tập các phần tử x1, x2, , xn. • Ví dụ: Bài toán 8 hậu, Mã đi tuần 2/2/2017 4 Ý tưởng • Ý tưởng chính của phương pháp quay lui là các bước hướng tới lời giải cuối cùng của bài toán dựa trên việc Thử-và-Sai. • Tại mỗi bước: – Nếu có 1 lựa chọn được chấp nhận thì ghi nhận lại lựa chọn này và và tiến hành các bước thử tiếp theo; – Nếu tất cả các lựa chọn không được chấp nhận thì trở lại bước trước, xóa bỏ sự ghi nhận của ứng viên và chọn lựa ứng viên tiếp theo. 2/2/2017 5 Ví dụ • Mã đi tuần trên bàn cờ 4 x 4 (bắt đầu từ Ô(1,1) 2/2/2017 6 2 2/2/2017 Ví dụ • Mã đi tuần trên bàn cờ 4 x 4 (bắt đầu từ Ô(1,1) 1 2/2/2017 7 Ví dụ • Mã đi tuần trên bàn cờ 4 x 4 (bắt đầu từ Ô(1,1) 1 2 2/2/2017 8 Ví dụ • Mã đi tuần trên bàn cờ 4 x 4 (bắt đầu từ Ô(1,1) 1 5 8 11 2 13 4 9 6 10 2/2/2017 14 7 12 3 9 3 2/2/2017 Ví dụ • Mã đi tuần trên bàn cờ 4 x 4 (bắt đầu từ Ô(1,1) 1 14 5 8 11 2 13 4 9 6 10 7 12 3 2/2/2017 10 Ví dụ • Mã đi tuần trên bàn cờ 4 x 4 (bắt đầu từ Ô(1,1) 1 5 8 11 2 13 4 9 6 10 7 12 3 2/2/2017 11 Ví dụ • Mã đi tuần trên bàn cờ 4 x 4 (bắt đầu từ Ô(1,1) 1 8 5 2/2/2017 2 4 10 11 9 6 7 12 3 12 4 2/2/2017 Ví dụ • Mã đi tuần trên bàn cờ 4 x 4 (bắt đầu từ Ô(1,1) 1 8 5 2 4 10 11 9 6 7 12 3 2/2/2017 13 Quay lui • Khi quay lui điểm quan trọng của thuật toán là phải ghi nhớ tại mỗi bước đi để tránh trùng lặp khi quay
