Bài giảng Phân tích thiết kế giải thuật: Backtracking Method (tiếp) - GV. Hà Đại Dương

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. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: Backtracking Method (tiếp) - GV. Hà Đại Dương2/2/2017Analysis and Design of AlgorithmsLecture 11,12Backtracking MethodLecturer: Ha Dai Duongduonghd@mta.edu.vn2/2/20171Nội dung1.2.3.4.5.6.7.Lược đồ chungBài toán 8 hậuBài toán ngựa đi tuầnTrò chơi SudokuLiệt kê các hoán vịLiệt kê dãy nhị phân độ dài NDuyệt đồ thị2/2/20172Bà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 đốitượng đó.• Bài toán trên có thể qui về bài toán: Liệt kê tấtcả 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/2017312/2/2017Bài toán liệt kê• Bài toán liệt kê: có thể tiếp cận theo cách liệtkê (phương pháp sinh - Generating) các khảnăng ứng với mỗi thành phần của vectorphương án (tìm hiểu sau)Thứ tự từ điển (từ bé đến lớn)123,132,213,231,312,321Thứ tự từ điển ngược (từ lớn đến bé)321,312,231,213,132,1232/2/20174Ý 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 nhautừ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ặplại bước 3 khi i