Bài giảng Phân tích và thiết kế giải thuật Chương 6: PGS.TS. Dương Tuấn Anh

Chương 6 Giải thuật quay lui

Giải thuật quay lui Giải thuật nhánh-và-cận

ể ả ế ấ ề i quy t v n đ : thi

ằ ị ế t ả i cho bài tóan không ph i là bám c xác đ nh mà là b ng

ử

Giải thuật quay lui ươ ổ ộ ng pháp t ng quát đ gi M t ph ờ ả ậ ế ả i gi i thu t tìm l k gi ượ ậ ộ ậ theo m t t p qui lu t tính tóan đ ử (trial and error). cách th và s a sai

ườ ử ng là phân rã quá trình th và s a

ườ theo l

ữ ộ ậ ệ ử ữ i đ quy m t ộ ố ữ ạ ượ ồ ng thì nh ng ễ ả ộ ố ệ ệ thăm dò m t s h u h n

ữ ẫ Khuôn m u thông th ộ ậ sai thành nh ng công tác b ph n. Th công tác b ph n này đ c di n t ậ cách thu n ti n và bao g m vi c nh ng công tác con .

ể ư ộ

ầ ấ ạ ệ ầ

ộ ộ quá trình Ta có th coi toàn b quá trình này nh là m t tìm ki mế (search process) mà d n d n c u t o và duy t qua m t cây các công tác con.

Bài toán đường đi của con hiệp sĩ (The Knight’s Tour Problem)

ộ ượ ờ n (cid:0) ộ n v i ớ n2 ô. M t con hi p sĩ – đ

ể ậ ệ ượ ặ c di ở c đ t trên bàn c

ầ Cho m t bàn c chuy n tuân theo lu t ch i c vua – đ ạ t i ô đ u tiên có t a đ x ơ ờ ọ ộ 0, y0.

ấ ộ ướ phủ

ề ộ trình ượ ờ c sao cho ộ ầ ế ộ l V n đ là tìm m t ỗ toàn b bàn c (m i ô đ g m ồ n2 –1 b c vi ng đúng m t l n).

ể ả ủ 2 ô là xét bài toán,

Cách rõ ràng đ thu gi m bài toán ph n ho c làặ

ệ ướ ự th c hi n b ế ế c đi k ti p, hay

ệ ằ ế ợ ệ phát hi n r ng không ki m đ ượ ướ c b c đi h p l nào.

procedure try next move; begin initialize selection of moves; repeat select next candidate from list of next moves; if acceptable then begin record move; if board not full then begin (6.3.1) try next move; if not successful then erase previous recording end end until (move was successful) (cid:0) (no more candidates) end

Cách biểu diễn dữ liệu

ễ ả ờ ằ ộ Chúng ta di n t bàn c b ng m t ma tr n ậ h.

ượ ô ch a h đ ô đã đ ế c vi ng ạ ướ i b ứ ể c chuy n th

type index = 1..n ; var h: array[index, index] of integer; ư ề ượ h[x, y] = 0: ế h[x, y] = i: c vi ng t i (1(cid:0) i (cid:0) n2)

ệ ể ượ ễ ả ằ c di n t b ng “i <

ề Đi u ki n “board not full” có th đ n2”.

ế ọ ộ ủ u, v: t a đ c a ô đ n.

ệ ề ể ượ ễ ả ằ c di n t b ng

Đi u ki n “acceptable” có th đ (1(cid:0) u(cid:0) n) (cid:0) (1(cid:0) v(cid:0) n) (cid:0) (h[u,v]=0)

(6.3.2)

q1 then h[u,v]:=0

procedure try(i: integer; x,y : index; var q: boolean); var u, v: integer; q1 : boolean; begin initialize selection for moves; repeat let u, v be the coordinates of the next move ; if (1(cid:0) u(cid:0) n) (cid:0) (1(cid:0) v(cid:0) n) (cid:0) (h[u,v]=0) then begin h[u,v]:=i; if i < sqr(n) then begin try(i + 1, u, v, q1); if (cid:0) end else q1:= true end until q1 (cid:0) (no more candidates); q:=q1 end

ọ ộ ủ ệ

ố ừ ượ ớ ể ả c đánh s t

ể ọ Cho t a đ c a ô hi n hành , có 8 kh năng đ ch n ế ế ế 1 đ n 8 i. Chúng đ ô k ti p đ đi t ư nh sau:

(cid:0)

Sự tinh chế sau cùng

ơ c t a đ

ạ ộ ạ ệ ằ ả Cách đ n gi n nh t đ đ t đ ọ b ng cách c ng đ sai bi ấ ể ạ ượ ọ ộ u, v t ộ t to đ t i hai m ng ừ x, y là ả a và b.

ượ ế ế ố ứ ể Và k đ c dùng đ đánh s ng viên (candidate) k ti p.

program knightstour (output); const n = 5; nsq = 25; type index = 1..n var i,j: index; q: boolean; s: set of index; a,b: array [1..8] of integer; h: array [index, index] of integer;

q1 then h[u,v]:=0

procedure try (i: integer; x, y: index; var q:boolean); var k,u,v : integer; q1: boolean; begin k:=0; repeat k:=k+1; q1:=false; u:=x+a[k]; v:=y+b[k]; if (u in s) (cid:0) (v in s) then if h[u,v]=0 then begin h[u,v]:=i; if i < nsq then begin try(i+1, u,v,q1); if (cid:0) end else q1:=true end until q1 (cid:0) (k =8); q:=q1 end {try};

h[1,1]:=1; try (2,1,1,q); if q then for i:=1 to n do begin for j:=1 to n do write(h[i,j]:5); writeln end else writeln (‘NO SOLUTION’) end.

begin s:=[1,2,3,4,5]; a[1]:= 2; b[1]:= 1; a[2]:= 1; b[2]:= 2; a[3]:= –1; b[3]:= 2; a[4]:= –2; b[4]:=1; a[5]:= –2; b[5]:= –1; a[6]:= –1; b[6]:= –2; a[7]:= 1; b[7]:= –2; a[8]:= 2; b[8]:= –1; for i:=1 to n do for j:=1 to n do h[i,j]:=0;

ở ộ

ọ ớ ọ ộ

ở ầ

ệ

ằ

ượ

ủ ụ ệ

c kh i đ ng b ng l nh g i v i t a đ kh i đ u x ắ ầ

ế

ừ

đó chuy n đi b t đ u.

H[x0,y0]:= 1; try(2, x0, y0, q)

ộ ờ

ả ạ ượ ớ ị

ớ

Th t c đ quy đ y0 , t Hình 6.3.1 trình bày m t l

i gi

c v i v trí <1,1> v i n = 5.

i đ t đ

ụ

ế ớ ộ

ể

ả

ế

i quy t

ớ

ừ T thí d trên ta đi đ n v i m t ki u “gi ề ấ v n đ ” m i:

ể

ặ

Đ c đi m chính là

ề ờ ả ầ ủ

ng v l

i đ y đ và ghi l

ướ ướ c h ề ướ

ị

i gi c này mà sau đó nó có th

ướ

ệ ằ ế ờ ả ầ ủ ứ

ộ ướ

i đ y đ , t c là m t b

ạ “b i thông ỡ và ể b tháo g tin v b ẫ xóa đi khi phát hi n r ng b c này đã không d n ế ẫ i gi đ n l c đi d n đ n ượ ọ ế ế ắ ”(deadend). (Hành vi này đ c g i “tình th b t c là quay lui bactracking.)

Khuôn mẫu tổng quát của giải thuật quay lui

procedure try; begin intialize selection of candidates; repeat select next; if acceptable then begin record it; if solution incomplete then begin try next step; (6.3.3) if not successful then cancel recording end end until successful (cid:0) no more candidates end

ế ạ ỗ ướ ố ứ

ể

ư i m i N u t c, s ng b ử ả viên ph i th là ố ị c đ nh thì ki u ể ẫ m u trên có th ế ổ bi n đ i nh :

(cid:0)

ệ

ủ ụ ượ c Th t c đ ọ ằ g i b ng l nh g iọ

try(1).