intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Cấu trúc dữ liệu - Phần 5

Chia sẻ: Nguyen Nguyen | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
186
lượt xem 29
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo bài giảng môn Cấu trúc dữ liệu - Phần 5 Giải thuật quay lui

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu - Phần 5

  1. Giải thuật quay lui (back tracking) GVGD: Trương Phước Hải
  2. Nội dung 1. Kỹ thuật quay lui 2. Bài toán liệt kê 3. Bài toán 8 hậu 4. Bài toán mã đi tuần 2
  3. Kỹ thuật quay lui  Kỹ thuật quay lui là quá trình lần ngược trở lại con đường đã qua để thử tìm một lời giải khác cho bài toán start end 3
  4. Kỹ thuật quay lui  Đặc điểm Kỹ thuật quay lui thường được dùng để giải các bài toán liệt  kê cấu hình có dạng là tập các thành phần (X0, X1, …, XN-1)  Tư tưởng Xây dựng dần cấu hình bằng cách thử tất cả khả năng (giá  trị) cho mỗi phần tử của cấu hình Khi đến phần tử cuối cùng của cấu hình thì ta tìm được 1  nghiệm của bài toán 4
  5. Kỹ thuật quay lui  Ý tưởng thực hiện Thành phần X[i] có tập các khả năng {1, 2, …, Ni}. Thử lần  lượt từng khả năng cho X[i] (X[i] = j, với j  {1, 2, …, Ni}) Trường hợp chọn được khả năng j cho X[i]  Nếu X[i] là phần tử cuối thì tìm được một cấu hình  Ngược lại xét đến thành phần tiếp theo X[i+1]  Trường hợp không tìm được khả năng nào cho X[i]: quay  lại bước trước để thử khả năng khác cho X[i-1] 5
  6. Kỹ thuật quay lui  Mô hình tổng quát của giải thuật quay lui Try(i) For (j  {1, 2, …, nj}) Thử chọn khả năng j cho X[i] If (X[i] ở cuối cùng cấu hình) then Else Try(i + 1) Cuối If Cuối for Cuối Try 6
  7. Nội dung 1. Kỹ thuật quay lui 2. Bài toán liệt kê 3. Bài toán 8 hậu 4. Bài toán mã đi tuần 7
  8. Bài toán liệt kê  Bài toán 1 Liệt kê tất cả dãy nhị phân có độ dài N bit   Ví dụ Các dãy nhị phân có độ dài 3 bit: 000, 001, 010, 011, 100,  101, 110, 111 8
  9. Bài toán liệt kê  Tổ chức dữ liệu Biểu diễn dãy nhị phân N bit dưới dạng mảng một chiều  X[0], X[1], …, X[N-1] Phần tử của mảng X[i] có tập giá trị {0, 1}  9
  10. Bài toán liệt kê  Ý tưởng Thử gán cho X[i] lần lượt mang các giá trị {0, 1}  Với mỗi giá trị chọn được cho X[i], thử các giá trị có thể có  cho X[i + 1] Tiếp tục thực hiện cho đến phần tử cuối cùng X[N – 1], khi  đó ta tìm được một dãy nhị phân cho bài toán 10
  11. Bài toán liệt kê  Giải thuật thủ tục Try của bài toán Try(i) For (j  {0, 1}) X[i] = j If (i = N-1) then Else Try(i + 1) Cuối If Cuối for Cuối Try 11
  12. Bài toán liệt kê  Cài đặt ngôn ngữ void Try(int X[], int N, int i) { for (int j = 0; j
  13. Bài toán liệt kê  Cây tìm kiếm cho trường hợp N = 3 Try(0) x0 = 0 x0 = 1 Try(1) Try(1) x1 = 0 x1 = 1 x1 = 0 x1 = 1 Try(2) Try(2) Try(2) Try(2) x2 = 0 x2 = 1 x2 = 0 x2 = 1 x2 = 0 x2 = 1 x2 = 0 x2 = 1 000 001 010 011 100 101 110 111 13
  14. Bài toán liệt kê  Bài toán 2 Liệt kê tất cả cách chọn k phần tử từ tập gồm N phần tử  {1, 2, …, N}  Ví dụ Cho tập gồm 5 phần tử {1, 2, 3, 4, 5}, các cách chọn ra 3  phần tử từ tập này là: {123, 124, 125, 134, 135, 145, 234, 235, 245, 345} 14
  15. Bài toán liệt kê  Phân tích bài toán Mỗi cách chọn là một dãy các phần tử có dạng (x1x2 … xk)  x1 < x2 < … < xk  xk ≤ N  xk-1 ≤ xk – 1 ≤ N – 1  => xi ≤ N – k + i  => x1 ≤ N – k + 1  => xi-1 + 1 ≤ xi ≤ N – k + i với 1 ≤ i ≤ k (x0 = 0)  15
  16. Bài toán liệt kê  Tổ chức dữ liệu Dùng mảng một chiều k + 1 phần tử (X[0], X[1], …, X[k])  để biểu diễn một cách chọn  Ý tưởng Ban đầu khởi tạo X[0] = 0  Với mỗi X[i] (i{1, ..., k}), gán lần lượt từng giá trị trong  miền giá trị của X[i]. Khi đến phần tử thứ k thì ta có được một cách chọn Miền giá trị của X[i]: X[i-1] + 1 ≤ X[i] ≤ N – k + i  16
  17. Bài toán liệt kê  Giải thuật thủ tục Try của bài toán Try(i) For (j = Xi-1 + 1; j ≤ N – k + i) X[i] = j If (i = k) then Else Try(i + 1) Cuối If Cuối for Cuối Try 17
  18. Bài toán liệt kê  Cài đặt ngôn ngữ void Try(int X[], int N, int k, int i) { for (int j = X[i-1]+1; j
  19. Bài toán liệt kê  Bài toán 3 Liệt kê tất cả hoán vị của tập gồm N phần tử {1, 2, …, N}   Ví dụ Tập họp gồm 3 phần tử {1, 2, 3} có các hoán vị sau: {123,  132, 213, 231, 321, 312} 19
  20. Bài toán liệt kê  Phân tích bài toán Mỗi hoán vị được biểu diễn dưới dạng một dãy các phần tử  (x0x1…xN-1) Các phần tử xi của một hoán vị là khác nhau đôi một  Sử dụng mảng một chiều X[0], X[1], …, X[N-1] để biểu  diễn một hoán vị 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2