2. 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 bi 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 thnh nh畛ng c担ng t叩c b畛 ph畉n. Th動畛ng th狸 nh畛ng c担ng
t叩c b畛 ph畉n ny 動畛c di畛n t畉 theo l畛i 畛 quy m畛t c叩ch
thu畉n ti畛n v bao g畛m vi畛c thm d嘆 m畛t s畛 h畛u h畉n nh畛ng
c担ng t叩c con.
Ta c坦 th畛 coi ton b畛 qu叩 tr狸nh ny 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
3. Bi to叩n 動畛ng i c畛a con hi畛p s挑 (The
Knights Tour Problem)
Cho m畛t bn c畛 n n v畛i n2 担. M畛t con hi畛p s挑 動畛c di
chuy畛n tu但n theo lu畉t ch董i c畛 vua 動畛c 畉t tr棚n bn c畛 t畉i
担 畉u ti棚n c坦 t畛a 畛 x0, y0.
V畉n 畛 l t狸m m畛t l畛 tr狸nh g畛m n2 1 b動畛c sao cho ph畛 ton
b畛 bn c畛 (m畛i 担 動畛c vi畉ng 炭ng m畛t l畉n).
C叩ch r探 rng 畛 thu gi畉m bi to叩n ph畛 n2 担 l x辿t bi 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畛 no.
3
4. 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
end
until (move was successful) (no more candidates)
end
4
5. C叩ch bi畛u di畛n d畛 li畛u
Ch炭ng ta di畛n t畉 bn 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 n2)
i畛u ki畛n board not full c坦 th畛 動畛c di畛n t畉 b畉ng i < n2.
u, v: t畛a 畛 c畛a 担 畉n.
i畛u ki畛n acceptable c坦 th畛 動畛c di畛n t畉 b畉ng
(1un) (1vn) (h[u,v]=0)
5
6. 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 (1un) (1vn) (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
8. 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
9. 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
10. 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;
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.
10
12. 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 ny m sau 坦 n坦 c坦 th畛 b畛 th叩o g畛 v x坦a i
khi ph叩t hi畛n r畉ng b動畛c ny 達 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). (Hnh vi ny 動畛c g畛i l quay lui
-bactracking.)
12
13. 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 no more candidates
end
13
14. 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動 :
Th畛 t畛c 動畛c g畛i
b畉ng l畛nh g畛i
try(1).
proceduretry (i: integer);
var k : integer;
begin k:=0;
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)
if not successful then
cancel recording
end
end
until successful (k=m)
end
14
15. Bito叩n8conh畉u
Bi to叩n ny 達 動畛c C.F. Gauss kh畉o s叩t nm 1850,
nh動ng 担ng ta kh担ng hon ton gi畉i quy畉t 動畛c.
T叩m con h畉u 動畛c 畉t vo bn c畛 sao cho kh担ng c坦
con h畉u no c坦 th畛 t畉n c担ng con h畉u no.
D湛ng khu担n m畉u 畛 h狸nh 6.3.1, ta s畉 c坦 動畛c m畛t th畛
t畛c sau cho bi to叩n 8 con h畉u:
15
16. 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
end
until successful no more positions
end
16
17. 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 hng, c湛ng m畛t c畛t hay l c湛ng 動畛ng ch辿o tr棚n bn c畛.
C叩ch bi畛u di畛n d畛 li畛u
Lm c叩ch no 畛 di畛n t畉 8 con h畉u tr棚n bn 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 hng 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
19. program eightqueeen1(output);
{find one solution to eight queens
problem}
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);
var j: integer;
begin
j:=0;
repeat
j:=j+1; q:=false;
if a[j] b[i+j] c[i-j] then
begin
x[i]:=j;
a[j]:=false; b[i+j]:=false;
c[i-j]:=false;
ifi<8 then
begin
try (i+1, q);
if 測 q then
begin
a[j]:=true; b[i+j]:=true;
c[i-j]:=true
end
end
else q:=true
end
until q (j=8)
end {try};
19
20. 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 bi to叩n 8 con h畉u 動畛c cho 畛 h狸nh v畉 sau:
20
22. S畛 m畛 r畛ng: T狸m t畉t c畉 c叩c l畛i gi畉i
S畛 m畛 r畛ng l t狸m kh担ng ch畛 m畛t l畛i gi畉i m t畉t c畉
nh畛ng l畛i gi畉i c畛a bi to叩n 達 cho.
Ph動董ng ph叩p: M畛t khi m畛t l畛i gi畉i 動畛c t狸m th畉y v
ghi l畉i, ta ti畉p t畛c x辿t 畛ng vi棚n k畉 trong qu叩 tr狸nh ch畛n
畛ng vi棚n m畛t c叩ch c坦 h畛 th畛ng.
Khu担n m畉u t畛ng qu叩t 動畛c d畉n xu畉t t畛 (6.3.4) v
動畛c tr狸nh by nh動 sau:
22
23. procedure try(i: integer);
var k: integer;
begin
for k:=1 to m do
begin
select k-th candidate;
if acceptable then
begin
record it;
if i<n then try (i+1) else print solution;
cancel recording
end
end
end
23
24. Trong gi畉i thu畉t m畛 r畛ng, 畛 董n gi畉n h坦a i畛u ki畛n d畛ng c畛a qu叩 tr狸nh ch畛n,
ph叩t bi畛u repeat 動畛c thay th畉 b畉ng ph叩t bi畛u for
program eightqueens(output);
var i: integer;
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 print;
var k : integer;
begin
for k : 1 to 8 do write(x[k]:4);
writeln
end {print};
procedure try (i:integer);
var j: integer;
begin
for j:=1 to 8 do
if a[j] b[i+j] c[i-j] then
begin
x[i]:=j;
a[j]:=false; b[i+j]:= false;
c[i-j]:=false;
if i < 8 then try(i+1) else print;
a[j]:=true; b[i+j]:= true;
c[i-j]:= true;
end
end {try};
24
25. 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);
end.
Gi畉i thu畉t m畛 r畛ng c坦 th畛 s畉n sinh t畉t c畉 92 l畛i gi畉i
cho bi to叩n 8 con h畉u.
Nh動ng th畉t ra ch畛 c坦 12 l畛i gi畉i th畉t s畛 kh叩c bi畛t
nhau.
25
30. 畛 ph畛c t畉p c畛a gi畉i thu畉t quay lui
Th畛i gian t鱈nh to叩n c畛a c叩c gi畉i thu畉t quay lui th動畛ng
l hm m滴 (exponential).
N畉u m畛i n炭t tr棚n c但y kh担ng gian tr畉ng th叩i c坦 trung
b狸nh 留 n炭t con, v chi畛u di c畛a l畛i i l畛i gi畉i l N, th狸
s畛 n炭t tr棚n c但y s畉 t畛 l畛 v畛i 留 N.
Th畛i gian t鱈nh to叩n c畛a gi畉i thu畉t 畛 quy t動董ng 畛ng
v畛i s畛 n炭t tr棚n c但y kh担ng gian tr畉ng th叩i n棚n c坦 畛
ph畛c t畉p hm m滴.
30
31. Gi畉i thu畉t nh叩nh v c畉n (branch-and-bound)
Bi
to叩n ng動畛i th動董ng gia du hnh (TSP): cho m畛t t畉p c叩c
thnh ph畛 v kho畉ng c叩ch gi畛a m畛i c畉p thnh ph畛, t狸m m畛t l畛
tr狸nh i qua t畉t c畉 m畛i thnh ph畛 sao cho t畛ng kho畉ng c叩ch
c畛a l畛 tr狸nh nh畛 h董n M.
i畛u ny d畉n 畉n m畛t bi to叩n kh叩c: cho m畛t 畛 th畛 v担
h動畛ng, c坦 c叩ch no 畛 n畛i t畉t c畉 c叩c n炭t b畉ng m畛t chu tr狸nh
董n hay kh担ng. 但y ch鱈nh l bi to叩n Chu tr狸nh Hamilton
(HCP).
畛 gi畉i bi to叩n (HCP), ta c坦 th畛 c畉i bi棚n gi畉i thu畉t t狸m ki畉m
theo chi畛u s但u tr動畛c (DFS) 畛 gi畉i thu畉t ny c坦 th畛 sinh ra
m畛i l畛i i 董n m i qua m畛i 畛nh trong 畛 th畛.
31
32. T狸m ki畉m v辿t c畉n: Gi畉i thu畉t DFS c畉i bi棚n sinh ra m畛i l畛i i
董n
i畛u ny c坦 th畛 th畛c hi畛n 動畛c b畉ng c叩ch s畛a l畉i th畛 t畛c visit
nh動 sau:
procedure visit( k: integer);
var t: integer;
begin
id := id +1; val[k]:= id;
for t:= 1 to V do
if a[k, t] then
if val[k]= 0 then visit(t);
id := id 1; val[k] := 0
end;
Th畛 t畛c 畛 quy ny c坦 th畛
sinh ra m畛i l畛i i 董n t畛
m畛t 畛nh kh畛i 畉u no 坦.
V鱈 d畛:
id :=0;
for k:= 1 to V do val[k]:=0;
visit(1);
32
33. M畛t th鱈 d畛 v畛 bi to叩n TSP
A
1
6
B
2
H
1
C
4
D
G
E
2
I
3
2
1
2
1
1
J
F
3
2
L
4
1
1
K
M
H狸nh 5.10
33
34. T狸m ki畉m v辿t c畉n c叩c l畛i i 董n
A
G
F
B
C
D
E
D
F
E
C
G
B
H
J
D
I
L
F
M
B
D
J
M
K M
J
D
B
K M
J
K
I
K
F
C
I
K
L
M
H
I
E M
L
D
H
J
M
I
K M
J
H
J
M
G
K
I
K
I
K M
J
H
J
M
J
H
I
J
H
I
K
I
K
I
K M
J
L M
G
H
L M
G
H
J
H
I
K
I
K
M L
G
L M
G
H
J
H
G
L M
G
C
G
M L
L
E
M L
I
C
G
C
H
E
F
M L
L
B
E
L
L
H
K
J
C F
E
B D
C F
I
D B
B D
H
F C
D B
G
G
F C
H狸nh 5.11
34
35. T畛 gi畉i thu畉t sinh t畉t c畉 c叩c l畛i i 董n
畉n gi畉i thu畉t gi畉i bi to叩n TSP
Ta c坦 th畛 c畉i bi棚n th畛 t畛c visit 畛 tr棚n 畛 c坦 th畛 nh畉n
di畛n chu tr狸nh Hamilton b畉ng c叩ch cho n坦 ki畛m tra
xem c坦 t畛n t畉i m畛t c畉nh n畛i t畛 畛nh k v畛 畛nh 1 xu畉t
ph叩t khi val[k]=V hay kh担ng.
Trong th鱈 d畛 tr棚n, xem h狸nh v畉, ta t狸m th畉y 2 chu
tr狸nh Hamilton l
AFDBCELMJKIHG
A G H I K J M L E C B D F v hai chu tr狸nh ny ch畛 l m畛t.
Ch動董ng tr狸nh nh畉n di畛n chu tr狸nh Halmiton c坦 th畛
動畛c s畛a 畛i 畛 c坦 th畛 gi畉i bi to叩n TSP b畉ng c叩ch
theo d探i chi畛u di c畛a l畛i i hi畛n hnh trong m畉ng val, v
theo d探i l畛i i c坦 chi畛u di nh畛 nh畉t trong s畛 c叩c chu
tr狸nh Hamilton t狸m th畉y.
35
36. t動畛ng nh叩nh v c畉n
Khi 叩p d畛ng gi畉i thu畉t DFS c畉i bi棚n 畛 sinh ra m畛i l畛i i 董n,
trong qu叩 tr狸nh t狸m ki畉m m畛t l畛i i t畛t nh畉t (t畛ng tr畛ng s畛
nh畛 nh畉t) cho bi to叩n TSP, c坦 m畛t k畛 thu畉t t畛a nh叩nh quan
tr畛ng l k畉t th炭c s畛 t狸m ki畉m ngay khi th畉y r畉ng n坦 kh担ng th畛
no thnh c担ng 動畛c.
Gi畉 s畛 m畛t l畛i i 董n c坦 chi ph鱈 x 達 動畛c t狸m th畉y. Th狸 th畉t
v担 鱈ch 畛 duy畛t ti畉p tr棚n l畛i i ch動a-畉y-畛 no m chi ph鱈
cho 畉n hi畛n gi畛 達 l畛n h董n x. i畛u ny c坦 th畛 動畛c th畛c hi畛n
b畉ng c叩ch kh担ng g畛i 畛 quy th畛 t畛c visit n畉u l畛i i ch動a-畉y畛 hi畛n hnh 達 l畛n h董n chi ph鱈 c畛a l畛i i 畉y 畛 t畛t nh畉t cho
畉n b但y gi畛.
36
37. t動畛ng nh叩nh v c畉n (tt.)
R探 rng ta s畉 kh担ng b畛 s坦t l畛i i chi ph鱈 nh畛 nh畉t no n畉u ta
b叩m s叩t m畛t chi畉n l動畛c nh動 v畉y.
K畛 thu畉t t鱈nh c畉n (bound) c畛a c叩c l畛i gi畉i ch動a-畉y-畛 畛
h畉n ch畉 s畛 l畛i gi畉i ph畉i d嘆 t狸m 動畛c g畛i l gi畉i thu畉t nh叩nh v
c畉n.
Gi畉i thu畉t ny c坦 th畛 叩p d畛ng khi c坦 chi ph鱈 動畛c g畉n vo c叩c
l畛i i.
37
![C叩ch bi畛u di畛n d畛 li畛u
Ch炭ng ta di畛n t畉 bn 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 n2)
i畛u ki畛n board not full c坦 th畛 動畛c di畛n t畉 b畉ng i < n2.
u, v: t畛a 畛 c畛a 担 畉n.
i畛u ki畛n acceptable c坦 th畛 動畛c di畛n t畉 b畉ng
(1un) (1vn) (h[u,v]=0)
5](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-5-320.jpg)
![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 (1un) (1vn) (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](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-6-320.jpg)
![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](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-8-320.jpg)
![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](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-9-320.jpg)
![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;
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.
10](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-10-320.jpg)
![Th畛 t畛c 畛 quy 動畛c kh畛i 畛ng b畉ng l畛nh g畛i v畛i t畛a 畛 kh畛i 畉u x0, y0 ,
t畛 坦 chuy畉n i b畉t 畉u.
H[x0,y0]:= 1; try(2, x0, y0, q)
H狸nh 6.3.1 tr狸nh by m畛t l畛i gi畉i 畉t 動畛c v畛i v畛 tr鱈 <1,1> v畛i n = 5.
1
6
15
10
21
14
9
20
5
16
19
2
7
22
11
8
13
24
17
4
25
18
3
12
23
11](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-11-320.jpg)
![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 hng, c湛ng m畛t c畛t hay l c湛ng 動畛ng ch辿o tr棚n bn c畛.
C叩ch bi畛u di畛n d畛 li畛u
Lm c叩ch no 畛 di畛n t畉 8 con h畉u tr棚n bn 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 hng 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](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-17-320.jpg)
![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](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-18-320.jpg)
![program eightqueeen1(output);
{find one solution to eight queens
problem}
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);
var j: integer;
begin
j:=0;
repeat
j:=j+1; q:=false;
if a[j] b[i+j] c[i-j] then
begin
x[i]:=j;
a[j]:=false; b[i+j]:=false;
c[i-j]:=false;
ifi<8 then
begin
try (i+1, q);
if 測 q then
begin
a[j]:=true; b[i+j]:=true;
c[i-j]:=true
end
end
else q:=true
end
until q (j=8)
end {try};
19](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-19-320.jpg)
![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 bi to叩n 8 con h畉u 動畛c cho 畛 h狸nh v畉 sau:
20](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-20-320.jpg)
![Trong gi畉i thu畉t m畛 r畛ng, 畛 董n gi畉n h坦a i畛u ki畛n d畛ng c畛a qu叩 tr狸nh ch畛n,
ph叩t bi畛u repeat 動畛c thay th畉 b畉ng ph叩t bi畛u for
program eightqueens(output);
var i: integer;
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 print;
var k : integer;
begin
for k : 1 to 8 do write(x[k]:4);
writeln
end {print};
procedure try (i:integer);
var j: integer;
begin
for j:=1 to 8 do
if a[j] b[i+j] c[i-j] then
begin
x[i]:=j;
a[j]:=false; b[i+j]:= false;
c[i-j]:=false;
if i < 8 then try(i+1) else print;
a[j]:=true; b[i+j]:= true;
c[i-j]:= true;
end
end {try};
24](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-24-320.jpg)
![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);
end.
Gi畉i thu畉t m畛 r畛ng c坦 th畛 s畉n sinh t畉t c畉 92 l畛i gi畉i
cho bi to叩n 8 con h畉u.
Nh動ng th畉t ra ch畛 c坦 12 l畛i gi畉i th畉t s畛 kh叩c bi畛t
nhau.
25](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-25-320.jpg)
![T狸m ki畉m v辿t c畉n: Gi畉i thu畉t DFS c畉i bi棚n sinh ra m畛i l畛i i
董n
i畛u ny c坦 th畛 th畛c hi畛n 動畛c b畉ng c叩ch s畛a l畉i th畛 t畛c visit
nh動 sau:
procedure visit( k: integer);
var t: integer;
begin
id := id +1; val[k]:= id;
for t:= 1 to V do
if a[k, t] then
if val[k]= 0 then visit(t);
id := id 1; val[k] := 0
end;
Th畛 t畛c 畛 quy ny c坦 th畛
sinh ra m畛i l畛i i 董n t畛
m畛t 畛nh kh畛i 畉u no 坦.
V鱈 d畛:
id :=0;
for k:= 1 to V do val[k]:=0;
visit(1);
32](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-32-320.jpg)
![T畛 gi畉i thu畉t sinh t畉t c畉 c叩c l畛i i 董n
畉n gi畉i thu畉t gi畉i bi to叩n TSP
Ta c坦 th畛 c畉i bi棚n th畛 t畛c visit 畛 tr棚n 畛 c坦 th畛 nh畉n
di畛n chu tr狸nh Hamilton b畉ng c叩ch cho n坦 ki畛m tra
xem c坦 t畛n t畉i m畛t c畉nh n畛i t畛 畛nh k v畛 畛nh 1 xu畉t
ph叩t khi val[k]=V hay kh担ng.
Trong th鱈 d畛 tr棚n, xem h狸nh v畉, ta t狸m th畉y 2 chu
tr狸nh Hamilton l
AFDBCELMJKIHG
A G H I K J M L E C B D F v hai chu tr狸nh ny ch畛 l m畛t.
Ch動董ng tr狸nh nh畉n di畛n chu tr狸nh Halmiton c坦 th畛
動畛c s畛a 畛i 畛 c坦 th畛 gi畉i bi to叩n TSP b畉ng c叩ch
theo d探i chi畛u di c畛a l畛i i hi畛n hnh trong m畉ng val, v
theo d探i l畛i i c坦 chi畛u di nh畛 nh畉t trong s畛 c叩c chu
tr狸nh Hamilton t狸m th畉y.
35](https://image.slidesharecdn.com/chap6new-140227195557-phpapp02/85/Chap6-new-35-320.jpg)
