Bài giảng Cấu trúc dữ liệu và giải thuật - Phương pháp quay lui

Phương pháp quay luiBài toánPhương phápLược đồ tổng quátVí dụ minh hoạBài toán 8 hậuBài toán mã đi tuầnBài toán tìm các hoán vị của dãy số 1..nBài toán tìm các tập con có tổng cho trước1Bài toánDùng để thiết kế thuật toán tìm ra một nghiệm hoặc tất cả các nghiệm của bài toánTrong nhiều trường hợp, việc tìm nghiệm quy về việc tìm một véctơ hữu hạn V(x1,x2,,xn, ) nhưng độ dài véctơ có thể không được xác định trước.2Bài toán (tiếp)Véctơ này cần thoả mãn một số điều kiện nào đó tuỳ thuộc bài toán.Các thành phần xi của vectơ được chọn từ một tập hữu hạn Ai(i=1,2..n,).3Phương phápTa xây dựng vectơ nghiệm dần từng bước, bắt đầu từ vectơ không ().Thành phần đầu tiên x1 được chọn ra từ tập S1 = A1.Khi đã chọn được các thành phần x1, x2,..,xi-1 từ các điều kiện của bài toán ta xác định tập Si các ứng viên để chọn làm thành phần xiTập Si là tập con của Ai và phụ thuộc vào các thành phần x1,x2,,xi-1 đã chọn.4Phương pháp (tiếp)Chọn một phần tử xi trong tập Si ta mở rộng vectơ nghiệm (x1,x2,,xi-1) thành vectơ nghiệm (x1,x2,,xi).Lặp lại quá trình trên để tiếp tục mở rộng vectơ nghiệm (x1,x2,,xi).Nếu không thể chọn được thành phần xi+1 (khi Si+1=) ta quay lại chọn phần tử khác của Si làm xi. Nếu không còn một phần tử nào khác của Si ta quay lại chọn một phần tử khác của Si-1 làm xi-1 và cứ thế tiếp tục5Phương pháp (tiếp)Trong quá trình mở rộng vectơ nghiệm ta phải kiểm tra vectơ nghiệm có là nghiệm của bài toán hay không.Nếu chỉ tìm 1 vectơ nghiệm, khi tìm được vectơ nghiệm ta dừng lạiNếu cần tìm tất cả các vectơ nghiệm, quá trình trên chỉ dừng khi tất cả các khả năng chọn các xi của vectơ nghiệm đã được duyệt hết.6Lược đồ tổng quát Quaylui(vectơ,i) {Xác định thành xi của vectơ nghiệm}Bước 1: Xác định SiBước 2: Với mọi xi  Si thực hiện các bước sau:Bước 2.1: vectơ = vectơ +(xi);Bươc 2.2: Nếu vectơ là nghiệm thì Viết nghiệmBước 2.3: Quaylui(vectơ,i+1);Bước 2.4: vectơ = vectơ – (xi);7Bài toán 8 quân hậuInput: Bàn cờ 8 x 88 quân hậuOutput:Đặt 8 quân hậu vào 8 ô khác nhau sao cho trên mỗi hàng, mỗi cột, mỗi đường chéo chỉ có một quân8Bài toán 8 hậu (tiếp )XXXXXXXX9Bài toán 8 hậu (tiếp )Ý tưởngSử dụng phương pháp quay luiVét cạn mọi trường hợp có thể xảy ra	10Bài toán 8 hậu (tiếp )X11Bài toán 8 hậu (tiếp )XXỐi! Tôi bị ănXX12Bài toán 8 hậu (tiếp )XX13Bài toán 8 hậu (tiếp )Bài toán 8 hậu (tiếp )XXX14Bài toán 8 hậu (tiếp )Bài toán 8 hậu (tiếp )XXX15Bài toán 8 hậu (tiếp)XXXX16Bài toán 8 hậu (tiếp)XXXX17Bài toán 8 hậu (tiếp)XXXXX18Bài toán 8 hậu (tiếp)XXXXX19Bài toán 8 hậu (tiếp)XXXXXX20Bài toán 8 hậu (tiếp)XXXXXXX21Bài toán 8 hậu (tiếp)XXXXXXXHết chỗ đặt tướng !!!22Bài toán 8 hậu (tiếp)XXXXXXXCất tướng ở vị trí này23Bài toán 8 hậu (tiếp)XXXXXCất tướng khỏi ô này24Bài toán 8 hậu (tiếp)XXXXCất tướng khỏi ô nàyX25Bài toán 8 hậu (tiếp)XXXXX26Bài toán 8 hậu (tiếp)XXXXXKhông đặt tướng được!!!27Bài toán 8 hậu (tiếp)XXXXKhông đặt được tướng ở vị trí nàyX28Bài toán 8 hậu (tiếp)XXXXX29Bài toán 8 hậu (tiếp)XXXXXX30Bài toán 8 hậu (tiếp)XXXXXXX31Bài toán 8 hậu (tiếp)XXXXXXX32Bài toán 8 hậu (tiếp)XXXKhông đặt được tướng ở vị trí nàyX33Bài toán 8 hậu (tiếp )DATHAU(i); {Đặt bà thứ i trên bàn cờ }Bước 1: Khởi động chọn vị trí cho bà thứ i;Bước 2: Thực hiện các bước sau cho đến khi (Thành công) hoặc (Hết chỗ đặt tướng bà) : Bước 2.1: Thực hiện phép chọn vị trí cho bà thứ i;Bước 2.2: Nếu Antoàn thực hiện các bước sau:34Bài toán 8 hậu (tiếp )Bước 2.1.a Đặt tướngBước 2.1.b Nếu (in) InKêtQua ngược lại thực hiện bước 2.Bước 2: Với mọi j  1..n thực hiện:Bước 2.1: Nếu (B[j] =1) thực hiện:Bước 2.1.a: A[i]=j;B[j] =0;Bước 2.1.a: TRY(i+1);B[j]=1; A[i] =0; 61Bài toán tìm các tập Con có tổng cho trướcInput:A tập n số nguyên dươngM là số nguyên dương cho trướcOutput:Tìm A’  A, sao cho  A’ = M62A = { 3, 5, 20, 15, 35, 69, 72}M = 38 Bài toán tìm các tập Con có tổng cho trước (tiếp)63Bài toán tìm các tập Con có tổng cho trước (tiếp) 352015356972 M = 3835201543 > MQuay lui!!!64 M = 3833Bài toán tìm các tập Con có tổng cho trước (tiếp)352015356972 M = 3835153533558 > MQuay lui!!!65Bài toán tìm các tập Con có tổng cho trước (tiếp) - Giải thuậtTa dùng mảng A[1..n] để lưu các số nguyên thuộc tập A đã choMảng I[1..n] lưu chỉ số các thành phần thuộc A’ cần tìmS lưu tổng các số của A’ trong quá trình hình thành66Bài toán tìm các tập Con có tổng cho trước (tiếp) - Giải thuậtTAPCONBước 1: k=1; I[1 ]=0; S =0;Bước 2: Khi k 0 thực hiện các bước:Bước 2.1: I[k] =I[k]+1;Bước 2.2: Nếu I[k]<=n thực hiện các bước sau, ngược lại thực hiện bước 2.367Bài toán tìm các tập Con có tổng cho trước (tiếp) - Giải thuậtTAPCONBước 2.2.a: Nếu S+A[I[k]] = M viết kết quả l[1..k], ngược lại thực hiện:Bước 2.2.b: S =S+A[I[k]];l[k+1]=I[k];k=k+1Bước 2.3:k=k-1;S = S- A[i[k]];6869