Phân tích và thiết kế thuật toán - Liệt kê các hoán vị

2/2/2017 1 Lecture 11,12 Backtracking Method Lecturer: Ha Dai Duong duonghd@mta.edu.vn Analysis and Design of Algorithms 2/2/2017 1 Nội dung 1. Lược đồ chung 2. Bài toán 8 hậu 3. Bài toán ngựa đi tuần 4. Trò chơi Sudoku 5. Liệt kê các hoán vị 6. Liệt kê dãy nhị phân độ dài N 7. 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 2/2/2017 2 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<N. 2/2/2017 5 Phương án nghiệm • Bộ gồm N số từ 1 đến N khác nhau từng đôi một. Ứng viên • Các giá trị từ 1 đến N Tính hợp lệ • x[i] nhận giá trị J nếu J chưa được dùng cho các x[1] đến x[i-1] 2/2/2017 6 2/2/2017 3 Cài đặt • Dùng mảng b[j], j=1..N để dánh dấu giá trị j đã được dùng hay chưa. – b[j] = 0 : j đã được dùng – b[j] = 1 : j chưa được dùng 2/2/2017 7 2/2/2017 8 Minh họa • Với n=3 2/2/2017 9 2/2/2017 4 Minh họa • Với n=4 2/2/2017 10 Nội dung 1. Lược đồ chung 2. Bài toán 8 hậu 3. Bài toán ngựa đi tuần 4. Trò chơi Sudoku 5. Liệt kê các hoán vị 6. Liệt kê dãy nhị phân độ dài N 7. Duyệt đồ thị 2/2/2017 11 Bài toán • Bài toán 1: Liệt kê tất cả các số nhị phân có độ dài N. Ví dụ với N=3, ta có các (8) liệt kê sau: 000, 001, 010, 011, 100, 101, 110, 111. • Bài toán 2: Liệt kê tập tất cả các tập con của tập có N phần tử. Nhận xét: Bài toán 2 có thể chuyển về bài toán 1. 2/2/2017 12 2/2/2017 5 Ý tưởng thuật toán 2/2/2017 13 Phương án nghiệm • Dãy N các giá trị 0, 1 (đảm bảo không có 2 nghiệm nào trùng nhau) 2/2/2017 14 Cài đặt 2/2/2017 15 2/2/2017 6 Minh họa 2/2/2017 16 Nội dung 1. Lược đồ chung 2. Bài toán 8 hậu 3. Bài toán ngựa đi tuần 4. Trò chơi Sudoku 5. Liệt kê các hoán vị 6. Liệt kê dãy nhị phân độ dài N 7. Duyệt đồ thị 2/2/2017 17 Bài toán 2/2/2017 18 2/2/2017 7 Tìm kiếm theo chiều sâu DFS ( Depth First Search) • Ý tưởng 2/2/2017 19 Mô tả 2/2/2017 20 Cài đặt 2/2/2017 21 2/2/2017 8 Cài đặt 2/2/2017 22 Cài đặt 2/2/2017 23 Minh họa 2/2/2017 24 2/2/2017 9 Đường đi từ 1 đến 4 2/2/2017 25 Đường đi từ 2 đến 5 2/2/2017 26 Tìm kiếm theo chiều rộng BFS ( Breadth First Search) • Ý tưởng 2/2/2017 27 2/2/2017 10 Mô tả 2/2/2017 28 Cài đặt 2/2/2017 29 2/2/2017 30 2/2/2017 11 Minh họa 2/2/2017 31 Bài tập 1. Liệt kê các hoán vị của tập 4 phần tử (theo thuật toán mục 5) 2. Liệt kê tất cả các dãy nhị phân có độ dài 5 (theo thuật toán mục 6) 2/2/2017 32 Bài tập Cho đồ thị có hướng 3. Thực hiện từng bước thuật toán DFS trên đồ thị để tìm đường đi từ đỉnh 1 đến đỉnh 4. 4. Thực hiện từng bước thuật toán BFS trên đồ thị để tìm đường đi từ đỉnh 2 đến đỉnh 5. 2/2/2017 33 2/2/2017 12 Bài tập 5. Cài đặt thuật toán giải bài toán người du lịch (dựa trên thuật toán liệt kê các hoán vị) theo phương pháp quay lui. Đánh giá độ phức tạp thuật toán bằng lý thuyết, bằng thực nghiệm và so sánh. 6. Cài đặt thuật toán tìm đường đi trên đồ thị, thuật toán DFS, theo phương pháp quay lui . Đánh giá độ phức tạp thuật toán bằng lý thuyết, bằng thực nghiệm và so sánh. 2/2/2017 34 Bài tập 7. Cài đặt thuật toán tìm đường đi trên đồ thị, thuật toán BFS, theo phương pháp quay lui . Đánh giá độ phức tạp thuật toán bằng lý thuyết, bằng thực nghiệm và so sánh. 2/2/2017 35