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

Thuật toán quay lùi

Chia sẻ: NGUYỄN DUY SƠN | Ngày: | Loại File: DOC | Số trang:16

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

Phương pháp liệt kê là cách cuốicùng để có thể giải được một số bài toán tổ hợp hiện nay. Mộttrong những phương pháp liệt kê có tính phổ dụng cao đó là phương pháp quay lùi. Để hiểu rõ hơn về phương pháp này mời các bạn tham khảo tài liệu Thuật toán quay lùi sau đây.

Chủ đề:
Lưu

Nội dung Text: Thuật toán quay lùi

  1.   DUY Sơn (Sưu Tầm)     Triệu Sơn – Thanh Hoá  Một bài toán liệt kê tổ hợp luôn cần phải đảm bảo hai nguyêntắc, đó là: không được  bỏ sót một cấu hình và không được trùnglặp một cấu hình. Có thể nói rằng phương  pháp liệt kê là cách cuốicùng để có thể giải được một số bài toán tổ hợp hiện nay.  Mộttrong những phương pháp liệt kê có tính phổ dụng cao đó là phươngpháp quay lui.   Nội dung chính của phương pháp này là việc xây dựng dần cácthành phần của cấu  hình bằng cách thử tất cả các khả năng. Giả thiếtcấu hình cần được tìm được mô tả  bằng một bộ giá trị (x 1 ,x 2 ,..,x N ).Giả sử đã xác định được i ­ 1 thành phần (x 1 ,x 2 ,...,x  i­1 ),bây giờ ta xác định thành phần x i bằng cách duyệt tất cảcác khả năng có thể đề cử  cho nó (đánh số từ 1 đến n i ).Với mỗi khả năng j, kiểm tra xem j có được chấp nhận  hay không. Cóthể có hai trường hợp có thể xảy ra:  ­ Nếu j được chấp nhận thì xác định x i theo j, sau đó nếu j = N thì ta được một cấu  hình,trái lại ta tiếptục tiến hành việc xác định x i+1 .  ­ Nếu thử tất cảcác khả năng mà mà không có khả năng nào được chấp nhận thì ta  sẽlùi lại bước trướcđể xác định x i­1 .  Thông thường ta phân tích quá trình tìm kiếm thành cây tìm kiếm.Không gian tìm kiếm  càng lớn hay càng nhiều khả năng tìm kiếm thì câytìm kiếm càng lớn, càng nhiều  nhánh. Vì vậy hạn chế và bỏ bớt cácnhánh vô nghiệm của cây tìm kiếm thì sẽ tiết  kiệm được thời gianvà bộ nhớ, tránh bị tràn dữ liệu. Quá trình tìm kiếm lời giải  theothuật toán quay lui có thể được mô tả bởi mô hình cây tìm dướiđây:  Cần phải lưu ý là ta phải ghi nhớ tại mỗi bước đã đi qua,những khả năng nào đã thử  để tránh trùng lặp. Những thông tin nàyđược lưu trữ theo kiểu dữ liệu ngăn xếp ­  Stack ( vào sau ra trước) ­ vì thế nên thuật toán này phù hợp thểhiện bởi thủ tục đệ  quy. Ta có thể mô tả bước xác định x i bởi thủ tục đệ quy sau:  Procedure Try (i: integer);  Var j : integer;  Begin  For j:= 1to ni do  If (chấp nhận j) then  Begin  (xác định xi theo j )  if i = N then (ghi nhận một cấu hình)  1
  2. else try(i+1);  End;  End;  Trong thủ tục mô tả trên, điều quan trọng nhất là đưa rađược một danh sách các khả  năngđề cử và xác định được giá trịcủa biểu thức logic [ chấp nhận j ]. Ngoài việc phụ  thuộc j, giá trị này còn phụ thuộc vào việc đã chọn các khả năng tại i ­ 1bước trước  đó. Trong những trường hợp như vậy, cần ghi nhớ trạng thái mới của quá trìnhsau khi  [xác định xi theo j ] vàtrả lại trạng thái cũ sau lời gọi Try(i+1).Các trạng thái này được  ghi nhận nhờ một số biến tổng thể(global), gọi là các biến trạng thái.  Dễ thấy rằng bài toán vô nghiệm khi ta đã duyệt hết mọi khảnăng mà không có khả  năng nào thoả mãn yêu cầu. Ta nói rằng là đã vét cạn mọi trường hợp.Chú ý rằng là  đến một lúc nào đó ta phải lùi liên tiếp nhiều lần.Từ đó suy ra rằng, thông thường bài  toán vô nghiệm khi không thể lùiđược nữa. Thuật toán này sẽ không có tính khả thi  cao bởi dùng thủtục đệ quy dễ bị lỗi tràn Stack.  Bài 1: Hành trình ký tự Cho tệp văn bản HT_KITU.INP chứa các dòng ký tự chiều  dài khôngquá 32. Hãy lập trình thực hiện các công việc sau: Lần lượt đọc cácdòng vào  một xâu, sau đó từ xâu xây dựng lưới ô vuông dạng tam giácnhư sau: ví dụ xâu  =’Vinh’, lưới ô vuông có dạng như hình 1. Xuấtphát từ ô góc trên trái (chữ V), đi theo  các hướng có thể để xâydựng lại xâu đã cho. Với mỗi hành trình thành công hãy in ra  số thứtự của hành trình và chỉ ra hành trình trên lưới, mỗi ký tự của hànhtrình thay  bằng một dấu ’*’.  Ví dụ:  Sau mỗi lời giải phải ấn ENTER để in lời giải tiếp.  Hướngdẫn giải  Tổ chức hai mảng hai chiều F, Kt[1..32,1..32] of Char.Mảng Kt dùngđể tạo ra ma trận  kí tự dạng tam giác như trên gồm các kí tự từ xâuS đọc từ file dữ liệu. Mảng F dùng  để ghi nhận các hành trình thànhcông, nếu ô (i,j) thuộc hành trình thì F[i,j] = ’*’.  Sau khi xây dựng xong ma trận kí tự, ta dùng thủ tục đệ quy Try(i,j,h: byte) để tìm tất  cả các hành trình. Giả sử ta đangở ô (i,j) nào đó trên hành trình và đã được một xâu kí  tự độ dài h ≤ length(S ). Nếu h = length(S )thì ta đã được một hành trình và ta sẽ ghi  nhận nó, in ra màn hìnhhành trình đó. Còn nếu h 
  3. Const D : Array[1..2] of shortint= (0,1);  C : Array[1..2] of shortint= (1,0);  Fi = ’HT_KITU.INP’;  Var Kt,F : Array[1..32,1..32] of Char;  S : string;  t : word;  dem : longint;  Procedure Init;  Var k,i,j : byte;  G : Text;  Begin  Assign(G,Fi); Reset(G);  Read(G,S); t:= length(S);  Fillchar(F,sizeof(F),’ ’);  F[1,1]:=’*’; k:= 0;  For i:= 1 to t do  begin  For j:=1 to t do  begin  Kt[i,j]:= S[j+k];  If Kt[i,j] = #0 then Kt[i,j]:= ’ ’;  end;  inc(k);  end;  Close(G);  End;  Procedure Write_Out;  Var i,j : Byte;  Begin  Inc(dem);  TextColor(Red); Writeln(’Hanh trinh thu:’,dem);  For i:=1 to t do  begin  For j:=1 to t do  If F[i,j]=’*’ then                                                                      begin  TextColor(White); Write(’* ’)  end  Else  begin  TextColor(Green);Write(Kt[i,j],’ ’);  end;  Writeln;  end;  Readln;  End;  3
  4. Procedure Try(i,j,h: byte);  Var k,x,y: byte;  Begin  If h = t then Write_Out else  begin  For k:=1 to 2 do  begin  x:= i + D[k]; y:= j + C[k];  F[x,y]:=’*’;  Try(x,y,h+1);  F[x,y]:=’ ’;  end;  end;  End;  BEGIN  Clrscr;  Init;  Try(1,1,1);  END.  Bài 2: Biểu thức zero  Cho một số tự nhiên N ≤ 9. Giữa các số từ 1 đến N hãy thêm vào cácdấu + và ­ sao cho  kết quả thu được bằng 0. Hãy viết chương trình tìmtất cả các khả năng có thể.  Dữ liệu vào: Lấy từ file văn bản ZERO.INP với một dòng ghi số N.  Dữ liệu ra: Ghi vào file văn bản có tên ZERO.OUT có cấu trúc nhưsau:  ­ Dòng đầu ghi sốlượng kết quả tìm được.  ­ Các dòng sau mỗidòng ghi một kết quả tìm được.  Ví dụ  Hướng dẫn giải  áp dụng thuật toán đệ quy quay lui để giải quyết bài toánnay, ta sẽ dùng thủ tục đệ  quy Try(i). Giả sử ta đã điền các dấu’+’ và ’­’ vào các số từ 1 đến i, bây giờ cần điền  các dấugiữa i và i + 1. Ta có thể chọn một trong ba khả năng: hoặc là điềndấu ’+’,  hoặc là điền dấu ’­’, hoặc là không điền dấu nào cả.Khi đã chọn một trong ba khả  năng trên, ta tiếp tục lựa chọn dấuđể điền vào giữa i + 1 và i + 2 bằng cách gọi đệ quy  Try(i+1). Ta sẽlần lượt duyệt tất cả các khả năng đó để tìm tất cả các nghiệmcủa bài  toán, như vậy bài toán sẽ không bị thiếu nghiệm.  Nếu i = N ta sẽ kiểm tra xem cách điền đó có thoả mãn kết quảbằng 0 hay không. Để  kiểm tra ta dùng thủ tục Test trong chương trình. Nếutổng đúng bằng 0 thì cách điền  4
  5. đó là một nghiệm của bài toán, taghi nhận nó. Nếu i 
  6. else DocSo:= M;  End;  Procedure Test;  Var St : string;  i : byte;  T : longint;  Begin  St:= ’1’; k:= 1; T:= 0;  For i:= 2 to N do St:= St + D[i] + S[i];  While k 
  7. ­ Các số trên cùng mộtdòng trong các file vào/ ra, được ghi cách nhau ít nhất một dấu  trắng.  ­ Giới hạn kích thước:N ≤ 100, M ≤50, K ≤10.  ­ Dữ liệu vào trong cáctest là hợp lệ và đảm bảo có ít nhất một đáp án.  Ví dụ:  Hướng dẫn giải  Ta nhận thấy rằngmỗi nghiệm của bài toán chính là một cấu hình của tổ hợp chập K  củaM phần tử. Ta áp dụng thuật toán quay lui để duyệt mọi cấu hình tổhợp để tìm ra  cấu hình thoả mãn. Tuy nhiên để giảm bớt số lần duyệtta cần phải loại những thẻ mà  chúng có tổng điểm bằng 0 và cầnđánh dấu những thẻ đã được chọn.  Dùng mảng ok[0..51] of boolean để phân biệt giữa ô có điểm và những ô không có  điểm. Nếu ok[i]= false thìcho biết thẻ thứ i không có điểm. Còn logic[i,j] = true cho ta  biết người thứ i đánh dấu vàothứ j của thẻ.  Văn bản chương trình  Program Xoso_dien_toan;  Type MangA = array[0..100,0..11] of byte;  MangBool = array[0..51] of boolean;  MangLogic = array[0..101,0..51] of boolean;  Cauhinh = array[0..11] of byte;  Const Fi = ’XOSO.INP’;  Fo = ’XOSO.OUT’;  var M,N,K : byte;  A : MangA;  B : Cauhinh;  Ok : MangBool;  Diem : integer;  Logic : MangLogic;  F : Text;  Procedure Init;  Begin  Fillchar(A,sizeof(A),0);  Fillchar(B,sizeof(B),0);  Fillchar(ok,sizeof(ok),1);  Fillchar(logic,sizeof(logic),0);  End;  Procedure Read_inp;  Var i,j : byte;  7
  8. Begin  Assign(F,Fi); Reset(F);  Readln(F,N,M,K);  For i:= 1 to N do  begin  For j:= 1 to k do  begin  Read(f,A[i,j]); Logic[i,A[i,j]]:= true;  end;  Read(F,A[i,k+1]); Inc(diem,A[i,k+1]);  If A[i,k+1] = 0 then  For j:= 1 to k do ok[A[i,j]]:= false;  end;  Close(F);  End;  Function Chapnhan(j: byte): boolean;  Var v : byte;  Begin  Chapnhan:= false;  For v:= 1 to n do  If (A[v,K+1] = 0) and logic[v,j] then exit;  Chapnhan:=true;  End;  Procedure Rutgon(j: byte);  Var i : byte;  Begin  For i:= 1 to N do  If logic[i,j] then  begin  Dec(A[i,k+1]);Dec(diem);  end;  End;  Procedure Morong(j: byte);  Var i : byte;  Begin  For i:= 1 to N do  If logic[i,j] then  begin  Inc(A[i,k+1]); Inc(diem);  end;  End;  Procedure Write_out;  Var d: byte;  Begin  For d:= 1 to K do write(f,B[d],’ ’); Writeln(F);  8
  9. End;  Procedure Try(i:byte);  Var j: byte;  Begin  For j:= B[i­1] + 1 to M ­ K + i do  If ok[j] and chapnhan(j) then  begin  B[i]:= j;  Ok[j]:= false;  Rutgon(j);  If (diem = 0) and (i = k) then write_out  else if i 
  10. Sắp xếp 28 quân bài domino ta có thể tạo ra một hìmh chữ nhật kích thước 7*8 ô  vuông. Mỗi cách sắp xếp như vậy sẽ tạo ra một bản đồ số. Ngược lại, mỗi bản đồ  số có thể tương ứng với một số cách xếp. Ví dụ bản đồ số: 4 2 5 2 6 3 5 4  5 0 4 3 1 4 1 1  1 2 3 0 2 2 2 2  1 4 0 1 3 5 6 5  4 0 6 0 3 6 6 5  4 0 1 6 4 0 3 0  6 5 3 6 2 1 5 3  tương ứng với hai cách xếp mô tả bởi hai bảng số sau: 16 16 24 18 18 20 12 11  06 06 24 10 10 20 12 11  08 15 15 03 03 17 14 14  08 05 05 02 19 17 28 26  23 01 13 02 19 07 28 26  23 01 13 25 25 07 21 04  27 27 22 22 09 09 21 04  16 16 24 18 18 20 12 11  06 06 24 10 10 20 12 11  08 15 15 03 03 17 14 14  08 05 05 02 19 17 28 26  23 01 13 02 19 07 28 26  23 01 13 25 25 07 21 04  27 27 22 22 09 09 21 04  Bài toán đặt ra là cho trước một bảnng số, hãy liệt kê tất cả các cách xếp có thể tạo ra  từ nó. Dữ liệu vào từ file DOMINO.INP là ma trận 7*8 mô tả bản đồ số ban đầu. 10
  11. Kết quả ghi ra file DOMINO.OUT dòng đầu là số lượng p cách xếp tìm được. Tiếp  theo là p nhóm dòng, mỗi nhóm gồm 7 dòng ghi các dòng của các bảng tương ứng với  một bảng số tìm được. Hướng dẫn giải  Vói mỗi quân bài domino ta có thể có hai khả năng xếp vào hình chữ nhật: hoặc là đặt  nằm ngang, hoặc là đặt nằm dọc. Ta sẽ thử tất cả các cách để đặt chúng vào hình chữ  nhật cho đến khi nào đặt được cả 28 quân bài vào hình chữ nhật thì đó là một trong  các cách xếp thoả mãn. Mỗi cách xếp thoả mãn sẽ được lưu vào mảng  L[1..10,1..7,1..8]. Văn bản chương trình  Program Bo_bai_domino_voi_cac_ban_do_so; Type Bandoso = array[1..7,1..8] of byte; Sothutu = array[0..6,0..6] of byte; Cauhinh = array[1..10,1..7,1..8] of byte; Const Fi = ’DOMINO.INP’; Fo = ’DOMINO.OUT’; D : array[1..2] of byte = (0,1); C : array[1..2] of byte = (1,0); Var A,B : Bandoso; L : Cauhinh; Gt : Sothutu; TS : set of byte; T,dem: byte; F : Text; Procedure Read_inp; Var i,j,k : byte; Begin Assign(F,Fi); Reset(F); dem:= 0; For i:= 1 to 7 do begin For j:= 1 to 8 do read(F,A[i,j]); Readln(F); end; For i:= 0 to 6 do For j:= i to 6 do begin Inc(k); Gt[i,j]:= k; Gt[j,i]:= k; end; Close(F); End; Function Sott(x: byte) : String; Var S : String; Begin Str(X,S); If length(S) = 1 then S:= ’0’ + S; 11
  12. Sott:= S; End; Procedure Result; Var i,j : byte; Begin Inc(dem); For i:= 1 to 7 do For j:= 1 to 8 do L[dem][i,j]:= B[i,j]; End; Procedure Try(i,j : byte); Var k,u,v,x : byte; Begin While (j  0) do inc(j); If (j = 8) and (B[i,j] > 0) then Try(i+1,1) else For k:= 1 to 2 do begin u:= i + D[k]; v:= j + C[k]; If (u in [1..7]) and (v in [1..8]) and (B[u,v] = 0) then begin x:= Gt[A[i,j],A[u,v]]; If not (x in Ts) then begin Inc(t); Ts:= Ts + [x]; B[i,j]:= x; B[u,v]:= x; If t = 28 then Result else If v = 8 then Try(i+1,1) else Try(i,v+1); Dec(t); Ts:= Ts ­ [x]; B[i,j]:= 0; B[u,v]:= 0; end end; end; End; Procedure Write_out; Var k,i,j : byte; Begin Assign(F,Fo); Rewrite(F); Writeln(dem); For k:= 1 to dem do begin For i:= 1 to 7 do begin For j:= 1 to 8 do write(F,Sott(L[dem][i,j]),’ ’); Writeln(F); end; Writeln(F); Writeln(F); end; 12
  13. Close(F); End; BEGIN Read_inp; Try(1,1); Write_out; END. Bài 5: Robot quét vôi  Có 9 căn phòng (đánh số từ 1 đến 9) đã được quét vôi với mầu trắng, xanh hoặc vàng.  Có 9 rôbôt (đánh số từ 1 đến 9) phụ trách việc quét vôi các phòng. Mỗi rôbôt chỉ quét  vôi một số phòng nhất định. Việc quét vôi được thực hiện nhờ một chương trình cài  sẵn theo qui tắc: ­ Nếu phòng đang có mầu trắng thì quét mầu xanh, ­ Nếu phòng đang có mầu xanh thì quét mầu vàng, ­ Nếu phòng đang có mầu vàng thì quét mầu trắng. Cần phải gọi lần lượt một số các rôbôt ra quét vôi (mỗi lần một rôbôt, một rôbôt có  thể gọi nhiều lần và có thể có rôbôt không được gọi. Rôbôt được gọi sẽ quét vôi tất  cả các phòng mà nó phụ trách) để cuối cùng các phòng đều có mầu trắng. Hãy tìm một  phương án như vậy sao cho lượng vôi phải quét là ít nhất. Giả thiết rằng luợng vôi  cho mỗi lượt quét đối với các phòng là như nhau. Dữ liệu: đọc từ file văn bản ROBOT.INP gồm các dòng: ­ 9 dòng đầu, mỗi dòng mô tả danh sách các phòng được quét vôi bởi một rôbôt theo  thứ tự từ rôbôt 1 đến rôbôt 9. Mỗi dòng như vậy gồm các số hiệu phòng viết sát nhau.  Chẳng hạn dòng thứ 3 có nội dung: 2356 mô tả rôbôt 3 phụ trách việc quét vôi các  phòng 2, 3, 5, 6. ­ Dòng cuối mô tả mầu vôi ban đầu của các phòng. Dòng gồm 9 ký tự viết sát nhau, ký  tự thứ i biểu diễn mầu vôi của phòng i với quy ước: ký tự T chỉ mầu trắng, ký tự X  chỉ mầu xanh, ký tự V chỉ mầu vàng. Kết quả: đưa ra file văn bản ROBOT.OUT gồm một dòng dưới dạng: ­ Nếu không có phương án thì ghi một chữ số 0, ­ Trái lại ghi dãy thứ tự các rôbôt được gọi (các số hiệu rôbôt viết sát nhau). Ví dụ  Hướngdẫn giải  13
  14. Ta sẽ giải bài toán bằng cách duyệt theo cây tìm kếm. Với mỗi con robot ta có thể  không gọi hoặc sẽ gọi tối đa là hai lần, do đó là sẽ có ba cách lựa chọn. Ta sẽ lần lượt  duyệt các danh sách để gọi các con robot. Vì có tất cả 9 danh sách nên ta phải duyệt  tối đa là 39 cách gọi. Do bài toán đòi hỏi là lượng vôi ít nhất nên ta sẽ tìm cách gọi nào  là tối ưu nhất. Để giảm bớt số lần duyệt ta có thể dùng thêm cận để kiểm tra điều  kiện có thực hiện tiếp hay không. Nếu ở bước thứ i ta cần gọi là S robot là số lần gọi  tối ưu lúc đó là Min thì nếu S > min thì ta có thể nhánh này của cây và quay lại bước  thứ i − 1, nếu S 
  15. Ví dụ: Hướng dẫn giải  Sau mỗi bước hoặc robot gần người thêm một dơn vị khoảng cách hoặc không gian bị  hạn chế thêm một đơn vị độ dài cả về chiều rộng lẫn chiều dài, do đó ta đi đến khẳng  định: nếu người tồn tại sau K = Min{M,N} bước thì người tồn tại mãi mãi hay nếu  người bị robot ăn thịt thì không thể tồn tại sau K bước di chuyển. Với khẳng định trên đây lặp không quá K bước trong đó mỗi bước lặp liên quan đến  việc thực hiện 5 cách đi trong bước. Như vậy tổng số bước không vượt quá 5 K thuật  toán. Để lưu trữ về tình trạng bản đồ của hành tinh ta dùng mảng A[1..K,1..M,1..N]. Sau  mỗi bước thử cách đi cho nhà du hành ta sẽ sử dụng một thủ tục để cho các con robot  di chuyển tiến lại gần nhà du hành. 15
  16. 16
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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