Bài giảng Phân tích và thiết kế giải thuật - Chương 6: Giải thuật quay lui

Chương 6

Giải thuật quay lui

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

1

Giải thuật quay lui

Một phương pháp tổng quát để giải quyết vấn đề: thiết kế

giải thuật tìm lời giải cho bài tóan không phải là bám theo

một tập qui luật tính tóan được xác định mà là bằng cách

thử và sửa sai (trial and error).

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

sai thành những công tác bộ phận. Thường thì những công

tác bộ phận này được diễn tả theo lối đệ quy một cách

thuận tiện và bao gồm việc thăm dò một số hữu hạn những

công tác con.

Ta có thể coi toàn bộ quá trình này như là một quá trình 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.

2

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

Knight’s Tour Problem)

Cho một bàn cờ n × n với n²ô. Một con hiệp sĩ – được di

chuyển tuân theo luật chơi cờ vua – được đặt trên bàn cở tại

ô đầu tiên có tọa độ x₀, y₀.

Vấn đề là tìm một lộ trình gồm n²–1 bước sao cho phủ toàn

bộ bàn cờ (mỗi ô được viếng đúng một lần).

Cách rõ ràng để thu giảm bài toán phủ n²ô là xét bài toá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.

3

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

try next move;

(6.3.1)

if not successful then erase previous recording

end

until (move was successful) (no more candidates)

end

4

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.

type index = 1..n ;

var h: array[index, index] of integer;

h[x, y] = 0: ô <x,y> chưa hề được viếng

h[x, y] = i: ô <x,y> đã được viếng tại bước chuyển thứ i

(1≤ i ≤n²)

Điều kiện “board not full” có thể được diễn tả bằng “i < n²”.

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

Điều kiện “acceptable” có thể được diễn tả bằng

(1≤u≤n) (1≤v≤n) (h[u,v]=0)

5

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≤u≤n) (1≤v≤n) (h[u,v]=0) then

begin h[u,v]:=i;

if i < sqr(n) then

(6.3.2)

begin

try(i + 1, u, v, q1); if ¬ q1 then h[u,v]:=0

end

else q1:= true

end

until q1 (no more candidates);

q:=q1

end

6

Cho tọa độ của ô hiện hành <x, y>, có 8 khả năng để chọn ô

kế tiếp <u, v> để đi tới. Chúng được đánh số từ 1 đến 8 như

sau:

3

2

4

5

1

8

6

7

Sự tinh chế sau cùng

Cách đơn giản nhất để đạt được tọa độ u, v từ x, y là bằng

cách cọng độ sai biệt toạ độ tại hai mảng 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;

8

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) (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 ¬ q1 then h[u,v]:=0

end

else q1:=true

end

until q1 (k =8);

q:=q1

end {try};

9

begin

s:=[1,2,3,4,5];

a[1]:= 2; b[1]:= 1;

a[2]:= 1; b[2]:= 2;

h[1,1]:=1; try (2,1,1,q);

if q then

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

begin

for j:=1 to n do

write(h[i,j]:5);

writeln

end

else writeln (‘NO

SOLUTION’)

end.

for j:=1 to n do h[i,j]:=0;

10

Thủ tục đệ quy được khởi động bằng lệnh gọi với tọa độ khởi đầu x₀, y₀,

từ đó chuyến đi bắt đầu.

H[x₀,y₀]:= 1; try(2, x₀, y₀, q)

Hình 6.3.1 trình bày một lời giải đạt được với vị trí <1,1> với n = 5.

1

6

15

20

7

10

5

21

16

11

4

14

19

8

9

2

22

17

12

13

18

24

3

25

23

11

Từ thí dụ trên ta đi đến với một kiểu “giải quyết vấn

đề” mới:

Đặc điểm chính là

“bước hướng về lời giải đầy đủ và ghi lại thông tin

về bước này mà sau đó nó có thể bị tháo gỡ và xóa đi

khi phát hiện rằng bước này đã không dẫn đến lời

giải đầy đủ, tức là một bước đi dẫn đến “tình thế bế

tắc”(dead-end). (Hành vi này được gọi là quay lui

-bactracking.)

12

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;

if not successful then cancel recording

end

(6.3.3)

until successful no more candidates

end

13

procedure try (i: integer);

var k : integer;

begin k:=0;

Nếu tại mỗi

bước, số ứng

viên phải thử là

cố định thì kiểu

mẫu trên có thể

biến đổi như :

repeat

k:=k+1; select k-th candidate;

if acceptable then

begin

record it;

if i<n then

begin

try (i+1);

(6.3.4)

Thủ tục được gọi

bằng lệnh gọi

if not successful then

cancel recording

end

try(1).

end

until successful (k=m)

end

14

Bài toán 8 con hậu

Bài toán này đã được C.F. Gauss khảo sát năm 1850,

nhưng ông ta không hoàn toàn giải quyết được.

“Tám con hậu được đặt vào bàn cờ sao cho không có

con hậu nào có thể tấn công con hậu nào”.

Dùng khuôn mẫu ở hình 6.3.1, ta sẽ có được một thủ

tục sau cho bài toán 8 con hậu:

15

procedure try (i: integer);

begin

initialize selection of positions for i-th queen;

repeat

make next selection;

if safe then

begin

setqueen;

if i < 8 then

begin

try (i + 1);

if not successful then remove queen

end

until successful no more positions

end

16

Luật cờ: Một con hậu có thể tấn công các con hậu khác nằm trên cùng

một hàng, cùng một cột hay là cùng đường chéo trên bàn cờ.

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

Làm cách nào để diễn tả 8 con hậu trên bàn cờ?

var x: array[1..8] of integer;

a: array[1..8] of Boolean;

b: array[b1..b2] of Boolean;

c: array[c1..c2] of Boolean;

với

x[i] chỉ vị trí của con hậu trên cột thứ i;

a[j] cho biết không có con hậu trên hàng thứ j;

b[k] cho biết không có con hậu trên đường chéo  thứ k;

c[k] cho biết không có con hậu trên đường chéo  thứ k.

17

Việc chọn trị cho các mốc b1, b2, c1, c2 được xác định

bởi cách mà các chỉ số của các mảng b và c được tính.

Hãy chú ý rằng trên cùng một đường chéo chiều 

tất cả các ô sẽ có cùng giá trị của tổng hai tọa độ i +j,

và trên cùng một đường chép chiều  diagonal, tất cả

các ô sẽ có cùng giá trị của hiệu hai tọa độ (i – j ).

Như vậy, phát biểu setqueen được tinh chế như sau:

x[i]:=j; a[j]:=false; b[i+j]:=false;c[i-j]:=false;

Phát biểu removequeen được chi tiết hóa như sau:

a[j] = true; b[i+j] = true ; c[i-j] := true

Điều kiện safe được diễn tả như sau:

a[j] b[i+j] c[i-j]

18

program eightqueeen1(output);

{find one solution to eight queens

problem}

begin

x[i]:=j;

a[j]:=false; b[i+j]:=false;

c[i-j]:=false;

if i<8 then

begin

var

i : integer; q: boolean;

a : array [1..8] of boolean;

b : array [2..16] of boolean;

c : array [–7..7] of boolean;

x : array [1..8] of integer;

procedure try(i: integer; var q:

boolean);

try (i+1, q);

if ¬ q then

begin

a[j]:=true; b[i+j]:=true;

c[i-j]:=true

end

var j: integer;

begin

j:=0;

end

repeat

else q:=true

j:=j+1; q:=false;

if a[j] b[i+j] c[i-j] then

end

until q (j=8)

end {try};

19

begin

for i:= 1 to 8 do a[i]:=true;

for i:= 2 to 16 do b[i]:=true;

for i:= –7 to 7 do c[i]:=true;

try (1,q);

if q then

for i:=1 to 8 do

write (x[i]:4);

writeln

end

Một lời giải của bài toán 8 con hậu được cho ở hình vẽ sau:

20

Bài giảng Phân tích và thiết kế giải thuật - Chương 6: Giải thuật quay lui - Dương Tuấn Anh