Giáo trình giải thuật - giải thuật quay lui

Chia sẻ: Đặng Duy Nhật | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

379
lượt xem 141
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

* Đặ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 * 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.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình giải thuật - giải thuật quay lui

Giải thuật quay lui (back tracking) GVGD: Trương Phước Hải
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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