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 liệt kê các hoán vị, bài toán liệt kê dãy nhị phân độ dài N và bài toán duyệt đồ thị. 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ê các hoán vị Liệt kê dãy nhị phân độ dài N Duyệt đồ thị 2/2/2017 2 Bài toán • Có N đối tượng (được đánh số từ 1 đến N), hãy liệt kê tất cả các hoán vị có thể của N đối tượng đó. • Bài toán trên có thể qui về bài toán: Liệt kê tất cả các hoán vị của N số nguyên đầu tiên. • Ví dụ: Các hoán vị của 3 số 1,2,3: 123,132,213,231,312,321 (thứ tự từ điển) 321,312,231,213,132,123 (thứ tự TD ngược) 2/2/2017 3 1 2/2/2017 Bài toán liệt kê • Bài toán liệt kê: có thể tiếp cận theo cách liệt kê (phương pháp sinh - Generating) các khả năng ứng với mỗi thành phần của vector phương án (tìm hiểu sau) Thứ tự từ điển (từ bé đến lớn) 123,132,213,231,312,321 Thứ tự từ điển ngược (từ lớn đến bé) 321,312,231,213,132,123 2/2/2017 4 Ý tưởng thuật toán Ý tưởng (Thử và Sai) 1. Cần xếp các số từ 1-N vào N vị trí (khác nhau từng đôi một) 2. Giả sử đã xếp được đến vị trí thứ i-1. 3. Tìm 1 giá trị thích hợp (chưa được dùng) trong khoảng từ 1 đến N cho vị trí thứ i. Lặp lại bước 3 khi i
